# فصل ۰۴ — بدترین حالت، حالتِ متوسط، و حالتی که واقعاً داری

<div dir="rtl">

# فصل ۰۴ — بدترین حالت، حالتِ متوسط، و حالتی که واقعاً داری

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

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

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

![دو ترازوی کنارِ هم که یکی وزن را روی کفه‌ها پخش کرده و دیگری همه‌اش را روی یک کفه ریخته](/lesson-assets/t3-s04-worst-average-actual/prompt/01-image-three-questions.png)

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

- بدترین حالت، حالتِ متوسط و توزیعِ ورودیِ واقعی را از هم جدا کنی
- یک ورودیِ خصمانه برای `hash table` خودت بسازی و اثرش را اندازه بگیری
- بگویی چرا گزارشِ فقط یکی از این سه گمراه‌کننده است

## قبل از شروع

**از فصلِ ۳:** `poly_hash`، `bucket`، `chaining` و `load factor` — کدِ همان ساختار این‌جا دوباره می‌آید تا فصل خودبسنده باشد. **از فصلِ ۱:** بهترین، بدترین و متوسطِ یک جست‌وجوی خطی.

</div>

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

<div dir="rtl">

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

## ۱. سه پرسش که یکی نیستند

«هزینهٔ جست‌وجو در `hash table` چقدر است؟» در واقع سه پرسشِ قاطی‌شده است:

1. **بدترین حالت:** بدترین ورودیِ ممکن چقدر خرج برمی‌دارد؟
2. **حالتِ متوسط:** اگر کلیدها تصادفی باشند، به‌طورِ متوسط چقدر؟
3. **حالتی که واقعاً داری:** با همان کلیدهایی که برنامهٔ تو دریافت می‌کند، چقدر؟

**این سه، سه عددِ متفاوت‌اند و هیچ‌کدام دیگری را نتیجه نمی‌دهد.** جدولی با اندازهٔ ثابتِ ۴۰۱ خانه می‌سازیم و سه دستهٔ ۵۱۲تاییِ کلید به آن می‌دهیم.

</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):
    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


def build(keys, size):
    buckets = table_new(size)
    for k in keys:
        table_put(buckets, k, 1)
    return buckets


def 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


SIZE = 401
rng = random.Random(SEED)
random_keys = [f"user-{rng.randrange(10 ** 9)}" for _ in range(512)]
real_keys = [f"order-2026-{i:05d}" for i in range(512)]
print("تصادفی:", random_keys[0])
print("واقعی :", real_keys[0])
```

```text
تصادفی: user-835549143
واقعی : order-2026-00000
```

<div dir="rtl">

## ۲. ساختنِ ورودیِ خصمانه

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

</div>

```python
def hostile_keys(n, size, scan=400_000):
    """کلیدهایی که همه در یک خانهٔ واحدِ جدولی به اندازهٔ size می‌افتند."""
    found = []
    for i in range(scan):
        key = f"user-{i}"
        if poly_hash(key) % size == 0:
            found.append(key)
            if len(found) == n:
                return found
    raise ValueError(f"only {len(found)} keys found in {scan} candidates")


hostile = hostile_keys(512, SIZE)
print("خصمانه:", hostile[:3])
print("همه در یک خانه؟", len({poly_hash(k) % SIZE for k in hostile}) == 1)
```

```text
خصمانه: ['user-152', 'user-659', 'user-705']
همه در یک خانه؟ True
```

<div dir="rtl">

**کلیدها کاملاً معمولی‌اند** — `user-152` از `user-835549143` مشکوک‌تر نیست؛ فقط یکی‌یکی انتخاب شده‌اند.

> 🤔 **اول حدس بزن:** برای هر سه دسته حدس بزن: میانگینِ گام، و بدترین گام. مخصوصاً برای دستهٔ «واقعی»، چون کلیدهایش پشتِ سرِ هم و کاملاً ساختارمندند.

</div>

```python
for name, keys in (("تصادفی", random_keys), ("واقعی", real_keys), ("خصمانه", hostile)):
    average, worst = cost(build(keys, SIZE), keys)
    used = sum(1 for b in build(keys, SIZE) if b)
    print(f"{name:>7}: خانهٔ پر {used:>4} از {SIZE}"
          f"  ·  میانگینِ گام {average:>7.2f}  ·  بدترین گام {worst:>4}")
```

```text
 تصادفی: خانهٔ پر  293 از 401  ·  میانگینِ گام    1.59  ·  بدترین گام    5
  واقعی: خانهٔ پر  349 از 401  ·  میانگینِ گام    1.32  ·  بدترین گام    2
 خصمانه: خانهٔ پر    1 از 401  ·  میانگینِ گام  256.50  ·  بدترین گام  512
```

<div dir="rtl">

**یک ساختار، یک تابعِ `hash`، یک تعدادِ کلید — و میانگینی که از `1.32` تا `256.50` می‌رود.**

سه چیز در این جدول هست که هر کدام یک درسِ جداست:

- **دستهٔ «واقعی» از دستهٔ تصادفی بهتر درآمد، نه بدتر:** ۳۴۹ خانهٔ پر در برابرِ ۲۹۳. **پیش‌بینیِ رایج این است که «دادهٔ واقعی بدتر از تصادفی است»؛ این‌جا نبود.**
- **دستهٔ خصمانه تمامِ ۵۱۲ کلید را در یک خانه گذاشته.** جدول عملاً یک `list` است و میانگینِ گامش دقیقاً همان `(n+1)/2` فصلِ ۱ است.
- **نسبتِ بدترین به متوسط ۱۶۱ برابر است.** هیچ‌کدام از این دو عدد غلط نیست؛ فقط هیچ‌کدام تنهایی کافی نیست.

## ۳. برخوردِ کامل یعنی برگشت به فصلِ ۱

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

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

</div>

```python
HOSTILE_LADDER = [64, 128, 256, 512]
print("— ورودیِ خصمانه")
table([(n, cost(build(hostile[:n], SIZE), hostile[:n])[0]) for n in HOSTILE_LADDER],
      "میانگینِ گام", ",.2f")
print("\n— ورودیِ تصادفی، همان جدول")
table([(n, cost(build(random_keys[:n], SIZE), random_keys[:n])[0]) for n in HOSTILE_LADDER],
      "میانگینِ گام", ",.2f")
```

```text
— ورودیِ خصمانه
         n      میانگینِ گام     نسبت به سطر قبل
        64             32.50                   —
       128             64.50                1.98
       256            128.50                1.99
       512            256.50                2.00

— ورودیِ تصادفی، همان جدول
         n      میانگینِ گام     نسبت به سطر قبل
        64              1.05                   —
       128              1.15                1.10
       256              1.31                1.14
       512              1.59                1.21
```

<div dir="rtl">

**ستونِ چپ `2.00` است و ستونِ راست حولِ `1.15`.** `O(n)` در برابرِ چیزی که هنوز نزدیکِ ثابت است.

**و صادقانه‌اش این است: ستونِ راست هم دارد بالا می‌رود** — با اندازهٔ ثابتِ جدول، در نهایت آن هم خطی می‌شود (فصلِ ۳). **فرقِ این دو در مرتبه نیست، در ثابتِ ضرب است: ۴۰۱ برابر، دقیقاً به‌اندازهٔ تعدادِ خانه‌ها.** سیاستِ بزرگ‌شدنِ فصلِ ۳ ستونِ راست را نجات می‌دهد و **ستونِ چپ را هم، فقط چون این کلیدها برای ۴۰۱ ساخته شده‌اند**: در جدولِ ۸۰۹ خانه‌ای میانگینِ گامشان `1.23` می‌شود. ولی اگر مهاجم کلیدهایی بسازد که خودِ عددِ `hash`شان یکی است، مثلِ جابه‌جاییِ حروف برای `sum_hash`، جدولِ بزرگ‌تر فقط خانه‌های خالیِ بیشتری می‌سازد.

## ۴. میانگینی که همه‌چیز را پنهان می‌کند

واقعی‌ترین حالت نه این است نه آن: **۴۶۱ کلیدِ عادی، و ۵۱ کلیدِ ساختهٔ یک مهاجم.**

</div>

```python
mixed = random_keys[:461] + hostile[:51]
buckets = build(mixed, SIZE)
average, worst = cost(buckets, mixed)
print(f"میانگینِ گام: {average:.2f}   ·   بدترین گام: {worst}")
print("طولِ پنج زنجیرِ اول:", sorted((len(b) for b in buckets), reverse=True)[:5])
```

```text
میانگینِ گام: 4.17   ·   بدترین گام: 53
طولِ پنج زنجیرِ اول: [53, 4, 4, 4, 4]
```

<div dir="rtl">

**میانگین `4.17` است و کاملاً بی‌آزار به‌نظر می‌رسد.** ولی طولِ زنجیرها را ببین: یک زنجیرِ ۵۳تایی، و بعدش همه چهارتایی. **یک خانه سیزده برابرِ بقیه بار دارد و میانگین چیزی دربارهٔ آن نمی‌گوید.**

> 🌱 **ریشه‌اش کجاست:** اینکه میانگین به‌تنهایی چه چیزی را پنهان می‌کند، در [ریشه ترمِ ۶ فصل ۶](/courses/risheh/lessons/term-6-probability-statistics/session-06-center-spread) با مرکز و پراکندگی ساخته می‌شود: دو دسته عدد می‌توانند میانگینِ یکسان و شکلِ کاملاً متفاوت داشته باشند. **کاربری که در آن زنجیرِ ۵۳تایی افتاده، میانگین را تجربه نمی‌کند؛ ۵۳ را تجربه می‌کند.**

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

> ⚠️ **مواظب باش:** این آزمایش یک تلهٔ بی‌صدا دارد که **هیچ پیامِ خطایی نمی‌دهد**: اگر جدول را بینِ دو آزمایش دوباره نسازی، کلیدهای خصمانه را روی جدولی می‌پرسی که اصلاً درشان نکرده‌ای.

</div>

```python
clean = build(random_keys, SIZE)
print("گامِ کلیدهای خصمانه روی جدولِ تصادفی:", cost(clean, hostile)[0])
print("گامِ کلیدهای خصمانه روی جدولِ خودشان:", cost(build(hostile, SIZE), hostile)[0])
```

```text
گامِ کلیدهای خصمانه روی جدولِ تصادفی: 3.0
گامِ کلیدهای خصمانه روی جدولِ خودشان: 256.5
```

<div dir="rtl">

**`3.0` در برابرِ `256.5` — و هر دو سطر بدونِ هیچ خطایی چاپ شدند.** سطرِ اول اصلاً دربارهٔ حمله حرف نمی‌زند؛ فقط می‌گوید آن کلیدها **در این جدول نیستند**. **هر گزارشی که ساختارش را بینِ دو آزمایش از نو نساخته باشد، می‌تواند همین‌طور دروغ بگوید.**

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

> ✅ **چک کن:** در `hostile_keys` آرگومانِ `size` را `397` بگذار ولی جدول را همان ۴۰۱ خانه نگه دار، و جدولِ بخشِ ۲ را دوباره بگیر. **میانگینِ گامِ دستهٔ خصمانه باید به `1.59` برگردد — دقیقاً عددِ دستهٔ تصادفی.** کلیدهایی که برای یک اندازه ساخته شده‌اند، روی اندازهٔ دیگری هیچ خاصیتی ندارند. **و همین می‌گوید مهاجم دقیقاً چه چیزی باید بداند تا حمله‌اش کار کند.**

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

</div>

```python
try:
    buckets = table_new(SIZE)
    buckets[poly_hash("user-1")].append(["user-1", 1])
except IndexError as err:
    print(f"{type(err).__name__}: {err}")
```

```text
IndexError: list index out of range
```

<div dir="rtl">

`poly_hash` عددی تا حدودِ یک میلیون می‌دهد و جدول ۴۰۱ خانه دارد. **بدونِ `% len(buckets)`، `hash` یک عدد است، نه یک شمارهٔ خانه.** خوبیِ این خطا این است که فوری و صریح بلند می‌شود — بر خلافِ تلهٔ قبلی که فقط یک عددِ آرام و غلط چاپ کرد.

> 🤖 **از دستیارت بپرس:** **خروجیِ بخشِ ۴ را جلویش بگذار و بپرس:** «میانگینِ گام ۴٫۱۷ است و بدترین گام ۵۳؛ آیا این جدول سالم است؟» — جوابِ درست باید به توزیع نگاه کند، نه به میانگین. بعد این را هم بپرس: **«پایتون برای همین حمله چه کاری کرده؟»** و جواب را با فصلِ ۲ بسنج.

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

</div>

| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
| worst case | وُرست کیس | گران‌ترین ورودیِ ممکن، هرچقدر هم نادر |
| average case | اَوریج کیس | میانگین روی ورودیِ تصادفی |
| adversarial input | ادورسِریال اینپوت | ورودی‌ای که کسی عمداً برای گران کردنِ کار ساخته |
| full collision | فول کولیژن | حالتی که همهٔ کلیدها به یک `bucket` می‌افتند |

<div dir="rtl">

## تمرین‌ها

قبل از تمرین، بدونِ نگاه به بالا جواب بده: بزرگ کردنِ جدول کِی ورودیِ خصمانه را نجات می‌دهد و کِی نمی‌دهد؟

**تمرینِ اجباری:** `hostile_keys` را طوری تغییر بده که کلیدها را به‌جای یک خانه در **چهار** خانه پخش کند، و جدولِ بخشِ ۳ را دوباره بگیر. **سؤالِ اصلی: ستونِ نسبت عوض می‌شود یا فقط عددها؟** جوابت باید بگوید کدام‌شان مرتبه است و کدام‌شان ثابت — و همین تفاوت، کلِ حرفِ `Big-O` است.

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

## در فصل بعد

**فصلِ بعد سراغِ خودِ `set` و `dict` می‌رود** و همان پرسشِ فصلِ ۱ را با `set` می‌پرسد: صد هزار پرسش، و ظرفی که هر بار دو برابر می‌شود.

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

</div>

---
Source: https://yaadestan.com/courses/bonyad/lessons/t3/s04-worst-average-actual (یادستان, Yaadestan)
