# 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 দিয়ে একটি শিক্ষামূলক উদাহরণ; নিচের hash-গুলো বোঝানোর জন্য বেছে নেওয়া, Python `hash()`-এর output নয়:

```
key        hash(key)        hash % 8   → bucket
"cat"      13                    5      → bucket 5
"dog"       9                    1      → bucket 1
"emu"      21                    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-টা বাঁচে:

1. **একই key ও একই capacity → একই bucket।** Key থাকা অবস্থায় তার hash স্থির থাকতে হবে; resize হলে নতুন capacity-তে bucket বদলাতে পারে।
2. **সমান key-দের hash সমান হতেই হবে।** যদি `a == b` হয় তাহলে `hash(a) == hash(b)`। (উল্টোটা জরুরি না — অসমান key collide করতে পারে।)
3. **Key-কে hashable হতে হবে।** তার hash ও equality আচরণ স্থির থাকতে হবে। Python list key হতে পারে না; tuple-এর সব element hashable হলে সেটি key হতে পারে। শুধু immutable বললেই যথেষ্ট নয়: `(1, [2])` tuple হলেও hashable নয়।
4. **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, যেমন dynamic array-র capacity বাড়ানোর খরচ অনেক append-এর মধ্যে ভাগ হয়।

## 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। সুতরাং:

- fixed-size key-এর hash: O(1); নতুন string key-তে m অক্ষর থাকলে hash তৈরি O(m) হতে পারে
- jump to bucket: O(1)
- constant-length chain scan: O(1)

Worst case এখনো O(n): সব key যদি একটা bucket-এ collide করে, table একটা লম্বা list-এ নেমে আসে। এই worst case বিরল হলেও সম্ভব; custom hash বা প্রতিকূল input-এ এটি গুরুত্বপূর্ণ।

## কখন 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 ([Tree অধ্যায়](../07-trees/README.md))। Heap sorted range query-র সাধারণ সমাধান নয়।
- বারবার সবচেয়ে ছোট/বড় 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

```python
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

```python
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

```python
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

```python
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](./visual-explanation.md)।