Python dict and set internals: Worked examples — Coding deep dive

This is the "hit every cell" drill for Python dict and set internals. We are not learning new theory here — we are pushing the machinery through every kind of input it can meet: normal inserts, collisions, deletions, resizes, degenerate keys, and the exam-style traps.

If any symbol below feels unfamiliar, that means the parent note built it — go back and rebuild it there first. Here we use the tools.

Symbols we will lean on (built here, on this page)

Intuition WHY the magic constants

$5 i + 1$ and >>= 5?

The $5 i + 1$ part with $& (m - 1)$ is a linear congruential recurrence modulo $2^{k}$ . A number-theory fact: $x \mapsto (5 x + 1) mod 2^{k}$ is a full-cycle permutation — starting anywhere it visits all $2^{k}$ slots before repeating (because $5 - 1 = 4$ is divisible by every prime factor of $2^{k}$ , namely 2, and $5 \cdot 1 + 1$ keeps it odd-stepped). So an item is never lost: the probe sequence is guaranteed to reach an EMPTY slot if one exists.
The perturb part injects the high bits of the hash that the start mask discarded. Two keys with identical low bits (same $i_{0}$ ) but different high bits diverge within a few probes instead of walking the same long chain. Shifting perturb >>= 5 feeds those high bits in gradually; once perturb reaches 0 the pure $5 i + 1$ full-cycle guarantee takes over.

The scenario matrix

Every problem this topic throws at you falls into one of these cells. The worked examples afterwards are each labelled with the cell they cover.

#	Cell class	What makes it special	Covered by
A	Clean insert, no collision	first-try slot is EMPTY	Ex 1
B	Collision + perturbed probe	two keys share low bits	Ex 2
C	Delete → DUMMY → probe survives	chain must not break	Ex 3
D	Reuse a DUMMY on insert	insert lands on a deleted slot	Ex 4
E	Resize boundary (the 2/3 line)	count `fill` = active + dummy	Ex 5
F	Degenerate keys — `1 == 1.0 == True`	equal keys collapse	Ex 6
G	Unhashable / zero-degenerate input	`hash([])`, empty dict	Ex 7
H	Limiting behaviour — $α \to 1$	probe count blows up	Ex 8
I	Real-world word problem	word-frequency counter	Ex 9
J	Exam twist — worst-case adversary	all keys same slot	Ex 10
K	`set`-specific behaviour	no values, no order guarantee	Ex 11

Ex 1 — Clean insert (Cell A)

Ex 2 — Collision and the perturbed probe (Cell B)

The figure below is the state after both inserts: two keys aimed at slot 3, and the amber arrow traces b's perturbed path escaping to slot 0. Read it as the answer to this example — the text just narrates the arrow.

Figure s01 — Ex 2 (Cell B). An 8-slot blueprint table. Key a (cyan filled) sits at its start slot 3. Key b (cyan filled) also hashes to start slot 3 but collides, so the amber curved arrow arcs from slot 3 over the busy cells to land in EMPTY slot 0 — the visual proof that the perturbed probe carries a colliding key to a fresh slot without losing it.

Worked example Two keys, same low bits

$m = 8$ . hash(a) = 3, hash(b) = 11. Insert a then b.

Forecast: both start at slot 3 — where does b end up?

Place a. $i_{0} (a) = 3 & 7 = 3$ . Slot 3 empty → a at slot 3.
Start b. $i_{0} (b) = 11 & 7 = 3$ . Collision — slot 3 holds a. Why a collision? $11 = 101 1_{2}$ , low 3 bits $= 011 = 3$ , same as a. Same low bits ⇒ same start.
Perturb setup. perturb = hash(b) = 11. Why this step? perturb carries the high bits the mask threw away (Symbols section); feeding them in makes b diverge from a instead of sharing its chain.
First probe. $i_{1} = (5 \cdot 3 + 1 + 11) & 7 = 27 & 7 = 3$ Slot 3 still occupied by a → keep probing. Now update perturb: $11 ≫ 5 = 0$ . Why this step? We are applying the perturbed-probe recurrence $i_{n + 1} = (5 i_{n} + 1 + perturb) & (m - 1)$ defined in the Symbols section. The $5 i_{n} + 1$ part is the full-cycle LCG that guarantees we eventually reach an EMPTY slot; the +perturb term injects the high bits of hash(b) so b scatters away from a. The perturb >>= 5 then shifts in the next batch of high bits for the following probe — here it becomes 0, so from now on the pure $5 i + 1$ cycle drives the search.
Second probe. $i_{2} = (5 \cdot 3 + 1 + 0) & 7 = 16 & 7 = 0$ Slot 0 empty → b at slot 0.

Verify: $27 & 7 = 3$ (still busy), $16 & 7 = 0$ (landed). b reached a distinct slot, so no key was lost. ✓

Ex 3 — Delete makes a DUMMY; the chain survives (Cell C)

The figure shows the danger: a is gone but b still lives further down the chain, so the deleted slot must stay "walk-through," not "stop."

Figure s02 — Ex 3 (Cell C). Same 8-slot table after a at slot 3 is deleted: slot 3 is now amber and labelled DUMMY (a tombstone), while b still lives at slot 0. The cyan arc shows a lookup for b starting at slot 3, refusing to stop on the DUMMY, and probing onward to reach b — the key intuition being that a naive EMPTY here would have cut the chain and made b "disappear."

Worked example Delete the middle of a probe chain

Continue Ex 2: slot 3 = a, slot 0 = b. They form a chain 3 → 0 for keys hashing to 3. Now delete a.

Forecast: if we set slot 3 to EMPTY, can we still find b?

Naive (wrong) delete: slot 3 → EMPTY. Then look up b: start at slot 3, see EMPTY, report "not found." b is lost even though it sits at slot 0. Why it fails? The lookup's stop rule says EMPTY ⇒ not present, so it never reaches slot 0.
Correct delete: slot 3 → DUMMY. Why this step? DUMMY means "occupied for searching, free for inserting." Probes pass through it.
Look up b again: start slot 3 = DUMMY → don't stop, keep probing → $i_{1} = 0$ = b. Found. ✓

Verify: With DUMMY at 3, the probe sequence for b is unchanged ( $3 \to 0$ ), so b is still reachable. Active entries $n = 1$ , but fill $= 2$ (one live b + one dummy). ✓

Ex 4 — Reusing a DUMMY on insert (Cell D)

Worked example Insert into a table that has a tombstone

Table from Ex 3: slot 3 = DUMMY, slot 0 = b. Insert c with hash(c) = 3.

Forecast: does c go into the free DUMMY at slot 3, or push onward?

Start. $i_{0} (c) = 3 & 7 = 3$ . Slot 3 is DUMMY.
Remember the DUMMY, keep scanning. Insertion must first confirm c isn't already present further down the chain, so it records slot 3 as a reuse candidate and probes on. Why this step? If c already lived at slot 0 we must not create a duplicate — correctness beats speed.
Probe on. $i_{1} = (5 \cdot 3 + 1 + 3) & 7 = 19 & 7 = 3$ (still DUMMY, but we already noted it); perturb $3 ≫ 5 = 0$ ; $i_{2} = (5 \cdot 3 + 1 + 0) & 7 = 0$ = b — different key, keep going; $i_{3} = (5 \cdot 0 + 1 + 0) & 7 = 1$ = EMPTY. Why continue past b? b \ne c, so it's not a match; only EMPTY confirms c is new.
EMPTY confirms c is new → place c in the remembered DUMMY at slot 3, not slot 1. Why reuse the DUMMY? It shortens future chains and reclaims dead space.

Verify: $19 & 7 = 3$ , then slot 0 (b), then slot 1 (EMPTY). c reuses slot 3. Now fill $= 2$ (b, c) — the dummy became live, so fill did not grow. ✓

Ex 5 — The resize boundary (Cell E)

The bar chart makes the 2/3 line literal: two bars stay under it, the third pokes over and triggers the resize.

Figure s03 — Ex 5 (Cell E). Three cyan/amber bars show fill = 4, 5, 6 for an $m = 8$ table, plotted against the amber dashed resize line at $\frac{2}{3} \cdot 8 = 5.33$ . The fill=4 and fill=5 bars stay under the line (cyan, "no resize"); the fill=6 bar pokes above it (amber, "RESIZE"). The intuition: the trigger is a strict crossing of the $\frac{2}{3} m$ line, and fill counts dummies too.

Worked example Does inserting the 6th key resize an

$m = 8$ table? Threshold: resize when fill $> \frac{2}{3} m$ , where fill $= n + (dummies)$ and $α = fill / m$ (Symbols section).

Forecast: is $5/8$ over the line? Is $6/8$ ?

Compute the line. $\frac{2}{3} \cdot 8 = \frac{16}{3} = 5.333 \dots$ Why this step? Compare fill against $\frac{2}{3} m$ exactly — never eyeball it.
At fill = 5: $5 < 5.333$ ⇒ no resize. Load factor $α = 5/8 = 0.625 < 2/3$ . ✓
At fill = 6: $6 > 5.333$ ⇒ resize fires. $α = 6/8 = 0.75 > 2/3$ .
Dummy variant: 4 live keys + 2 dummies also gives fill = 6 → resize fires even though $n = 4$ . Why? fill counts active plus DUMMY. The resize purges dummies.
New size: next power of two large enough — here $m = 16$ — then rehash every key with the new mask $& 15$ . Why rehash? Slot depends on $m$ via $h & (m - 1)$ ; change $m$ , every slot moves.

Verify: $\frac{2}{3} \cdot 8 = \frac{16}{3}$ ; $5 < \frac{16}{3}$ (no), $6 > \frac{16}{3}$ (yes). $6/8 = 0.75$ , $5/8 = 0.625$ . ✓

Ex 6 — Degenerate equal keys collapse (Cell F)

Worked example

1, 1.0, True are one key

d = {}
d[1] = "a"; d[1.0] = "b"; d[True] = "c"

Forecast: how many entries end up in d? Which value survives?

Check equality. 1 == 1.0 is True, 1 == True is True. Why this matters? The table's match rule is "same hash and ==."
Check hashes. hash(1) == hash(1.0) == hash(True) == 1. Why the contract? Equal objects must share a hash, or the table couldn't find them.
All three target the same slot and match → they are the same key. Writes overwrite the value; the first key object (1) stays.

Verify: len(d) == 1, d[1] == "c" (last write wins). ✓

Ex 7 — Unhashable and zero/degenerate inputs (Cell G)

Worked example Empty structures and forbidden keys

Forecast: which of these raise, and which just return trivially?

hash(()) — empty tuple is immutable → hashable. Returns a fixed integer (not an error). Why? A tuple's hash is fixed if its contents are hashable; empty ⇒ constant.
hash([]) — raises TypeError: unhashable type: 'list'. Why? Lists are mutable; a changing hash would strand the key. See Immutability and Hashability.
len({}) — empty dict, no slots active → 0. 3 in set() → False with zero probes. Why? Degenerate empty containers are valid — every lookup immediately hits EMPTY.
hash((1, [2])) — raises TypeError: the tuple contains a list, so it's unhashable even though the tuple itself is immutable. Why? Hashability is recursive — every element must be hashable.

Verify: len({}) == 0; 3 in set() is False; () hashes without error. ✓

Ex 8 — Limiting behaviour as $α \to 1$ (Cell H)

The curve shows the whole story: flat and cheap up to the CPython cap, then a wall as $α \to 1$ .

Figure s04 — Ex 8 (Cell H). The cyan curve plots expected probes $E = 1/ (1 - α)$ against load factor $α$ from 0 to nearly 1. Amber dots mark $α = 2/3 (E = 3)$ , $α = 0.9 (E = 10)$ , and $α = 0.99 (E = 100)$ ; the dotted white vertical line is the CPython $2/3$ cap. The intuition the picture carries: cost stays flat and small left of the cap, then rises like a wall toward the right — which is exactly why resizing must keep $α$ bounded.

Worked example Probe count near a full table

Expected probes for an unsuccessful search: $E \approx \frac{1}{1 - α}$ , with $α = fill / m$ .

Forecast: how fast does $E$ grow from $α = 2/3$ to $α = 0.99$ ?

Derive the formula first. Under uniform hashing each probed slot is occupied with probability $\approx α$ , independently. To need $\geq k$ probes, the first $k - 1$ slots must all be full: probability $α^{k - 1}$ . So the expected count is $E = \sum_{k \geq 1} α^{k - 1} = 1 + α + α^{2} + \dots$ Why this step? $E$ is the expected number of probes; "each extra probe happens only if the previous slots were all full" turns the average into a sum of the tail probabilities $α^{k - 1}$ .
Sum the geometric series. This is a geometric series with first term 1 and common ratio $α$ . Because $0 \leq α < 1$ the ratio is below 1, so it converges to $E = \frac{1}{1 - α} .$ Why this step? A geometric series $1 + r + r^{2} + \dots$ with $∣ r ∣ < 1$ sums to $\frac{1}{1 - r}$ (multiply the sum $S$ by $r$ , subtract: $S - r S = 1$ , so $S = 1/ (1 - r)$ ). Here $r = α < 1$ is guaranteed because resizing keeps $α \leq 2/3$ — which is exactly why the closed form is legitimate to use.
At the CPython cap $α = 2/3$ : $E = \frac{1}{1 - 2/3} = 3$ . Why this is fine? Constant 3 ⇒ the "O(1)" claim holds because resizing keeps $α \leq 2/3$ .
At $α = 0.9$ : $E = \frac{1}{0.1} = 10$ .
At $α = 0.99$ : $E = \frac{1}{0.01} = 100$ .
Limit $α \to 1^{-}$ : $E \to \infty$ . The table degenerates toward a linear scan. Why? Almost every slot is full, so probes almost never find EMPTY quickly.

Verify: $1/ (1 - 2/3) = 3$ , $1/ (1 - 0.9) = 10$ , $1/ (1 - 0.99) = 100$ . Monotone increasing, diverges at 1. ✓

Ex 9 — Real-world word problem (Cell I)

Worked example Word-frequency counter and its amortized cost

Count word frequencies in a stream of n = 1000 words using a dict. Assume 500 distinct words.

Forecast: what's the total time cost, and how many resizes happen?

Each word: one lookup + one update, average O(1) probes. Why average O(1)? Resizing bounds $α = fill / m \leq 2/3$ , so $E \leq 3$ probes each.
Find the final table size. We need $\frac{2}{3} m > 500$ (so the 500 distinct keys fit under the cap). Check powers of two: $\frac{2}{3} \cdot 512 = 341.3 < 500$ (too small); $\frac{2}{3} \cdot 1024 = 682.7 > 500$ (fits). So the table ends at $m = 1024$ .
Total rehash work across all resizes. Resizes copy the table at sizes $8, 16, 32, \dots, 512$ (the size before each doubling up to 1024). Their sum is $8 + 16 + \dots + 512 = 8 (2^{0} + 2^{1} + \dots + 2^{6}) = 8 (2^{7} - 1) = 8 \cdot 127 = 1016.$ Why is this a geometric sum, and why $< 2 m$ ? Because sizes double, the series is geometric with ratio 2; the identity $2^{0} + \dots + 2^{6} = 2^{7} - 1$ means the whole sum is less than the next term $2^{7}$ . Multiplying by 8: $1016 < 8 \cdot 128 = 1024 = m$ . So all past rehash work together is bounded by the final table size — the doubling makes earlier copies negligible.
Amortized per operation: $\frac{O ( n ) + O ( m )}{n} = O (1)$ . Why amortized O(1)? The rare O(n) resize is paid for by the ~n cheap inserts before it — see Amortized Analysis and Big-O Notation.

Verify: $\frac{2}{3} \cdot 512 = \frac{1024}{3} < 500$ ; $\frac{2}{3} \cdot 1024 = \frac{2048}{3} > 500$ . Sum $8 + 16 + 32 + 64 + 128 + 256 + 512 = 1016 < 1024$ . ✓

Ex 10 — Exam twist: the adversary (Cell J)

Worked example All keys hash to the same slot

An attacker sends $n$ keys all with hash(k_i) & (m-1) = 0 (same low bits, distinct high bits). Worst-case lookup cost?

Forecast: is it still O(1)? What breaks the average-case guarantee?

Every key starts at slot 0. Each insert collides and probes down a single long chain. Why? Identical starting slot ⇒ the perturbed sequence lengthens per key.
Lookup of the last key walks the whole chain: O(n) probes. Why? The uniform-hashing assumption behind $E = 1/ (1 - α)$ is violated — hashes are not spread out.
Resizing doesn't save you. Doubling $m$ adds one more low bit, but the attacker chose keys agreeing on all used low bits, so they still collide after rehash. Why? The pathology is in the hash distribution, not the load factor. See Hash Functions.
Big-O verdict: worst case O(n) per operation, contradicting the naive "always O(1)." Why we still say O(1)? Because it's the average under uniform hashing — see Big-O Notation.

Verify: For $n$ keys all in one chain, the $n$ -th lookup touches $n$ slots ⇒ cost $= n = O (n)$ , not constant. ✓

Ex 11 — `set`-specific behaviour (Cell K)

Worked example What a

set does that a dict does not

s = {3, 1, 2}
s.add(3)              # duplicate
s.discard(99)         # absent element
print(len(s))

Forecast: what is len(s)? Does s remember the order 3,1,2?

A set entry is (hash, key) only — no value. Why it matters? Same open-addressing table as dict, but each slot stores one fewer field. Membership x in s uses the identical probe machinery from Ex 1–2.
s.add(3) re-probes to slot for 3, finds an equal key already there → no new entry. Sets store each key at most once. Why? The match rule "same hash and ==" collapses duplicates exactly as in Ex 6.
s.discard(99) probes for 99, hits EMPTY (not present) → does nothing, no error. Why the degenerate case is safe? discard (unlike remove) tolerates the absent-key path — a clean "not found" from the probe.
Order: unlike dict (insertion-ordered since 3.7), a set gives no order guarantee — iteration order follows the hash slots, which scatter keys. Why? set has no compact insertion-order array; you see whatever the slot layout yields.

Verify: len(s) == 3 ({1,2,3}); the duplicate add and the absent discard both leave it at 3. ✓

Recall Self-test — one line each

Load factor definition? ::: $α = fill / m$ , where fill = active entries + dummies. Slot for hash=27, m=8? ::: $27 & 7 = 3$ . Why does the $5 i + 1$ probe reach every slot? ::: it's a full-cycle permutation mod $2^{k}$ , so it visits all $2^{k}$ slots before repeating. b with hash=11 in $m = 8$ after colliding at 3 lands where (Ex 2)? ::: slot 0. Why delete → DUMMY not EMPTY? ::: so probe chains passing through it aren't cut, losing later keys. Resize line for $m = 8$ ? ::: fill $> 16/3 = 5.333$ , i.e. fires at fill = 6. Does fill = 5 resize? ::: No — $5/8 = 0.625 < 2/3$ . Where does $E = 1/ (1 - α)$ come from? ::: geometric sum $\sum α^{k - 1}$ of "keep probing while slots are full." $E$ probes at $α = 0.99$ ? ::: $1/ (1 - 0.99) = 100$ . Successful-search probes at $α = 2/3$ ? ::: $\frac{1}{α} ln \frac{1}{1 - α} \approx 1.65$ , cheaper than a miss. Ex9 rehash sum $8 + \dots + 512$ ? ::: $1016$ , and $< m = 1024$ because sizes double. Adversary with all-same low bits ⇒ lookup cost? ::: O(n) worst case. Does a set preserve insertion order? ::: No — only dict does (since 3.7).