بنیاد — ساختمان داده و الگوریتم، با اندازه‌گیری واقعی

فصل ۴ از ۷

پیشرفت ترم
۰٪

ترم ۳ · `hash`: چرا جست‌وجو می‌تواند هزینهٔ ثابت داشته باشد

بدترین حالت، حالتِ متوسط، و حالتی که واقعاً داری

فصل ۴رایگان

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

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

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

دو ترازوی کنارِ هم که یکی وزن را روی کفه‌ها پخش کرده و دیگری همه‌اش را روی یک کفه ریخته

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

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

قبل از شروع#

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

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

📓 نوت‌بوک: نوت‌بوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و به‌ترتیب داخلش هست.

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

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

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

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

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])
تصادفی: user-835549143
واقعی : order-2026-00000

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

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

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)
خصمانه: ['user-152', 'user-659', 'user-705']
همه در یک خانه؟ True

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

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

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}")
 تصادفی: خانهٔ پر  293 از 401  ·  میانگینِ گام    1.59  ·  بدترین گام    5
  واقعی: خانهٔ پر  349 از 401  ·  میانگینِ گام    1.32  ·  بدترین گام    2
 خصمانه: خانهٔ پر    1 از 401  ·  میانگینِ گام  256.50  ·  بدترین گام  512

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

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

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

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

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

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

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")
— ورودیِ خصمانه
         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

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

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

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

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

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])
میانگینِ گام: 4.17   ·   بدترین گام: 53
طولِ پنج زنجیرِ اول: [53, 4, 4, 4, 4]

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

🌱 ریشه‌اش کجاست: اینکه میانگین به‌تنهایی چه چیزی را پنهان می‌کند، در ریشه ترمِ ۶ فصل ۶ با مرکز و پراکندگی ساخته می‌شود: دو دسته عدد می‌توانند میانگینِ یکسان و شکلِ کاملاً متفاوت داشته باشند. کاربری که در آن زنجیرِ ۵۳تایی افتاده، میانگین را تجربه نمی‌کند؛ ۵۳ را تجربه می‌کند.

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

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

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

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

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

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

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

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

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

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

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

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

تمرین‌ها

اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.

در فصل بعد#

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

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

به آخر این فصل رسیدی!

اگر ساختی و جواب داد، این دکمه مال توست.