# فصل ۰۳ — `hash table` را خودت بساز

<div dir="rtl">

# فصل ۰۳ — `hash table` را خودت بساز

## در این فصل چه یاد می‌گیری

تابعِ `hash` را داریم و می‌دانیم برخورد اجتناب‌ناپذیر است. این فصل از این دو، یک ساختارِ کامل می‌سازد — **در حدودِ سی خط، بدونِ هیچ کتابخانه‌ای** — و بعد دو بار اندازه‌اش می‌گیرد.

بارِ اول جدول ثابت می‌ماند: **میانگینِ گام‌های جست‌وجو از `6.03` به `40.56` می‌رود و ستونِ نسبت `1.95` می‌شود.** بارِ دوم همان کلیدها در جدولی می‌ریزند که وقتی شلوغ شد خودش را بزرگ می‌کند: **`1.33`، `1.28`، `1.31`، `1.32` — ستونِ نسبت `1.01`.** فرقِ این دو جدول، کلِ حرفِ این ترم است.

![قفسه‌ای از خانه‌های شماره‌دار که از هر خانه یک زنجیرِ کوتاه از برگه‌ها آویزان است](/lesson-assets/t3-s03-hash-table-by-hand/prompt/01-image-buckets-and-chains.png)

آخر این فصل می‌توانی:

- یک `hash table` با `bucket` و `chaining` را از صفر بنویسی
- `load factor` را حساب کنی و بگویی چرا جدولِ پر کند می‌شود
- بگویی `rehash` چقدر خرج دارد و چرا با وجودِ آن، درج هنوز ارزان است

## قبل از شروع

**از فصلِ ۲:** `poly_hash`، برخورد، و قاعدهٔ «اندازهٔ جدول را عددِ اول بگیر».

**از ترمِ ۲ فصلِ ۳:** هزینهٔ `amortised` و دوبرابرشدنِ ظرفیت. **این فصل دقیقاً همان الگو را روی یک ساختارِ دیگر تکرار می‌کند.**

</div>

| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیش‌فرضِ Colab) | حدودِ یک دقیقه |

<div dir="rtl">

> 📓 **نوت‌بوک:** [نوت‌بوک این فصل را در Colab باز کن](/notebooks/bonyad/term-3-hashing/session-03-hash-table-by-hand.ipynb) — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

## ۱. کوچک‌ترین نسخهٔ ممکن، با دست

پنج خانه می‌گیریم و شش کلید. هر خانه یک `bucket` است: یک `list` که هر جفتِ کلید-مقدارِ متعلق به آن خانه را نگه می‌دارد. وقتی دو کلید هم‌خانه شوند، هر دو در همان `bucket` کنارِ هم می‌نشینند — **اسمِ این کار `chaining` است.**

</div>

```python
def poly_hash(key):
    """همان تابعِ فصلِ قبل: هر حرف در ۳۱ ضرب و با حرفِ بعدی جمع می‌شود."""
    h = 0
    for ch in str(key):
        h = (h * 31 + ord(ch)) % 1_000_003
    return h


def table_new(size):
    """به‌اندازهٔ size خانه، و هر خانه یک bucketِ خالیِ جداگانه."""
    return [[] for _ in range(size)]


def table_put(buckets, key, value):
    """کلید را در bucketِ خودش می‌گذارد؛ اگر از قبل بود، مقدارش را عوض می‌کند."""
    bucket = buckets[poly_hash(key) % len(buckets)]
    for pair in bucket:
        if pair[0] == key:
            pair[1] = value
            return
    bucket.append([key, value])


def table_get(buckets, key):
    """مقدار، و تعدادِ جفتی که تا رسیدن به آن نگاه شد."""
    bucket = buckets[poly_hash(key) % len(buckets)]
    steps = 0
    for pair in bucket:
        steps += 1
        if pair[0] == key:
            return pair[1], steps
    return None, steps


small = table_new(5)
for name, city in (("sara", "shiraz"), ("reza", "tabriz"), ("nima", "rasht"),
                   ("mina", "yazd"), ("kian", "ahvaz"), ("dara", "kerman")):
    table_put(small, name, city)
for i, bucket in enumerate(small):
    print(f"bucket {i}: {bucket}")
print("جست‌وجوی nima:", table_get(small, "nima"))
print("جست‌وجوی sina:", table_get(small, "sina"))
```

```text
bucket 0: [['reza', 'tabriz'], ['kian', 'ahvaz']]
bucket 1: []
bucket 2: [['nima', 'rasht'], ['mina', 'yazd']]
bucket 3: []
bucket 4: [['sara', 'shiraz'], ['dara', 'kerman']]
جست‌وجوی nima: ('rasht', 1)
جست‌وجوی sina: (None, 0)
```

<div dir="rtl">

**کلِ ساختار همین است و دیگر هیچ چیز.** شش کلید در سه `bucket` نشسته‌اند و دو `bucket` خالی مانده. جست‌وجوی `nima` یک گام خورد: `poly_hash` گفت خانهٔ ۲، و اولین جفتِ آن خانه همان بود.

**و به سطرِ آخر خوب نگاه کن: جست‌وجوی کلیدی که اصلاً وجود ندارد صفر گام خورد.** `sina` به یک `bucket` خالی افتاد، و «خالی» یعنی جوابِ «نه» بدونِ حتی یک مقایسه. **این دقیقاً همان پرسشی است که در فصلِ ۱ هزار مقایسه خرج برمی‌داشت.**

> 🔧 **اگر کار نکرد:** خطِ `table_new` وسوسه‌انگیزترین جای این کد برای کوتاه‌نویسی است، و کوتاه‌نویسی‌اش **هیچ خطایی نمی‌دهد و ساختار را کاملاً خراب می‌کند**:

</div>

```python
broken = [[]] * 4                        # چهار ارجاع به یک list واحد
table_put(broken, "sara", "shiraz")
print("bucketهای معیوب:", broken)
print("طولِ هر bucket :", [len(b) for b in broken])

healthy = table_new(4)
table_put(healthy, "sara", "shiraz")
print("bucketهای درست:", healthy)
```

```text
bucketهای معیوب: [[['sara', 'shiraz']], [['sara', 'shiraz']], [['sara', 'shiraz']], [['sara', 'shiraz']]]
طولِ هر bucket : [1, 1, 1, 1]
bucketهای درست: [[['sara', 'shiraz']], [], [], []]
```

<div dir="rtl">

**یک درج، و هر چهار `bucket` پر شدند.** `[[]] * 4` چهار `list` نمی‌سازد؛ **چهار ارجاع به یک `list` واحد** می‌سازد. هیچ استثنایی بلند نمی‌شود، هیچ پیامی چاپ نمی‌شود، و جدولت از همان اولین درج غلط است. `[[] for _ in range(size)]` هر بار یک `list` تازه می‌سازد.

**این بدترین ردهٔ خطاست:** کدی که کار می‌کند و جوابِ غلط می‌دهد. تنها راهِ گرفتنش هم همان کاری است که این‌جا کردیم — **ساختار را چاپ کردن و با چشم دیدن.**

## ۲. `load factor`: نسبتی که همه‌چیز را تعیین می‌کند

اندازهٔ جدول را ثابت می‌گذاریم روی ۱۰۱ خانه و تعدادِ کلیدها را بالا می‌بریم. نسبتِ **تعدادِ کلید به تعدادِ خانه** اسم دارد: `load factor`.

> 🌱 **ریشه‌اش کجاست:** `load factor` یک نسبت است، نه یک شمارش — «به‌ازای هر خانه، چند کلید». همین ایده در [ریشه ترمِ ۲ فصل ۷](/courses/risheh/lessons/term-2-fractions/session-07-ratio) با نسبت و تناسب ساخته می‌شود. **و خاصیتِ مهمش همان خاصیتِ هر نسبتی است: به اندازهٔ جدول و تعدادِ کلیدها جداگانه بند نیست، فقط به رابطهٔ آن دو بند است.** جدولی با ۱۰۱ خانه و ۲۰۰ کلید، دقیقاً همان‌قدر شلوغ است که جدولی با ۱٬۰۱۰ خانه و ۲٬۰۰۰ کلید.

</div>

```python
rng = random.Random(SEED)
POOL = [f"user-{rng.randrange(10 ** 9)}" for _ in range(8_000)]
print("کلیدهای یکتا:", len(set(POOL)), "· سه نمونه:", POOL[:3])


def build_fixed(keys, size):
    """جدولی با اندازهٔ ثابت — هرگز بزرگ نمی‌شود."""
    buckets = table_new(size)
    for k in keys:
        table_put(buckets, k, 1)
    return buckets


def lookup_cost(buckets, keys):
    """میانگین و بیشینهٔ گام‌های جست‌وجو برای همهٔ کلیدها."""
    total = 0
    worst = 0
    for k in keys:
        steps = table_get(buckets, k)[1]
        total += steps
        worst = max(worst, steps)
    return total / len(keys), worst


FIXED = 101
LADDER = [1_000, 2_000, 4_000, 8_000]
for n in LADDER:
    average, worst = lookup_cost(build_fixed(POOL[:n], FIXED), POOL[:n])
    print(f"n={n:>6,}  load factor={n / FIXED:>6.2f}"
          f"  میانگینِ گام={average:>6.2f}  بلندترین زنجیر={worst:>4}")
```

```text
کلیدهای یکتا: 8000 · سه نمونه: ['user-835549143', 'user-473233031', 'user-125467289']
n= 1,000  load factor=  9.90  میانگینِ گام=  6.03  بلندترین زنجیر=  20
n= 2,000  load factor= 19.80  میانگینِ گام= 10.88  بلندترین زنجیر=  30
n= 4,000  load factor= 39.60  میانگینِ گام= 20.85  بلندترین زنجیر=  53
n= 8,000  load factor= 79.21  میانگینِ گام= 40.56  بلندترین زنجیر=  98
```

<div dir="rtl">

**میانگینِ گام در هر چهار سطر کمی بیشتر از نصفِ `load factor` است.** و منطقش همان منطقِ فصلِ ۱ است: وقتی به‌طورِ متوسط `load factor` جفت در هر `bucket` نشسته، جست‌وجوی خطی داخلِ همان `bucket` به‌طورِ متوسط نصفشان را می‌بیند — به‌علاوهٔ گامِ اولی که همیشه لازم است.

**یعنی جدولِ پر، هیچ جادویی ندارد: هر `bucket` خودش یک فهرستِ کوچک است و جست‌وجو در آن، همان جست‌وجوی خطیِ فصلِ ۱.** جدول فقط کار را به `size` تکه شکسته.

> 🤔 **اول حدس بزن:** با ثابت ماندنِ اندازهٔ جدول، اگر تعدادِ کلیدها دو برابر شود میانگینِ گام چند برابر می‌شود؟ **بنویسش**، بعد جدول را ببین.

</div>

```python
table([(n, lookup_cost(build_fixed(POOL[:n], FIXED), POOL[:n])[0]) for n in LADDER],
      "میانگینِ گام", ",.2f")
```

```text
         n      میانگینِ گام     نسبت به سطر قبل
     1,000              6.03                   —
     2,000             10.88                1.80
     4,000             20.85                1.92
     8,000             40.56                1.95
```

<div dir="rtl">

**نزدیکِ `2` و رو به بالا رفتن به سمتِ `2`.** یعنی `O(n)` — **همان مرتبه‌ای که با جست‌وجوی خطیِ ساده هم داشتیم.**

عددِ ۱۰۱ فقط یک ثابت است، و ثابت مرتبه را عوض نمی‌کند. **جدولی که بزرگ نمی‌شود، `hash table` نیست؛ صد و یک فهرستِ کوچک است.**

(ستونِ نسبت از `1.80` شروع می‌شود نه از `2.00`، چون در سطرهای اول آن «یک گامِ اولِ» هر جست‌وجو هنوز سهمِ محسوسی از کل دارد. هرچه زنجیرها بلندتر می‌شوند، سهمش کمتر و نسبت به `2` نزدیک‌تر می‌شود.)

## ۳. جدولی که خودش را بزرگ می‌کند

راهِ حل روشن است: نگذاریم `load factor` بالا برود. هر وقت از حدی گذشت، جدولِ بزرگ‌تری می‌سازیم و **همه‌چیز را دوباره جا می‌دهیم** — چون خانهٔ هر کلید به `len(buckets)` بند است و با عوض شدنِ اندازه، عوض می‌شود. اسمِ این کار `rehash` است.

اندازه‌ها را از یک فهرستِ آمادهٔ **عددِ اول** برمی‌داریم که هر کدام تقریباً دو برابرِ قبلی است — یکی به‌خاطرِ قاعدهٔ فصلِ ۲، و یکی به‌خاطرِ ترمِ ۲ فصلِ ۳: **رشدِ ضربی، نه جمعی.**

</div>

```python
GROW_AT = 0.75
TABLE_SIZES = (11, 23, 47, 97, 199, 401, 809, 1_619, 3_251, 6_521, 13_043, 26_099)
BUCKETS, COUNT, STEP, MOVES = 0, 1, 2, 3


def grow_new():
    """[bucketها، تعدادِ کلید، شمارهٔ اندازهٔ فعلی، تعدادِ جابه‌جایی]"""
    return [table_new(TABLE_SIZES[0]), 0, 0, 0]


def rehash(t):
    """اندازهٔ بعدی را می‌سازد و هر جفت را در خانهٔ تازه‌اش می‌گذارد."""
    t[STEP] += 1
    bigger = table_new(TABLE_SIZES[t[STEP]])
    for bucket in t[BUCKETS]:
        for pair in bucket:
            bigger[poly_hash(pair[0]) % len(bigger)].append(pair)
            t[MOVES] += 1
    t[BUCKETS] = bigger


def grow_put(t, key, value):
    """درج، و بزرگ کردنِ جدول به‌محضِ اینکه load factor از GROW_AT رد شود."""
    bucket = t[BUCKETS][poly_hash(key) % len(t[BUCKETS])]
    for pair in bucket:
        if pair[0] == key:
            pair[1] = value
            return
    bucket.append([key, value])
    t[COUNT] += 1
    if t[COUNT] > GROW_AT * len(t[BUCKETS]) and t[STEP] + 1 < len(TABLE_SIZES):
        rehash(t)


def build_growing(keys):
    t = grow_new()
    for k in keys:
        grow_put(t, k, 1)
    return t


for n in LADDER:
    t = build_growing(POOL[:n])
    average, worst = lookup_cost(t[BUCKETS], POOL[:n])
    print(f"n={n:>6,}  اندازهٔ جدول={len(t[BUCKETS]):>6,}"
          f"  load factor={n / len(t[BUCKETS]):>5.2f}"
          f"  میانگینِ گام={average:>5.2f}  بلندترین زنجیر={worst:>3}")
```

```text
n= 1,000  اندازهٔ جدول= 1,619  load factor= 0.62  میانگینِ گام= 1.33  بلندترین زنجیر=  5
n= 2,000  اندازهٔ جدول= 3,251  load factor= 0.62  میانگینِ گام= 1.28  بلندترین زنجیر=  4
n= 4,000  اندازهٔ جدول= 6,521  load factor= 0.61  میانگینِ گام= 1.31  بلندترین زنجیر=  5
n= 8,000  اندازهٔ جدول=13,043  load factor= 0.61  میانگینِ گام= 1.32  بلندترین زنجیر=  6
```

<div dir="rtl">

**`load factor` در هر چهار سطر حولِ `0.62` ثابت مانده، و به‌همراهش میانگینِ گام هم.** بلندترین زنجیر با هشت برابر شدنِ کلیدها از ۵ به ۶ رفت — یعنی تقریباً هیچ.

> 🤔 **اول حدس بزن:** ستونِ نسبتِ این میانگین چه عددی می‌دهد؟ **جوابت را بنویس**، بعد جدول را ببین.

</div>

```python
table([(n, lookup_cost(build_growing(POOL[:n])[BUCKETS], POOL[:n])[0]) for n in LADDER],
      "میانگینِ گام", ",.2f")
```

```text
         n      میانگینِ گام     نسبت به سطر قبل
     1,000              1.33                   —
     2,000              1.28                0.97
     4,000              1.31                1.02
     8,000              1.32                1.01
```

<div dir="rtl">

**`0.97`، `1.02`، `1.01`.** نزدیکِ یک، یعنی `O(1)`: **هزینهٔ یک جست‌وجو به تعدادِ کلیدهای داخلِ جدول بستگی ندارد.**

این همان عنوانِ ترم است و حالا با عدد پشتیبانی می‌شود. **و مقایسه‌اش با جدولِ بخشِ ۲ را در یک سطر بنویس: در `n = 8,000` جدولِ ثابت `40.56` گام می‌خواست و جدولِ بزرگ‌شونده `1.32` — بیش از سی برابر کمتر، با همان کلیدها و همان تابعِ `hash`.**

## ۴. `rehash` رایگان نیست

هر بار که جدول بزرگ می‌شود، همهٔ جفت‌ها جابه‌جا می‌شوند. شمرده‌ایمشان.

</div>

```python
table([(n, build_growing(POOL[:n])[MOVES]) for n in LADDER], "جابه‌جایی", ",d")
```

```text
         n         جابه‌جایی     نسبت به سطر قبل
     1,000             1,194                   —
     2,000             2,409                2.02
     4,000             4,848                2.01
     8,000             9,739                2.01
```

<div dir="rtl">

**`2.01`: کلِ کارِ همهٔ `rehash`ها روی هم، خطی است — نه درجه‌دو.** و عددِ مطلقش هم گویاست: برای هشت هزار کلید، حدودِ نُه هزار و هفتصد جابه‌جایی. **یعنی به‌ازای هر درج، تقریباً یک و یک‌چهارم جابه‌جاییِ اضافه.**

دلیلش دقیقاً همان چیزی است که ترمِ ۲ فصلِ ۳ دربارهٔ `list` نشان داد: چون هر اندازه دو برابرِ قبلی است، جابه‌جایی‌های گذشته روی هم از یک برابرِ اندازهٔ فعلی بیشتر نمی‌شوند. **یک درجِ تک ممکن است خیلی گران باشد — همان درجی که `rehash` را راه می‌اندازد — ولی میانگینِ بلندمدت ثابت می‌ماند.** این همان `amortised` است.

</div>

```python
table([(n, 1000 * clock(lambda keys=POOL[:n]: build_growing(keys), repeat=3))
       for n in LADDER], "زمانِ ساخت (ms)", ",.1f")
```

```text-approx
         n   زمانِ ساخت (ms)     نسبت به سطر قبل
     1,000               3.5                   —
     2,000               7.4                2.12
     4,000              14.5                1.95
     8,000              28.2                1.94
```

<div dir="rtl">

**ساعت هم می‌گوید ساختنِ جدول خطی است.** یعنی `n` درج، هر کدام با هزینهٔ ثابتِ `amortised`.

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** یک `hash table` با اندازهٔ ثابت، در برابرِ همان ساختار با سیاستِ بزرگ‌شدن — با کلیدهای کاملاً یکسان و همان تابعِ `hash`. **در کدام بازهٔ `n`؟** ۱٬۰۰۰ تا ۸٬۰۰۰ کلید؛ جدولِ ثابت ۱۰۱ خانه و جدولِ بزرگ‌شونده از ۱۱ خانه شروع می‌کند و در سقفِ `GROW_AT = 0.75` می‌ماند. **با چند تکرار، و کمینه یا میانگین؟** جدول‌های گام و جابه‌جایی یک اجرا، چون شمارش‌اند و قطعی؛ جدولِ زمان سه تکرار به‌علاوهٔ گرم‌کننده، کمینه.

> ✅ **چک کن:** `GROW_AT` را از `0.75` به `4.0` ببر و **فقط** جدولِ بخشِ ۳ را دوباره بگیر. **میانگینِ گام باید از حدودِ `1.3` به حدودِ `2.2` برود و ستونِ نسبت باید هنوز نزدیکِ `1` بماند** — چون جدول همچنان بزرگ می‌شود، فقط دیرتر. اگر ستونِ نسبت به `2` رفت، احتمالاً به‌جای `GROW_AT` شرطِ `t[STEP] + 1 < len(TABLE_SIZES)` را دست زده‌ای و جدول از یک جایی به بعد اصلاً بزرگ نمی‌شود.

> 🤖 **از دستیارت بپرس:** «در یک `hash table` با `chaining`، چرا `load factor` مهم‌تر از تعدادِ کلیدهاست؟» بعد این را هم بپرس: **«اگر به‌جای دو برابر کردنِ اندازه، هر بار صد خانه اضافه کنم، کلِ کارِ `rehash`ها چه شکلی رشد می‌کند؟»** — جوابِ درست `O(n²)` است و باید بتواند بگوید چرا؛ اگر دستیارت گفت «فرقی نمی‌کند»، جدولِ بخشِ ۴ را با همان تغییر بگیر و جلویش بگذار.

## واژه‌های تازهٔ این فصل

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| `hash table` | هَش تیبل | ساختاری که جای هر کلید را از `hash`ش حساب می‌کند |
| `bucket` | باکِت | یک خانهٔ جدول، که هر تعداد جفت می‌تواند داشته باشد |
| `chaining` | چینینگ | نگه داشتنِ کلیدهای هم‌خانه در یک فهرستِ کوچک، کنارِ هم |
| `load factor` | لود فَکتور | نسبتِ تعدادِ کلیدها به تعدادِ خانه‌ها |
| `rehash` | ری‌هَش | ساختنِ جدولِ بزرگ‌تر و جا دادنِ دوبارهٔ همهٔ کلیدها |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: چرا با عوض شدنِ اندازهٔ جدول، جای همهٔ کلیدها عوض می‌شود؟

**تمرینِ اجباری:** تابعِ `table_delete(buckets, key)` را بنویس که یک جفت را از `bucket`ش بردارد و بگوید موفق شد یا نه. حالا آزمایشی طراحی کن که نشان بدهد **حذف، `load factor` را پایین می‌آورد ولی اندازهٔ جدول را کوچک نمی‌کند** — و جدولِ چهار اندازه‌ای‌اش را بگیر. **سؤالِ اصلی: بعد از حذفِ نُه‌دهمِ کلیدها، میانگینِ گام چقدر می‌شود و چه چیزی هدر رفته؟** جوابت باید یک عددِ حافظه هم داشته باشد، نه فقط یک عددِ گام.

**تمرینِ ستاره‌دار ⭐:** `TABLE_SIZES` را با توان‌های دو عوض کن — `(8, 16, 32, …)` — و کلیدها را از `POOL` به `[f"unit-{i}" for i in range(n)]` تغییر بده. **قبل از اجرا پیش‌بینی کن** میانگینِ گام و بلندترین زنجیر چه می‌شوند و **از کدام بخشِ فصلِ ۲ پیش‌بینی‌ات را درآورده‌ای**. حالا اجرا کن و خطای پیش‌بینی‌ات را بنویس. بعد سؤالِ آخر: **کدام‌یک از دو تغییر مقصر بود، اندازه‌ها یا کلیدها؟** برای جواب دادن باید هر کدام را جدا عوض کنی.

## در فصل بعد

جدولِ بخشِ ۳ می‌گوید میانگینِ گام `1.32` است. فصلِ بعد همان ساختار را با کلیدهایی پر می‌کند که **کسی عمداً برایش ساخته** و همان عدد به `256.50` می‌رسد.

آن‌جا سه پرسشِ متفاوت را از هم جدا می‌کنیم — بدترین حالت، حالتِ متوسط، و حالتی که واقعاً داری — و می‌بینیم چرا گزارش کردنِ فقط یکی از این سه، گمراه‌کننده است. **و یک جدول هم می‌آید که میانگینش `4.17` است و بدترین گامش `53`؛ همان جدولی که اگر فقط میانگینش را گزارش کنی، هیچ چیزِ مهمی نگفته‌ای.**

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t3/s03-hash-table-by-hand (یادستان, Yaadestan)
