Hashing, Hash Tables, Collision Handling & Performance

What is Hashing?

Hashing is a technique to map data of arbitrary size to fixed-size values (hash codes) using a hash function. The goal is to distribute keys uniformly across a table for O(1) average-time lookups, insertions, and deletions.

Key Definitions

• Hash Function (h(k)): Converts a key k into an integer (index). Example: h("apple") = 5 (assuming table size = 10).
• Hash Table: An array of buckets where each bucket stores a key-value pair.
• Collision: When two keys hash to the same index.
• Load Factor (λ): Ratio of filled slots to total slots (λ = n/m).
  • Critical λ: When resizing is triggered (typically 0.7–0.8).

Hash Functions: Design Principles

A good hash function must:

1. Deterministic: Same key → same hash.
2. Uniform Distribution: Minimize collisions.
3. Fast Computation: O(1) time.
4. Avalanche Effect: Small key changes → drastically different hashes.

Common Hash Functions

Example: For keys ["cat", "dog", "bat"] and m = 7, compute hashes using:

• Division: h("cat") = ASCII sum % 7 = (99+97+116) % 7 = 212 % 7 = 5
• Multiplication: h("dog") = floor(7 * (100*0.618 mod 1)) ≈ 3

Collision Resolution Techniques

1. Separate Chaining

• Each bucket is a linked list of entries.
• Pros: Simple, handles high load factors.
• Cons: Extra memory for pointers, worst-case O(n) time.

graph LR
    A["Hash Table"] --> B["Bucket 0: []"]
    A --> C["Bucket 1: [Key1]"]
    A --> D["Bucket 2: [Key2, Key3]"] --> E["Key3"] --> F["Key2"]

Example: Insert "apple" and "maple" (both hash to index 5):

Index 5: ["apple" → "maple"]

2. Open Addressing

• Collisions are resolved by probing for the next empty slot.
• Methods:
  • Linear Probing: h(k, i) = (h(k) + i) % m
  • Quadratic Probing: h(k, i) = (h(k) + i²) % m
  • Double Hashing: h(k, i) = (h1(k) + i * h2(k)) % m

Example (Linear Probing): Insert "cat" (hash=5), "bat" (hash=5), "rat" (hash=5) into a table of size 7:

Index: 5 → "cat", 6 → "bat", 0 → "rat" (wraps around)

Performance Analysis

Load Factor Impact:

• λ < 0.5: Low collisions, fast operations.
• λ ≈ 0.7–0.8: Resize table (double size, rehash all keys).
• λ ≈ 1.0: Degraded to O(n) time.

Real-World Applications

1. eSewa (Nepal)

• Use: Hash tables store user transaction IDs (txn12345) for O(1) payment verification.
• How: Keys = transaction IDs; values = payment status (e.g., "completed").
• Why: Millions of daily transactions require fast lookups.

2. Khalti’s Fraud Detection

• Use: Hash tables detect duplicate transactions (e.g., same card number + amount).
• How: Hash function combines card_number + amount → index.
• Example:

  h("555544443333100") = 7  # Hashes to index 7
  if table[7] == "seen": flag_fraud()
  

3. Daraz’s Order Queue

• Use: Priority queues (hash tables with timestamps) manage order processing.
• How: Key = order_id; value = (timestamp, status).
• Example:

  {"ORD123": (1625000000, "shipped"),
   "ORD456": (1625000010, "processing")}
  

Worked Example: Hash Table Operations

Scenario: NTC’s network router uses a hash table to map IP addresses to port assignments. Table size = 11 (prime), hash function = h(k) = sum(ascii(k)) % 11.

Step 1: Insert IPs

Insert "192.168.1.1" and "192.168.1.2" (using ASCII sum of last octet):

• h("1") = 49 % 11 = 5
• h("2") = 50 % 11 = 6

State After Insertion:

Index: 5 → "192.168.1.1", 6 → "192.168.1.2"

Step 2: Collision Handling (Chaining)

Insert "192.168.1.11" (hash=5):

Index 5: ["192.168.1.1" → "192.168.1.11"]

Step 3: Search for "192.168.1.1"

• Compute hash: h("1") = 5.
• Check index 5: Traverse linked list → found in 1 probe.

Comparison: Chaining vs. Open Addressing

Advanced: Perfect Hashing

• Goal: Zero collisions for a static dataset.
• Use Case: Compilers (symbol tables), databases.
• Methods:
  • Two-Level Hashing: First hash → second hash.
  • CMPH (Minimal Perfect Hashing): Minimizes table size.

Example: For keys {"red", "green", "blue"}:

1. First hash: "red" → 1, "green" → 2, "blue" → 1 (collision).
2. Second hash on colliding keys: "red" → 1, "blue" → 2.

Exam Tip

1. Define Clearly: Start with "Hashing is a technique to...". Examiners check for completeness.
2. Draw Tables: Always show the state after each operation (insert/search/delete).
   • Example: For a question on open addressing, draw the table before and after probing.
3. Load Factor: Questions often ask when to resize. Memorize the critical λ (0.7–0.8).
4. Pseudocode: Write one-line hash functions (e.g., h(k) = k % m).
5. Real-World Link: Relate to eSewa/Khalti for applications or NTC routers for examples.

Visual Summary:

classDiagram
    class HashTable {
        +int size
        +int[] table
        +hash(key) int
        +insert(key, value)
        +search(key) value
    }
    class HashFunction {
        <<abstract>>
        +hash(key) int
    }
    class Chaining {
        +LinkedList[] buckets
    }
    class OpenAddressing {
        +probe(key, i) int
    }
    HashTable <|-- Chaining
    HashTable <|-- OpenAddressing
    HashFunction <|.. HashTable