Hash table — structure, open addressing vs chaining: Worked examples

The scenario matrix

Every problem in this topic is one of these cells. We will hit each one with a worked example.

#	Case class	What makes it special	Example
C1	No collision	every key lands in an empty slot	Ex 1
C2	Chaining collision	multiple keys share a bucket	Ex 2
C3	Linear-probe collision	array-internal sliding	Ex 3
C4	Quadratic probing	jumps $i^{2}$ , may skip slots	Ex 4
C5	Double hashing	second hash sets the step	Ex 5
C6	Degenerate: all-collide	worst case, every strategy	Ex 6
C7	Deletion + tombstone	the severed-chain trap	Ex 7
C8	Limiting load factor	$α \to 1$ , probe blow-up, rehash	Ex 8
C9	Word problem	real strings via polynomial hash	Ex 9
C10	Exam twist	quadratic probing fails to insert	Ex 10

Before we start, one symbol we reuse: $h (k) = k mod m$ means "the remainder when $k$ is divided by $m$ ." Example: $22 mod 5$ — how many left over after taking out fives? $22 = 4 \times 5 + 2$ , remainder $= 2$ . That remainder is always in ${0, 1, \dots, m - 1}$ , exactly the legal slot range. That is why $mod$ is the compression step: it forces any integer into a valid index.

Figure 1 below shows this compression visually: five big keys funnelling down to their five slots in a table of size $m = 5$ . Follow a coral arrow from a key to the slot its remainder picks — that arrow is the hash function.

C1 — The easy case: no collisions

C2 — Chaining collision

C3 — Linear probing

C4 — Quadratic probing

C5 — Double hashing

C6 — Degenerate: everything collides (all four strategies)

Worked example The worst case, every strategy

$m = 5$ . Insert $5, 10, 15, 20$ — all satisfy $k mod 5 = 0$ . We run all four resolution rules so no edge case is skipped.

Forecast: what is the search cost for the last key inserted, in each strategy?

Chaining: bucket 0 becomes [5,10,15,20]. Searching $20$ scans all 4 nodes → $O (n)$ .

Linear probing ( $f (i) = i$ ; $n = 4 < m = 5$ so it fits):

$5 \to$ slot 0. 2. $10 \to$ 0 taken $\to$ slot 1. 3. $15 \to$ slots 2. 4. $20 \to$ slot 3. → [5,10,15,20,_]. Search $20$ probes $0, 1, 2, 3$ = 4 probes.

Quadratic probing ( $f (i) = i^{2}$ , base 0):

$5$ , $i = 0$ → 0. 2. $10$ , $i = 1$ → $(0 + 1) mod 5 = 1$ . 3. $15$ : $i = 1$ taken, $i = 2$ → $(0 + 4) mod 5 = 4$ . 4. $20$ : $i = 1, 2$ taken, $i = 3$ → $(0 + 9) mod 5 = 4$ taken, $i = 4$ → $(0 + 16) mod 5 = 1$ taken… the reachable set from base 0 is ${0, 1, 4}$ — only 3 distinct slots, so $20$ can never be placed even though slots 2,3 are empty. (Same failure family as C10.)

Double hashing ( $h_{2} (k) = 1 + (k mod 4)$ , step $= i \cdot h_{2}$ ): $h_{2} (20) = 1 + (20 mod 4) = 1$ , so $20$ walks $0, 1, 2, 3$ and lands in slot 2 — 4 probes to place. Even distinct step sizes cannot beat $O (n)$ when every key shares the base.

Verify: chaining and linear both cost 4 for the last key; quadratic reaches only ${0, 1, 4}$ and fails to insert; double hashing also degrades to a length-4 walk. All four collapse to linear (or fail) under an adversarial hash — that is why the hash function quality matters more than the resolution strategy.

C7 — Deletion and the tombstone trap

Worked example Why you can't just blank a slot

From C3's table [_,_,_,10,17,24,_] (linear probing, $m = 7$ ). Delete 17, then search 24.

Forecast: if we set slot 4 to empty, what happens to the search for 24?

Naive delete: blank slot 4 → [_,_,_,10,_,24,_].
Search $24$ : start $h (24) = 3$ → slot 3 holds 10, not 24, keep probing → slot 4 is empty → search concludes "24 not present." Wrong! 24 is right there in slot 5. Why this breaks: an empty slot is the universal "stop" signal; blanking slot 4 severed the probe chain.
Correct delete: write a tombstone X in slot 4 → [_,_,_,10,X,24,_].
Re-search $24$ : slot 3 (10, no), slot 4 (tombstone → "keep going"), slot 5 (24 ✓).

Verify: with the tombstone, search $24$ takes 3 probes and succeeds. Insert may later reuse the X. This is the exact trap flagged in the parent's [!mistake].

C8 — Limiting load factor: probes blow up

Worked example Watching

$\frac{1}{1 - α}$ explode, then rehash Uniform-hashing open addressing. Compute expected unsuccessful-search probes at $α = 0.5, 0.9, 0.95$ . Then a table with $m = 10$ , $n = 7$ crosses the rehash threshold — what happens?

Forecast: guess the probe count at $α = 0.9$ before computing.

Formula (from parent): $E = \frac{1}{1 - α}$ , where $α = n / m$ is the load factor from the top box.
$α = 0.5$ : $\frac{1}{1 - 0.5} = 2$ probes.
$α = 0.9$ : $\frac{1}{1 - 0.9} = 10$ probes.
$α = 0.95$ : $\frac{1}{1 - 0.95} = 20$ probes — halving the gap to 1 doubles the pain. Why this shape? Each probe hits a full slot with probability $\approx α$ ; the tries form a geometric series summing to $\frac{1}{1 - α}$ .
Why threshold $\approx 0.7$ ? Read $E$ off the curve: at $α = 0.7$ , $E = \frac{1}{1 - 0.7} \approx 3.33$ probes — still cheap. Just past it, cost climbs steeply ( $0.8 \to 5$ , $0.9 \to 10$ ). So $0.7$ is the last point where the table is still fast; we resize before the curve's knee. It is a chosen safety margin, not a law.
Rehash trigger: $α = n / m = 7/10 = 0.7$ hits the threshold → allocate $m^{'} = 20$ , reinsert all 7 keys → new $α = 7/20 = 0.35$ .

Verify: new load factor $0.35 \Rightarrow$ expected probes $\frac{1}{1 - 0.35} \approx 1.54$ — back near $O (1)$ . Figure 3 plots the whole $\frac{1}{1 - α}$ curve with the three marked points and the dashed $0.7$ threshold line so you can see the knee. See Load factor and dynamic resizing / rehashing and Amortized analysis for why doubling keeps inserts $O (1)$ amortized.

C9 — Word problem: hashing real strings

C10 — Exam twist: quadratic probing fails to insert

Worked example When

$i^{2}$ can't find a free slot even though one exists $m = 6$ (deliberately not prime), quadratic step $f (i) = i^{2}$ , so $slot_{i} = (h (k) + i^{2}) mod 6$ . Slots $0$ and $3$ are free; everything else full. Insert a key with $h (k) = 0$ .

Forecast: the reachable slots from base 0 are $0 + i^{2} mod 6$ . List them.

$i = 0$ : $(0 + 0) mod 6 = 0$ — but slot 0 is full (say occupied by an earlier key we can't reuse).
$i = 1$ : $(0 + 1) mod 6 = 1$ — full.
$i = 2$ : $(0 + 4) mod 6 = 4$ — full.
$i = 3$ : $(0 + 9) mod 6 = 3$ — free! ... but watch the pattern continue.
$i = 4$ : $(0 + 16) mod 6 = 4$ ; $i = 5$ : $(0 + 25) mod 6 = 1$ . The reachable set is ${0, 1, 4, 3}$ — it cycles and never visits slot 2 or 5. Why this fails in general: with $m$ not prime (or $α$ too high), quadratic probing reaches only a subset of slots, so it can report "full" while empties exist.

Verify: distinct reachable slots $= {0, 1, 3, 4}$ , exactly 4 of the 6 — slots $2, 5$ unreachable from base 0. This is the classic exam trap; the fix is $m$ prime and $α \leq 0.5$ .

Recall Self-test across the matrix

Which cell does each belong to? Insert 3,11,5 into $m = 7$ , all distinct slots ::: C1 (no collision) Bucket 4 becomes [4,10,16] ::: C2 (chaining collision) Blanking a slot severs a probe chain ::: C7 (tombstone) $\frac{1}{1 - 0.9} = 10$ probes ::: C8 (limiting load factor) "ab"→slot 11, "ba"→slot 2, $m = 13$ ::: C9 (word problem) Quadratic reaches only ${0, 1, 3, 4}$ in $m = 6$ ::: C10 (exam twist)