Hashing — Frame by Frame¶
এটা একটা flipbook-এর মতো করে পড়ো। প্রতিটা frame একটা operation-এর পরে table-এর অবস্থা দেখায়। আমরা ব্যবহার করছি 4টা bucket-ওয়ালা একটা ছোট্ট table আর একটা toy hash: hash(key) = sum of letter positions (a=1, b=2, ...), তারপর % 4।
Movie 1: তিনটা key insert করা (এখনো collision নেই)¶
Frame 0 — খালি table¶
Frame 1 — insert ("cab", 10)¶
"cab" → c(3)+a(1)+b(2) = 6 → 6 % 4 = 2
bucket 0: []
bucket 1: []
bucket 2: [("cab", 10)] <- landed here
bucket 3: []
items = 1, load = 0.25
Frame 2 — insert ("ad", 20)¶
"ad" → a(1)+d(4) = 5 → 5 % 4 = 1
bucket 0: []
bucket 1: [("ad", 20)] <- landed here
bucket 2: [("cab", 10)]
bucket 3: []
items = 2, load = 0.5
Frame 3 — lookup "cab"¶
"cab" → 6 → 6 % 4 = 2 → jump to bucket 2
scan chain: ("cab",10) → match on first try → return 10
work done: 1 hash + 1 jump + 1 compare. Array size irrelevant.
Movie 2: একটা collision আর chaining কীভাবে সেটা হজম করে¶
Frame 4 — insert ("be", 30) — COLLISION¶
"be" → b(2)+e(5) = 7 → 7 % 4 = 3 ... fine, but now:
"da" → d(4)+a(1) = 5 → 5 % 4 = 1 <- bucket 1 is already taken by "ad"!
insert ("da", 40):
bucket 0: []
bucket 1: [("ad", 20), ("da", 40)] <- chain grew; both keys coexist
bucket 2: [("cab", 10)]
bucket 3: [("be", 30)]
items = 4, load = 1.0
Frame 5 — lookup "da" (chain ধরে হাঁটা)¶
"da" → 5 % 4 = 1 → bucket 1
scan chain:
("ad", 20) key "ad" == "da"? no → next
("da", 40) key "da" == "da"? yes → return 40
Collisions cost a couple of extra compares, not a rescan of everything.
Frame 6 — lookup "zz" (একটা miss)¶
"zz" → z(26)+z(26) = 52 → 52 % 4 = 0 → bucket 0
bucket 0 is [] → key absent → raise KeyError / return default
A miss is also O(1): one empty bucket proves absence.
Movie 3: load factor একটা resize-এ বাধ্য করে¶
Load এখন 1.0 — chain তৈরি হচ্ছে। আসল table-গুলো প্রায় 0.7-এ resize করে। চলো 8 bucket-এ resize করি আর প্রতিটা key rehash করি (% 8 হলে উত্তরগুলো বদলে যায়!)।
Frame 7 — 8 bucket-এ resize করার পর¶
"cab" → 6 % 8 = 6 (was bucket 2, now 6)
"ad" → 5 % 8 = 5 (was bucket 1, now 5)
"da" → 5 % 8 = 5 (still collides with "ad" — same sum)
"be" → 7 % 8 = 7
bucket 0: []
bucket 1: []
bucket 2: []
bucket 3: []
bucket 4: []
bucket 5: [("ad", 20), ("da", 40)]
bucket 6: [("cab", 10)]
bucket 7: [("be", 30)]
items = 4, load = 0.5 <- breathing room again
লক্ষ করো: "ad" আর "da" এখনো collide করছে কারণ আমাদের toy hash অক্ষর যোগ করে, তাই anagram সবসময় টাই হয়। আসল hash function-গুলো position-ও মিশিয়ে নেয়, তাই anagram প্রায় কখনোই collide করে না। Bad hash = জটলা পাকানো bucket; good hash = সমান ছড়ানো।
Movie 4: Two Sum-কে hashing animation হিসেবে দেখা¶
Problem (নিজের ভাষায়): nums = [2, 7, 11, 15]-এ এমন দুটো index খোঁজো যাদের value-র যোগফল target = 9।
seen dict-টা ম্যাপ করে value → ইতিমধ্যে পেরিয়ে আসা value-গুলোর index।
Frame A: i=0, x=2, need 9-2=7. 7 in seen {} ? no. seen={2:0}
nums: [2] 7 11 15
^
seen: {2:0}
Frame B: i=1, x=7, need 9-7=2. 2 in seen {2:0}? YES → answer (0, 1)
nums: 2 [7] 11 15
^
seen: {2:0} <- the dict remembered the partner instantly
এক pass। কোনো inner loop নেই। Dict-টা হাঁটার পাশে ভাসতে থাকা একটা memory cloud।
Movie 5: good hash বনাম bad hash (ছড়ানো কেন জরুরি)¶
একই 8টা key, দুটো আলাদা hash function:
GOOD HASH (even spread) BAD HASH (everything mod-collides)
bucket 0: [k3] bucket 0: []
bucket 1: [k7] bucket 1: []
bucket 2: [k1, k5] bucket 2: [k1,k2,k3,k4,k5,k6,k7,k8]
bucket 3: [k8] bucket 3: []
bucket 4: [k2] lookup = scan 8 items = O(n)!
bucket 5: [k6] the table became a linked list
bucket 6: [k4]
lookup = ~1 compare = O(1)
"Average O(1), worst O(n)"-এর পুরো গল্পটা এই এক ছবিতেই।
এই frame-গুলো থেকে কী মনে রাখবে¶
- Insert/lookup = hash, jump, ছোট্ট scan। Array কত বড় তাতে কিছু যায় আসে না।
- Collision একদম routine ব্যাপার; chain সেগুলোকে সস্তা রাখে।
- Resize মাঝেমধ্যে O(n) rehash-এর দাম দিয়ে chain ছোট রাখে।
- Loop-এর সময় ব্যবহার করা dict হলো "অতীতের স্মৃতি" — বেশিরভাগ hashing pattern-এর প্রাণ।
Interactive version-টা চেষ্টা করো https://visualgo.net/en-এ (Hash Table mode), তারপর এগিয়ে যাও operations.md-তে।