Open addressing — linear probing, quadratic probing, double hashing: Exercises

Before we start, three reminders in plain words, each anchored to a picture of a row of numbered lockers (the table):

A table of size $m$ is a row of $m$ lockers numbered $0, 1, \dots, m - 1$ . Look at the chalk figure below — that is the whole universe we play in.
The base hash $h_{1} (k)$ answers "which locker is key $k$ 's home?" It is just $k mod m$ here — the remainder after dividing $k$ by $m$ , i.e. "how far past the last full lap of $m$ did we land." (See Hash functions — division & multiplication methods.)
A probe is one attempt: we look at a locker, and it is either empty (stop) or full (walk on by the rule).

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

The $mod m$ at the end just means "if you walk off the right end of the locker row, wrap back to locker $0$ " — like a clock. We will lean on that wrap constantly.

Definition When do we STOP probing? (the termination rule — read this before any exercise)

Every open-addressing operation must be able to halt, including the ugly edge case of a completely full table. The universal rule:

There are only $m$ lockers, so the probe sequence has at most $m$ distinct entries $i = 0, 1, \dots, m - 1$ .
Insert / unsuccessful search: probe $i = 0, 1, 2, \dots$ and stop as soon as you hit an empty (or, for insert, a tombstone). But if you reach $i = m - 1$ without finding a free slot, you have tried every reachable locker — abort: the table is full (insert fails / triggers a resize).
Why $m$ is the ceiling: if the probe sequence is a full permutation of $0.. m - 1$ (which is exactly what " $h_{2}$ coprime to $m$ ", "prime $m$ ", etc. guarantee), then after $m$ probes you have visited every locker. Probing an $(m + 1)$ -th time can only revisit a locker you already saw — pointless. So "if you probe $m$ times, you've tried the whole table, so give up" is the safety valve that prevents an infinite loop even on a full table.

Level 1 — Recognition

You are checking that you can read a formula and turn one crank of it.

Recall Solution L1.1

WHAT: we want $47 mod 11$ — the remainder when $47$ is divided by $11$ . WHY $mod$ : the locker row has only $11$ seats, so any key number must be folded down into ${0, \dots, 10}$ . Division-remainder does exactly that fold. $47 = 4 \times 11 + 3$ , so $47 mod 11 = 3$ . Home locker is 3.

Recall Solution L1.2

Home: $36 mod 10 = 6$ . That is probe $i = 0$ — full. Recall the rule: "linear" means the offset $f (i) = i$ , so from the home slot each next probe just adds $1$ . WHY $f (i) = i$ : it is the simplest possible offset — walking one locker at a time guarantees that after $m$ steps you have touched every locker, so no free slot is ever skipped. Probe $i = 1$ : $f (1) = 1$ , so $(6 + 1) mod 10 = 7$ — full. Probe $i = 2$ : $f (2) = 2$ , so $(6 + 2) mod 10 = 8$ — empty. Key $36$ lands in slot 8. Notice how linear probing just crawls $6 \to 7 \to 8$ , one locker at a time.

Recall Solution L1.3

$i 0123 5 + i^{2} 56914 (5 + i^{2}) mod 13 5691$ Sequence: $5, 6, 9, 1$ . The jumps $+ 1, + 4, + 9$ get bigger — that is the whole point of the square.

Level 2 — Application

Now you run a full insertion sequence and keep the table state straight.

Recall Solution L2.1

$15 mod 7 = 1$ → slot 1 (empty).
$22 mod 7 = 1$ → taken; $i = 1$ : $(1 + 1) = 2$ → slot 2.
$8 mod 7 = 1$ → taken, slot 2 taken; $i = 2$ : $(1 + 2) = 3$ → slot 3.
$29 mod 7 = 1$ → 1,2,3 taken; $i = 3$ : $(1 + 3) = 4$ → slot 4. Final: index $[0]$ empty, $[1] = 15, [2] = 22, [3] = 8, [4] = 29$ , $[5], [6]$ empty. A four-locker traffic jam (slots 1–4) formed from one home slot — primary clustering in the flesh.

Recall Solution L2.2

Step size: $h_{2} (36) = 1 + (36 mod 6) = 1 + 0 = 1$ . Uh-oh — is a step of $1$ legal? We need $h_{2}$ coprime to $m$ (sharing no common factor > 1) so the probe sequence hits every slot. Since $m = 7$ is prime, every value $1..6$ is coprime to $7$ , so step $1$ is fine. Probe $i = 1$ : $(1 + 1 \cdot 1) mod 7 = 2$ — empty (assume). Key $36$ → slot 2. Here double hashing happened to behave like linear (step $1$ ), but that is a coincidence of this one key; a different key would get a different step.

Recall Solution L2.3

$50 mod 7 = 1$ (home, full). $h_{2} (50) = 1 + (50 mod 6) = 1 + 2 = 3$ . Probe $i = 1$ : $(1 + 3) mod 7 = 4$ → slot 4. Compare with $36$ above: same home (slot 1) but step $3$ vs step $1$ → different paths. That divergence is exactly how double hashing dodges secondary clustering.

Level 3 — Analysis

Now you reason about behaviour, not just crank arithmetic.

Recall Solution L3.1

Load factor $α = n / m = 15/20 = 0.75$ — "the table is 75% full." WHY this formula: under uniform hashing each probe hits an occupied slot with probability $\approx α$ ; the expected count of probes before the first empty one is $\frac{1}{1 - α}$ . $\frac{1}{1 - 0.75} = \frac{1}{0.25} = 4.$ So about 4 probes per failed lookup. (See Load factor and rehashing.)

Recall Solution L3.2

$i 01234567 i^{2} mod 8 01410141$ Distinct residues: ${0, 1, 4}$ — only 3 slots. The other 5 slots ( $2, 3, 5, 6, 7$ ) are unreachable, so an insert can fail even though the table is mostly empty. WHY the $α \leq 0.5$ bound (for prime $m$ ): take a prime $m$ and consider the probes $i = 0, 1, \dots, ⌊ m /2 ⌋$ . Claim: these first $⌈ m /2 ⌉$ probes are all distinct. Suppose two of them collided, $i^{2} \equiv j^{2} (mod m)$ with $0 \leq i < j \leq ⌊ m /2 ⌋$ . Then $m ∣ (j^{2} - i^{2}) = (j - i) (j + i)$ . Since $m$ is prime it must divide one factor. But $0 < j - i < m$ and $0 < j + i < m$ (both are below $m$ because $i, j \leq m /2$ ), so $m$ divides neither — contradiction. Hence the first $⌈ m /2 ⌉$ probes land on $⌈ m /2 ⌉$ different lockers. So as long as at most half the table is full ( $α \leq 0.5$ ), those half-a-table's-worth of distinct probes cannot all be occupied — at least one is empty, and the insert must succeed. Above $α = 0.5$ that counting argument breaks and an insert can spin without ever hitting a free reachable slot. (See Prime table sizes.)

Recall Solution L3.3

First, a word we need: the home range of a cluster is the set of home slots that would funnel a new key into that cluster — i.e. all the lockers whose home-slot value lands the key onto the cluster, so it then crawls to the cluster's tail. Now the reasoning: a cluster is a contiguous run of $L$ full lockers. Any key whose home lands on any of those $L$ occupied slots (or the single empty-looking slot just before the run's start, which under insertion still funnels in) crawls forward to the cluster's tail and extends it. So the cluster's home range has size about $L + 1$ . Probability the next uniformly-random home falls in that range $\approx \frac{L + 1}{m}$ — proportional to $L$ . Bigger clusters swallow more keys ⇒ rich-get-richer ⇒ primary clustering.

Level 4 — Synthesis

Now you combine ideas — designing/comparing, not just computing.

Recall Solution L4.1

Start state: slot $1$ full, slot $6$ full, rest empty. Linear:

$85$ : home 1 full → $i = 1$ : $2$ empty → 2.
$92$ : home 1 full, 2 full → $i = 2$ : $3$ empty → 3.
$101$ : home 3 now full → $i = 1$ : $4$ empty → 4. Linear result: keys pile at $2, 3, 4$ — one tight run. Quadratic ( $f = i^{2}$ ):
$85$ : home 1 full → $i = 1$ : $(1 + 1) = 2$ empty → 2.
$92$ : home 1 full, $i = 1$ : $(1 + 1) = 2$ full → $i = 2$ : $(1 + 4) = 5$ empty → 5.
$101$ : home 3 → $i = 1$ : $(3 + 1) = 4$ empty → 4. Quadratic result: keys at $2, 5, 4$ — spread out, no 3-in-a-row jam. That is the point of the growing square jump.

Recall Solution L4.2

Solve $\frac{1}{1 - α} \leq 5 \Rightarrow 1 - α \geq \frac{1}{5} \Rightarrow α \leq 0.8$ . Min table size: $α = n / m \leq 0.8 \Rightarrow m \geq n /0.8 = 90/0.8 = 112.5 \Rightarrow m \geq 113$ . $113$ is already prime, so the smallest valid prime size is $113$ . Convenient. (Choosing prime sizes is discussed in Prime table sizes and enables Load factor and rehashing triggers when $α$ crosses $0.8$ .)

Recall Solution L4.3

Requirement: $h_{2} (k)$ must be coprime to $m$ . Since $m = 2^{4}$ , its only prime factor is $2$ , so "coprime to $m$ " simply means "odd." Concrete formula: $h_{2} (k) = (2 (k mod 8) + 1)$ — always odd, ranges over $1, 3, 5, \dots, 15$ . Any odd step size and a power-of-two $m$ produce a full permutation. WHY an odd step reaches every slot: stepping by $s$ from any start visits every locker exactly once iff you can only return to the start after exactly $m$ steps, i.e. the smallest multiple of $s$ divisible by $m$ is $m \cdot s$ — which happens exactly when $s$ and $m$ share no common factor. For $m = 2^{p}$ the only factor to avoid is $2$ , so any odd $s$ works; an even $s$ would share the factor $2$ and cycle through only half (or fewer) of the lockers. Check with a value: $k = 20$ : $20 mod 8 = 4$ , $h_{2} = 2 \cdot 4 + 1 = 9$ (odd ✓, coprime to 16 ✓).

Level 5 — Mastery

Now you defend a full design against edge cases and delete correctly.

Recall Solution L5.1

Search $B$ (home $3$ ): probe $i = 0$ → slot 3 is EMPTY → algorithm concludes " $B$ not present" and stops. BUG — $B$ is sitting right next door in slot 4, but the trail was cut. Why the naive delete fails: search stops at the first EMPTY, because during insertion an EMPTY meant "nothing was ever placed beyond here." Deleting to EMPTY lies about that history. Tombstone fix: mark slot 3 as DELETED (a tombstone), not EMPTY. Now searching $B$ : probe slot 3 sees DELETED → keep going → probe slot 4 → found $B$ . ✓ Inserts may overwrite a tombstone; searches pass through it. Too many tombstones ⇒ rehash (see Load factor and rehashing).

Recall Solution L5.2

(a)

$α = 0.5$ : $\frac{1}{1 - 0.5} = 2$ probes.
$α = 0.9$ : $\frac{1}{1 - 0.9} = 10$ probes. Ratio: $10/2 = 5 \times$ slower for going from half-full to 90%-full. Justification: as $α$ climbs toward $1$ the denominator $1 - α$ shrinks toward $0$ , so the cost $\frac{1}{1 - α}$ grows without bound — a tiny move from $0.9$ to $0.99$ multiplies the cost tenfold. Resizing (doubling the table) when $α$ crosses, say, $0.7$ keeps every operation cheap. The curve below shows the explosion.

(b) With $α = 1$ every locker is full. The probe sequence is a permutation of the $m$ lockers, so the algorithm probes $i = 0, 1, \dots, m - 1$ — exactly $m$ probes, all landing on full lockers. What stops the loop: the termination rule from the top of the page — "if you have probed $m$ times you have visited every locker in the table, so abort." Without that ceiling the counter $i$ would keep incrementing and the probe sequence would just revisit lockers forever (an infinite loop). With it, insert into a full table cleanly fails after $m$ probes and signals "resize me." This is why we never let $α$ actually reach $1$ — we resize well before.

Recall Solution L5.3

(a) Scheme — double hashing. It is the only one of the three that kills both primary clustering (linear's $+ 1$ crawl builds long runs) and secondary clustering (quadratic's fixed $i^{2}$ path is shared by all same-home keys): under double hashing two keys must agree on both $h_{1}$ and $h_{2}$ to walk the same path, which is very rare. (b) Table size. Need $\frac{1}{1 - α} \leq 4 \Rightarrow 1 - α \geq \frac{1}{4} \Rightarrow α \leq 0.75 \Rightarrow m \geq 1000/0.75 = 1333.3 \Rightarrow m \geq 1334$ . Pick the next prime, $1361$ , so any $h_{2} \in [1, m - 1]$ is coprime to $m$ (guarantees a full-permutation probe sequence with no divisibility worries) — see Prime table sizes. (c) Hashes. $h_{1} (k) = k mod 1361$ (division method, Hash functions — division & multiplication methods); $h_{2} (k) = 1 + (k mod 1360)$ so $h_{2} \in [1, 1360]$ , never $0$ (no infinite loop) and always coprime to the prime $1361$ . If keys may be adversarial, upgrade $h_{1}$ to a Universal hashing family so an attacker cannot force collisions. (d) Deletion. Use tombstones (DELETED): searches pass through them, inserts reuse them. This preserves probe chains (see L5.1). Track the tombstone count and rehash when tombstones dominate. (e) Resize trigger. When the live load factor $α = \frac{live items}{m}$ crosses $0.75$ , rehash into a fresh table of the next prime $\geq 2 m$ . This keeps unsuccessful cost under 4 probes and preserves the contiguous-array Cache locality advantage over Hashing — chaining. Sanity check: at $n = 1000$ , $m = 1361$ , $α = 1000/1361 \approx 0.735 < 0.75$ , and $\frac{1}{1 - 0.735} \approx 3.77 \leq 4$ probes. ✓ The design meets the cost budget.