Python dict and set internals: Exercises — Coding deep dive

Level 1 — Recognition

Recall Solution L1.1

Use $i_{0} = h & (m - 1)$ with $m = 16$ , so $m - 1 = 15 = 111 1_{2}$ (keep the low 4 bits). $100 = 0110010 0_{2}$ . The low 4 bits are $010 0_{2} = 4$ . $i_{0} = 100 & 15 = 4.$ Check against remainder: $100 mod 16 = 4$ . ✓ Answer: slot 4.

Recall Solution L1.2

(b) keep probing. A DUMMY means a key that once lived here was deleted. If we stopped, any key whose probe chain passed through this slot would be wrongly reported missing. Only an EMPTY slot ends an unsuccessful search. Answer: keep probing (skip the dummy).

Recall Solution L1.3

A key must be hashable, which in practice means immutable enough that its hash never changes. 42 ✓, "hi" ✓, (1, 2) ✓ (tuple of hashables), frozenset({3}) ✓. The list [1, 2] is mutable → unhashable; hash([1,2]) raises TypeError. Answer: all except [1, 2].

Level 2 — Application

Recall Solution L2.1

$m - 1 = 7 = 11 1_{2}$ (keep low 3 bits).

A: $i_{0} = 3 & 7 = 3$ . Slot 3 empty → A goes to slot 3.
B: $i_{0} = 11 & 7 = 3$ . $11 = 101 1_{2}$ , low 3 bits $= 011 = 3$ . Collision with A. Probe once with $perturb = 11$ : $i_{1} = (5 \cdot 3 + 1 + 11) & 7 = 27 & 7.$ $27 = 1101 1_{2}$ , low 3 bits $= 011 = 3$ … wait, recompute: $27 mod 8 = 3$ . Still slot 3? That is occupied, so probe again. Update perturb: $11 ≫ 5 = 0$ . $i_{2} = (5 \cdot 3 + 1 + 0) & 7 = 16 & 7 = 0.$ Slot 0 empty → B goes to slot 0. (Figure below traces this.)

Recall Solution L2.2

$E \approx \frac{1}{1 - 0.5} = \frac{1}{0.5} = 2.$ Answer: 2 probes on average. Compare with the CPython cap $α = 2/3$ , where $E = 3$ .

Recall Solution L2.3

Threshold: $\frac{2}{3} m = \frac{2}{3} \cdot 8 = 5.333 \dots$ . After the insert, $fill = 6$ . Test: is $6 > 5.333$ ? Yes. Answer: resize fires, growing to the next adequate power of two (16) and rehashing all keys.

Level 3 — Analysis

Recall Solution L3.1

The invariant is: if a == b then hash(a) == hash(b). Here 1 == 1.0 == True is True, and hash(1) == hash(1.0) == hash(True) == 1. So all three land at the same start slot and compare equal there. The table therefore treats them as the same key. Each assignment overwrites the value; the first key object (1) is retained but the last value ("c") wins. Answer: {1: "c"}.

Recall Solution L3.2

A search stops only at EMPTY. With just 2 EMPTY slots out of 8, a probe sequence may pass through many dummies (which look "occupied" to the searcher) before reaching an EMPTY slot. Effectively $α_{search} = fill / m = 6/8 = 0.75$ , giving $E \approx 1/ (1 - 0.75) = 4$ probes despite only 2 live keys. Fix: counting dummies in $fill$ pushes the table over $\frac{2}{3} m = 5.33$ , so it resizes and purges dummies, restoring short chains. This is exactly why CPython counts dummies in fill.

Recall Solution L3.3

Choose $n$ keys whose hashes all share the same low $k$ bits, e.g. hashes $0, m, 2 m, 3 m, \dots$ — every one has $i_{0} = 0$ . Then every insert collides and the probe chain for the last key is length $\approx n$ . Resizing changes $m$ , but if the adversary keeps supplying keys with matching low bits for the new $m$ too, the collisions persist. Resizing bounds $α$ (average), but it cannot repair a pathological hash distribution. Answer: worst case = O(n); resizing only guarantees the average.

Level 4 — Synthesis

Recall Solution L4.1

Mask $= 7$ . All three of P, Q, R have low 3 bits $= 001 = 1$ ( $1, 9, 17 \equiv 1 (mod 8)$ ), so they pile up starting at slot 1 — a clustering chain.

Insert P ( $h = 1$ ): $i_{0} = 1$ . Empty → P at slot 1.

Insert Q ( $h = 9$ ): $i_{0} = 9 & 7 = 1$ (occupied). Probe, $perturb = 9$ : $i_{1} = (5 \cdot 1 + 1 + 9) & 7 = 15 & 7 = 7$ . Empty → Q at slot 7.

Insert R ( $h = 17$ ): $i_{0} = 17 & 7 = 1$ (occupied). Probe, $perturb = 17$ : $i_{1} = (5 \cdot 1 + 1 + 17) & 7 = 23 & 7 = 7$ (occupied by Q). Update $perturb = 17 ≫ 5 = 0$ : $i_{2} = (5 \cdot 7 + 1 + 0) & 7 = 36 & 7 = 4$ . Empty → R at slot 4.

Delete P: slot 1 becomes DUMMY (not EMPTY).

Final: slot 1 = DUMMY, slot 4 = R, slot 7 = Q, rest EMPTY.

Search X ( $h = 25$ ): $i_{0} = 25 & 7 = 1$ → DUMMY, skip, keep probing (probe 1). $perturb = 25$ : $i_{1} = (5 \cdot 1 + 1 + 25) & 7 = 31 & 7 = 7$ → Q, different key (probe 2). $perturb = 25 ≫ 5 = 0$ : $i_{2} = (5 \cdot 7 + 1 + 0) & 7 = 4$ → R, different key (probe 3). $perturb = 0$ : $i_{3} = (5 \cdot 4 + 1 + 0) & 7 = 21 & 7 = 5$ → EMPTY → not found (probe 4). Answer: X takes 4 probes. (The DUMMY at slot 1 cost us a probe — the L3.2 effect in action.)

Recall Solution L4.2

A resize rehashes all current keys: cost $\propto$ current size. Sizes at resize form a geometric series $1, 2, 4, \dots, m$ with $m \leq N$ . Total rehash work: $1 + 2 + 4 + \dots + m = 2 m - 1 < 2 N .$ Plus $N$ for the inserts themselves → total $< 3 N = O (N)$ . Divide by $N$ inserts: $O (1)$ amortized per insert. See Amortized Analysis and Big-O Notation.

Level 5 — Mastery

Recall Solution L5.1

Condition: $fill > \frac{2}{3} m$ . For $m = 8$ : $\frac{2}{3} \cdot 8 = 5. \overline{3}$ . The smallest integer $fill$ strictly greater is 6. So the insert that raises $fill$ from 5 to 6 triggers resize. General rule: resize on the insert making $fill = ⌊ \frac{2}{3} m ⌋ + 1.$ Check $m = 8$ : $⌊ 5.33 ⌋ + 1 = 6$ . ✓ For $m = 16$ : $⌊ 10.67 ⌋ + 1 = 11$ .

Recall Solution L5.2

$α$	$E = 1/ (1 - α)$
0.25	$1.333$
0.5	$2.0$
0.667	$3.0$
0.9	$10.0$

At $α = 0.9$ an unsuccessful search averages 10 probes — the "constant" in O(1) has ballooned. Capping at $2/3$ keeps it near 3, a good speed/memory trade. Pushing to 0.9 saves ~25% memory but triples-plus the probe count. Answer: CPython buys speed with a modest memory cost by capping $α \leq 2/3$ .

Recall Solution L5.3

Open addressing (CPython): a miss probes inside one shared array, so cost scales with $α = fill / m$ (dummies inflate it — see L3.2). Because all probes hit the same contiguous array, the CPU cache prefetches neighbours → cache-friendly.
Separate chaining (Java): a miss walks the linked list (or tree) of one bucket, so cost scales with that bucket's node count. Nodes are heap-scattered → more cache misses, but deletes need no dummy markers (just unlink). See Java HashMap Internals and Collision Resolution. Answer: CPython miss-cost tracks $fill$ ; Java tracks per-bucket length; open addressing wins on locality by staying in one array.

Recall Feynman recap

Every problem above is the same locker-wall from the parent note: the machine (hash) picks a start locker; if taken, a fixed jump rule (the perturbed probe) sends you to the next; a removed bag leaves a "was-here" sticky note (DUMMY) you must walk past; and when the wall gets two-thirds full the janitor builds a bigger wall and re-files everything (resize + rehash).