Foundations — Python dict and set internals

This page is the ground floor. The parent note (Python dict and set internals) throws around hash(k), h & (m-1), perturb, $\alpha$, slots, dummies, powers of two, &, and %. If any of those made you pause, this is where each one is built from nothing. Read top to bottom; every symbol is earned before it is used.

1. An array and an index — the absolute starting point

Before anything hash-related, you must be comfortable with an array and an index.

• Plain words: "give me box number $i$" is instant — the computer computes the box's memory address by simple arithmetic (start + i × box_size) and reads it. No scanning.
• The picture: a numbered strip of lockers (figure above). The label under each locker is its index.
• Why the topic needs it: the entire point of a hash table is to convert a key into one of these index numbers, so we get that instant "box number $i$" jump. Everything downstream is about which index to pick.

We will call the number of boxes $m$ (for "size of the table") throughout.

2. hash(key) — turning a thing into a number

• Plain words: it is a "name-to-number machine." You feed it "cat", it spits out something like -4038109 (some big, seemingly random integer).
• The picture: a black box with a key going in and a number coming out — see figure below.
• Why the topic needs it: an index has to be a number between $0$ and $m-1$. A key might be a string or a tuple. hash is the bridge: object → integer. (The integer is not yet a valid index — it's usually far too big or negative. Section 5 fixes that.)

Why this law? If equal keys could hash differently, they'd point at different boxes, and the table would store the same logical key twice — chaos. This law is exactly why 1, 1.0, and True collapse into one dict entry in the parent note: they are ==, so they are forced to hash the same. See Hash Functions for how these numbers are actually produced, and Immutability and Hashability for which objects are even allowed through the machine.

3. Bits and binary — because the index trick reads bits directly

CPython does not compute the index with ordinary division. It reads the bits of the hash. So we need to know what bits are.

For example $18$ in binary: $18=16+2=1\underset{8}{\underbrace{0}}\underset{4}{\underbrace{0}}\underset{2}{\underbrace{1}}\underset{1}{\underbrace{0}}=10010_2$

• Plain words: binary is just counting with only two digits instead of ten. The rightmost bit is the "ones," next is "twos," next "fours," and so on.
• The picture: the figure shows $18$ as lit/unlit switches, each labelled with its place value.
• Why the topic needs it: the index formula plucks out the low bits of the hash. To understand that, you must see a number as its bits. The "low bits" are the ones on the right (small place values).

4. Powers of two and $m-1$ — the magic mask

Here is the key observation. Take $m=8=2^3$. Then: $m-1=7=111_2$ In binary, $m-1$ is all $1$s in exactly the low $k$ bits (three $1$s here, because $8=2^3$).

• Plain words: subtracting $1$ from a power of two turns it into a solid block of low $1$s.
• The picture: $8=1000_2$, and $7=0111_2$ — the single high bit drops and the three below it all light up (shown in the next figure).
• Why the topic needs it: this block of $1$s is a mask. Combined with the & operation (next section), it slices off exactly the low $k$ bits of any number — which is what turns a giant hash into a legal index. See Load Factor and Rehashing for why $m$ grows by doubling (staying a power of two).

5. & (bitwise AND) and % (modulo) — extracting a legal index

Now the punchline that the parent note states without proof:

WHAT the picture shows / WHY it works: the mask $m-1=0\dots 0111$ has $1$s only in the low $k$ bits. Doing h & (m-1):

• every high bit of $h$ meets a $0$ in the mask → forced to $0$ (thrown away),
• every low bit of $h$ meets a $1$ in the mask → kept unchanged.

So you keep exactly the low $k$ bits — which is the remainder when dividing by $2^k$, because each discarded high bit was a multiple of $2^k$ (i.e. a multiple of $m$, so it vanishes under % m).

Worked check ($m=8$, $h=18$): $18\&7=10010_2\&00111_2=00010_2=2,18\mathrm{mod}8=2.✓$

Why prefer & over %? Same answer, but masking is a single fast CPU operation; division is slower. That's the only reason. This produces $i_0$, the first slot to try — the starting index in the parent's Step 1.

6. perturb, high bits, and >>= — spreading collisions apart

Step 5 only used the low bits. So two keys with the same low bits (like the parent's $18$ and $10$, both ending in $010$) start at the same slot — a collision. We need a way to send them to different later slots. That is what perturb is for.

• Plain words: the high bits of the hash were thrown away by the mask in Step 5. perturb is a reservoir of those thrown-away bits, and we drip them back in one probe at a time.
• Why the topic needs it: two keys sharing low bits differ in their high bits. Feeding those high bits into the probe formula makes their probe paths diverge quickly, avoiding long clumps (clustering). See Collision Resolution for the full probe machinery and Java HashMap Internals for a completely different (chaining) approach to the same problem.

You do not need to memorise the probe formula here — just know that perturb is "the high bits, saved for later," and >>= is how they're released.

7. $\alpha$, fill, m, n — the fullness dial

• Plain words: $\alpha$ is "how full the table is," between $0$ (empty) and $1$ (packed).
• The picture: a fuel gauge. CPython keeps it below the $2/3$ mark; cross it and the table resizes.
• Why the topic needs it: the average number of probes for a lookup grows like $\frac{1}{1-\alpha }$ (parent note). Keeping $\alpha \le 2/3$ keeps that constant around $3$ — that is why lookups are O(1) on average. We write $n$ for active keys only; fill may exceed $n$ because deleted "dummy" slots also count. See Load Factor and Rehashing and Amortized Analysis for why the occasional expensive resize still averages out to O(1) per operation.

The prerequisite map

Equipment checklist

Cover the right side and test yourself. If any answer is fuzzy, reread that section.

Next: build the probe sequence and deletion machinery on top of these foundations — every symbol here is now in your toolbox.