Open addressing — linear probing, quadratic probing, double hashing: Worked examples

This is the worked-examples companion to the parent open-addressing note. The parent gave you the three probe formulas and one example each. Here we hunt down every case class open addressing can throw at you — every collision pattern, every degenerate table, every deletion trap — and work each one to the last arithmetic step.

Before we start, one reminder of the machinery we are about to use constantly:

Definition When do we STOP probing? (the stopping condition)

We do not probe forever. A probe loop ends in exactly one of four ways:

Search — found: a probe lands on a slot holding our key $k$ → success.
Search — absent: a probe lands on an EMPTY (never-used) slot → the key is not in the table (the chain ended). A tombstone does NOT stop a search — you walk through it.
Insert — placed: a probe lands on an EMPTY or DELETED slot → we write $k$ there.
Give up: if we have made $m$ probes ( $i = 0$ to $m - 1$ ) without any of the above, we have examined every slot — the table is full (for this probe sequence). Insertion fails; this is the signal to rehash into a bigger table.

So the loop always runs at most $m$ steps. Quadratic on a non-prime $m$ (Ex 5) can hit this "give up" wall even while free slots exist, because its sequence never visits them.

The scenario matrix

Every problem this topic can throw at you is one of the case classes below. Read the matrix first as a checklist — then each worked example is tagged with the cell(s) it fills, and together they cover the whole grid. If your viewer does not render tables, the same list is spelled out beneath it.

#	Case class	What makes it special	Example
A	No collision	home slot is empty, $i = 0$ done	Ex 1
B	Single collision	one probe needed	Ex 1, 2
C	Cluster crawl (linear)	long contiguous run of full slots	Ex 2
D	Wrap-around	probe passes slot $m - 1$ and loops to $0$	Ex 3
E	Quadratic escape	jump skips past a cluster	Ex 4
F	Quadratic failure	free slot exists but is unreachable	Ex 5
G	Double hashing, same home	two keys, same $h_{1}$ , different $h_{2}$	Ex 6
H	Double hashing, $h_{2} = 0$ trap	degenerate step size	Ex 6
I	Deletion + tombstone (search & reuse)	search crosses / insert reuses a deleted slot	Ex 7
J	Load-factor / limiting value	probe cost as $α \to 1$	Ex 8
K	Word problem (real world)	translate a story into probes	Ex 9
L	Exam twist	count total probes / compare schemes	Ex 10

Same list, plainly (in case the table above does not render): A = no collision; B = one collision; C = linear cluster crawl; D = wrap-around past the end; E = quadratic jump over a cluster; F = quadratic cannot reach a free slot; G = double hashing splits keys with the same home; H = the $h_{2} = 0$ infinite-loop trap; I = deletion needs a tombstone (both for searching past it and for reusing it); J = load factor pushing probe cost to infinity; K = a real-world story problem; L = an exam-style "count and compare" twist.

We use one small table for most examples so you can see the state build up:

$m = 11, h_{1} (k) = k mod 11.$

Why $m = 11$ ? Because $11$ is prime, which (as the parent note stressed and Prime table sizes explains) is exactly the condition that makes quadratic and double hashing behave. We will break that rule on purpose in Ex 5 to watch it fail.

Warm-up: no collision & a first collision (cells A, B)

Cluster crawl in linear probing (cell C)

A cluster is a run of already-full slots with no gap between them. Look at figure s01: the blue slots $1, 2, 3$ form one such run, and the orange slot $4$ is a new key that hit inside the run and got dragged to its far end — extending the cluster by one. That growth is what we mean by "clustering is live": each new colliding key makes the run longer, so the next colliding key must crawl even further.

Figure s01 (below): linear probing on $m = 11$ . Blue = keys $12, 23, 34$ already placed in slots $1, 2, 3$ ; the bracket marks the full contiguous cluster; the orange arrow shows key $45$ being dragged to slot $4$ at the cluster's end.

Figure — Open addressing — linear probing, quadratic probing, double hashing

Worked example Ex 2 — cell C: build a cluster in

$m = 11$ , linear Insert in order: $12, 23, 34, 45$ . All four satisfy $k mod 11 = 1$ (we verify each below). Forecast: four keys all wanting slot $1$ . Guess the final four slots.

$12 mod 11 = 1$ → slot $1$ empty → place. Why? home free. (A)
$23 mod 11 = 1$ → $1$ taken, $i = 1$ : slot $2$ empty → place. Why? step $+ 1$ . (B)
$34 mod 11 = 1$ → $1, 2$ taken, $i = 2$ : $(1 + 2) = 3$ empty → place. Why? keep crawling; the cluster ${1, 2}$ forces us to $3$ . (C)
$45 mod 11 = 1$ → $1, 2, 3$ taken, $i = 3$ : $(1 + 3) = 4$ empty → place. Why? the cluster is now length $3$ , so the $4^{th}$ key needs $3$ steps past home to clear the run. (cell C — the cluster is actively growing: each insert lengthens the run the next insert must cross.)

Verify: $12 = 11 + 1$ , $23 = 2 \cdot 11 + 1$ , $34 = 3 \cdot 11 + 1$ , $45 = 4 \cdot 11 + 1$ — all remainder $1$ ✓. Slots used: $1, 2, 3, 4$ . The number of probes was $1, 2, 3, 4$ respectively — rich-get-richer, exactly the primary-clustering cost the parent note warned about.

Wrap-around across the array end (cell D)

What if the home slot is near the top of the array and the cluster runs off the end? The $mod m$ loops us back to slot $0$ . Never treat the array as having an "end" — it is a ring.

Figure s02 (below): the ring. Blue slots $9, 10$ are full; the green arrow shows a new key with home $9$ probing $9 \to 10 \to$ wrapping back to slot $0$ ; the dashed line reminds you that "one past slot $10$ " is slot $0$ .

Quadratic escape vs failure (cells E, F)

Quadratic probing changes the offset to $i^{2}$ : the steps are $0, 1, 4, 9, 16, \dots$ . Small $i$ still moves gently, but the jumps grow fast, letting a key leap over a cluster.

Figure s03 (below): quadratic escape. Blue slots $1, 2, 3$ are a full cluster. The gray arrow is the tiny $i = 1$ step ( $+ 1$ ) landing on slot $2$ ; the green arc is the $i = 2$ step ( $+ 4$ ) that vaults from home slot $1$ clear over slots $3, 4$ into the green slot $5$ .

Worked example Ex 5 — cell F: quadratic

failure on $m = 8$ (non-prime), $f (i) = i^{2}$ Table size $m = 8$ (a power of two — deliberately not prime). Home $h_{1} (k) = 0$ . Which slots can $i^{2} mod 8$ ever reach? Forecast: with $8$ slots you might expect all $8$ reachable. Guess how many actually are.

Compute $i^{2} mod 8$ for $i = 0, 1, \dots, 7$ : $0, 1, 4, 1, 0, 1, 4, 1.$ Why this step? The probe sequence only ever visits $(0 + i^{2}) mod 8$ , so its reachable slots are exactly these residues.
The distinct values are ${0, 1, 4}$ — only 3 slots. Why? $i^{2} mod 8$ repeats with period $4$ and never produces $2, 3, 5, 6, 7$ .
Consequence: if slots $0, 1, 4$ are full but $2, 3, 5, 6, 7$ are empty, a key with home $0$ can never be inserted even though $5$ slots are free. Why does the insert give up? Following the stopping-condition rule, after $m = 8$ probes ( $i = 0$ to $7$ ) it has never landed on an EMPTY or DELETED slot — its sequence only visits ${0, 1, 4}$ , all full — so it hits the "give up" branch and insertion fails, despite the table being mostly empty (load factor only $α = 3/8$ ). (cell F: unreachable free slot)

Verify: the set ${i^{2} mod 8 : i = 0 \dots 7} = {0, 1, 4}$ , size $3 < 8$ ✓. Fix: use a prime $m$ (like our $11$ ) and keep $α \leq 0.5$ . On $m = 11$ the first $⌈ 11/2 ⌉ = 6$ quadratic probes are all distinct.

Double hashing — same home, different paths (cells G, H)

Double hashing makes the step size itself depend on the key via a second hash $h_{2} (k)$ . Two keys that collide at home now walk different routes.

We use $h_{2} (k) = 1 + (k mod 10)$ on our $m = 11$ table. Why the " $1 +$ "? So the step is never $0$ — a step of $0$ would probe the same slot forever (cell H, the trap). Why $mod 10$ i.e. $mod (m - 1)$ ? To keep $h_{2}$ in $1 \dots 10$ , and since $11$ is prime, every value $1 \dots 10$ is coprime to $11$ , guaranteeing the probe visits all slots.

Figure s04 (below): diverging paths. Gray slot $1$ is the shared home. The blue arc shows key $1$ (step $h_{2} = 2$ ) landing in slot $3$ ; the orange arc shows key $12$ (step $h_{2} = 3$ ) landing in slot $4$ — same home, different destinations, no secondary clustering.

Worked example Ex 6 — cells G & H: double hashing,

$m = 11$ , $h_{2} (k) = 1 + (k mod 10)$ Two keys collide at home slot $1$ : $k = 1$ and $k = 12$ (both $\equiv 1 (mod 11)$ ). Slot $1$ already holds an earlier key, so both must probe. Forecast: same home slot — in quadratic they would share a path (secondary clustering). Guess whether double hashing splits them.

Key $1$ : $h_{2} (1) = 1 + (1 mod 10) = 1 + 1 = 2$ . Step size $= 2$ .
- $i = 0$ : $(1 + 0 \cdot 2) mod 11 = 1$ taken. Why? every probe sequence starts at the home slot; it is occupied, so we continue.
- $i = 1$ : $(1 + 1 \cdot 2) mod 11 = 3$ empty → place. Why? first real move uses step $2$ .
Key $12$ : $h_{2} (12) = 1 + (12 mod 10) = 1 + 2 = 3$ . Step size $= 3$ .
- $i = 0$ : $(1 + 0 \cdot 3) mod 11 = 1$ taken. Why? same home slot $1$ — it is also occupied here.
- $i = 1$ : $(1 + 1 \cdot 3) mod 11 = 4$ empty → place. Why? same home slot $1$ , but step $3$ → different landing.
The point: identical $h_{1}$ (both $= 1$ ) but different $h_{2}$ ( $2$ vs $3$ ) → different probe sequences → no secondary clustering. (cell G)
The trap (cell H): what if $h_{2} (k)$ came out $0$ ? Then $(1 + i \cdot 0) mod 11 = 1$ for every $i$ — you would probe slot $1$ forever and, hitting our $m$ -probe stopping wall, wrongly declare the table full. The " $1 +$ " guarantees $h_{2} \geq 1$ , so this never happens.

Verify: $h_{2} (1) = 2$ , $(1 + 2) mod 11 = 3$ ✓; $h_{2} (12) = 3$ , $(1 + 3) mod 11 = 4$ ✓. Key $1$ →slot $3$ , key $12$ →slot $4$ . Paths diverged.

Deletion and the tombstone — search past it AND reuse it (cell I)

Worked example Ex 7 — cell I: tombstone used for searching AND for a later insert,

$m = 11$ , linear Insert $A = 1$ (home $1$ , slot $1$ ) then $B = 12$ (home $1$ , taken → slot $2$ ). Then delete $A$ , then search for $B$ , then insert a new key $C = 1$ (home $1$ ). Forecast: after deleting $A$ with a tombstone, (i) can we still find $B$ , and (ii) where does the brand-new $C$ go — a fresh slot, or does it reclaim $A$ 's old spot?

State after inserts: slot $1 = A$ , slot $2 = B$ . Why? $12 mod 11 = 1$ , home taken, linear step to slot $2$ .
Delete $A$ correctly: set slot $1$ = DELETED (a tombstone), not EMPTY. Why? an EMPTY here would break $B$ 's chain (see the parent-note mistake box). A tombstone says "someone was here — walk on."
Search $B = 12$ : $i = 0$ probe slot $1$ → DELETED → keep going (tombstones do not stop a search). $i = 1$ probe slot $2$ → found $B$ . ✓ Total $2$ probes. Why? the DELETED marker preserves the probe chain so later keys stay reachable. (search past a tombstone)
Insert $C = 1$ (reuse!): home is slot $1$ .
- $i = 0$ : probe slot $1$ → it is DELETED. Why does this stop the insert? By the stopping-condition rule, an insert may write on EMPTY or DELETED — a tombstone is a legal, reusable seat.
- Action: write $C$ into slot $1$ , reclaiming $A$ 's old spot. Why do this rather than skip past? Reusing tombstones stops the table from silently filling up with dead markers, which would otherwise inflate the effective load factor. (insert reuses a tombstone)

Verify: with a tombstone the search reaches slot $2$ where $B$ lives — success in $2$ probes (a blank would have failed in $1$ ). The later insert of $C$ lands back in slot $1$ , the very slot the tombstone occupied. See Load factor and rehashing: too many un-reused tombstones inflate the effective load factor, so we periodically rehash to clear them.

Load factor as a limiting value (cell J)

Worked example Ex 8 — cell J: expected probes as

$α$ grows, and the limit $α \to 1$ Using the parent's result $E [X] = \frac{1}{1 - α}$ for an unsuccessful search, evaluate at $α = 0.5, 0.9, 0.99$ and describe the limit. Forecast: guess how fast the probe count blows up between $α = 0.9$ and $0.99$ .

$α = 0.5$ : $\frac{1}{1 - 0.5} = 2$ probes. Why? half the slots full → on average try $2$ before an empty.
$α = 0.9$ : $\frac{1}{1 - 0.9} = 10$ probes. Why? $90%$ full → $10 \times$ the cost of half-full.
$α = 0.99$ : $\frac{1}{1 - 0.99} = 100$ probes. Why? the $\frac{1}{1 - α}$ curve has a vertical asymptote at $α = 1$ .
Limit: as $α \to 1^{-}$ , $\frac{1}{1 - α} \to \infty$ . Why? the denominator $\to 0$ . This is the mathematical reason we rehash long before the table fills.

Verify: $1/ (1 - 0.5) = 2$ , $1/ (1 - 0.9) = 10$ , $1/ (1 - 0.99) = 100$ ✓. Cost multiplied by $10$ each time we halved the free space.

A real-world word problem (cell K)

Worked example Ex 9 — cell K: the parking-lot problem

A parking lot has $11$ numbered bays ( $0 \dots 10$ ). A car's "home bay" is its plate number $mod 11$ . Cars use linear probing to park. Cars arrive with plates $10, 21, 32$ . Which bay does each take? Forecast: all three plates end in a pattern — guess if they collide.

Plate $10$ : $10 mod 11 = 10$ → bay $10$ empty → park. Why? home free. (A)
Plate $21$ : $21 mod 11 = 10$ → bay $10$ taken. $i = 1$ : $(10 + 1) mod 11 = 0$ → wrap to bay $0$ , empty → park. Why? linear step $+ 1$ past the top loops to bay $0$ . (D, wrap)
Plate $32$ : $32 mod 11 = 10$ → bay $10$ taken; $i = 1$ : bay $0$ taken; $i = 2$ : $(10 + 2) mod 11 = 1$ → park in bay $1$ . Why? cluster now spans bays $10, 0$ so the third car crawls to $1$ . (C + D)

Verify: $10 mod 11 = 10$ , $21 mod 11 = 10$ , $32 mod 11 = 10$ ✓ (all $\equiv 10$ ). Bays taken: $10, 0, 1$ . Notice the cluster physically wraps across the array boundary.

Exam-style twist — count total probes & compare (cell L)

Worked example Ex 10 — cell L: total probes, linear vs double,

$m = 11$ Insert keys $1, 12, 23$ (all home $= 1$ ) into an empty $m = 11$ table and count the total number of probes (a probe = one slot examined) under (a) linear, (b) double hashing with $h_{2} (k) = 1 + (k mod 10)$ . Forecast: guess which scheme uses fewer total probes here.

(a) Linear:

$1$ : slot $1$ empty → $1$ probe. Running total $= 1$ .
$12$ : slot $1$ taken, slot $2$ empty → $2$ probes. Total $= 3$ .
$23$ : slots $1, 2$ taken, slot $3$ empty → $3$ probes. Total $= 6$ . Why? clustering forces each new colliding key to re-examine the whole run. Total (linear) $= 6$ .

(b) Double hashing:

$1$ : slot $1$ empty → $1$ probe. Total $= 1$ .
$12$ : $h_{2} (12) = 1 + (12 mod 10) = 3$ . $i = 0$ slot $1$ taken; $i = 1$ : $(1 + 3) = 4$ empty → $2$ probes. Total $= 3$ .
$23$ : $h_{2} (23) = 1 + (23 mod 10) = 1 + 3 = 4$ . $i = 0$ slot $1$ taken; $i = 1$ : $(1 + 4) = 5$ empty → $2$ probes. Total $= 5$ . Why? different step sizes ( $3$ vs $4$ ) spread the keys so no long run forms; each collider needs just $2$ probes. Total (double) $= 5$ .

The comparison: linear used $6$ probes, double hashing used $5$ . Double hashing wins because after the first collision the two colliding keys ( $12$ and $23$ ) get different step sizes ( $3$ vs $4$ ), so neither has to crawl through the other — each finishes in $2$ probes instead of the growing $2, 3, \dots$ crawl that linear's cluster forces. The gap widens the more colliding keys you add.

Verify: linear placements $1, 2, 3$ with probe counts $1, 2, 3$ summing to $6$ ✓. Double: $h_{2} (12) = 3 \Rightarrow$ slot $4$ ; $h_{2} (23) = 4 \Rightarrow$ slot $5$ ; probe counts $1, 2, 2$ summing to $5$ ✓. Double hashing wins by avoiding the crawl.

Recall Did every cell get covered?

A(Ex1,2,9) · B(Ex1,2) · C(Ex2,9,10) · D(Ex3,9) · E(Ex4) · F(Ex5) · G(Ex6) · H(Ex6) · I(Ex7) · J(Ex8) · K(Ex9) · L(Ex10). ✓ Full grid.

Total probes for Ex 10 under linear?

6

Total probes for Ex 10 under double hashing?

5

Reachable quadratic residues

i^{2} mod 8

only

{0, 1, 4}

— 3 slots

Expected unsuccessful probes at

α = 0.99

100

Where does the reused insert C land in Ex 7?

slot

1

— it reclaims

A

's tombstone

Max probes before an insert gives up?

m

(it has then examined every slot)