Hashing, Collisions, Hash Tables, and Performance Analysis

TAKEAWAYS:

• Hashing converts keys into array indices using a hash function, enabling O(1) average-time operations.
• Collisions occur when two keys hash to the same index; they are resolved via chaining (linked lists) or open addressing (probing).
• Load factor (λ = n/m) determines hash table efficiency; resizing (rehashing) maintains performance.
• Perfect hashing eliminates collisions but requires precomputed hash functions for static datasets.
• Hash tables are used in databases (indexing), compilers (symbol tables), and caching (e.g., browser caches).
• Time complexity depends on collision resolution: O(1) average (with good hash function) vs. O(n) worst-case (all collisions).

1. Introduction to Hashing

Hashing is a technique to map keys (e.g., integers, strings) to array indices using a hash function. The goal is to distribute keys uniformly to minimize collisions (multiple keys mapping to the same index).

How Hashing Works

1. Hash Function: A function $h(k)$ that takes a key $k$ and returns an index in the hash table.
   • Example: For a table of size 10, $h(k)=k\mathrm{mod}10$.
2. Hash Table: An array where each index holds a bucket (can be a single value or a linked list for chaining).
3. Operations:
   • Insertion: Compute $h(k)$, place $k$ at index $h(k)$.
   • Search: Compute $h(k)$, check the bucket at $h(k)$.
   • Deletion: Remove $k$ from its bucket.

Example: Hashing Strings

Suppose we hash the strings "apple", "banana", and "pear" into a table of size 5 using $h(k)=\sum \text{ASCII values of characters}\mathrm{mod}5$:

• $h("apple")=(97+112+112+108+101)\mathrm{mod}5=528\mathrm{mod}5=3$
• $h("banana")=(98+97+110+97+110+97)\mathrm{mod}5=599\mathrm{mod}5=4$
• $h("pear")=(112+101+97+114)\mathrm{mod}5=424\mathrm{mod}5=4$ Here, "banana" and "pear" collide at index 4.

2. Collision Resolution Techniques

Collisions degrade performance. Two common methods:

A. Chaining (Separate Chaining)

• Each bucket is a linked list storing colliding keys.
• Pros: Simple, handles many collisions.
• Cons: Extra memory for pointers; worst-case O(n) time if all keys collide.

Example: Insertion with Chaining Insert "apple", "banana", "pear" into a table of size 5 (as above):

Index: 0: []
       1: []
       2: []
       3: ["apple"]
       4: ["banana" → "pear"]

graph TD
    A["Hash Table"] --> B["Index 0: []"]
    A --> C["Index 1: []"]
    A --> D["Index 2: []"]
    A --> E["Index 3: [apple]"]
    A --> F["Index 4: [banana --> pear]"]

B. Open Addressing (Closed Hashing)

• All keys stored in the table itself; collisions resolved by probing (finding next empty slot).
• Pros: No extra memory for pointers.
• Cons: Clustering (collisions beget collisions); worst-case O(n) time.

Probing Methods:

1. Linear Probing: Check next slot sequentially.
   • $h(k,i)=(h(k)+i)\mathrm{mod}m$, where $i=0,1,2,\dots$
2. Quadratic Probing: Use quadratic function to jump.
   • $h(k,i)=(h(k)+i^2)\mathrm{mod}m$
3. Double Hashing: Use a second hash function.
   • $h(k,i)=(h1(k)+i\cdot h2(k))\mathrm{mod}m$

Example: Linear Probing Insert "apple" (index 3), "banana" (index 4), "pear" (index 4, collides):

• Place "pear" at index 0 (next empty slot after 4).

Index: 0: ["pear"]
       1: []
       2: []
       3: ["apple"]
       4: ["banana"]

3. Performance Analysis

Load Factor (λ)

• $\lambda =\frac{n}{m}$, where $n$ = number of keys, $m$ = table size.
• Ideal λ: 0.7 (balance between memory and collisions).
• Resizing: When $\lambda >0.7$, double the table size and rehash all keys.

Time Complexity

Example: Resizing

Initial table size = 5, $\lambda =0.8$ (resize to 10):

• Recompute all hash values with new size.
• New $h(k)=k\mathrm{mod}10$.

4. Perfect Hashing

• Goal: Eliminate collisions entirely.
• Methods:
  1. Universal Hashing: Choose hash function randomly from a family.
  2. CMPH (Minimal Perfect Hashing): Precompute hash function for static datasets.
• Use Case: Compilers (symbol tables), databases (indexing).

5. Applications in Real World

A. Databases (Indexing)

• Example: eSewa uses hash tables to store user credentials (email → password) for O(1) login verification.
• How: Hash the email to locate the password in constant time.

B. Compilers (Symbol Tables)

• Example: Ncell’s billing system uses hash tables to map phone numbers to user accounts.
• How: Hash the phone number to quickly access account details during billing.

C. Caching (Browser/OS)

• Example: WhatsApp’s message cache uses hash tables to store and retrieve messages by chat ID.
• How: Hash the chat ID to locate messages in memory.

D. Networking (Routing Tables)

• Example: NTC’s IP routing uses hash tables to map IP addresses to next-hop routers.
• How: Hash the destination IP to find the routing entry.

Worked Example: Daraz Order Queue Daraz uses a hash table to manage order IDs for fast lookup:

• Key: Order ID (e.g., "ORD123").
• Value: Order details (customer, items, status).
• Operation: When a customer checks order status, Daraz hashes "ORD123" to retrieve details in O(1) time.

6. Comparison: Chaining vs. Open Addressing

7. Common Hash Functions

1. Division Method: $h(k)=k\mathrm{mod}m$
   • Simple but may not distribute keys uniformly.
2. Multiplication Method: $h(k)=\lfloor m\cdot (k\cdot A\mathrm{mod}1)\rfloor$
   • $A$ is a constant (e.g., $A=(\sqrt{5}-1)/2$).
3. Universal Hashing: Randomly select hash function from a family to reduce worst-case collisions.

8. Exam Tip

• Define hashing: "A technique to map keys to array indices using a hash function."
• Collision resolution: Always mention chaining or open addressing with examples.
• Performance: Relate load factor ($\lambda$) to resizing (e.g., "resize when $\lambda >0.7$").
• Applications: Link to real-world systems like eSewa (user authentication) or Daraz (order lookup).
• Code: Write a simple hash table in pseudocode and trace insertion/search steps.

Practice Question: Given a hash table of size 7 and keys {12, 25, 37, 48, 60} with $h(k)=k\mathrm{mod}7$:

1. Draw the table after insertion using chaining.
2. Show how to resolve collisions using linear probing.
3. What is the load factor after insertion? When should the table resize?