# فصل ۰۲ — `hash`: از کلید تا شمارهٔ خانه

<div dir="rtl">

# فصل ۰۲ — `hash`: از کلید تا شمارهٔ خانه

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

فصلِ قبل نشان داد که گشتن گران است. راهِ نگشتن این است که **جای هر کلید را حساب کنیم**: تابعی که هر کلیدی را به یک عدد تبدیل کند، و آن عدد شمارهٔ خانه‌اش باشد. اسمِ آن تابع `hash` است و این فصل دو نسخه‌اش را می‌سازد.

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

![دستگاهی که برگه‌های متفاوت را از یک قیف می‌گیرد و هرکدام را به یکی از خانه‌های شماره‌دار می‌اندازد](/lesson-assets/t3-s02-hash-function/prompt/01-image-key-to-slot.png)

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

- یک تابعِ `hash` بنویسی و پخشش را با عدد اندازه بگیری، نه با حدس
- بگویی چرا اندازهٔ جدول با خودِ تابعِ `hash` معامله می‌کند
- توضیح بدهی چرا `hash` یک رشته در پایتون قابلِ ذخیره کردن نیست

## قبل از شروع

**از فصلِ ۱:** جست‌وجوی خطی، و اینکه پرسشِ عضویت روی ظرفِ ترتیبی `O(n)` است.

**از ترمِ ۱ فصلِ ۴:** شمارندهٔ عملیات — در این فصل هم شمارش را بر ثانیه ترجیح می‌دهیم.

</div>

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

<div dir="rtl">

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

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

فرض کن هشت خانه داری و کلیدهایت عددِ صحیح‌اند. ساده‌ترین راهِ تبدیلِ یک کلید به شمارهٔ خانه، **باقی‌ماندهٔ تقسیم** است — همان `%` پایتون.

> 🌱 **ریشه‌اش کجاست:** باقی‌مانده در [ریشه ترمِ ۱ فصل ۵](/courses/risheh/lessons/term-1-numbers/session-05-divide) به‌عنوانِ «چه چیزی جا نشد» ساخته می‌شود: ۲۵ شکلات بینِ ۸ نفر، هر نفر ۳ تا و **۱ تا روی میز**. **دو خاصیتش دقیقاً همان دو چیزی است که این ترم را ممکن می‌کند** — باقی‌مانده همیشه از مقسومٌ‌علیه کوچک‌تر است (پس هر کلیدی به یک خانهٔ معتبر می‌افتد)، و برای هر ورودی یکتاست (پس همان کلید همیشه به همان خانه می‌رود).

</div>

```python
BOXES = 8
for key in (17, 25, 3, 40):
    print(f"کلید {key:>3}  →  خانهٔ {key % BOXES}")
```

```text
کلید  17  →  خانهٔ 1
کلید  25  →  خانهٔ 1
کلید   3  →  خانهٔ 3
کلید  40  →  خانهٔ 0
```

<div dir="rtl">

**چهار کلید، سه خانه.** `17` و `25` هر دو به خانهٔ `1` رفتند و این اصلاً خطا نیست: هشت خانه داریم و بی‌نهایت کلیدِ ممکن، پس **هم‌خانه شدن اجتناب‌ناپذیر است**. اسمش برخورد است و فصلِ بعد تکلیفش را روشن می‌کند.

**آنچه این‌جا مهم است این است که هزینهٔ محاسبهٔ خانه، به تعدادِ کلیدهای موجود هیچ ربطی ندارد.** یک تقسیم، تمام. چه ده کلید داشته باشی چه ده میلیون.

## ۲. کلیدهایی که عدد نیستند

کلیدهای واقعی معمولاً رشته‌اند: نامِ کاربر، نشانیِ ایمیل، شناسهٔ سفارش. برای این‌ها اول باید یک عدد ساخت.

**و پایتون خودش راهِ ساختنِ عدد از یک نویسه را دارد: `ord`.** هر نویسه در کامپیوتر یک شمارهٔ ثابت دارد و `ord` همان شماره را می‌دهد.

</div>

```python
print(ord("a"), ord("b"), ord("A"), ord("-"), ord("0"))
```

```text
97 98 65 45 48
```

<div dir="rtl">

**`a` و `b` پشتِ سرِ هم‌اند و `A` جای کاملاً دیگری است.** این عددها قرارداد هستند و **تنها چیزی که برای ما اهمیت دارد ثابت بودنشان است** — `ord("a")` در هر اجرا و روی هر ماشینی `97` است. **کلِ کاری که یک `hash` رشته‌ای می‌کند این است که این عددها را طوری با هم قاطی کند که نتیجه خوب پخش شود.** دو تابع می‌نویسیم که کیفیتشان زمین تا آسمان فرق دارد.

</div>

```python
def sum_hash(key):
    """ساده‌ترین hash ممکن: کدِ عددیِ حرف‌ها را جمع می‌زند."""
    h = 0
    for ch in str(key):
        h += ord(ch)
    return h


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


for word in ("abc", "bca", "cba"):
    print(f"{word}   sum_hash={sum_hash(word):>8}   poly_hash={poly_hash(word):>8}")
```

```text
abc   sum_hash=     294   poly_hash=   96354
bca   sum_hash=     294   poly_hash=   97344
cba   sum_hash=     294   poly_hash=   98274
```

<div dir="rtl">

**سه کلیدِ متفاوت، یک عددِ یکسان از `sum_hash`.** جمع کردن جای حرف‌ها را نمی‌بیند، پس هر جابه‌جاییِ حروف به همان عدد می‌رسد — و در دادهٔ واقعی، کلیدهایی که حروفِ یکسان دارند اصلاً کم نیستند.

`poly_hash` قبل از هر جمع، عددِ قبلی را در `31` ضرب می‌کند. **همین یک ضرب کافی است تا جای هر حرف در نتیجه اثر بگذارد.** باقی‌ماندهٔ `1_000_003` هم فقط برای این است که عدد بی‌نهایت بزرگ نشود.

## ۳. پخشِ یکنواخت، با عدد

«خوب پخش می‌کند» یک ادعاست و در این دوره ادعا بدونِ اندازه‌گیری قبول نمی‌شود. دو هزار کلیدِ شبیهِ کلیدهای واقعی می‌سازیم و می‌شماریم در هر خانه چند تا می‌افتد.

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

</div>

```python
def spread(fn, keys, size):
    """چند کلید در هر خانه می‌افتد."""
    counts = [0] * size
    for k in keys:
        counts[fn(k) % size] += 1
    return counts


def report(fn, name, keys, size):
    counts = spread(fn, keys, size)
    print(f"{name:>10}  اندازهٔ جدول {size:>4}:"
          f"  خانهٔ خالی {sum(1 for c in counts if c == 0):>3}"
          f"  ·  کم‌جمعیت‌ترین {min(counts):>3}"
          f"  ·  پرجمعیت‌ترین {max(counts):>3}")


KEYS = [f"unit-{i}" for i in range(2_000)]
report(sum_hash, "sum_hash", KEYS, 67)
report(poly_hash, "poly_hash", KEYS, 67)
```

```text
  sum_hash  اندازهٔ جدول   67:  خانهٔ خالی   1  ·  کم‌جمعیت‌ترین   0  ·  پرجمعیت‌ترین  75
 poly_hash  اندازهٔ جدول   67:  خانهٔ خالی   0  ·  کم‌جمعیت‌ترین  26  ·  پرجمعیت‌ترین  33
```

<div dir="rtl">

**`sum_hash` یک خانه با هفتاد و پنج کلید ساخته و یک خانه را کاملاً خالی گذاشته. `poly_hash` همه‌چیز را بینِ ۲۶ و ۳۳ نگه داشته.**

و این عددها معنایی مستقیم دارند: **پرجمعیت‌ترین خانه، بدترین حالتِ یک جست‌وجوست.** با `sum_hash` بدترین پرسش هفتاد و پنج مقایسه می‌خواهد، با `poly_hash` سی و سه. **همان کلیدها، همان جدول، فقط تابعِ متفاوت.**

## ۴. جدول هم در معامله شریک است

حالا `poly_hash` را ثابت نگه می‌داریم و فقط **اندازهٔ جدول** را از ۶۷ به ۶۴ می‌بریم — از یک عددِ اول به یک توانِ دو.

</div>

```python
report(poly_hash, "poly_hash", KEYS, 67)
report(poly_hash, "poly_hash", KEYS, 64)
```

```text
 poly_hash  اندازهٔ جدول   67:  خانهٔ خالی   0  ·  کم‌جمعیت‌ترین  26  ·  پرجمعیت‌ترین  33
 poly_hash  اندازهٔ جدول   64:  خانهٔ خالی   0  ·  کم‌جمعیت‌ترین   1  ·  پرجمعیت‌ترین  66
```

<div dir="rtl">

**تابع عوض نشد، کلیدها عوض نشدند، و پرجمعیت‌ترین خانه از ۳۳ به ۶۶ رفت — دقیقاً دو برابر.** یک خانه هم فقط یک کلید گرفته.

دلیلش این است که کلیدهای واقعی ساختار دارند — و **این ادعا را همین‌جا می‌سازیم، از هیچ‌جا قرض نگرفته‌ایم.**

**اول با دست.** دنبالهٔ `0، 4، 8، 12، 16، …` را در نظر بگیر که هر بار `4` تا جلو می‌رود. **مانده‌اش بر `8` می‌شود `0، 4، 0، 4، …` — فقط دو خانه از هشت‌تا؛ و مانده‌اش بر `7` می‌شود `0، 4، 1، 5، 2، 6، 3، …` — هر هفت خانه.**

**تفاوت در یک کلمه است: `4` و `8` مقسومٌ‌علیهِ مشترک دارند و `4` و `7` ندارند.** اگر گامِ دنباله و تعدادِ خانه‌ها مقسومٌ‌علیهِ مشترکی مثلِ `d` داشته باشند، دنباله فقط به **یک `d`ام** از خانه‌ها می‌رسد. **و عددِ اول با هیچ عددِ کوچک‌تر از خودش مقسومٌ‌علیهِ مشترک ندارد.**

**حالا ببینیم `hash`های ما واقعاً چنین گامی دارند یا نه:**

</div>

```python
from collections import Counter

gaps = Counter(poly_hash(KEYS[i + 1]) - poly_hash(KEYS[i]) for i in range(len(KEYS) - 1))
print("پرتکرارترین گام‌های بینِ hashهای پیاپی:", gaps.most_common(3))

lattice = [22 * i for i in range(80)]
print("یک دنباله با گامِ ثابتِ ۲۲، هشتاد عضو:")
print("  بر ۶۴:", len({v % 64 for v in lattice}), "مانده از ۶۴")
print("  بر ۶۷:", len({v % 67 for v in lattice}), "مانده از ۶۷")
```

```text
پرتکرارترین گام‌های بینِ hashهای پیاپی: [(1, 1800), (22, 179), (673, 17)]
یک دنباله با گامِ ثابتِ ۲۲، هشتاد عضو:
  بر ۶۴: 32 مانده از ۶۴
  بر ۶۷: 67 مانده از ۶۷
```

<div dir="rtl">

**دو هزار کلید و فقط سه گامِ پرتکرار: `1`، `22` و `673`.** یعنی `hash`های ما اصلاً پخش‌وپلا نیستند؛ **رشته‌های ده‌تاییِ پشتِ سرِ هم‌اند که با پرش‌های `22` تایی از هم جدا می‌شوند** — و `22` با `64` مقسومٌ‌علیهِ مشترکِ `2` دارد. **همان دنباله بر `64` نصفِ خانه‌ها را می‌بیند و بر `67` همه را.**

**قاعدهٔ عملی‌ای که از این درمی‌آید و تا آخرِ ترم به‌کارش می‌بریم: اندازهٔ جدول را عددِ اول بگیر.** و قاعدهٔ کلی‌ترش مهم‌تر است: **کیفیتِ پخش، خاصیتِ تابعِ `hash` تنها نیست؛ خاصیتِ سه‌تاییِ تابع، اندازهٔ جدول، و کلیدهای واقعیِ توست.**

## ۵. برخورد وقتی جدول بزرگ نشود

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

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

</div>

```python
def collisions(fn, keys, size):
    """چند جفت کلید هم‌خانه شده‌اند."""
    pairs = 0
    for c in spread(fn, keys, size):
        pairs += c * (c - 1) // 2
    return pairs


rng = random.Random(SEED)
RANDOM_KEYS = [f"user-{rng.randrange(10 ** 9)}" for _ in range(2_000)]
FIXED = 1_031
table([(n, collisions(poly_hash, RANDOM_KEYS[:n], FIXED))
       for n in (250, 500, 1_000, 2_000)], "جفتِ هم‌خانه", ",d")
```

```text
         n      جفتِ هم‌خانه     نسبت به سطر قبل
       250                27                   —
       500               114                4.22
     1,000               444                3.89
     2,000             1,946                4.38
```

<div dir="rtl">

**حولِ `4`.** برخورد با **مربعِ** تعدادِ کلیدها بالا می‌رود، نه پابه‌پای آن — چون هر جفتِ ممکن یک شانسِ هم‌خانه شدن دارد و تعدادِ جفت‌ها خودش با مربعِ `n` می‌رود (همان `all_pairs` ترمِ ۱ فصلِ ۵).

**نتیجهٔ عملی‌اش صریح است: جدولی که بزرگ نشود، دیر یا زود شلوغ می‌شود، و آن‌وقت `hash` دیگر کمکی نمی‌کند.** فصلِ بعد دقیقاً همین را حل می‌کند.

## ۶. هزینهٔ خودِ `hash`

یک نگرانیِ به‌جا: اگر `hash` گران باشد، کلِ ماجرا بی‌فایده است. پس بشماریمش.

</div>

```python
def poly_hash_counted(key):
    """همان poly_hash، با شمارندهٔ گام."""
    h = 0
    ops = 0
    for ch in str(key):
        h = (h * 31 + ord(ch)) % 1_000_003
        ops += 1
    return h, ops


table([(length, poly_hash_counted("x" * length)[1])
       for length in (250, 500, 1_000, 2_000)], "گامِ hash", ",d")
```

```text
         n         گامِ hash     نسبت به سطر قبل
       250               250                   —
       500               500                2.00
     1,000             1,000                2.00
     2,000             2,000                2.00
```

<div dir="rtl">

**دقت کن ستونِ `n` این جدول چیزِ دیگری است: `n` این‌جا طولِ کلید است، نه تعدادِ کلیدها.** و نتیجه صریح است: هزینهٔ `hash` با طولِ کلید خطی می‌رود و **به تعدادِ کلیدهای داخلِ جدول هیچ ربطی ندارد.**

پس اگر کلیدها کوتاه باشند — که تقریباً همیشه هستند — هزینهٔ `hash` یک عددِ ثابتِ کوچک است. **این همان چیزی است که کلِ ایده را ممکن می‌کند.**

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** دو تابعِ `hash` روی کلیدهای یکسان و جدولِ یکسان؛ بعد یک تابعِ ثابت روی دو اندازهٔ متفاوتِ جدول. **در کدام بازهٔ `n`؟** دو هزار کلید در جدولِ ۶۴ و ۶۷ خانه‌ای برای پخش، ۲۵۰ تا ۲٬۰۰۰ کلید در جدولِ ۱٬۰۳۱ خانه‌ای برای برخورد، و طولِ کلیدِ ۲۵۰ تا ۲٬۰۰۰ برای هزینهٔ خودِ `hash`. **با چند تکرار، و کمینه یا میانگین؟** یک اجرا؛ هر سه اندازه‌گیری شمارش‌اند و شمارش قطعی است.

## ۷. `hash` خودِ پایتون

پایتون تابعِ `hash` را از قبل دارد و `set` و `dict` از همان استفاده می‌کنند.

</div>

```python
print("hash(1)       =", hash(1))
print("hash(1.0)     =", hash(1.0))
print("hash(True)    =", hash(True))
print("hash(-1)      =", hash(-1))
print("hash(10 ** 20) =", hash(10 ** 20))
```

```text
hash(1)       = 1
hash(1.0)     = 1
hash(True)    = 1
hash(-1)      = -2
hash(10 ** 20) = 848750603811160107
```

<div dir="rtl">

سه چیز در این خروجی هست. **اول:** `hash` یک عددِ صحیحِ کوچک، خودِ آن عدد است. **دوم:** `1` و `1.0` و `True` هر سه `hash` یکسان دارند، چون در پایتون با هم برابرند — و این قاعده‌ای است که فصلِ ۶ کاملاً بازش می‌کند. **سوم:** `hash(-1)` برابرِ `-2` است، چون پایتون `-1` را برای اعلامِ خطا نگه داشته.

## ۸. چرا `hash` یک رشته بینِ دو اجرا عوض می‌شود

حالا مهم‌ترین نکتهٔ این فصل. پایتون را دو بار در دو فرایندِ جدا اجرا می‌کنیم و از هرکدام `hash` یک رشته و `hash` یک عدد را می‌گیریم.

</div>

```python
import os
import subprocess

PROBE = "print(hash('bonyad'), hash(12345))"


def probe_with_seed(seed):
    """پایتون را در یک فرایندِ تازه، با یک PYTHONHASHSEED مشخص، اجرا می‌کند."""
    env = dict(os.environ)
    env["PYTHONHASHSEED"] = str(seed)
    done = subprocess.run([sys.executable, "-c", PROBE],
                          capture_output=True, text=True, env=env)
    text_hash, int_hash = done.stdout.split()
    return int(text_hash), int(int_hash)


first = probe_with_seed(1)
second = probe_with_seed(2)
print("hash('bonyad') در دو اجرا یکی است؟", first[0] == second[0])
print("hash(12345)    در دو اجرا یکی است؟", first[1] == second[1])
```

```text
hash('bonyad') در دو اجرا یکی است؟ False
hash(12345)    در دو اجرا یکی است؟ True
```

<div dir="rtl">

**`hash` عدد ثابت است و `hash` رشته نیست.** خودِ عددها را هم ببین:

</div>

```python
print("اجرای اول:", first)
print("اجرای دوم:", second)
```

```text-approx
اجرای اول: (2613271495042824151, 12345)
اجرای دوم: (3016696591514293467, 12345)
```

<div dir="rtl">

پایتون هنگامِ شروع یک عددِ تصادفی می‌سازد و آن را در `hash` هر رشته‌ای دخالت می‌دهد. دلیلش امنیت است: بدونِ این کار، هر کسی می‌توانست از پیش کلیدهایی بسازد که همه در یک خانه بیفتند و سرویس را زمین بزند — همان حمله‌ای که فصلِ ۴ با دست بازسازی‌اش می‌کند.

**و دو نتیجهٔ عملیِ سخت‌گیرانه از این درمی‌آید:**

1. **`hash` یک رشته را هرگز ذخیره نکن و بینِ دو اجرا مقایسه‌اش نکن.** عددی که دیروز نوشتی، امروز کلیدِ دیگری است.
2. **هر عددی که از `hash` یک رشته درمی‌آید، بازتولیدپذیر نیست.** برای همین در همین کتاب، خروجیِ بالا در بلوکی آمده که دروازهٔ وارسیِ ما آن را مقایسه نمی‌کند — درست مثلِ هر عددِ ثانیه‌ای. **و برای همین `poly_hash` خودمان را نوشتیم:** جدولِ فصلِ بعد باید روی ماشینِ تو هم دقیقاً همان عددها را بدهد.

> ✅ **چک کن:** در `poly_hash` عددِ `31` را به `1` تغییر بده و بخشِ ۳ را دوباره اجرا کن. **باید دقیقاً همان عددهای `sum_hash` را بگیری** — چون ضرب در یک، یعنی اصلاً ضربی در کار نیست. اگر عددها فرق داشتند، احتمالاً به‌جای `31` جای دیگری از تابع را دست زده‌ای؛ خطِ حلقه را با نسخهٔ اصلی حرف‌به‌حرف مقایسه کن.

> 🔧 **اگر کار نکرد:** یکی از رایج‌ترین لغزش‌ها این است که یادت برود کلید را اول از `hash` رد کنی و مستقیم باقی‌ماندهٔ خودِ کلید را بگیری:

</div>

```python
try:
    print("unit-7" % 64)
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
TypeError: not all arguments converted during string formatting
```

<div dir="rtl">

پیامِ خطا اصلاً دربارهٔ باقی‌مانده حرف نمی‌زند و همین گیج‌کننده‌اش می‌کند: علامتِ `%` روی رشته معنیِ کاملاً دیگری دارد — قالب‌بندی. **این نمونهٔ خوبی از خطایی است که متنش تو را به جای اشتباه راهنمایی می‌کند؛** چیزی که کم داری، `poly_hash(...)` دورِ کلید است.

> 🤖 **از دستیارت بپرس:** «چرا ضرب کردن در یک عددِ اول، `hash` یک رشته را بهتر پخش می‌کند؟» بعد این را هم بپرس: **«چرا پایتون `hash` رشته‌ها را تصادفی می‌کند ولی `hash` عددهای صحیح را نه؟»** — جوابِ درست باید بگوید چه کسی می‌تواند کلیدها را انتخاب کند؛ اگر دستیارت فقط گفت «برای امنیت»، بپرس امنیت در برابرِ **چه کسی**.

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| `ord` | اُرد | شمارهٔ ثابتی که هر نویسه در کامپیوتر دارد |
| `hash` | هَش | تابعی که هر کلید را به یک عدد تبدیل می‌کند |
| hash function | هَش فانکشن | خودِ آن تابع، به‌عنوان یک انتخابِ طراحی |
| collision | کولیژن | دو کلیدِ متفاوت که به یک خانه می‌افتند |
| uniform spread | یونیفرم اسپرد | پخشِ کلیدها به‌طورِ تقریباً یکسان بینِ همهٔ خانه‌ها |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: چرا پرجمعیت‌ترین خانه مهم‌تر از میانگینِ خانه‌هاست؟

**تمرینِ اجباری:** یک دستهٔ کلیدِ دیگر بساز — مثلاً نشانیِ ایمیلِ ساختگی به شکلِ `user-<عدد>@example.com` — و هر چهار ترکیبِ بخشِ ۳ و ۴ را رویش بگیر: دو تابع، دو اندازهٔ جدول. **سؤالِ اصلی: آیا تفاوتِ ۶۴ و ۶۷ روی این کلیدها هم به همان بزرگی است؟** جوابت باید بگوید ساختارِ این کلیدها با ساختارِ `unit-<عدد>` چه فرقی دارد.

**تمرینِ ستاره‌دار ⭐:** تابعی بنویس که بدترین کلیدهای ممکن را برای `sum_hash` بسازد: صد کلیدِ متفاوت که همه‌شان `hash` یکسان بدهند. (راهنمایی: جابه‌جا کردنِ حروفِ یک کلمه.) **قبل از اجرا پیش‌بینی کن** پرجمعیت‌ترین خانه چند می‌شود، بعد اندازه بگیر. حالا سؤالِ سخت: **همین کار را برای `poly_hash` چقدر سخت‌تر است؟** لازم نیست انجامش بدهی؛ کافی است بگویی چرا، و بگویی این «سخت‌تر بودن» دقیقاً همان چیزی است که فصلِ ۴ سراغش می‌رود.

## در فصل بعد

حالا هم تابعِ `hash` را داریم و هم می‌دانیم برخورد اجتناب‌ناپذیر است. فصلِ بعد از این دو، یک ساختارِ کامل می‌سازد: **`hash table`، با دست، از صفر** — با `bucket` و `chaining` و `load factor`.

و همان‌جا دو جدول کنارِ هم می‌آید که کلِ ترم را خلاصه می‌کنند. جدولِ اول برای جدولی است که هرگز بزرگ نمی‌شود: **میانگینِ گام‌های جست‌وجو از `6.03` به `40.56` می‌رود، با ستونِ نسبتِ نزدیکِ `2`.** جدولِ دوم همان کلیدها را در جدولی می‌ریزد که خودش را بزرگ می‌کند: **میانگینِ گام `1.33` شروع می‌شود و در آخرین سطر `1.32` است.**

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t3/s02-hash-function (یادستان, Yaadestan)
