Hash Tables, Open Addressing & Collision Probing Dynamics
“Division and multiplication hash functions, linear vs quadratic probing, double hashing, and primary/secondary clustering.”
1.The Hashing Paradigm & Collision Resolution
§ 5.1.A Hash Table implements the dictionary ADT, mapping a universe of keys U into m table slots using a hash function h: U -> {0, 1, ..., m - 1}.
Collision Resolution Strategies:
1. Chaining (Open Hashing): Colliding elements are stored in a linked list at slot T[h(k)].
2. Open Addressing (Closed Hashing): All elements are stored directly in the table array. If a collision occurs, a sequence of alternative slots is probed until an empty slot is found:
- Linear Probing: h(k, i) = (h'(k) + i) bmod m.
- Quadratic Probing: h(k, i) = (h'(k) + c_1 i + c_2 i^2) bmod m.
- Double Hashing: h(k, i) = (h_1(k) + i * h_2(k)) bmod m.
2.The Clustering Phenomena (Primary vs Secondary)
§ 5.2.Primary Clustering (Linear Probing):
When keys hash to nearby slots, long contiguous runs of occupied slots develop. Any key hashing to any slot in the run extends the run by one, compounding the probability of future collisions. Search times degrade rapidly as alpha -> 1.
Secondary Clustering (Quadratic Probing):
Two keys with the same initial hash h'(k_1) = h'(k_2) trace the exact same sequence of probes throughout the entire table.
Double Hashing Solution:
Because h_2(k) varies independently of h_1(k), two keys hashing to the same initial slot will have completely different step sizes, eliminating both primary and secondary clustering.
3. Worked Problem: Double Hashing Probe Sequence Execution
Ensure h2(k) step size is added modulo m at each probe iteration i.
Problem: Keys are inserted into a hash table of size m = 11 using Double Hashing with hash functions h1(k) = k % 11 and h2(k) = 1 + (k % 7). If slot h1(k) is occupied, find the sequence of probes for key k = 37.
Step 1: Compute primary hash h1(37):
h1(37) = 37 % 11 = 4.
Step 2: Compute step size h2(37):
h2(37) = 1 + (37 % 7) = 1 + 2 = 3.
Step 3: Generate probe indices h(37, i) = (h1(37) + i * h2(37)) % 11 for i = 0, 1, 2, 3:
- i = 0: h(37, 0) = 4 % 11 = 4 (Initial slot).
- i = 1: h(37, 1) = (4 + 1 * 3) % 11 = 7.
- i = 2: h(37, 2) = (4 + 2 * 3) % 11 = 10.
- i = 3: h(37, 3) = (4 + 3 * 3) % 11 = 13 % 11 = 2.
Final Probe Sequence: Indices 4 -> 7 -> 10 -> 2.
Primary Academic References & Exam Sources
Every concept in Notes From a B.Tech Brain is synthesized from authoritative academic texts, seminal peer-reviewed research, verified exam archives, and renowned university lectures.
Curated for clarity, rigorous numerical solving, and semester excellence:
Visual thinkers who want to see each algorithm step animated clearly.
GATE-targeted coverage with step-by-step GATE PYQ walkthroughs.