GATE CS - PROGRAMMING & DATA STRUCTURES:Hashing
Mastering hashing concepts and implementation.
Hashing for GATE CS
GATE hashing is almost always: given h(k) and a collision method, where does each key land? Know chaining vs open addressing, and what load factor α = n/m means for average search cost.
Hash function (division method)
h(k) = k mod m — m often chosen prime to spread keys. Other methods (multiplication, mid-square) appear less often; if given, follow the formula in the question.
Example: m = 11, key 42 → 42 mod 11 = 9.
Collisions
Two keys with the same h(k). Fix with chaining or open addressing.
Chaining (separate chaining)
Each slot holds a list. Insert at the head of slot h(k) — O(1) for the insert step; search averages O(1 + α).
No clustering. Extra pointer memory. Worst case still O(n) if everything hashes to one bucket.
Open addressing (probe the table)
Store keys in the table itself. Probe until an empty slot.
| Method | Probe |
|---|---|
| Linear | `(h(k) + i) mod m` |
| Quadratic | `(h(k) + c₁i + c₂i²) mod m` (constants given in question) |
| Double hashing | `(h₁(k) + i·h₂(k)) mod m` |
Linear probing suffers primary clustering. Delete usually needs a tombstone (lazy delete) so search does not stop early.
Worked: linear probing
m = 7, h(k) = k mod 7. Insert 50, 700, 76, 85, 92 in order (empty table).
- 50 → 50%7 = 1
- 700 → 0
- 76 → 6
- 85 → 1 collision → try 2
- 92 → 1 → 2 occupied → 3
Final slots (index → key): 0:700, 1:50, 2:85, 3:92, 6:76.
Load factor and rehashing
α = n/m. For open addressing, α must stay < 1. As α grows, probe sequences lengthen (rough average search ~ 1/(1−α) for unsuccessful search under uniform hashing assumptions).
Rehash: allocate a larger table, re-insert all keys with the new m. Triggered when α crosses a threshold (e.g. 0.7) — exact threshold is implementation-specific; GATE will state it if needed.
Complexities (say it carefully)
| Average (good hash, moderate α) | Worst | |
|---|---|---|
| Search / insert / delete | O(1) | O(n) |
“O(1) hashing” on the paper means average case under the usual assumptions — not a guarantee for adversarial keys.
Practise a few insert sequences by hand, then move on via the GATE hub. Previous chapter: Graphs.