Hashing — The Concept¶

একটা বাস্তব জীবনের analogy দিয়ে শুরু করি¶

Theater-এর coat check-এর কথা ভাবো।

তুমি তোমার কোট জমা দিলে। Attendant কিন্তু rack ধরে হেঁটে হেঁটে তোমার কোট অন্য সব কোটের সাথে মিলিয়ে দেখে না। বরং সে তোমাকে ticket #42 ধরিয়ে দেয় আর তোমার কোট hook #42-এ ঝুলিয়ে রাখে। তুমি ফিরে এলে ticket দেখাও, আর attendant সোজা hook 42-এ লাফ দেয়।

ওই ticket number-টাই একটা hash। নম্বর দেওয়া hook-এর rack-টা হলো bucket array। পুরো system-টা কাজ করে কারণ নম্বরটা জিনিসটা থেকেই হিসেব করা হয় (বা জিনিসের সাথে দেওয়া হয়), তাই জিনিস খুঁজতে কখনো search করতে হয় না।

"Fingerprint" ব্যাপারটা বোঝায় এমন আরেকটা analogy: এমন একটা library যেখানে বই তার title-এর প্রথম অক্ষর দিয়ে shelf-এ রাখা হয়। "Dune" যায় shelf D-তে। "Dune" খুঁজতে তোমাকে পুরো library scan করতে হয় না — title থেকেই "D" হিসেব করে সোজা সেই shelf-এ হেঁটে যাও। Title-টাই ঠিকানা বানায়।

Hash function = fingerprint থেকে ঠিকানা¶

Hash function যেকোনো key (string, number, tuple) নেয় আর একটা fixed-size সংখ্যা — একটা fingerprint — বের করে। তারপর modulo দিয়ে সেই fingerprint-কে একটা valid array index-এ চেপে ফেলি:

index = hash(key) % number_of_buckets

8টা bucket দিয়ে একটা উদাহরণ:

key        hash(key)        hash % 8   → bucket
"cat"      8757049... (big)     5      → bucket 5
"dog"      4201337...           1      → bucket 1
"emu"      9913702...           5      → bucket 5   ← same as "cat"!

দুটো আলাদা key একই bucket-এ পড়লে সেটাই collision। Collision স্বাভাবিক এবং প্রত্যাশিত — কায়দাটা হলো সেটা সুন্দরভাবে সামলানো।

Memory-র ছবি (chaining)¶

Collision সামলানোর সবচেয়ে beginner-friendly উপায় হলো chaining: প্রতিটা bucket-এ (key, value) pair-এর একটা ছোট list থাকে।

buckets (array of 8 slots)

index  contents
  0    []
  1    [("dog", 7)]
  2    []
  3    []
  4    []
  5    [("cat", 3), ("emu", 9)]      <- two keys collided; both live here
  6    []
  7    [("ant", 1)]

"emu"-র lookup:

1. hash("emu") % 8  → 5            (one cheap computation)
2. go to bucket 5                  (one array jump, O(1))
3. scan the tiny chain: "cat"? no. "emu"? yes!   (chain is short)

Chain যতক্ষণ ছোট থাকে, প্রতিটা operation দ্রুত হয়।

Core invariants¶

এই নিয়মগুলো মেনেই structure-টা বাঁচে:

একই key → একই bucket, সবসময়। Table-এর জীবদ্দশায় hash(k) deterministic হতেই হবে।
সমান key-দের hash সমান হতেই হবে। যদি a == b হয় তাহলে hash(a) == hash(b)। (উল্টোটা জরুরি না — অসমান key collide করতে পারে।)
Key-কে immutable (hashable) হতে হবে। Insert করার পর key বদলে গেলে তার hash-ও বদলাত, আর জিনিসটা ভুল bucket-এ হারিয়ে যেত। ঠিক এই কারণেই Python-এর list dict-এর key হতে পারে না কিন্তু tuple পারে।
Load factor সীমার মধ্যে থাকে। Load factor = items / buckets। Python তার dict প্রায় 2/3 ভরে গেলে resize করে, যাতে chain (CPython-এ technically probe sequence) ছোট থাকে।

Load factor আর resizing¶

load factor = number_of_items / number_of_buckets

  8 buckets, 2 items  → load 0.25  → chains nearly empty, very fast
  8 buckets, 6 items  → load 0.75  → collisions piling up
  resize: 16 buckets, rehash all 6 → load 0.375 → fast again

Resize করলে প্রতিটা item rehash হয় (প্রত্যেকে নতুন bucket-এ পড়তে পারে), যেটার খরচ O(n) — কিন্তু এত বিরল ঘটে যে অনেক insert-এর উপর ভাগ করলে প্রতিটা insert এখনো average O(1)-ই থাকে। এটা সেই একই "amortized" idea, যেমন Python list তার capacity double করে।

Average O(1) কেন?¶

ধরো key-গুলো মোটামুটি সমানভাবে ছড়িয়ে পড়ে (একটা ভালো hash function-এর কাজ এটাই)। b-টা bucket-এ n-টা item থাকলে average chain length হয় n / b — মানে load factor। Load factor একটা constant-এর নিচে রাখো (Python রাখে), তাহলে average chain-এর length-ও constant। সুতরাং:

compute hash: O(1)
jump to bucket: O(1)
constant-length chain scan: O(1)

Worst case এখনো O(n): সব key যদি একটা bucket-এ collide করে, table একটা লম্বা list-এ নেমে আসে। ভালো built-in hash function থাকলে দুর্ঘটনাবশত এমনটা হওয়া কার্যত অসম্ভব।

কখন hashing ব্যবহার করবে¶

দ্রুত membership test দরকার: "এটা কি আগে দেখেছি?"
Exact key দিয়ে দ্রুত key → value lookup দরকার।
জিনিসের occurrence গুনছ।
কোনো computed signature দিয়ে item group করতে চাও।

কখন hashing ব্যবহার করবে না¶

Key-গুলো sorted order-এ বা range query দরকার ("10 থেকে 50-এর মধ্যের সব key") → sorted array, balanced BST (../07-trees/), বা heap।
বারবার সবচেয়ে ছোট/বড় item দরকার → heap।
Key-গুলো ছোট dense integer 0..k → একটা সাধারণ array-ই সহজ এবং দ্রুত।
String-এ prefix matching দরকার ("'pre' দিয়ে শুরু সব word") → trie।
Memory ভীষণ টানাটানি: hash table ইচ্ছে করেই খালি slot রাখে।

Complexity table¶

Operation	Average	Worst	Notes
Insert `d[k] = v`	O(1)	O(n)	Worst case = pathological collision বা resize-এর মুহূর্ত
Lookup `d[k]`, `k in d`	O(1)	O(n)
Delete `del d[k]`	O(1)	O(n)
Iterate all items	O(n)	O(n)	Python dict insertion order-এ iterate করে (3.7+)
Resize (internal)	O(n)	O(n)	Insert-গুলোর উপর ভাগ হয়ে amortized হয়ে যায়

dict vs set vs Counter vs defaultdict¶

Tool	Stores	Use when
`dict`	key → value	প্রতিটা key-র জন্য একটা value মনে রাখতে হবে
`set`	keys only	শুধু membership / uniqueness নিয়ে মাথাব্যথা
`Counter`	key → count	গুনছ; `+`, `-`, `most_common()` ফ্রি-তে পাও
`defaultdict`	key → value with auto-default	`if key not in d` check ছাড়াই group বা accumulate করো

Dry run সহ ছোট্ট Python snippet¶

1. সাধারণ dict দিয়ে counting¶

freq = {}
for ch in "banana":
    freq[ch] = freq.get(ch, 0) + 1
# freq == {'b': 1, 'a': 3, 'n': 2}

Dry run:

ch='b' → get('b',0)=0 → freq={'b':1}
ch='a' → get('a',0)=0 → freq={'b':1,'a':1}
ch='n' → freq={'b':1,'a':1,'n':1}
ch='a' → get('a',0)=1 → freq={'b':1,'a':2,'n':1}
ch='n' → freq={'b':1,'a':2,'n':2}
ch='a' → freq={'b':1,'a':3,'n':2}

2. Duplicate-এর জন্য seen-set¶

def has_duplicate(nums):
    seen = set()
    for x in nums:
        if x in seen:          # O(1) average
            return True
        seen.add(x)
    return False

has_duplicate([3, 1, 4, 1])   # True

[3, 1, 4, 1]-এর উপর dry run:

x=3: not in {}        → seen={3}
x=1: not in {3}       → seen={3,1}
x=4: not in {3,1}     → seen={3,1,4}
x=1: 1 in {3,1,4}? YES → return True

3. defaultdict দিয়ে grouping¶

from collections import defaultdict

groups = defaultdict(list)
for word in ["tab", "bat", "cat"]:
    key = "".join(sorted(word))    # canonical signature
    groups[key].append(word)
# groups == {'abt': ['tab', 'bat'], 'act': ['cat']}

Dry run:

"tab" → sorted → "abt" → groups={'abt':['tab']}
"bat" → sorted → "abt" → groups={'abt':['tab','bat']}
"cat" → sorted → "act" → groups={'abt':['tab','bat'],'act':['cat']}

4. দুই লাইনে Counter¶

from collections import Counter
Counter("banana").most_common(1)   # [('a', 3)]

Dry run: Counter এক pass-এ {'b':1,'a':3,'n':2} বানায়, তারপর most_common(1) সবচেয়ে বেশি count-ওয়ালা একটা pair ফেরত দেয়।

এক বাক্যের সারমর্ম¶

Hashing "খুঁজে দেখো"-কে বদলে দেয় "কোথায় থাকতে বাধ্য সেটা হিসেব করে সেখানে চলে যাও"-তে — পুরো জাদুটাই এটুকু।

পরের file: frame-by-frame movie-র জন্য visual-explanation.md।