# فصل ۰۶ — چه چیزی می‌تواند کلید باشد — و چرا

<div dir="rtl">

# فصل ۰۶ — چه چیزی می‌تواند کلید باشد — و چرا

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

تا حالا هر کلیدی که به `set` و `dict` داده‌ایم رشته یا عدد بوده. این فصل می‌پرسد **چه چیزی اصلاً می‌تواند کلید باشد**، و از یک خطای واقعی شروع می‌کند: `TypeError: unhashable type: 'list'`.

بعد قاعده‌ای را می‌بینی که پشتِ آن خطاست، و یک `dict` که **سه بار درج می‌شود و آخرش یک عضو دارد**. آخرِ فصل هم، با همان `hash table` دست‌سازِ فصلِ ۳، کلیدی را که بعد از درج عوض شده گم می‌کنیم — **در حالی که خودش هنوز همان‌جا داخلِ `bucket` نشسته و کاملاً دیده می‌شود.**

![کلیدی که بعد از ساخته شدنِ قفل، دندانه‌هایش تغییر کرده و دیگر در همان قفل نمی‌چرخد](/lesson-assets/t3-s06-what-can-be-a-key/prompt/01-image-key-that-changed.png)

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

- بگویی `hashable` بودن یعنی چه و چرا `list` نیست
- قاعدهٔ هم‌خوانیِ `__hash__` و `__eq__` را با یک مثالِ اجراشدنی توضیح بدهی
- کلیدِ مرکب بسازی و هزینه‌اش را اندازه بگیری

## قبل از شروع

**از فصلِ ۲:** `hash` به‌عنوان تابعی که کلید را به عدد تبدیل می‌کند، و اینکه `hash(1)` و `hash(1.0)` و `hash(True)` یکی‌اند.

**از فصلِ ۳:** `poly_hash`، `bucket` و `chaining`. کدِ همان جدول این‌جا دوباره می‌آید.

</div>

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

<div dir="rtl">

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

## ۱. خطایی که همه یک بار می‌گیرند

</div>

```python
seen = set()
seen.add("user-1")
seen.add(("user", 1))
print("تا اینجا مشکلی نیست:", len(seen))
try:
    seen.add(["user", 1])
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
تا اینجا مشکلی نیست: 2
TypeError: unhashable type: 'list'
```

<div dir="rtl">

> 🔧 **اگر کار نکرد:** پیام دقیقاً می‌گوید چه چیزی کم است: `list` قابلِ `hash` گرفتن نیست. **راهِ حل تقریباً همیشه یک نویسه است — `[` را به `(` عوض کن** و همان محتوا در یک `tuple` می‌نشیند که `hashable` است. اگر محتوا باید تغییرپذیر بماند، آن‌وقت اصلاً نباید کلید باشد؛ باید **مقدار** باشد.

و همین‌جا سؤالِ اصلیِ فصل درمی‌آید: **چرا `tuple` می‌تواند و `list` نمی‌تواند؟**

## ۲. `hashable` یعنی چه

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

از این یک شرط درمی‌آید: **چیزی می‌تواند کلید باشد که `hash`ش در تمامِ عمرش ثابت بماند.** پایتون این را با یک قاعدهٔ ساده‌تر تضمین می‌کند: **چیزهایی که می‌شود تغییرشان داد، `hashable` نیستند.** `list` تغییرپذیر است، `tuple` نیست. `set` تغییرپذیر است، رشته و عدد نیستند.

</div>

```python
print("hash یک tuple:", hash(("a", 1)) == hash(("a", 1)))
try:
    hash(("a", [1]))
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
hash یک tuple: True
TypeError: unhashable type: 'list'
```

<div dir="rtl">

**سطرِ دوم مهم‌تر از سطرِ اول است.** `tuple` خودش تغییرپذیر نیست، ولی می‌تواند چیزِ تغییرپذیری **داخلش** داشته باشد — و آن‌وقت خودش هم `hashable` نیست. `hash` یک `tuple` از `hash` عضوهایش ساخته می‌شود، پس عضوی که `hash` ندارد کلِ `tuple` را از کار می‌اندازد.

## ۳. قاعدهٔ هم‌خوانی: اگر برابرند، `hash`شان هم باید یکی باشد

پایتون دو کارِ جداگانه با یک کلید می‌کند: اول از `hash` جای `bucket` را پیدا می‌کند (پشتِ صحنه `__hash__` صدا زده می‌شود)، بعد داخلِ آن `bucket` با `==` دنبالِ کلید می‌گردد (که `__eq__` است). **این دو باید با هم بخوانند، وگرنه ساختار می‌شکند:**

> **اگر `a == b` باشد، حتماً باید `hash(a) == hash(b)` باشد.**

خلافش لازم نیست: دو چیز می‌توانند `hash` یکسان داشته باشند و برابر نباشند — که همان برخوردِ فصلِ ۲ است و `chaining` تکلیفش را روشن می‌کند.

پایتون خودش این قاعده را رعایت می‌کند، و یک نتیجهٔ عجیب دارد:

</div>

```python
print("1 == 1.0 == True ?", 1 == 1.0 == True)
print("hash(1), hash(1.0), hash(True):", hash(1), hash(1.0), hash(True))

box = {}
box[1] = "اولی"
box[1.0] = "دومی"
box[True] = "سومی"
print("dict بعد از سه درج:", box)
print("طولش:", len(box))
```

```text
1 == 1.0 == True ? True
hash(1), hash(1.0), hash(True): 1 1 1
dict بعد از سه درج: {1: 'سومی'}
طولش: 1
```

<div dir="rtl">

**سه درج، یک عضو.** `1` و `1.0` و `True` در پایتون با هم برابرند، پس از نظرِ `dict` **یک کلیدند** — هر سه به یک `bucket` می‌روند و `==` می‌گوید همان‌اند، پس فقط مقدار جایگزین می‌شود.

**و کلیدِ باقی‌مانده `1` است، نه `True`**: کلید از اولین درج می‌ماند و فقط مقدار به‌روز می‌شود. **این دقیقاً همان کاری است که `table_put` ما در فصلِ ۳ می‌کرد** — آن‌جا هم وقتی کلید پیدا می‌شد، `pair[1]` عوض می‌شد و `pair[0]` دست‌نخورده می‌ماند.

## ۴. کلیدِ مرکب

قاعدهٔ «تغییرناپذیر باشد» یک نتیجهٔ عملیِ مفید دارد: **`tuple` کلیدِ مرکب می‌سازد.** هر جا کلیدت یک چیز نیست و چند چیز است، به‌جای چسباندنشان به هم در یک رشته، `tuple`شان کن.

</div>

```python
grid = {}
grid[(0, 0)] = "خانهٔ شروع"
grid[(1, 2)] = "خانهٔ گنج"
grid[(2, 1)] = "خانهٔ تله"
print(grid)
print("کلیدِ (1, 2):", grid[(1, 2)], "· کلیدِ (2, 1):", grid[(2, 1)])
```

```text
{(0, 0): 'خانهٔ شروع', (1, 2): 'خانهٔ گنج', (2, 1): 'خانهٔ تله'}
کلیدِ (1, 2): خانهٔ گنج · کلیدِ (2, 1): خانهٔ تله
```

<div dir="rtl">

`(1, 2)` و `(2, 1)` دو کلیدِ کاملاً متفاوت‌اند — همان چیزی که با چسباندن به رشته به‌راحتی از دست می‌رفت. **و ترتیبِ چاپ همان ترتیبِ درج است**، چون `dict` ترتیبِ درج را نگه می‌دارد.

## ۵. کلیدی که بعد از درج عوض شود

حالا نشان می‌دهیم اگر پایتون این قید را نمی‌گذاشت، چه اتفاقی می‌افتاد. `hash table` دست‌سازِ فصلِ ۳ چنین قیدی ندارد: `poly_hash` روی `str(key)` کار می‌کند و `str` یک `list` هم به‌راحتی ساخته می‌شود. **پس می‌شود یک `list` را در آن کلید کرد — و بعد عوضش کرد.**

</div>

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


def table_new(size):
    return [[] for _ in range(size)]


def table_put(buckets, key, value):
    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


buckets = table_new(7)
key = [1, 2]
table_put(buckets, key, "گنج")
print("قبل از تغییر  :", table_get(buckets, [1, 2]))
key.append(3)                                  # همان list، حالا یک عضو بیشتر
print("دنبالِ [1, 2]  :", table_get(buckets, [1, 2]))
print("دنبالِ [1, 2, 3]:", table_get(buckets, [1, 2, 3]))
print("ولی هنوز اینجاست:", [b for b in buckets if b])
```

```text
قبل از تغییر  : ('گنج', 1)
دنبالِ [1, 2]  : (None, 1)
دنبالِ [1, 2, 3]: (None, 0)
ولی هنوز اینجاست: [[[[1, 2, 3], 'گنج']]]
```

<div dir="rtl">

**سه سطرِ آخر را با هم بخوان؛ هر کدام نصفِ داستان‌اند.**

- **`[1, 2]` پیدا نمی‌شود:** `hash` همان است، پس به `bucket` درست می‌رویم و یک گام هم برمی‌داریم — ولی جفتی که آن‌جاست دیگر با `[1, 2]` برابر نیست.
- **`[1, 2, 3]` هم پیدا نمی‌شود:** این بار `hash` عوض شده، پس اصلاً به `bucket` اشتباهی می‌رویم که خالی است — **صفر گام.**
- **و مقدار هنوز سرِ جایش است.** هیچ چیزی گم نشده و هیچ خطایی هم بلند نشده؛ فقط دیگر هیچ راهی به آن نیست.

**این بدترین حالتی است که یک ساختارِ داده می‌تواند به تو بدهد: نه خطا، نه پیام، فقط دادهٔ غیرقابلِ دسترسی.** و دقیقاً برای جلوگیری از همین است که پایتون `list` را از کلید بودن محروم می‌کند — **قید، محدودیت نیست؛ ضمانت است.**

## ۶. هزینهٔ کلیدِ مرکب

کلیدِ `tuple` رایگان نیست: `hash` گرفتن از آن یعنی `hash` گرفتن از هر عضوش.

> 🤔 **اول حدس بزن:** اگر تعدادِ عضوهای `tuple` دو برابر شود، تعدادِ گام‌های `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(("ab",) * length)[1])
       for length in (250, 500, 1_000, 2_000)], "گامِ hash", ",d")
```

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

<div dir="rtl">

**`2.00`. `n` این‌جا تعدادِ عضوهای `tuple` است، نه تعدادِ کلیدها.** پس هزینهٔ `hash` با **اندازهٔ کلید** خطی است — همان نتیجهٔ فصلِ ۲، این بار برای کلیدِ مرکب.

**نتیجهٔ عملی: کلیدِ کوچک نگه دار.** یک `tuple` دوتایی عملاً رایگان است؛ یک `tuple` هزارتایی به‌ازای هر `lookup` هزار گام خرج می‌کند و آن‌وقت دیگر «هزینهٔ ثابت» حرفِ بی‌معنایی است.

و حالا سؤالِ دیگر: با ثابت ماندنِ اندازهٔ کلید، آیا `lookup` با کلیدِ `tuple` هنوز به تعدادِ کلیدها بی‌اعتناست؟

</div>

```python
rng = random.Random(SEED)
LADDER = [25_000, 50_000, 100_000, 200_000]
base = [(rng.randrange(10 ** 6), rng.randrange(10 ** 6)) for _ in range(200_000)]
maps = {n: {k: 1 for k in base[:n]} for n in LADDER}
asks = [base[rng.randrange(25_000)] if i % 2 == 0
        else (rng.randrange(10 ** 6), rng.randrange(10 ** 6)) for i in range(100_000)]


def hits_in(container, qs):
    hits = 0
    for q in qs:
        if q in container:
            hits += 1
    return hits


print("تعدادِ «بله» در همهٔ اندازه‌ها یکی است؟",
      len({hits_in(maps[n], asks) for n in LADDER}) == 1)
table([(n, 1000 * clock(lambda c=maps[n]: hits_in(c, asks), repeat=3))
       for n in LADDER], "زمان (ms)", ",.1f")
```

```text-approx
تعدادِ «بله» در همهٔ اندازه‌ها یکی است؟ True
         n         زمان (ms)     نسبت به سطر قبل
    25,000               6.7                   —
    50,000               6.9                1.03
   100,000               8.9                1.29
   200,000              10.8                1.22
```

<div dir="rtl">

**نزدیکِ `1`، با یک بالا رفتنِ ملایم.** صد هزار پرسش، و هشت برابر شدنِ `dict` زمان را کمتر از دو برابر کرد — نه هشت برابر. **آن بالا رفتنِ ملایم `Big-O` نیست؛ همان اثرِ حافظه است که فصلِ قبل هم دیدیمش.**

> 📏 **اندازه بگیر:** **چه چیزی با چه چیزی مقایسه شد؟** یک `dict` با کلیدِ `tuple`، در چهار اندازه، با پرسش‌های کاملاً یکسان و جوابِ تأییدشدهٔ برابر. **در کدام بازهٔ `n`؟** ۲۵٬۰۰۰ تا ۲۰۰٬۰۰۰ کلید با صد هزار پرسشِ ثابت برای زمان، و طولِ کلیدِ ۲۵۰ تا ۲٬۰۰۰ برای هزینهٔ `hash`. **با چند تکرار، و کمینه یا میانگین؟** جدولِ گام یک اجرا چون شمارش قطعی است؛ جدولِ زمان سه تکرار به‌علاوهٔ گرم‌کننده، کمینه.

> ✅ **چک کن:** در بخشِ ۵، خطِ `key.append(3)` را به `key = [1, 2, 3]` تغییر بده. **حالا سطرِ «دنبالِ [1, 2]» جواب می‌دهد و سطرِ آخر هم `[1, 2]` را نشان می‌دهد؛ فقط سطرِ «دنبالِ [1, 2, 3]» همان `(None, 0)` می‌ماند.** دلیلش این است که این خط `list` را عوض نمی‌کند، فقط نامِ `key` را به یک `list` تازه وصل می‌کند — و آنی که داخلِ جدول نشسته دست‌نخورده می‌ماند. **همین تفاوت، تفاوتِ «تغییر دادن» و «جایگزین کردن» است.**

> 🤖 **از دستیارت بپرس:** «چرا `tuple` می‌تواند کلیدِ `dict` باشد ولی `list` نه؟» بعد این را هم بپرس: **«اگر `tuple`ام یک `list` داخلش داشته باشد چه؟»** — جوابِ درست باید بگوید `hash` یک `tuple` از عضوهایش ساخته می‌شود؛ اگر دستیارت گفت «`tuple` همیشه `hashable` است»، خروجیِ بخشِ ۲ را جلویش بگذار.

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| `hashable` | هَشِبل | چیزی که `hash` دارد و `hash`ش هرگز عوض نمی‌شود |
| immutable | ایمیوتِبل | تغییرناپذیر؛ بعد از ساخته شدن عوض نمی‌شود |
| `__hash__` | دانِدر هَش | کاری که پایتون برای گرفتنِ `hash` یک چیز صدا می‌زند |
| `__eq__` | دانِدر ایکیو | کاری که پایتون برای مقایسهٔ دو چیز با `==` صدا می‌زند |
| composite key | کامپوزیت کی | کلیدی که از چند بخش ساخته شده، معمولاً یک `tuple` |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: قاعدهٔ هم‌خوانیِ `__hash__` و `__eq__` را در یک جمله بنویس.

**تمرینِ اجباری:** یک `dict` بساز که کلیدش `tuple` سه‌تاییِ `(سال, ماه, روز)` است و مقدارش تعدادِ رویدادهای آن روز. حالا همان کار را با کلیدِ رشته‌ایِ `"۱۴۰۵-۰۳-۱۲"` هم بنویس و **زمانِ ساختِ هر دو را در چهار اندازه اندازه بگیر**. **سؤالِ اصلی: کدام گران‌تر است و چرا؟** جوابت باید هم به تعدادِ عضوهای کلید اشاره کند و هم به هزینهٔ ساختنِ خودِ رشته.

**تمرینِ ستاره‌دار ⭐:** با `hash table` دست‌سازِ فصلِ ۳ ساختاری بساز که **جلوی کلیدِ تغییرپذیر را بگیرد**: قبل از درج بررسی کند که کلید `hashable` است و اگر نبود، خطای خودت را بلند کند. (راهنمایی: `hash(key)` داخلِ `try` کافی است.) **قبل از اجرا پیش‌بینی کن** این بررسی چقدر به هزینهٔ هر درج اضافه می‌کند، بعد اندازه بگیر و خطای پیش‌بینی‌ات را بنویس. **و در آخر: آیا این بررسی جلوی همهٔ حالت‌ها را می‌گیرد؟** فکر کن به کلیدی که موقعِ درج `hashable` است.

## در فصل بعد

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

دو روشِ اول هر دو `O(n²)` هستند و ستونِ نسبتشان نزدیکِ `4` است؛ روشِ سوم `O(n)` است و ستونِ نسبتش نزدیکِ `2`. **ولی نتیجهٔ اصلیِ آن فصل در جدول نیست:** یک «امضای هوشمند» می‌سازیم که سریع‌تر است، هیچ خطایی نمی‌دهد، و **از دوازده هزار متنِ یکتا فقط ۳٬۲۱۳تا را می‌بیند.**

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t3/s06-what-can-be-a-key (یادستان, Yaadestan)
