Exercises — Hash table — structure, open addressing vs chaining

$\alpha =\frac{n}{m}=\frac{12}{16}=0.75$ WHAT we did: plugged into the definition of load factor. WHY it matters: open addressing stores every key inside the array, so it needs at least one free slot — it only works while $\alpha <1$. Here $\alpha =0.75<1$, so it operates, but it is already above the usual rehash threshold ($\approx 0.7$), so a good implementation would rehash to a bigger array right about now (see Load factor and dynamic resizing / rehashing).

(a) Chaining — multiple keys hang outside the array in a list at one bucket. (See Linked lists.) (b) Open addressing — all keys live inside the flat array; 22 slid to the next slot by probing. Mnemonic: CHAIN out, PROBE in.

Compute each home slot ($k\mathrm{mod}5$), appending to the tail of that bucket's list:

• 9 % 5 = 4 → bucket 4: [9]
• 14 % 5 = 4 → bucket 4: [9, 14] (collision → chain it)
• 24 % 5 = 4 → bucket 4: [9, 14, 24]
• 19 % 5 = 4 → bucket 4: [9, 14, 19]? No — $19\mathrm{mod}5=4$, append: [9, 14, 24, 19]
• 3 % 5 = 3 → bucket 3: [3]

Final table:

Search 24: go to bucket 4, scan the list front-to-back: 9 (no), 14 (no), 24 (yes) → examined 3 nodes.

Slot rule: ${\text{slot}}_i=(h(k)+i)\mathrm{mod}7$, trying $i=0,1,2,\dots$ until empty.

• 8 % 7 = 1 → slot 1 empty → place. [_,8,_,_,_,_,_]
• 15 % 7 = 1 → slot 1 taken → $i=1$: $(1+1)=2$ empty → place. [_,8,15,_,_,_,_] WHY slide right: $f(1)=1$ nudges us one slot along.
• 22 % 7 = 1 → slot 1 taken, slot 2 taken → $i=2$: $(1+2)=3$ empty → place. [_,8,15,22,_,_,_]

Final: [_, 8, 15, 22, _, _, _] (indices 1,2,3 filled). This is a primary cluster — three keys in a contiguous run.

Treat the string as a base-$p$ number, most significant character first: $h_{\text{code}}(\text{"abc"})=97\cdot 31^2+98\cdot 31^1+99\cdot 31^0$ $=97\cdot 961+98\cdot 31+99=93217+3038+99=96354$ Compression (turn the huge integer into a valid slot): $\text{index}=96354\mathrm{mod}100=54$ WHY base-$p$ and not a plain sum: the powers $31^2,31^1,31^0$ give each position a different weight, so "abc" and "cba" (an anagram) produce different codes — a plain sum would collide them. See Polynomial rolling hash & Rabin–Karp.

The model says each probed slot is occupied with probability $\approx \alpha$, so the expected number of probes is the geometric sum $E=1+\alpha +{\alpha }^2+\cdots =\frac{1}{1-\alpha }.$ At $\alpha =0.8$: $E=\frac{1}{1-0.8}=\frac{1}{0.2}=5\text{ probes.}$ For $E=4$, solve $\frac{1}{1-\alpha }=4\Rightarrow 1-\alpha =\frac{1}{4}\Rightarrow \alpha =\mathrm{0.75.}$

search(22): $22\mathrm{mod}7=1$. Probe:

• $i=0$: slot 1 holds 8 ≠ 22 → keep going.
• $i=1$: slot 2 is empty → search concludes "22 is not here" and stops. ✗

But 22 is in slot 3! The blanked slot 2 severed the probe chain — an empty slot is the universal "stop" signal. Fix: on deletion, write a tombstone (a DELETED marker) instead of a blank. Search treats a tombstone as "keep probing"; insertion treats it as "reusable free slot." With a tombstone in slot 2, search(22) correctly walks 1 → 2 (tombstone, continue) → 3 (found). ✓

(a) Trigger condition: $\alpha =n/8>0.7\Rightarrow n>5.6$. The first integer $n$ crossing this is $n=6$, giving $\alpha =6/8=0.75>0.7$. So the rehash fires on the 6th insert. (b) All $n=6$ keys are reinserted into the new array of capacity $m=16$: ${\alpha }_{\text{new}}=\frac{6}{16}=\mathrm{0.375.}$ WHY doubling: halving $\alpha$ buys many cheap inserts before the next rehash, so the expensive $O(n)$ copy happens rarely — the amortized cost per insert stays $O(1)$.

Choose separate chaining. Reasons, each tied to the workload:

1. Frequent deletions → chaining deletes by simply unlinking a list node ($O(1)$ given the node), with no tombstones to accumulate and pollute the table. Open addressing would degrade under this churn (see L3.2 trap).
2. Unknown final $n$ → chaining tolerates $\alpha >1$ gracefully (lists just grow), so an under-sized array is only mildly slow, not broken. Open addressing fails at $\alpha =1$.
3. Load-factor robustness → search stays $O(1+\alpha )$ instead of the sharper $\frac{1}{1-\alpha }$ blow-up.

Trade-off acknowledged: chaining loses cache-friendliness (pointer chasing) — but for a correctness- and flexibility-driven compiler table that is an acceptable price. This is the CHAIN out, PROBE in decision applied deliberately. See Sets and Maps / Dictionaries.

Compute the complement: the probability of no collision means all $k$ keys land in distinct slots. The 1st key is free; the 2nd must avoid 1 taken slot ($\frac{364}{365}$); the $i$-th must avoid $i-1$ taken slots: $P(\text{no collision})={\prod }_{i=0}^{k-1}\frac{m-i}{m}=\frac{365}{365}\cdot \frac{364}{365}\cdots \frac{343}{365}.$ Therefore $P(\text{collision})=1-{\prod }_{i=0}^{22}\frac{365-i}{365}\approx 1-0.4927=0.5073\approx \mathrm{0.51.}$ WHY this matters for hashing: with only 23 keys in 365 slots ($\alpha \approx 0.063$, a nearly empty table) a collision is already more likely than not. This is the Birthday paradox — the reason collision resolution is mandatory, not a rare afterthought.

(a) In chaining, each bucket is a self-contained list. Deleting a key means unlinking its node; the list's other nodes remain reachable because the list's own pointers are repaired, not a global probe sequence. There is no "chain across the array" to sever — so no stop-signal ambiguity — so no tombstone is ever required. (b) Adversary: pick keys all congruent mod $m$, e.g. for $m=5$ insert $5,10,15,20,\dots$ (all $\equiv 0$). Every key lands in bucket 0, forming one list of length $n$. Searching for the last key scans all $n$ nodes → $O(n)$.

• Load factor at $n=5$, $m=5$: $\alpha =5/5=1$, yet the worst-case cost is not $1+\alpha =2$ but the full list length $5$. WHY: $O(1+\alpha )$ is an average over uniform hashing; a pathological hash (or a malicious key stream) defeats the average. The real defence is a good, unpredictable hash function — see Hash functions — properties and design.

L1.1: $\alpha =0.75$ · L1.2: chaining / open addressing. L2.1: bucket 4 = [9,14,24,19], bucket 3 = [3], search 24 = 3 nodes · L2.2: [_,8,15,22,_,_,_] · L2.3: code $96354$, index $54$. L3.1: $5$ probes; $E=4$ at $\alpha =0.75$ · L3.2: tombstone fixes severed chain. L4.1: rehash on 6th insert; new $\alpha =0.375$ · L4.2: chaining. L5.1: $\approx 0.51$ · L5.2: adversary all-same-bucket, $\alpha =1$, cost $O(n)$.