# Hashing — key থেকে সঠিক বাক্সে

Hash table-এ key দেখে আগে একটি **bucket** বেছে নিই, তারপর সেখানে আসল key মিলিয়ে দেখি। এই উদাহরণে চারটি bucket এবং শেখার জন্য ছোট একটি hash ব্যবহার করছি: `a=1, b=2` থেকে `z=26`; অক্ষরের মান যোগ করে bucket সংখ্যার ভাগশেষ নিই। এটি production hash নয়।

## 1. Insert: hash হিসাব করে bucket বেছে নাও

`cab`-এর যোগফল `3 + 1 + 2 = 6`, তাই bucket `6 % 4 = 2`। `ad`-এর যোগফল `1 + 4 = 5`, তাই bucket `5 % 4 = 1`। বাক্সের index-ই bucket number।

```dsa
kind: array
title: "চার bucket-এ দুটি key রাখা"
steps:
  - label: "শুরু · 0টি item"
    values: ["খালি", "খালি", "খালি", "খালি"]
    muted: [0, 1, 2, 3]
    note: "Load factor = item / bucket = 0 / 4 = 0।"
  - label: "cab → 10 রাখো"
    values: ["খালি", "খালি", "cab: 10", "খালি"]
    active: [2]
    muted: [0, 1, 3]
    note: "Load factor = 1 / 4 = 0.25।"
  - label: "ad → 20 রাখো"
    values: ["খালি", "ad: 20", "cab: 10", "খালি"]
    active: [1]
    muted: [0, 3]
    note: "Load factor = 2 / 4 = 0.5।"
```

এখন `cab` খুঁজতে একই hash আবার হিসাব করি: bucket 2-তে যাই, `cab` key মেলে, উত্তর `10`। অন্য bucket দেখার দরকার হয় না।

## 2. Collision: একই bucket মানে একই key নয়

এরপর `be → 30` রাখলে `7 % 4 = 3`। কিন্তু `da → 40`-এর hash `5 % 4 = 1`, যেখানে `ad` আগেই আছে। **দুই key-কে একই chain-এ রাখলে কেউ হারায় না।**

```mermaid
flowchart LR
  B0["bucket 0"] --> E0["খালি"]
  B1["bucket 1"] --> AD["ad · value 20"] --> DA["da · value 40"]
  B2["bucket 2"] --> CAB["cab · value 10"]
  B3["bucket 3"] --> BE["be · value 30"]
```

| খোঁজা key | hash ও bucket | যে তুলনাগুলো হয় | ফল |
| --- | --- | --- | --- |
| `cab` | `6 % 4 = 2` | `cab == cab` | 10 |
| `da` | `5 % 4 = 1` | `ad != da`, তারপর `da == da` | 40 |
| `zz` | `52 % 4 = 0` | bucket খালি; তুলনাও লাগে না | key নেই |

`be` ঢোকার পরে load `3/4 = 0.75`; `da` ঢোকার পরে `4/4 = 1`। ছবি **separate chaining** বোঝায়; Python `dict`-এর ভেতরের গঠন হুবহু এমন নয়।

## 3. Resize: শুধু বড় করলেই হয় না, bucket আবার হিসাব করো

এই উদাহরণে load 1 হলে চার থেকে আট bucket করি। Resize threshold implementation অনুযায়ী বদলায়। নতুন bucket number হলো **hash % 8**, তাই পুরনো index রেখে দিলে lookup ভুল হবে।

| key | hash | আগে: `% 4` | পরে: `% 8` |
| --- | --- | --- | --- |
| cab | 6 | 2 | 6 |
| ad | 5 | 1 | 5 |
| da | 5 | 1 | 5 |
| be | 7 | 3 | 7 |

```dsa
kind: array
title: "Resize-এর পরে আট bucket"
steps:
  - label: "4টি item, 8টি bucket · load 0.5"
    values: ["খালি", "খালি", "খালি", "খালি", "খালি", "ad, da", "cab", "be"]
    active: [5, 6, 7]
    muted: [0, 1, 2, 3, 4]
    note: "Bucket 5-এ ad → da chain আছে; value যথাক্রমে 20 ও 40। cab-এর value 10, be-এর 30।"
```

`ad` ও `da` এখনও collide করে: আমাদের hash-এ অক্ষরের যোগফল একই। ভালো hash-এ অক্ষরের অবস্থানও প্রভাব ফেলে, তবু collision সম্ভব। তাই **hash মেলার পর key-ও মেলাতে হয়**।

## 4. Two Sum: আগে দেখা জোড়াটি মনে রাখো

`[2, 7, 11, 15]` থেকে যোগফল 9 হয় এমন দুই index চাই। `seen` রাখে **আগে দেখা value → তার index**। প্রতিটি `x`-এর জন্য দরকার `9 - x`।

```dsa
kind: array
title: "আগের মান মনে রাখলে দ্বিতীয় loop লাগে না"
steps:
  - label: "i = 0 · x = 2"
    values: [2, 7, 11, 15]
    active: [0]
    pointers: {i: 0}
    note: "দরকার 7। seen খালি, তাই মেলেনি। এবার seen-এ 2 → 0 রাখি।"
  - label: "i = 1 · x = 7"
    values: [2, 7, 11, 15]
    active: [0, 1]
    pointers: {আগের: 0, i: 1}
    note: "দরকার 2। seen-এ 2 → 0 পাওয়া গেছে। উত্তর indices [0, 1]; এখানেই থামি।"
```

নিজেকে `seen`-এ রাখার **আগে** complement খুঁজি। তা না হলে `[3, 3]`, target 6-এর মতো ক্ষেত্রে একই index দুবার নেওয়ার ভুল হতে পারে। গড়ে প্রতিটি lookup O(1); পুরো traversal **O(n)** সময়, **O(n)** অতিরিক্ত জায়গা।

## 5. কেন key ছড়িয়ে থাকা দরকার?

একই আট key যদি আট bucket-এ মোটামুটি ছড়ায়, প্রতিটি chain ছোট থাকে। সব key একই bucket-এ পড়লে lookup আবার লম্বা তালিকা খোঁজার মতো হয়। নিচের দুটি distribution কেবল খরচ বোঝানোর উদাহরণ।

| bucket | ছড়ানো অবস্থায় key | সব এক জায়গায় পড়লে key |
| --- | --- | --- |
| 0 | k3 | খালি |
| 1 | k7 | খালি |
| 2 | k1, k5 | k1, k2, k3, k4, k5, k6, k7, k8 |
| 3 | k8 | খালি |
| 4 | k2 | খালি |
| 5 | k6 | খালি |
| 6 | k4 | খালি |
| 7 | খালি | খালি |

বাঁয়ের উদাহরণে সফল lookup-এ 1–2টি key তুলনা লাগে; ডানের chain-এর শেষে পৌঁছাতে 8টি। ভালো distribution ও নিয়ন্ত্রিত load factor-এ গড় খরচ **O(1)**, কিন্তু worst case **O(n)**। String key-এর দৈর্ঘ্য m হলে প্রথমবার hash হিসাবেই **O(m)** লাগতে পারে।

**নিজে চেষ্টা করো:** `ab` ও `ba`-এর bucket বের করো। চার থেকে আট bucket করলেও তারা আলাদা হবে কি? উত্তর দিয়ে বোঝাও কেন শুধু resize দিয়ে খারাপ hash ঠিক করা যায় না। পরের পাঠ: [operations](./operations.md)। [VisuAlgo Hash Table](https://visualgo.net/en/hashtable)-এ নিজেও insert করে দেখতে পারো।