Hashing: Functions, Collisions, and Resolution Techniques

What is Hashing?

Hashing is a technique to store and retrieve data efficiently by mapping keys to indices in an array (called a hash table). The goal is O(1) average-time operations (insertion, deletion, search).

Key Terms

• Hash Function (h(k)): A function that converts a key into an index. Example: h(key) = key % table_size
• Hash Table: An array where data is stored at indices computed by the hash function.
• Collision: When two keys hash to the same index.
• Load Factor (λ): Ratio of filled slots to total slots. High λ → more collisions.

---

In the Real World

1. eSewa (Nepal) uses hashing to store user transaction IDs. When you pay a bill, eSewa’s backend hashes your transaction ID to locate the record in milliseconds, avoiding slow database searches.
2. Daraz’s Order Queue uses a hash table to track order statuses. Your order ID (e.g., ORD12345) is hashed to find its current state (processing/shipped/delivered) in constant time.
3. Ncell’s Caller ID Lookup hashes phone numbers to quickly fetch subscriber names (e.g., 98XXXXXXXX → index in a hash table storing names).

---

Hash Functions

A good hash function must:

• Distribute keys uniformly (minimize collisions).
• Be deterministic (same key → same index).
• Be fast (computable in O(1)).

Common Hash Functions

---

Collision Resolution Techniques

When two keys collide, we resolve it using:

1. Open Addressing (Closed Hashing): Find the next empty slot.
2. Separate Chaining (Open Hashing): Store colliding keys in a linked list/array at the same index.

1. Open Addressing

Methods:

• Linear Probing: Check next slot sequentially. h(k) = (h(k) + i) % m (where i = 1, 2, 3...).
• Quadratic Probing: Jump in squares to reduce clustering. h(k) = (h(k) + i²) % m.
• Double Hashing: Use a second hash function to determine step size. h(k, i) = (h1(k) + i * h2(k)) % m.

Example: Linear Probing Insert keys [62, 37, 36, 44, 67, 91, 107] into a table of size 10. Hash function: h(k) = k % 10.

Final Table State:

Index: 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9
Value: - | 91| 62| - | 44| - | 36| 37| 67| 107

Trace of Insertion Steps:

---

2. Separate Chaining

Store colliding keys in a linked list/array at the same index.

Example: Chaining with Linked Lists Insert the same keys [62, 37, 36, 44, 67, 91, 107] into a table of size 10.

Final Table State:

Index: 0 | 1   | 2   | 3 | 4   | 5 | 6   | 7          | 8   | 9
Value: - | 91  | 62  | - | 44  | - | 36  | 37 → 67    | 107 | -

Advantages/Disadvantages:

---

Performance Analysis

• Average Case: O(1) for insert/search/delete (with good hash function).
• Worst Case: O(n) if all keys collide (hash function fails).
• Load Factor (λ): Optimal λ ≈ 0.7 for open addressing, higher for chaining.

Amortized Time Complexity:

Where α = λ (load factor).

---

Real-World Worked Example: Ncell’s Caller ID

Ncell stores 10 million subscriber records. To fetch a name in <10ms, they:

1. Use a hash table of size 1,000,000 (load factor λ ≈ 0.8).
2. Hash phone numbers with h(phone) = (phone % 1,000,000).
3. Resolve collisions via separate chaining (linked lists).
4. Average lookup time: O(1 + 0.8) ≈ constant time.

Trace for Phone 9812345678:

1. Hash: 9812345678 % 1,000,000 = 123456.
2. Check Table[123456] → linked list with 2 entries (due to λ=0.8).
3. Search list linearly (max 2 comparisons).
4. Return name: "Ramesh Shrestha".

---

Exam Tip

1. Define hashing clearly: "A technique to map keys to array indices using a hash function."
2. Collision resolution: Always explain how the method works (e.g., "Linear probing checks slots sequentially").
3. Draw tables: Show before/after states for insertions/deletions.
4. Compare methods: Use a table for open vs. closed addressing.
5. Practical touch: Relate to eSewa/Daraz (e.g., "How would you design a hash table for 1 million orders?").
6. Code snippets: Write pseudocode for probing (e.g., while (table[h] != null && table[h].key != key) h = (h + 1) % size;).

---

Practice Questions

1. Insert [11, 22, 33, 44, 55] into a table of size 5 using quadratic probing.
2. Compare linear vs. double hashing for collision resolution.
3. Why does universal hashing reduce clustering attacks?
4. Design a hash table for a bank’s loan records (keys: loan IDs, values: customer details). Choose a resolution method and justify.

---

# Python: Linear Probing Implementation
class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [None] * size

    def insert(self, key):
        index = key % self.size
        while self.table[index] is not None:
            index = (index + 1) % self.size  # Linear probe
        self.table[index] = key

# Trace for inserting [62, 37, 36, 44, 67, 91, 107] (size=10)
ht = HashTable(10)
for key in [62, 37, 36, 44, 67, 91, 107]:
    ht.insert(key)
print(ht.table)  # Output: [-1, 91, 62, -1, 44, -1, 36, 37, 67, 107]