# Hashing — Operations Cookbook (dict / set / Counter)

যে operation-গুলো সত্যিই ব্যবহার করবে — সবগুলো, cost আর gotcha সহ। Average cost ধরে নিচ্ছে Python-এর built-in hash (যেটা সাধারণ input-এর জন্য চমৎকার)।

## এক নজরে cost table

| Operation | Average | Worst | Comment |
| --- | --- | --- | --- |
| `d[k] = v` (insert/update) | O(1) | O(n) | Worst case শুধু adversarial collision বা resize-এর সময় |
| `d[k]` (lookup) | O(1) | O(n) | Key না থাকলে KeyError |
| `d.get(k, default)` | O(1) | O(n) | Miss হলেও exception নেই |
| `k in d` / `x in s` | O(1) | O(n) | List-এর বদলে set পছন্দ করার আসল কারণ |
| `del d[k]` / `s.discard(x)` | O(1) | O(n) | `s.remove(x)` miss-এ error দেয়; `discard` দেয় না |
| `d.pop(k, default)` | O(1) | O(n) | Lookup + delete + value ফেরত |
| `len(d)` | O(1) | O(1) | Size cache করা থাকে |
| `for k in d` (iterate) | O(n) | O(n) | Python 3.7+-এ insertion order |
| `d.setdefault(k, v)` | O(1) | O(n) | না থাকলে insert, তারপর current value ফেরত |
| `s1 & s2`, `s1 \| s2`, `s1 - s2` | O(len) | — | Set algebra, set-এর size-এর সমানুপাতিক |
| `Counter(iterable)` | O(n) | — | এক pass-এ সব গোনা |
| `c.most_common(k)` | O(n log n) | — | Count দিয়ে sort করে (ছোট k-র জন্য ভেতরে heap দিয়ে O(n log k)) |

একটা সাধারণ list-এর সাথে তুলনা করো: `x in my_list` প্রতিবারই O(n)। Loop-এর ভেতরে সেটা হয়ে যায় O(n^2) — beginner code-এ সবচেয়ে common accidental slowdown।

## dict operations

### Insert আর update

```python
d = {}
d["apple"] = 3        # insert
d["apple"] = 5        # update (same key, value overwritten)
```

### Lookup: তিন রকম

```python
d = {"apple": 5}

d["apple"]            # 5
d["pear"]             # KeyError!  use only when key MUST exist
d.get("pear")         # None       quiet miss
d.get("pear", 0)      # 0          miss with a default — perfect for counting
```

`get` দিয়ে বানানো counting idiom:

```python
counts = {}
for x in [1, 2, 2, 3]:
    counts[x] = counts.get(x, 0) + 1
# {1: 1, 2: 2, 3: 1}
```

### Delete

```python
d = {"a": 1, "b": 2}
del d["a"]            # KeyError if absent
v = d.pop("b")        # removes AND returns 2
v = d.pop("z", None)  # safe pop with default → None
```

### Iterate

```python
d = {"a": 1, "b": 2}

for k in d:                 # keys
    ...
for v in d.values():        # values
    ...
for k, v in d.items():      # both — the one you want most often
    ...
```

### setdefault — এক ধাপে insert-if-absent

```python
groups = {}
groups.setdefault("fruit", []).append("apple")
groups.setdefault("fruit", []).append("pear")
# {'fruit': ['apple', 'pear']}
```

বারবার এটা করতে হলে `defaultdict(list)` একই কাজ আরো পরিষ্কারভাবে করে।

## set operations

```python
s = set()
s.add(3)              # insert
s.add(3)              # no-op (sets hold each value once)
3 in s                # True, O(1)
s.discard(99)         # no error even though absent
s.remove(3)           # KeyError if absent — prefer discard when unsure
```

```python
a = {1, 2, 3}
b = {3, 4}
a & b                 # {3}        intersection
a | b                 # {1,2,3,4}  union
a - b                 # {1, 2}     difference
a ^ b                 # {1,2,4}    symmetric difference (in exactly one)
```

Order ঠিক রেখে de-duplicate করা (একটা classic):

```python
def dedupe(items):
    seen = set()
    out = []
    for x in items:
        if x not in seen:
            seen.add(x)
            out.append(x)
    return out

dedupe([3, 1, 3, 2, 1])   # [3, 1, 2]
```

## Counter operations

```python
from collections import Counter

c = Counter("mississippi")
c["s"]                 # 4
c["z"]                 # 0   <- missing keys give 0, NOT KeyError. Huge convenience.
c.most_common(2)       # [('i', 4), ('s', 4)]

a = Counter("aab")     # {'a': 2, 'b': 1}
b = Counter("ab")      # {'a': 1, 'b': 1}
a - b                  # Counter({'a': 1})        subtraction drops zero/negative
a + b                  # Counter({'a': 3, 'b': 2})
```

`a - b` উত্তর দেয় "`a`-র এমন কী আছে যেটা `b` cover করতে পারে না?" — এক expression-এ একদম Ransom Note-এর প্রশ্নটাই।

## 20 সেকেন্ডে defaultdict

```python
from collections import defaultdict

g = defaultdict(list)   # missing key → fresh []
g["x"].append(1)        # no 'if "x" not in g' dance
g["x"].append(2)        # {'x': [1, 2]}

cnt = defaultdict(int)  # missing key → 0
cnt["a"] += 1
```

সাবধান: শুধু `g["typo"]` *পড়লেই* key-টা default value সহ তৈরি হয়ে যায়। শুধু membership check করতে হলে `"typo" in g` ব্যবহার করো।

## Pitfalls (দুইবার পড়ো)

### 1. Iterate করতে করতে mutate করা

```python
d = {"a": 1, "b": 2}
for k in d:
    if d[k] == 1:
        del d[k]        # RuntimeError: dictionary changed size during iteration
```

Fix: একটা snapshot-এর উপর iterate করো।

```python
for k in list(d):       # list(...) copies the keys first
    if d[k] == 1:
        del d[k]
```

### 2. Key হিসেবে unhashable type

```python
d = {}
d[[1, 2]] = "x"         # TypeError: unhashable type: 'list'
d[(1, 2)] = "x"         # fine — tuples are immutable, hence hashable
```

নিয়ম: key-কে immutable হতে হবে। list → tuple, set → frozenset, dict → sorted item-দের tuple।

### 3. Key হিসেবে float

```python
d = {0.3: "hit"}
d.get(0.1 + 0.2)        # None!  because 0.1 + 0.2 == 0.30000000000000004
```

Float-এ rounding error থাকে, তাই equality (এবং সেই সাথে hashing) চুপচাপ fail করে। Key হিসেবে ব্যবহার করো integer (scale বাড়িয়ে: dollar না, cent), `Fraction`, বা rounded string।

### 4. `is` বনাম `in` গুলিয়ে ফেলা

`x in s` membership টেস্ট করে (hashing ব্যবহার করে)। `x is y` identity টেস্ট করে (একই object কিনা)। Beginner-রা মাঝে মাঝে `if x is in s` লিখে ফেলে — সেটা syntax error; শুধু `in`-ই যথেষ্ট।

### 5. "Worst case হবেই না" ধরে নেওয়া

Competitive programming-এ adversary-রা এমন input বানাতে পারে যেটা পুরনো setup-এ Python-এর default string hash-এর নিচে collide করে। Built-in `dict` প্রতি run-এ string hashing randomize করে, তাই তুমি সুরক্ষিত; কিন্তু custom rolling hash-এর নিজস্ব randomization লাগে (দেখো [patterns.md](patterns.md))।

## Quick self-test

- Loop-এর ভেতরে `x in some_list` কেন বিপজ্জনক? (প্রতিবার O(n) → মোট O(n^2)।)
- `Counter("aa")["b"]` কী ফেরত দেয়? (0 — কোনো KeyError নেই।)
- List কেন dict-এর key হতে পারে না? (Mutate করতে পারে, তাই তার hash মিথ্যা বলত।)
- Iteration-এর সময় key delete করার নিরাপদ উপায় কী? (`list(d)`-এর উপর iterate করো।)

পরেরটা: [patterns.md](./patterns.md) — এই operation-গুলোর উপর দাঁড়ানো named problem-solving pattern।