Worked examples — Chaining — linked lists in buckets, load factor, resizing

Before we start, one reminder of the symbols we lean on the whole page, each in plain words:

The symbol $\mathrm{mod}$ means remainder: $13\mathrm{mod}4=1$ because $13=3\times 4+1$, remainder $1$. That remainder is always between $0$ and $m-1$, which is exactly why it makes a valid bucket index.

---

The scenario matrix

Every problem chaining can hand you falls into one of these cells. The worked examples below each carry a tag like (C3) so you can see which cell they fill.

Cell	Scenario class	The edge it stresses
C1	Empty / single-key table	$n=0$ and $n=1$: degenerate, $\alpha =0$
C2	Light table, no collision	$\alpha <1$, every key its own bucket
C3	Collision into a shared bucket	two+ keys, chain length $>1$
C4	Exactly at the resize threshold	$\alpha ={\alpha }_{max}$ boundary, resize triggers
C5	Heavy / oversized table	$\alpha >1$ (chaining survives) and $\alpha \ll 1$ (waste)
C6	Adversarial worst case	all keys collide → one chain of length $n$
C7	Amortized cost over many inserts	geometric doubling sum
C8	Real-world word problem	mapping a story onto $n,m,\alpha$
C9	Exam-style twist	successful vs unsuccessful search formula

---

Example 1 — The empty and single-key table (C1)

Step 1 — Compute $\alpha$ for the empty table. $\alpha =\frac{n}{m}=\frac{0}{8}=0.$ Why this step? $\alpha$ is defined as $n/m$; with $n=0$ there are literally zero items to average, so the average per bucket is $0$. This is the smallest $\alpha$ can ever be.

Step 2 — Expected unsuccessful search cost. Using the recap formula, expected cost $=1+\alpha =1+0=1$. Why this step? The "$1$" never disappears — even on an empty table you must compute the hash and touch the (empty) bucket once to discover it's empty. Search is never free; it is $O(1)$, not $O(0)$.

Step 3 — Insert $k=42$. $h(42)=42\mathrm{mod}8=2(\text{since }42=5\times 8+2).$ Key $42$ becomes the head of bucket $2$'s chain. Now $n=1$, so $\alpha =1/8=0.125$. Why this step? This is the base case of everything: one hash, one prepend, $O(1)$ work, and $\alpha$ ticks up by $1/m$.

---

Example 2 — Light table, no collisions (C2)

Step 1 — Hash each key. $h(3)=3,h(7)=7,h(4)=4,h(9)=9.$ Why this step? For $k\mathrm{mod}10$, the bucket is just the last digit. Four distinct last digits → four distinct buckets.

Step 2 — Place them. Buckets $3,4,7,9$ each hold exactly one key; buckets $0,1,2,5,6,8$ are empty.

Figure s01: a vertical column of $10$ buckets (numbered $0$–$9$, top to bottom). Four of them — buckets $3$, $4$, $7$, $9$ — each show a single green box holding their one key (the key equals the slot number here); the other six buckets are empty rectangles. The picture makes the "one key per occupied bucket, no chains longer than $1$" situation obvious at a glance.

Step 3 — Load factor and longest chain. $\alpha =\frac{n}{m}=\frac{4}{10}=0.4,\text{longest chain}=1.$ Why this step? $\alpha =0.4$ means "on average $0.4$ items per bucket" — but average hides the truth here: no bucket exceeds length $1$. This is the happy case chaining is designed to make common.

---

Example 3 — Collisions form a chain (C3)

Step 1 — Hash each key. $5\mathrm{mod}4=1,9\mathrm{mod}4=1,13\mathrm{mod}4=1,1\mathrm{mod}4=1.$ Why this step? All four are $\equiv 1(\mathrm{mod}4)$ (they differ by multiples of $4$), so all four collide into bucket $1$. The hash cannot tell them apart by slot.

Step 2 — Build the chain (prepend at head). Insert order $5,9,13,1$; each new key goes to the front: $\text{bucket }1:1\to 13\to 9\to 5.$ Why this step? Prepend is $O(1)$ — no walking to the tail. The chain reads newest-first.

Figure s02: the same $4$-bucket column. Buckets $0$, $2$, $3$ are empty rectangles; bucket $1$ has a horizontal row of four red boxes joined by white arrows, reading $1\to 13\to 9\to 5$ from the head. A red caption underlines "length 4" — one bucket carrying the entire table while three sit idle.

Step 3 — Chain length and $\alpha$. Bucket $1$ has length $4$; all other buckets empty. $\alpha =4/4=1$. Why this step? Note $\alpha =1$ says "average $1$ per bucket," yet reality is one bucket of $4$ and three of $0$. Average is not maximum — a crucial lesson chaining teaches.

---

Example 4 — Exactly at the resize threshold (C4)

Step 1 — Check the threshold. Inserting key $1$ would make $n=4$, so $\alpha$ would become $4/4=1$. $1>0.75\Rightarrow \text{resize triggered.}$ Why this step? The rule fires on the would-be $\alpha$ after the insert, not before. At $\alpha =0.75$ exactly we're still fine; the insert that exceeds it forces the grow.

Step 2 — Double the array. Recall $m^{\prime }$ is the new bucket count after doubling: $m^{\prime }=2m=2\times 4=8.$ Why this step? Doubling (not adding a constant) is what makes resizes exponentially rare and keeps amortized insert $O(1)$ — see Example 7.

Step 3 — Rehash all four keys with $h^{\prime }(k)=k\mathrm{mod}{m}^{\prime }=k\mathrm{mod}8$. $5\mathrm{mod}8=5,9\mathrm{mod}8=1,13\mathrm{mod}8=5,1\mathrm{mod}8=1.$ So: bucket $1$: $1\to 9$; bucket $5$: $13\to 5$. The old length-4 chain split into two length-2 chains.

Figure s03: now an $8$-bucket column (slots $0$–$7$). Bucket $1$ holds two blue boxes $1\to 9$; bucket $5$ holds two yellow boxes $13\to 5$; every other bucket is empty. A green caption reads "resize m=4 → 8: long chain SPLITS," making visible how the single overloaded bucket of Figure s02 fans out into two half-length chains.

Step 4 — New load factor. $\alpha =\frac{n}{m^{\prime }}=\frac{4}{8}=0.5\le \mathrm{0.75.}✓$ Why this step? Doubling $m$ roughly halves $\alpha$, buying us room before the next resize. The chains got flatter exactly as promised.

---

Example 5 — Heavy table and wasteful table (C5)

Step 1 — Case (a), heavy: $m=10$. $\alpha =\frac{100}{10}=10,E[\text{cost}]=1+\alpha =11.$ Why this step? $\alpha =10$ means chains average $10$ nodes. Chaining survives $\alpha >1$ (unlike open addressing) — it just slows to $\sim 11$ touches per search. Graceful, but slow.

Step 2 — Case (b), oversized: $m=1000$. $\alpha =\frac{100}{1000}=0.1,E[\text{cost}]=1+0.1=\mathrm{1.1.}$ Why this step? Fast searches ($\sim 1.1$ touches) — but $1000$ buckets hold only $100$ items, so $\sim 900$ slots sit empty, wasting memory and hurting cache locality.

Step 3 — Verdict. Neither extreme is ideal. Keep $\alpha$ near a constant like $0.75$: fast and memory-lean. Why this step? This is the whole tuning philosophy — $\alpha$ is the knob trading time against space.

---

Example 6 — The adversarial worst case (C6)

Step 1 — Hash the adversarial keys. $8\mathrm{mod}8=0,16\mathrm{mod}8=0,24\mathrm{mod}8=0,\dots ,48\mathrm{mod}8=0.$ Every multiple of $8$ hashes to bucket $0$.

Figure s04: the $8$-bucket column with buckets $1$–$7$ all empty and bucket $0$ carrying a long row of six red boxes $48\to 40\to 32\to 24\to 16\to 8$ chained by white arrows. Two captions call it out: "attacker: all multiples of 8 → bucket 0" and "one chain of length n → worst case O(n)." Visually it's the exact opposite of the even spread in Figure s01.

Step 2 — Load factor at $n=6$. $\alpha =\frac{6}{8}=\mathrm{0.75.}$ Why this step? Here $\alpha$ looks healthy ($0.75$, under threshold!) yet the table is pathological. $\alpha$ measures the average, and the average is blind to this all-in-one-bucket disaster.

Step 3 — Worst-case search cost. search(48): hash to bucket $0$, then walk the chain of all $6$ keys until $48$ is found (or the end for an unsuccessful search). $\text{worst-case cost}=O(n)=6\text{ touches}.$ Why this step? The "expected $O(1+\alpha )$" promise assumed simple uniform hashing — keys spread evenly. An adversary who breaks that assumption forces all $n$ into one chain, collapsing to $O(n)$.

Step 4 — The fix. Use a good or randomized hash so an attacker cannot predict which keys collide. Why this step? You cannot make worst case impossible (pigeonhole guarantees some collisions), but you can make the all-collide case astronomically unlikely.

---

Example 7 — Amortized cost of many inserts (C7)

Step 1 — List the resize points. As $n$ climbs, the array doubles at $m=1,2,4,8,16$. At each doubling we copy every current key into the new array. The copy counts are the sizes just before each double: $1,2,4,8$. Why this step? Rehashing touches all $n$ current keys — that's the $O(m)$ cost per resize we must sum.

Step 2 — Sum the geometric series. $1+2+4+8=15=2\cdot 8-1<2n.$ More generally ${\sum }_{i=0}^{{\log }_{2}n-1}{2}^i=2^{{\log }_{2}n}-1=n-1<n$ (or $<2n$ counting the final table build). Why this step? A geometric series is dominated by its last term. The total is linear in $n$, not quadratic — this is the magic of doubling.

Step 3 — Amortize. $\frac{\text{total copies}}{n}=\frac{15}{16}<1=O(1)\text{amortized}.$ Why this step? Spread the occasional expensive resize over all the cheap inserts and each insert averages $O(1)$ — even though one individual insert (the one that resizes) costs $O(m)$.

Step 4 — Contrast with "add a constant." If instead we grew by $+1$ each time, copies would be $1+2+3+\cdots +n=\frac{n(n-1)}{2}=\Theta (n^2)$ → $\Theta (n)$ per insert. Terrible. Why this step? This is why we double: geometric growth ($\Theta (n)$ total) beats arithmetic growth ($\Theta (n^2)$ total).

---

Example 8 — Real-world word problem (C8)

Step 1 — Identify $n$ and $m$. $n=12,000$ sessions (items stored), $m=16,000$ buckets. Why this step? Word problems are just $n,m,\alpha$ in disguise. Nail down which quantity is which before touching arithmetic.

Step 2 — Load factor and current cost. $\alpha =\frac{12000}{16000}=0.75,E[\text{cost}]=1+0.75=\mathrm{1.75.}$ Since $1.75<2$, they are within budget. ✔ Why this step? The expected cost formula (our $1+\alpha$ recap) turns an abstract $\alpha$ into a concrete "node-touches" number we can compare against the $2$-touch goal.

Step 3 — Usage triples, same $m$. $\alpha =\frac{36000}{16000}=2.25,E[\text{cost}]=1+2.25=3.25>2.$ Budget blown — chains average $2.25$ nodes. Why this step? $\alpha$ scales linearly with $n$ when $m$ is fixed; tripling $n$ triples $\alpha$ (from $0.75$ to $2.25$).

Step 4 — Fix: resize. To pull $\alpha$ back to $0.75$ we need $m=n/\alpha =36000/0.75=48,000$ buckets — exactly $3\times$ the original. In doubling steps: $16000\to 32000\to 64000$; at $m=64000$, $\alpha =36000/64000=0.5625<0.75$. ✔ Why this step? Resizing restores the load factor and thus the speed — the same doubling policy from Example 4, now on a production scale.

---

Example 9 — Exam twist: successful vs unsuccessful search (C9)

Step 1 — Unsuccessful search. You must scan the entire chain (the key isn't there), so $E[\text{unsuccessful}]=1+\alpha =1+0.6=\mathrm{1.6.}$ Why this step? Absent key ⇒ no early stop ⇒ you walk the whole expected-length-$\alpha$ chain, plus the $1$ to hash. This is exactly our recap formula.

Step 2 — Successful search (careful formula). When the key is present you stop early, on average halfway down its chain. The standard formula is $1+\frac{\alpha }{2}-\frac{\alpha }{2n}$: $E[\text{successful}]=1+\frac{0.6}{2}-\frac{0.6}{2\cdot 300}=1+0.3-0.001=\mathrm{1.299.}$ Why this step? A present key lets you stop early, so you save roughly $\alpha /2$ versus the unsuccessful case. The tiny $-\alpha /(2n)$ term corrects for the key you're searching contributing to its own chain length.

Step 3 — Compare. $1.299<\mathrm{1.6.}$ Successful search is cheaper — you stop as soon as you hit the target instead of running off the end. Why this step? This matches intuition: finding something present lets you halt early; proving something absent forces a full scan.

---

Matrix coverage check

Recall Did we hit every cell?

C1 → Ex 1 (empty, single). C2 → Ex 2 (light, no collision). C3 → Ex 3 (chain forms). C4 → Ex 4 (resize boundary). C5 → Ex 5 (heavy + oversized). C6 → Ex 6 (adversarial $O(n)$). C7 → Ex 7 (amortized doubling). C8 → Ex 8 (word problem). C9 → Ex 9 (successful vs unsuccessful). ✔ Every cell covered.

---

Connections

• Chaining — linked lists in buckets, load factor, resizing (index 3.3.3) — the parent this page drills into.
• Hash Functions — Example 6's fix (randomized hashing) lives here.
• Open Addressing — the alternative that dies at $\alpha =1$ (contrast with Ex 5).
• Amortized Analysis — the formal backing for Example 7.
• Dynamic Arrays — same doubling series, applied to append.
• Pigeonhole Principle — why Example 6's collisions can never be fully avoided.
• Linked Lists — the bucket container walked in every search example.