4.2Open addressing: linear, quadratic, double hashing
The idea
Open addressing stores every key in the table itself and probes a sequence of slots until it finds an empty one.
Think of it like this: Looking for a parking space: if yours is taken, you try the next one, or skip ahead by a pattern.
Why it exists
GATE gives a small table and a probing rule; you must fill it exactly.
How it works
- Linear: try h, h + 1, h + 2, … (mod m).
- Quadratic: try h, h + 1, h + 4, h + 9, … (mod m).
- Double hashing: try h₁ + i·h₂ (mod m).
- Delete with a tombstone so searches do not stop early.
Worked example: m = 10, linear probing, keys 31 42 73 14 25 36
31 → 1, 42 → 2, 73 → 3, 14 → 4, 25 → 5, 36 → 6: no collision at all. Add 41 and it goes 1 → 2 → 3 → 4 → 5 → 6 → 7.
Now play with it
- →Switch the mode to quadratic probing with the same keys.
- →Insert keys that all end in the same digit and watch the cluster grow.
| slot | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
|---|---|---|---|---|---|---|---|---|---|---|
| key |
Green = where the key landed, red = occupied slots probed on the way.
- 31: probe 1, stored at slot 1
- 42: probe 2, stored at slot 2
- 73: probe 3, stored at slot 3
- 14: probe 4, stored at slot 4
- 25: probe 5, stored at slot 5
- 36: probe 6, stored at slot 6
Primary clustering (linear probing) makes runs of filled slots grow; quadratic probing may skip some slots entirely, so it can fail even when the table is not full. Double hashing here uses h2(k) = 5 − (k mod 5).
Check yourself
m = 7, linear probing, keys 8, 15, 22 inserted in that order. Where does 22 go?
Exam notes (the dense version)
All keys live in the table itself, so n ≤ m. The i-th probe for key k: linear (h(k) + i) mod m; quadratic (h(k) + c₁i + c₂i²) mod m; double hashing (h₁(k) + i·h₂(k)) mod m. Linear probing causes primary clustering, quadratic causes milder secondary clustering. Deleting needs a tombstone marker, otherwise later searches stop too early.
Previous year questions: Hashing (6)
PYQs are grouped by topic, so this is the full set for Hashing; try the ones that match this subtopic. Open all 6 on the topic page.