Visual walkthrough — Python dict and set internals

By the end we will have earned every symbol in this central formula from the parent note — the average number of boxes a not-found search touches, written as a fraction that only depends on how crowded the table is: $\frac{1}{1-\alpha }$ where $\alpha$ ("how full the table is") is defined carefully in Step 5, and the left side is read as "expected probes" once "probe" is defined in Step 4. Every symbol is earned before it is used.

---

Step 1 — What is a "slot"? A wall of numbered boxes

WHAT. We draw a row of $m=8$ boxes and give each a number underneath.

WHY. A hash table is just an array. Before we can talk about "which box a key goes in", we need a name for a box and a name for its position. That name is the index.

PICTURE. Look at the row below. The numbers $0$ through $7$ are the indices. Right now every box is EMPTY (chalk outline, nothing inside).

Where does an index come from? Not from where we want the key — from the key itself. That is Step 2.

---

Step 2 — Turn a key into a starting index with & (m-1)

WHAT. We compute the starting index: $i_0=\underset{\text{the key’s hash, any integer}}{\underbrace{h}}\&\underset{\text{a mask of the lowest bits}}{\underbrace{(m-1)}}$

• $h$ — the raw hash integer of the key.
• $\&$ — bitwise AND: keep a bit only where both sides have a $1$.
• $m-1$ — when $m$ is a power of two, $m-1$ in binary is all ones in the lowest bits. For $m=8$, $m-1=7=111_2$. AND-ing with it keeps exactly the lowest 3 bits and throws the rest away.

WHY this tool and not %? We could write $h\mathrm{mod}m$ (the remainder after dividing by $m$). For a power-of-two $m$, h & (m-1) gives the identical answer but is one cheap CPU instruction instead of a division. That is the only reason CPython insists $m$ is a power of two.

PICTURE. Take $h=18$. In binary $18=10010_2$. The mask $7=00111_2$ keeps only the last three bits $\to 010_2=2$. So key with hash $18$ starts at box $2$.

If box $2$ is empty, we drop the key there and we are done in one touch. The trouble begins when someone else also lands on box $2$.

---

Step 3 — A collision: two keys, one starting box

WHAT. Add a second key with hash $10$. Its low three bits: $10=1010_2$, keep last three $\to 010_2=2$. Same box as the first key.

WHY it happens. The mask only looked at the low bits. Two hashes that agree on their low bits ($18$ ends in $010$, $10$ ends in $010$) collide even though their high bits differ. So we need a rule for "box $2$ is taken — now where?"

PICTURE. Box $2$ is already FULL (first key, blue). The second key (pink) arrives, sees box $2$ occupied by a different key, and must go looking elsewhere. The red arrow is the collision.

---

Step 4 — Probing: the perturbed jump that visits every box

Before the formula, two pieces of programmer notation used inside it:

WHAT. CPython's next-index rule is: $i_{n+1}=(\underset{\text{scatter the current index}}{\underbrace{5i_n}}+\underset{\text{never sit still}}{\underbrace{1}}+\underset{\text{inject the high bits}}{\underbrace{\text{perturb}}})\&(m-1),\underset{\text{feed next high bits}}{\underbrace{\text{perturb}\gg =5}}$

Term by term:

• $i_n$ — the box we just found occupied.
• $5i_n+1$ — a cheap mixing step; multiplying by $5$ and adding $1$ walks around the boxes in a scattered (non-adjacent) order, so keys don't pile up in one run.
• $\text{perturb}$ — starts equal to the full hash $h$. It carries the high bits the mask threw away in Step 2.
• $\text{perturb}\gg =5$ — after each probe, right-shift perturb by 5 bits (integer-divide it by $32$), feeding fresh high bits into the next jump. Eventually perturb becomes $0$ and the pure $5i+1$ walk takes over.

WHY this tool and not linear probing? The simple rule $i_{n+1}=(i_n+1)$ (walk to the next box) causes clustering: full boxes clump into long runs, and every new collision in that run has to walk the whole run. The perturbed rule mixes in the discarded high bits, so two keys that shared low bits (like $18$ and $10$) diverge immediately on the very next jump.

PICTURE. Continue Example 1 from the parent. Second key: $i_0=2$, occupied. With $\text{perturb}=10$: $i_1=(5\cdot 2+1+10)\&7=21\&7=5.$ $21=10101_2$, low three bits $101_2=5$. Box $5$ is EMPTY $\to$ store here. The curved arrow shows the jump from $2$ to $5$, skipping $3$ and $4$ — that's the anti-clustering scatter.

---

Step 5 — What "load factor" measures, and why it is the whole story

WHAT. $\alpha$ is a single number that says "how crowded is the wall of boxes?" $\alpha =0$ is empty; $\alpha =0.9$ means 90% of boxes are taken.

WHY it is the only thing that matters for speed. When you probe, the only question that decides whether you must jump again is: "is the box I landed on occupied?" On average, the chance a random box is occupied is exactly $\alpha$. So $\alpha$ — not $n$, not $m$ alone — controls the cost. This is the hinge of the whole derivation.

PICTURE. Two walls: a sparse one ($\alpha =0.25$, lots of EMPTY, you almost never jump) and a crowded one ($\alpha =0.9$, jumps everywhere). Same math, different crowding.

---

Step 6 — Count the probes: a geometric series falls out

WHAT. We compute the expected number of boxes we touch for a search that ends at an EMPTY box — an unsuccessful (not-found) search. Let $X$ be that number of probes.

WHY a geometric series? By the uniform-hashing model each probe is an independent coin flip: with probability $\alpha$ the box is occupied (jump again), with probability $1-\alpha$ it is EMPTY (stop). "How many independent flips until the first EMPTY?" is the classic geometric question — that is why this tool, and not calculus, appears here.

The count, term by term.

• Probability we need $\ge k$ probes = the first $k-1$ boxes were all occupied. By independence (the model above), these events multiply: $P(X\ge k)={\alpha }^{k-1}$.
  • ${\alpha }^{k-1}$ — multiply $\alpha$ by itself $k-1$ times; each factor is one occupied box in a row.
• Therefore, by the identity above: $E[X]={\sum }_{k\ge 1}\underset{={\alpha }^{k-1}}{\underbrace{P(X\ge k)}}=1+\alpha +{\alpha }^2+{\alpha }^3+\cdots$

$\boxed{E[\text{probes, unsuccessful}]=\frac{1}{1-\alpha }}(\text{exact under uniform hashing})$

PICTURE. The curve $y=1/(1-\alpha )$. It is nearly flat and low for small $\alpha$, then rockets upward as $\alpha \to 1$. That vertical wall is the danger zone.

---

Step 7 — The other quadrant: cost of a successful lookup

WHAT. We want the average probes to find a key that is present. The trick: when we look up a present key, we retrace exactly the probe path we walked when we inserted it. So the cost of finding it now equals the cost of the unsuccessful search that placed it back then.

Setting up the labels (defining $i$). Suppose the table currently holds $n$ present keys, and we inserted them one after another. Label them by insertion order: key number $i$ was the $(i+1)$-th key inserted, for $i=0,1,2,\dots ,n-1$.

• $i$ — an insertion-order counter: $i=0$ is the very first key, $i=n-1$ is the most recent.
• When key $i$ was inserted, the table already held $i$ earlier keys, so its load factor at that moment was ${\alpha }_i=\frac{i}{m},$ where $i$ = keys already present and $m$ = number of boxes.

Cost of inserting key $i$. Insertion runs an unsuccessful search (it probes until EMPTY), so by Step 6 its expected probes were $\frac{1}{1-{\alpha }_i}=\frac{1}{1-\frac{i}{m}}=\frac{m}{m-i}.$

Averaging over all present keys. A successful lookup picks one of the $n$ present keys at random, so its expected cost is the average of those insertion costs — a plain arithmetic mean, sum divided by count: $E[\text{probes, successful}]=\frac{1}{n}{\sum }_{i=0}^{n-1}\frac{m}{m-i}.$

Turning the sum into $\ln$ (WHY the logarithm appears). Substitute $\alpha =n/m$ so $n=\alpha m$, and factor: $\frac{1}{n}{\sum }_{i=0}^{n-1}\frac{m}{m-i}=\frac{1}{\alpha m}{\sum }_{i=0}^{n-1}\frac{m}{m-i}=\frac{1}{\alpha }{\sum }_{i=0}^{n-1}\frac{1}{m-i}.$ The remaining sum ${\sum }_{i=0}^{n-1}\frac{1}{m-i}=\frac{1}{m}+\frac{1}{m-1}+\cdots +\frac{1}{m-n+1}$ is a stretch of the harmonic series. For large $m$ we approximate a sum of $1/x$ by the integral of $1/x$ (that is precisely the tool that converts a discrete reciprocal-sum into a closed form, because $\int \frac{dx}{x}=\ln x$): ${\sum }_{i=0}^{n-1}\frac{1}{m-i}\approx {\int }_{m-n}^m\frac{dx}{x}=\ln m-\ln (m-n)=\ln \frac{m}{m-n}=\ln \frac{1}{1-\alpha }.$ Putting the $1/\alpha$ back in front: $\boxed{E[\text{probes, successful}]\approx \frac{1}{\alpha }\ln \frac{1}{1-\alpha }}$ where $\ln$ is the natural logarithm — "to what power do you raise $e\approx 2.718$ to get this number?".

WHY it is smaller than a miss. Every present key was inserted when the table was less full than it is now, so on average a hit is found faster than a miss. Sanity-check at the cap $\alpha =2/3$: $E=\frac{1}{2/3}\ln \frac{1}{1-2/3}=\frac{3}{2}\ln 3\approx 1.5\times 1.0986\approx 1.65\text{ probes}.$ So a hit costs about 1.6 probes versus 3 for a miss — both are small constants, which is all "O(1)" needs.

PICTURE. Both curves on one axis: the successful curve (lower) always sits under the unsuccessful curve (higher), for every $\alpha$.

---

Step 8 — The edge case: cap $\alpha$ so the curve never explodes

WHAT. CPython triggers a resize the moment $\text{fill}$ crosses two-thirds of the table: $\text{fill}>\frac{2}{3}m⟹\text{resize},$ which keeps the load factor pinned at $\alpha \le \frac{2}{3}$ at all times. Feed that cap into the Step 6 miss formula: $E\le \frac{1}{1-\frac{2}{3}}=\frac{1}{\frac{1}{3}}=3.$

• $\text{fill}$ — occupied boxes (active keys plus dummies), from Step 5.
• $\frac{2}{3}m$ — the trigger line; $\frac{2}{3}$ is CPython's chosen ceiling for $\alpha$.
• The right-hand $3$ — the largest the average miss cost is ever allowed to be.

WHY this exact tool — a cap — and not a bigger table up front? Look again at Step 6's curve (redrawn below with the safe/forbidden regions shaded). The height $1/(1-\alpha )$ is flat and low on the left, then curves up and blows to infinity as $\alpha \to 1$. Picking the resize line at $\alpha =\frac{2}{3}$ keeps us on the flat part where the height is exactly $3$ — cheap — while not wasting so much memory that most boxes sit empty. A smaller cap (say $\frac{1}{4}$) would be even faster but waste memory; a larger cap (say $0.95$) would save memory but push cost toward the cliff. Two-thirds is the balance point. This is where the "O(1)" of the parent note actually comes from — it is O(1) because rehashing forbids $\alpha$ from ever reaching the steep part of the curve.

How rehashing bounds $\alpha$ over time (the sawtooth). Inserts push $\text{fill}$ up, raising $\alpha$ toward $\frac{2}{3}$. The instant it crosses, the table roughly doubles ($m\to$ next power of two), so $\alpha$ drops back to about $\frac{1}{3}$, and the climb restarts. Plotted over inserts, $\alpha$ traces a sawtooth bounded above by $\frac{2}{3}$ — never escaping to $1$.

All the edge / degenerate cases, closed one by one:

• $\alpha =0$ (empty table): $E=1/(1-0)=1$. One touch — you hit EMPTY immediately. ✓
• $\alpha \to 1$ (table nearly full): $E\to \infty$. This is forbidden by the cap — we never get here, because a resize fires at $\frac{2}{3}$.
• Dummies dominate (many deletes, few live keys): $\text{fill}$ counts dummies, so a table full of DUMMY markers still crosses $\frac{2}{3}m$ and resizes, which purges the dummies. Probe chains stay short. ✓
• All keys collide (adversarial hashes, all same low bits): the uniform-hashing assumption of Step 6 breaks, chains become length $n$, and lookup degrades to O(n). Resizing cannot fix a pathological hash — only a better hash function can. This is the true worst case, and it is why "O(1)" is an average, not a guarantee.

Recall Check the threshold arithmetic yourself

For $m=8$, does inserting the 5th key resize? ::: No. $5/8=0.625<2/3$. Resize fires at $\text{fill}=6$ since $6/8=0.75>2/3$. At $\alpha =2/3$, expected probes for a miss? ::: $1/(1-2/3)=3$. At $\alpha =2/3$, expected probes for a hit? ::: $\frac{3}{2}\ln 3\approx 1.65$. At $\alpha =0$? ::: $1$ probe.

Recall Why the O(n) rehash is still O(1) amortized

A resize from $m$ to $2m$ only happens after about $m$ inserts, so its O(n) cost is spread across those $\sim n$ operations → O(1) amortized per insert. See Amortized Analysis and Big-O Notation.

---

The one-picture summary

Everything on one board: key $\to$ hash $\to$ mask to a starting box $\to$ perturbed probe on collision $\to$ crowding measured by $\alpha$ $\to$ miss cost $1/(1-\alpha )$ (hit cost lower) $\to$ capped at $3$ by resizing.

Recall Feynman: the whole walkthrough in plain words

You have a wall of numbered lockers. To store your bag, you run your name through a machine (the hash) and it spits out a big number; you keep only the last few digits so it names a real locker. If that locker is taken by someone else, a little rule sends you jumping to another locker — and the jump mixes in the digits you'd thrown away, so two people whose names started the same don't keep bumping into each other. How many lockers you have to try depends on just one thing: how full the wall is. If a quarter are full you almost never jump; if it's nearly packed you jump forever. That "how full" number is $\alpha$, and the average tries for a bag that isn't there is $1/(1-\alpha )$; for a bag that is there it's a bit less, because it was filed when the wall was emptier. Since the janitor builds a bigger wall and re-files everyone whenever it passes two-thirds full, $\alpha$ never gets past $2/3$, so on average you open only about three lockers — no matter how many bags are stored. That "three, always" is what people mean by O(1).

---

See also: parent topic · Immutability and Hashability · Java HashMap Internals (uses chaining, not open addressing).