Python dict and set internals

HOW a lookup works (derivation from scratch)

We never dump the probe formula — let's build it.

Step 1 — Map a hash to a starting slot. The table has $m$ slots, and in CPython $m$ is always a power of two. To turn a possibly-huge hash into a valid index we take the low bits: $i_0 = h \;\&\; (m-1)$ Why this step? When $m=2^k$ , h & (m-1) keeps the lowest $k$ bits, which equals h % m but is faster — and it gives a value in $[0, m-1]$ , a legal index.

Step 2 — Probe if the slot is occupied by a different key. A naive probe is linear probing $i_{n+1} = (i_n + 1) \bmod m$ . Problem: it makes long runs (clustering). CPython uses a perturbed probe that mixes in the high bits of the hash so different keys with the same low bits diverge quickly: $i_{n+1} = (5 i_n + 1 + \text{perturb}) \;\&\; (m-1), \qquad \text{perturb} \gg\!= 5$ Why this step? The high bits of h (carried in perturb) only enter i_0 through the & (m-1) mask, so they are ignored at first. Feeding them in over successive probes guarantees the sequence eventually visits every slot, so an item is never lost.

Step 3 — Stop conditions. At each probed slot:

EMPTY → key is not present (stop). For insert, place it here.
Same hash AND == true → found it.
Different key → keep probing.

HOW deletion works (the dummy trick)

Worked examples

Worked example Example 1 — Insert into a tiny table (

$m=8$ ) Suppose hash(k1)=18, hash(k2)=10.

$i_0(k1) = 18 \;\&\; 7 = 2$ . Slot 2 empty → place k1 at slot 2. Why? $18 = 10010_2$ , low 3 bits $= 010 = 2$ .
$i_0(k2) = 10 \;\&\; 7 = 2$ . Collision! Slot 2 holds k1. Why a collision? $10 = 1010_2$ , low 3 bits also $= 010 = 2$ . Same low bits → same start.
Probe: $i_1 = (5\cdot 2 + 1 + \text{perturb}) \;\&\; 7$ with perturb $=10$ : $(10+1+10)\&7 = 21\&7 = 5$ . Slot 5 empty → place k2 at slot 5. Why move to 5 not 3? The perturbed step uses high bits, scattering the key.

Worked example Example 2 — Why

1, 1.0, and True collide as keys

d = {}
d[1] = "a"; d[1.0] = "b"; d[True] = "c"
print(d)            # {1: 'c'}

Why one entry? 1 == 1.0 == True is True, and hash(1)==hash(1.0)==hash(True)==1. The table sees them as the same key; later writes overwrite. The first key object stays, the value is last-write-wins.

Worked example Example 3 — Resize triggers past the 2/3 line

Threshold for resize: fill $> \tfrac{2}{3}m$ . For $m=8$ that is $\tfrac{2}{3}\cdot 8 = 5.33$ , so resize fires once fill reaches 6 (i.e. $\alpha = 6/8 = 0.75 > 2/3$ ). At $n=5$ , $\alpha = 5/8 = 0.625 < 2/3$ — no resize yet. Why this matters: don't eyeball it — compare against $\tfrac{2}{3}m$ exactly. Note fill counts active entries plus dummies, so 5 active keys + 1 dummy = fill 6 would also trigger. On resize, CPython grows to the next power of two big enough (here 16) and rehashes every key. Why rehash? The index formula h & (m-1) depends on $m$ ; change $m$ and every key's slot changes. Why O(1) amortized despite O(n) rehash? A resize from $m$ to $2m$ happens only after $\sim m$ inserts, so the O(n) cost is spread over n operations → O(1) amortized.

Common mistakes (steel-manned)

Recall Feynman: explain to a 12-year-old

Imagine a wall of numbered lockers. To store your bag you don't pick a locker randomly — you run your name through a little machine that spits out a locker number. Next time you want your bag, you run your name through the same machine, get the same number, and go straight to that locker. Fast! Sometimes two people get the same number (a "clash"); then there's a fixed rule ("try the next one this special way") so everyone still finds their stuff. When the lockers get too crowded, we move everyone to a bigger wall so searching stays quick.

Flashcards

What collision strategy does CPython dict/set use?

Open addressing (probing inside one array), not separate chaining.

First slot index for hash h, table size m (power of two)?

i0 = h & (m - 1), equivalent to h % m but faster.

CPython's perturbed probe recurrence?

i = (5*i + 1 + perturb) & (m-1); perturb >>= 5 each step, mixing in high bits.

Why feed high bits of the hash into the probe sequence?

The initial index only uses low bits; high bits ensure keys with equal low bits diverge and every slot is eventually visited.

What count and threshold trigger a CPython resize?

When fill > (2/3)*m, where fill = active entries PLUS DUMMY (deleted) slots.

Is α = 5/8 enough to trigger resize at m=8?

No — 5/8 = 0.625 < 2/3 ≈ 0.667; resize needs fill ≥ 6 (since (2/3)*8 = 5.33).

Expected probes for unsuccessful open-addressing search?

1/(1-α); at α=2/3 that's ~3 probes.

Why is deletion marked DUMMY not EMPTY?

EMPTY would prematurely terminate probe chains, hiding keys stored further along; DUMMY keeps chains intact, is reusable on insert, and is counted in fill.

Why are dummies counted in fill?

They lengthen probe chains without being live keys, so counting them forces a cleansing resize before lookups degrade.

Why can't a list be a dict key?

Lists are mutable → unhashable; a changing hash would make the key unfindable.

Why do d[1], d[1.0], d[True] collapse to one entry?

1 1.0 True and their hashes are all 1, so the table treats them as the same key.

Is dict's insertion order stored in the hash slots?

No — order is kept in a separate compact entry/index array; sets don't preserve order at all.

Amortized cost of n inserts despite O(n) resize?

O(1) amortized; a resize occurs only after ~m inserts, spreading its O(n) cost.

Requirement linking equality and hashing?

a b must imply hash(a) hash(b).

Connections

Hash Functions — what produces the integer hash(key).
Collision Resolution — open addressing vs separate chaining trade-offs.
Load Factor and Rehashing — the fill > 2/3 m resize rule.
Amortized Analysis — why doubling gives O(1) amortized inserts.
Big-O Notation — average vs worst-case for hash lookups.
Immutability and Hashability — why keys must be immutable.
Java HashMap Internals — contrast: chaining + treeify.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Socho ek dict ek lockers ki line hai — ek array jisme fixed number of "slots" hain. Jab tum d[key] = value karte ho, Python pehle hash(key) nikalta hai (ek bada integer), phir h & (m-1) se ek slot index banata hai jahan se start karna hai. Yahi trick lookup ko O(1) banati hai: agle baar same key ka same hash, same index, seedha pohonch gaye. List me x in lst poora scan karta hai (O(n)), dict me nahi.

Problem tab aati hai jab do keys ka same starting slot ban jaye — isko collision bolte hain. CPython ka solution open addressing hai: agle slots ko ek special perturbed formula (5*i + 1 + perturb) & (m-1) se try karta hai, aur perturb me hash ke high bits daal ke keys ko scatter karta hai taaki clustering na ho aur har key milti rahe.

Resize ka rule dhyaan se: jab fill > (2/3)*m ho tab table bada hota hai. Important — fill sirf active keys nahi, active entries + DUMMY (deleted) slots dono count karta hai. Isliye agar bahut delete karoge to dummies bhi fill badha denge aur resize trigger ho jayega (jo dummies clean kar deta hai). Ek galti se bacho: $5/8 = 0.625$ jo $2/3 \approx 0.667$ se chhota hai, to $m=8, n=5$ par resize nahi hota; threshold $(2/3)\cdot 8 = 5.33$ hai, yaani fill 6 pe trigger. Resize ke time har key rehash hoti hai kyunki index m par depend karta hai — yeh kabhi-kabhi O(n) kaam hai, isliye average O(1) amortized rehta hai.

Exam/interview ka 80/20: keys immutable/hashable honi chahiye (list key nahi ban sakti), 1 == 1.0 == True same key bante hain, average O(1) but worst case O(n), aur set order guarantee nahi karta jabki dict insertion order rakhta hai (par alag order-array me, hash slots me nahi). Bas itna solid ho gaya to topic clear.

WHY does this design exist?

WHAT is actually stored

HOW a lookup works (derivation from scratch)

HOW deletion works (the dummy trick)

Worked examples

Common mistakes (steel-manned)

Flashcards

Connections

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Hashing

Connections