Hash Tables

How the model works

A hash function maps a key to a slot: h(k) = k mod m for integer keys, or a polynomial string hash. When two keys map to the same slot, that is a collision:

• Separate chaining: each slot holds a list; colliding keys are appended. Expected list length is the load factor α = n/m.
• Linear probing: try h, h+1, h+2, … until a free slot. Simple and cache-friendly, but keys bunch into primary clusters. Expected probes for a successful search ≈ ½(1 + 1/(1 − α)).
• Quadratic probing: try h + 1², h + 2², …, which breaks up primary clusters.

As α approaches 1, open addressing degrades sharply. Tables usually resize (double m and rehash) at α ≈ 0.7. The readout compares measured average probes with these formulas. A poor hash, for example m sharing factors with patterned keys, makes collisions much worse.

Keys are integers or short strings; deletion (which needs tombstones in open addressing) is not shown.

Guided experiments

1. Fill to 70% with linear probing. m = 31, insert 22 random keys. Prediction: clusters form (the longest here is 7 slots) and the average search needs about 1.5 probes. The textbook value ½(1 + 1/(1 − α)) ≈ 2.2 is an average over large tables, so a single small table can differ. Try other seeds. Linear probing to 70%
2. Same keys, chaining. Prediction: average chain length 0.7; successful search ≈ 1 + α/2 ≈ 1.35 probes. Chaining
3. Bad table size. m = 10 and keys that are multiples of 5. Prediction: every key lands in slot 0 or 5, so long chains form however big the table is. Change m to 11 (prime) and they spread out. Patterned keys, m = 10

Challenge

With linear probing, why is inserting into a slot right after a long cluster more likely than into an isolated empty slot?

References

• Cormen, Leiserson, Rivest & Stein, Introduction to Algorithms, ch. 11 “Hash Tables”.
• Knuth, The Art of Computer Programming, Vol. 3, §6.4.