Python dict and set internals — Hinglish notes

3.3.9 · Coding › Hashing

WHY yeh design exist karta hai?

WHAT actually store hota hai

HOW lookup kaam karta hai (derivation from scratch)

Hum probe formula dump nahin karte — aaiye ise build karte hain.

Step 1 — Hash ko starting slot par map karo. Table mein $m$ slots hain, aur CPython mein $m$ hamesha power of two hota hai. Ek possibly-huge hash ko valid index mein badhane ke liye hum low bits lete hain: $i_{0} = h & (m - 1)$ Yeh step kyun? Jab $m = 2^{k}$ ho, h & (m-1) lowest $k$ bits rakhta hai, jo h % m ke barabar hai lekin faster hai — aur yeh $[0, m - 1]$ mein ek value deta hai, ek legal index.

Step 2 — Agar slot doosri key se occupied hai toh probe karo. Ek naive probe linear probing $i_{n + 1} = (i_{n} + 1) mod m$ hai. Problem: yeh lambi runs banata hai (clustering). CPython ek perturbed probe use karta hai jo hash ke high bits mix karta hai taaki same low bits wali different keys jaldi diverge hon: $i_{n + 1} = (5 i_{n} + 1 + perturb) & (m - 1), perturb ≫ = 5$ Yeh step kyun? h ke high bits (jo perturb mein carry hote hain) i_0 mein sirf & (m-1) mask se enter hote hain, toh pehle woh ignore hote hain. Unhe successive probes par feed karna guarantee karta hai ki sequence eventually har slot visit kare, toh koi item kabhi lost nahin hoti.

Step 3 — Stop conditions. Har probed slot par:

EMPTY → key present nahin (stop). Insert ke liye, yahan rakh do.
Same hash AND == true → mil gaya.
Different key → probing jaari rakho.

HOW deletion kaam karta hai (dummy trick)

Worked examples

Worked example Example 2 — WHY

1, 1.0, aur True keys ke roop mein collide karte hain

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

Ek hi entry kyun? 1 == 1.0 == True True hai, aur hash(1)==hash(1.0)==hash(True)==1. Table unhe same key samajhta hai; baad ki writes overwrite kar deti hain. Pehla key object rehta hai, value last-write-wins hoti hai.

Worked example Example 3 — Resize 2/3 line ke baad trigger hoti hai

Resize ka threshold: fill $> \frac{2}{3} m$ . $m = 8$ ke liye woh $\frac{2}{3} \cdot 8 = 5.33$ hai, toh resize tab fire hoti hai jab fill 6 reach kare (yaani $α = 6/8 = 0.75 > 2/3$ ). $n = 5$ par, $α = 5/8 = 0.625 < 2/3$ hai — abhi resize nahin. Yeh kyun matter karta hai: ise eyeball mat karo — bilkul $\frac{2}{3} m$ se compare karo. Note karo fill active entries plus dummies count karta hai, toh 5 active keys + 1 dummy = fill 6 bhi trigger karta. Resize par, CPython next power of two tak grow karta hai jo itna bada ho (yahan 16) aur har key ko rehash karta hai. Rehash kyun? Index formula h & (m-1) $m$ par depend karta hai; $m$ badlo aur har key ka slot badal jaata hai. O(n) rehash ke bawajood O(1) amortized kyun? $m$ se $2 m$ tak resize sirf $\sim m$ inserts ke baad hoti hai, toh O(n) cost n operations mein spread ho jaati hai → O(1) amortized.

Common mistakes (steel-manned)

Recall Feynman: ek 12-saal-ke bachche ko explain karo

Imagine karo ek wall of numbered lockers. Apna bag store karne ke liye aap randomly locker nahin chunte — aap apna naam ek chhoti machine se guzaarte ho jo ek locker number nikaalti hai. Agli baar jab aap apna bag chahte ho, aap apna naam usi machine se guzaarte ho, wohi number milta hai, aur seedha us locker par jaate ho. Fast! Kabhi kabhi do logon ko same number milta hai (ek "clash"); tab ek fixed rule hai ("is special tarike se agla try karo") taaki sabko apna samaan mile. Jab lockers zyada crowded ho jaayein, sab ko ek badi wall par shift karte hain taaki searching fast rahe.

Flashcards

CPython dict/set kaunsi collision strategy use karta hai?

Open addressing (ek array ke andar probing), separate chaining nahin.

Hash h, table size m (power of two) ke liye pehla slot index kya hai?

i0 = h & (m - 1), h % m ke barabar lekin faster.

CPython ka perturbed probe recurrence kya hai?

i = (5*i + 1 + perturb) & (m-1); perturb >>= 5 har step mein, high bits mix karta hai.

Hash ke high bits probe sequence mein kyun feed karte hain?

Starting index sirf low bits use karta hai; high bits ensure karte hain ki equal low bits wali keys diverge hon aur har slot eventually visit ho.

CPython resize kon sa count aur threshold par trigger karta hai?

Jab fill > (2/3)*m ho, jahan fill = active entries PLUS DUMMY (deleted) slots.

Kya α = 5/8 m=8 par resize trigger karne ke liye kaafi hai?

Nahin — 5/8 = 0.625 < 2/3 ≈ 0.667; resize ke liye fill ≥ 6 chahiye (kyunki (2/3)*8 = 5.33).

Unsuccessful open-addressing search ke liye expected probes kitne hain?

1/(1-α); α=2/3 par woh ~3 probes hai.

Deletion DUMMY kyun mark hota hai EMPTY kyun nahin?

EMPTY probe chains ko prematurely terminate kar deta, chain mein aage stored keys hide kar deta; DUMMY chains intact rakhta hai, insert par reusable hai, aur fill mein count hota hai.

Dummies ko fill mein kyun count karte hain?

Woh live keys hue bina probe chains lambi karte hain, toh unhe count karna lookups degrade hone se pehle cleansing resize force karta hai.

List dict key kyun nahin ho sakti?

Lists mutable hain → unhashable; changing hash key ko unfindable bana deta.

d[1], d[1.0], d[True] ek entry mein kyun collapse ho jaate hain?

1 1.0 True aur unke hashes sab 1 hain, toh table unhe same key treat karta hai.

Dict ka insertion order hash slots mein stored hai?

Nahin — order ek separate compact entry/index array mein rakha jaata hai; sets order bilkul preserve nahin karte.

O(n) resize ke bawajood n inserts ki amortized cost kya hai?

O(1) amortized; resize sirf ~m inserts ke baad hoti hai, apni O(n) cost spread karti hai.

Equality aur hashing ko link karne ki requirement kya hai?

a b ka matlab hona chahiye hash(a) hash(b).

Connections

Hash Functions — woh integer hash(key) produce karta hai.
Collision Resolution — open addressing vs separate chaining trade-offs.
Load Factor and Rehashing — fill > 2/3 m resize rule.
Amortized Analysis — doubling O(1) amortized inserts kyun deta hai.
Big-O Notation — hash lookups ke liye average vs worst-case.
Immutability and Hashability — keys immutable kyun honi chahiye.
Java HashMap Internals — contrast: chaining + treeify.