Part I · Hash tables · week 6
Linear probing
One key per slot: on a collision, step right until you find an empty one. Fast and compact — as long as you keep the table less than half full.
Run the animation, step by step → generated live from any input you type — nothing is pre-recorded
Cost and properties
| search hit | ~3/2 probes at 50% load |
|---|---|
| search miss | ~5/2 probes at 50% load |
| load factor | must stay < 1 (aim ≤ ½) |
| deletion | awkward — must reinsert the cluster |
Reference: Sedgewick & Wayne, §3.4; Knuth 1963.
Linear probing in Python
Runnable as-is, and written for reading. Watch the highlighted line move through it in the animation, or send it straight to the visualizer — it arrives with a test case ready to run, yours to edit.
class LinearProbingHashST:
# One key per slot. A collision walks RIGHT (wrapping) to the next
# empty slot, so keys form CLUSTERS -- and long clusters are the enemy.
def __init__(self, m=16):
self.m = m
self.keys = [None] * m
self.vals = [None] * m
self.n = 0
def _hash(self, key):
h = 0
for c in str(key):
h = (31 * h + ord(c)) & 0x7fffffff
return h % self.m
def put(self, key, val):
if self.n >= self.m // 2:
self._resize(2 * self.m) # keep the load factor <= 1/2
i = self._hash(key)
while self.keys[i] is not None: # probe until an empty slot
if self.keys[i] == key:
self.vals[i] = val
return
i = (i + 1) % self.m
self.keys[i] = key
self.vals[i] = val
self.n += 1
def get(self, key):
i = self._hash(key)
while self.keys[i] is not None:
if self.keys[i] == key:
return self.vals[i]
i = (i + 1) % self.m
return None # an empty slot proves absence
def _resize(self, capacity):
old_keys, old_vals = self.keys, self.vals
self.m, self.n = capacity, 0
self.keys = [None] * capacity
self.vals = [None] * capacity
for k, v in zip(old_keys, old_vals):
if k is not None:
self.put(k, v) # rehash: i changes with mWhy it works
An empty slot is a proof
Search probes right until it finds the key or an empty slot. The empty slot is what makes the miss correct: if the key existed it would have been placed at the first empty slot in this run, so an empty slot means absence. Everything about linear probing follows from that one property — including why deletion is hard.
Clustering, and Knuth's result
Contiguous runs of occupied slots (clusters) merge as the table fills, and a long cluster makes every key hashing into it slow. Knuth's 1962 analysis: with load factor α, a search hit costs ~½(1 + 1/(1−α)) probes and a miss ~½(1 + 1/(1−α)2). At α = ½ that is 1.5 and 2.5 probes; at α = 0.9 it is 5.5 and 50.5. The cost does not degrade gracefully — it explodes. Hence the resize at half full.
That analysis was, in Knuth's own telling, the result that convinced him analysis of algorithms was worth a career.
Resizing rehashes everything
i = hash(key) % m depends on m, so doubling the table means every key moves — you cannot copy the array. Watch the resize frames: the keys land in completely different slots. Amortised this is still constant time per operation (same argument as the resizing-array stack), but any single insert can be linear.
Why deletion is awkward
Simply blanking a slot breaks the empty-slot proof: keys past the hole become unreachable. The fix is to remove the key and reinsert every key in the rest of its cluster. That is why hash tables that need frequent deletion often use chaining instead — or tombstones, which slowly poison the table.
What to try in the animation
Set m small (say 8) to watch clusters merge and probe counts climb — then watch the automatic resize rescue it.
The animation is generated from the input box, in your browser — press Animate after editing it. To execute the Python itself, use Open in Visualizer above.
- course example —
m: 16 · insert: S E A R C H E X A M P L E · search: A Z - watch it resize —
m: 4 · insert: S E A R C H X M · search: X - long clusters —
m: 8 · insert: S E A R C H E X A M P L E · search: E
The rest of Hash tables
- Separate chaining Hash each key to one of m lists and search that list.