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

فصل ۲ از ۷

پیشرفت ترم
۰٪

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

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

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

دستگاهی که برگه‌های متفاوت را از یک قیف می‌گیرد و هرکدام را به یکی از خانه‌های شماره‌دار می‌اندازد

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

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

قبل از شروع#

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

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

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

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

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

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

🌱 ریشه‌اش کجاست: باقی‌مانده در ریشه ترمِ ۱ فصل ۵ به‌عنوانِ «چه چیزی جا نشد» ساخته می‌شود: ۲۵ شکلات بینِ ۸ نفر، هر نفر ۳ تا و ۱ تا روی میز. دو خاصیتش دقیقاً همان دو چیزی است که این ترم را ممکن می‌کند — باقی‌مانده همیشه از مقسومٌ‌علیه کوچک‌تر است (پس هر کلیدی به یک خانهٔ معتبر می‌افتد)، و برای هر ورودی یکتاست (پس همان کلید همیشه به همان خانه می‌رود).

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

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

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

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

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

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

print(ord("a"), ord("b"), ord("A"), ord("-"), ord("0"))
97 98 65 45 48

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

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}")
abc   sum_hash=     294   poly_hash=   96354
bca   sum_hash=     294   poly_hash=   97344
cba   sum_hash=     294   poly_hash=   98274

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

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

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

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

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

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)
  sum_hash  اندازهٔ جدول   67:  خانهٔ خالی   1  ·  کم‌جمعیت‌ترین   0  ·  پرجمعیت‌ترین  75
 poly_hash  اندازهٔ جدول   67:  خانهٔ خالی   0  ·  کم‌جمعیت‌ترین  26  ·  پرجمعیت‌ترین  33

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

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

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

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

report(poly_hash, "poly_hash", KEYS, 67)
report(poly_hash, "poly_hash", KEYS, 64)
 poly_hash  اندازهٔ جدول   67:  خانهٔ خالی   0  ·  کم‌جمعیت‌ترین  26  ·  پرجمعیت‌ترین  33
 poly_hash  اندازهٔ جدول   64:  خانهٔ خالی   0  ·  کم‌جمعیت‌ترین   1  ·  پرجمعیت‌ترین  66

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

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

اول با دست. دنبالهٔ 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های ما واقعاً چنین گامی دارند یا نه:

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}), "مانده از ۶۷")
پرتکرارترین گام‌های بینِ hashهای پیاپی: [(1, 1800), (22, 179), (673, 17)]
یک دنباله با گامِ ثابتِ ۲۲، هشتاد عضو:
  بر ۶۴: 32 مانده از ۶۴
  بر ۶۷: 67 مانده از ۶۷

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

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

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

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

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

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")
         n      جفتِ هم‌خانه     نسبت به سطر قبل
       250                27                   —
       500               114                4.22
     1,000               444                3.89
     2,000             1,946                4.38

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

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

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

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

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")
         n         گامِ hash     نسبت به سطر قبل
       250               250                   —
       500               500                2.00
     1,000             1,000                2.00
     2,000             2,000                2.00

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

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

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

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

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

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))
hash(1)       = 1
hash(1.0)     = 1
hash(True)    = 1
hash(-1)      = -2
hash(10 ** 20) = 848750603811160107

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

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

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

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])
hash('bonyad') در دو اجرا یکی است؟ False
hash(12345)    در دو اجرا یکی است؟ True

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

print("اجرای اول:", first)
print("اجرای دوم:", second)
اجرای اول: (2613271495042824151, 12345)
اجرای دوم: (3016696591514293467, 12345)

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

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

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

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

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

try:
    print("unit-7" % 64)
except TypeError as err:
    print(f"{type(err).__name__}: {err}")
TypeError: not all arguments converted during string formatting

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

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

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

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

تمرین‌ها

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

در فصل بعد#

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

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

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

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