Exercises — Chaining — linked lists in buckets, load factor, resizing

$\alpha =n/m=12/16=0.75$. What we did: plugged into the definition. Why: $\alpha$ is literally "keys divided by buckets," the average chain length. So the average bucket holds $0.75$ keys.

(a) $O(n)$ — every key could be in one chain. (b) $O(1+\alpha )$ — one bucket touch, then walk $\alpha$ items on average. (c) $O(1)$ — a hash is a fixed computation on the key. Why these: the "$1$" is the hash+bucket touch; the "$\alpha$" is the walk; the worst case ignores the average and imagines the whole chain collapsing to one slot.

False. At $\alpha =1$ the average chain length is $1$; buckets simply hold more nodes as $\alpha$ grows. It degrades gracefully. The "$\alpha \le 1$ hard wall" belongs to Open Addressing, where the array physically fills up.

Compute each slot: $10\mathrm{mod}5=0$, $7\mathrm{mod}5=2$, $12\mathrm{mod}5=2$, $2\mathrm{mod}5=2$, $17\mathrm{mod}5=2$.

• Bucket 0: $10$
• Bucket 1: (empty)
• Bucket 2: prepend order $7$, then $12$, then $2$, then $17$ → head-first: $17\to 2\to 12\to 7$
• Bucket 3: (empty)
• Bucket 4: (empty)

Read the figure to see why prepend reverses order. Follow the teal arrows in slot 2 from the head: they point $17\to 2\to 12\to 7$, which is exactly the reverse of the insertion order $7,12,2,17$. Each new key was clipped onto the head, shoving the older ones rightward — the picture makes that "shoving" visible in a way the text list cannot: you can trace the head pointer and watch the newest arrival always sitting leftmost.

$\alpha =n/m=5/5=1$. Expected unsuccessful-search work is $1+\alpha =2$ (one hash/bucket touch plus scanning $\alpha =1$ item on average). Note the gap with reality: this specific table has one chain of length 4 and three empty buckets — the uniform-hashing assumption is violated because $h(k)=k\mathrm{mod}5$ on these particular keys is not spreading them. The $1+\alpha$ formula is an average over random keys, not a guarantee for adversarial input.

Need $\frac{300}{m}\le 0.75\Rightarrow m\ge \frac{300}{0.75}=400$. Smallest integer: $m=400$. Why divide: $\alpha \le 0.75$ means $n\le 0.75m$, so $m\ge n/0.75$.

Resize when $n/m>0.75$, i.e. $n>0.75\times 4=3$. So $n=1,2,3$ are fine ($\alpha =0.25,0.5,0.75$). The 4th insert would make $n=4$, $\alpha =1>0.75$ → resize to $m=8$. First resize: on the 4th insert; new $m=8$. Why "$>$" not "$\ge$": $\alpha =0.75$ exactly equals the threshold and is allowed; only exceeding it triggers a grow.

Define every symbol first. Let $s$ be the new table size after a doubling (so $s\in \{8,16,\dots ,512\}$). Let $N$ be the number of keys stored immediately after the final resize — the count that filled the last table's predecessor.

When we double to size $s$, we copy every key currently stored. We trigger the resize the instant the old array of size $s/2$ would exceed its threshold ${\alpha }_{max}=0.75$, so the number of keys copied is at most $0.75\times (s/2)<s/2$. To get a clean, safe upper bound we use $\le s/2$ for each event:

• resize to $s=8$: copy $\le 4$
• resize to $s=16$: copy $\le 8$
• resize to $s=32$: copy $\le 16$ … up to resize to $s=512$: copy $\le 256$.

Total copy work is bounded by: $C_{\text{double}}\le 4+8+16+32+64+128+256=508.$ Now the comparison to $2N$. By the definition above, $N=256$ (the "$s/2=256$" that triggered the final grow). Then $2N=512$, and indeed $C_{\text{double}}\le 508<512=2N$. This is the geometric-series bound $\sum 2^i<2\cdot (\text{largest term})$. Spread over $N=256$ inserts, copy work per insert is $508/256<2=O(1)$ amortized. See Amortized Analysis and the same trick in Dynamic Arrays.

Add-4-slots scheme (same final key count $N=256$): you resize at sizes $4,8,12,\dots ,256$, copying $0+4+8+\cdots +252$ keys: $C_{\text{add4}}=4(0+1+2+\cdots +63)=4\cdot \frac{63\cdot 64}{2}=4\cdot 2016=8064.$ That is an arithmetic series growing like $\Theta (N^2)$, i.e. $\Theta (N)$ per insert — catastrophically worse than the constant we got from doubling. Why doubling wins: the copy costs form a geometric series bounded by $2N$; adding a constant makes them an arithmetic series that grows quadratically.

New slots: $3\mathrm{mod}8=3$, $7\mathrm{mod}8=7$, $11\mathrm{mod}8=3$, $15\mathrm{mod}8=7$.

Traverse the old chain head → tail: $15,11,7,3$. Prepend each into the new table:

Final:

• Bucket 3: $3\to 11$
• Bucket 7: $7\to 15$

The one chain of length 4 split into two chains of length 2. The figure lets you watch the split happen — trace one key across the two panels (e.g. the plum key $11$ leaves the crowded bucket 3 on the left and lands alone-then-paired in bucket 3 on the right, while $15$ jumps to bucket 7): the geometry shows the "spreading" that the text table only lists.

Chaining. (1) Deletion is a clean linked-list unlink — no "tombstone" markers needed, unlike Open Addressing where deleting mid-probe-sequence forces lazy-deletion bookkeeping. (2) It tolerates $\alpha =1.4>1$ gracefully (chains just hold ~1.4 items on average), whereas open addressing cannot even exist at $\alpha >1$ (more keys than slots). Why this is synthesis: you combined the deletion property (L1-level fact) with the $\alpha >1$ tolerance (L1-level fact) into a design decision under two constraints.

Use an asymmetric hysteresis pair:

• Grow (double $m$) when $\alpha$ would exceed $0.75$.
• Shrink (halve $m$) only when $\alpha$ drops below $0.25$ — not $0.375$.

Why the gap matters: after growing, $\alpha$ halves (to ~$0.375$); after shrinking, $\alpha$ doubles. If the shrink threshold were just below the post-grow value, a single delete could trigger a shrink, and one insert re-trigger a grow → $O(n)$ per operation forever (thrashing). A wide dead-zone ($0.25$ to $0.75$) means you must do $\Theta (m)$ operations between resizes, restoring amortized $O(1)$. Same reasoning as growable-and-shrinkable Dynamic Arrays. Why synthesis: you merged the doubling argument with a new shrink case and reasoned about the interaction between the two thresholds.

Number the keys $x_1,\dots ,x_n$ in the order they were inserted (each prepended to its bucket's head). To search for $x_i$, we examine $x_i$ itself plus every key inserted after $x_i$ that landed in the same bucket (they sit ahead of $x_i$ in the list).

Define an indicator $X_{ij}=1$ if $h(x_i)=h(x_j)$, else $0$, for $j>i$. Under uniform hashing $E[X_{ij}]=1/m$. The number of elements examined for $x_i$ is $1+{\sum }_{j>i}{X}_{ij}$.

Averaging over a uniformly random target $x_i$: $E[\text{cost}]=\frac{1}{n}{\sum }_{i=1}^n\left(1+{\sum }_{j=i+1}^n\frac{1}{m}\right)=\frac{1}{n}{\sum }_{i=1}^n\left(1+\frac{n-i}{m}\right).$ Split the sum: $\frac{1}{n}{\sum }_{i=1}^{n}1=1$, and $\frac{1}{nm}{\sum }_{i=1}^n(n-i)=\frac{1}{nm}\cdot \frac{n(n-1)}{2}=\frac{n-1}{2m}.$ So $E[\text{cost}]=1+\frac{n-1}{2m}.$ Now substitute $\alpha =n/m$ to see the load factor appear. Split the fraction: $\frac{n-1}{2m}=\frac{n}{2m}-\frac{1}{2m}$. The first piece is $\frac{n}{2m}=\frac{\alpha }{2}$ directly. For the second, multiply top and bottom by $n$: $\frac{1}{2m}=\frac{n}{2mn}=\frac{\alpha }{2n}$. Therefore $E[\text{cost}]=1+\frac{\alpha }{2}-\frac{\alpha }{2n},$ which is $O(1+\alpha )$. It matches the parent note's stated formula exactly. Why this tool (indicators): turning "same bucket?" into a $0/1$ variable lets linearity of expectation sum the collisions without tracking the messy joint distribution — the standard weapon for expected-cost proofs.

Put $m+1$ distinct keys into $m$ buckets via $h$. By the Pigeonhole Principle, since there are more keys ($m+1$) than buckets ($m$), at least one bucket receives $\ge \lceil (m+1)/m\rceil =2$ keys. Because $|U|>m$ guarantees $m+1$ distinct keys exist, no hash function can avoid this. Hence collisions are structurally unavoidable — chaining exists to handle them, not prevent them. Why pigeonhole: it is the minimal counting argument that forces a repeat, requiring nothing about how $h$ works — so it applies to every hash function.

• Insert $8$: $8\mathrm{mod}4=0$. $n=1$, $\alpha =0.25$ OK. Bucket 0: $8$.
• Insert $4$: $4\mathrm{mod}4=0$, prepend. $n=2$, $\alpha =0.5$ OK. Bucket 0: $4\to 8$.
• Insert $12$: $12\mathrm{mod}4=0$, prepend. $n=3$, $\alpha =0.75$ OK (equals threshold, allowed). Bucket 0: $12\to 4\to 8$.
• Insert $5$: would make $n=4$, $\alpha =1>0.75$ → resize to $m=8$ first, then insert $5$.

Rehash (walk old bucket 0 head → tail: $12,4,8$; prepend each with $k\mathrm{mod}8$):

Then insert the pending key $5$: $5\mathrm{mod}8=5$, prepend into bucket 5.

Final $m=8$:

• Bucket 0: $8$
• Bucket 4: $4\to 12$
• Bucket 5: $5$
• Buckets 1,2,3,6,7: empty

Final $\alpha =4/8=0.5$. The chain of length 3 at slot 0 got flattened into single-item buckets. Why this closes the loop: you exercised hashing, prepend order, the strict-$>$ threshold, doubling, an explicit rehash traversal order, and re-reading $\alpha$ — the entire machine in one problem.

L1 — $\alpha =n/m$; chaining survives $\alpha >1$. ::: Definitions and the open-addressing-vs-chaining distinction. L2 — Insert order reverses (prepend); $m\ge n/{\alpha }_{max}$. ::: Apply the mechanics. L3 — Doubling gives $\Theta (N)$ total copy work, $O(1)$ amortized. ::: Analyze cost growth. L4 — Chaining for deletes + $\alpha >1$; hysteresis avoids thrashing. ::: Design under constraints. L5 — Successful search $=1+\frac{\alpha }{2}-\frac{\alpha }{2n}$; pigeonhole forces collisions. ::: Prove from scratch.