در این فصل چه یاد میگیری#
تابعِ hash را داریم و میدانیم برخورد اجتنابناپذیر است. این فصل از این دو، یک ساختارِ کامل میسازد — در حدودِ سی خط، بدونِ هیچ کتابخانهای — و بعد دو بار اندازهاش میگیرد.
بارِ اول جدول ثابت میماند: میانگینِ گامهای جستوجو از 6.03 به 40.56 میرود و ستونِ نسبت 1.95 میشود. بارِ دوم همان کلیدها در جدولی میریزند که وقتی شلوغ شد خودش را بزرگ میکند: 1.33، 1.28، 1.31، 1.32 — ستونِ نسبت 1.01. فرقِ این دو جدول، کلِ حرفِ این ترم است.

آخر این فصل میتوانی:
- یک
hash tableباbucketوchainingرا از صفر بنویسی load factorرا حساب کنی و بگویی چرا جدولِ پر کند میشود- بگویی
rehashچقدر خرج دارد و چرا با وجودِ آن، درج هنوز ارزان است
قبل از شروع#
از فصلِ ۲: poly_hash، برخورد، و قاعدهٔ «اندازهٔ جدول را عددِ اول بگیر».
از ترمِ ۲ فصلِ ۳: هزینهٔ amortised و دوبرابرشدنِ ظرفیت. این فصل دقیقاً همان الگو را روی یک ساختارِ دیگر تکرار میکند.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | حدودِ یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. کوچکترین نسخهٔ ممکن، با دست#
پنج خانه میگیریم و شش کلید. هر خانه یک bucket است: یک list که هر جفتِ کلید-مقدارِ متعلق به آن خانه را نگه میدارد. وقتی دو کلید همخانه شوند، هر دو در همان bucket کنارِ هم مینشینند — اسمِ این کار chaining است.
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):
"""بهاندازهٔ size خانه، و هر خانه یک bucketِ خالیِ جداگانه."""
return [[] for _ in range(size)]
def table_put(buckets, key, value):
"""کلید را در bucketِ خودش میگذارد؛ اگر از قبل بود، مقدارش را عوض میکند."""
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
small = table_new(5)
for name, city in (("sara", "shiraz"), ("reza", "tabriz"), ("nima", "rasht"),
("mina", "yazd"), ("kian", "ahvaz"), ("dara", "kerman")):
table_put(small, name, city)
for i, bucket in enumerate(small):
print(f"bucket {i}: {bucket}")
print("جستوجوی nima:", table_get(small, "nima"))
print("جستوجوی sina:", table_get(small, "sina"))
bucket 0: [['reza', 'tabriz'], ['kian', 'ahvaz']]
bucket 1: []
bucket 2: [['nima', 'rasht'], ['mina', 'yazd']]
bucket 3: []
bucket 4: [['sara', 'shiraz'], ['dara', 'kerman']]
جستوجوی nima: ('rasht', 1)
جستوجوی sina: (None, 0)
کلِ ساختار همین است و دیگر هیچ چیز. شش کلید در سه bucket نشستهاند و دو bucket خالی مانده. جستوجوی nima یک گام خورد: poly_hash گفت خانهٔ ۲، و اولین جفتِ آن خانه همان بود.
و به سطرِ آخر خوب نگاه کن: جستوجوی کلیدی که اصلاً وجود ندارد صفر گام خورد. sina به یک bucket خالی افتاد، و «خالی» یعنی جوابِ «نه» بدونِ حتی یک مقایسه. این دقیقاً همان پرسشی است که در فصلِ ۱ هزار مقایسه خرج برمیداشت.
🔧 اگر کار نکرد: خطِ
table_newوسوسهانگیزترین جای این کد برای کوتاهنویسی است، و کوتاهنویسیاش هیچ خطایی نمیدهد و ساختار را کاملاً خراب میکند:
broken = [[]] * 4 # چهار ارجاع به یک list واحد
table_put(broken, "sara", "shiraz")
print("bucketهای معیوب:", broken)
print("طولِ هر bucket :", [len(b) for b in broken])
healthy = table_new(4)
table_put(healthy, "sara", "shiraz")
print("bucketهای درست:", healthy)
bucketهای معیوب: [[['sara', 'shiraz']], [['sara', 'shiraz']], [['sara', 'shiraz']], [['sara', 'shiraz']]]
طولِ هر bucket : [1, 1, 1, 1]
bucketهای درست: [[['sara', 'shiraz']], [], [], []]
یک درج، و هر چهار bucket پر شدند. [[]] * 4 چهار list نمیسازد؛ چهار ارجاع به یک list واحد میسازد. هیچ استثنایی بلند نمیشود، هیچ پیامی چاپ نمیشود، و جدولت از همان اولین درج غلط است. [[] for _ in range(size)] هر بار یک list تازه میسازد.
این بدترین ردهٔ خطاست: کدی که کار میکند و جوابِ غلط میدهد. تنها راهِ گرفتنش هم همان کاری است که اینجا کردیم — ساختار را چاپ کردن و با چشم دیدن.
۲. load factor: نسبتی که همهچیز را تعیین میکند#
اندازهٔ جدول را ثابت میگذاریم روی ۱۰۱ خانه و تعدادِ کلیدها را بالا میبریم. نسبتِ تعدادِ کلید به تعدادِ خانه اسم دارد: load factor.
🌱 ریشهاش کجاست:
load factorیک نسبت است، نه یک شمارش — «بهازای هر خانه، چند کلید». همین ایده در ریشه ترمِ ۲ فصل ۷ با نسبت و تناسب ساخته میشود. و خاصیتِ مهمش همان خاصیتِ هر نسبتی است: به اندازهٔ جدول و تعدادِ کلیدها جداگانه بند نیست، فقط به رابطهٔ آن دو بند است. جدولی با ۱۰۱ خانه و ۲۰۰ کلید، دقیقاً همانقدر شلوغ است که جدولی با ۱٬۰۱۰ خانه و ۲٬۰۰۰ کلید.
rng = random.Random(SEED)
POOL = [f"user-{rng.randrange(10 ** 9)}" for _ in range(8_000)]
print("کلیدهای یکتا:", len(set(POOL)), "· سه نمونه:", POOL[:3])
def build_fixed(keys, size):
"""جدولی با اندازهٔ ثابت — هرگز بزرگ نمیشود."""
buckets = table_new(size)
for k in keys:
table_put(buckets, k, 1)
return buckets
def lookup_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
FIXED = 101
LADDER = [1_000, 2_000, 4_000, 8_000]
for n in LADDER:
average, worst = lookup_cost(build_fixed(POOL[:n], FIXED), POOL[:n])
print(f"n={n:>6,} load factor={n / FIXED:>6.2f}"
f" میانگینِ گام={average:>6.2f} بلندترین زنجیر={worst:>4}")
کلیدهای یکتا: 8000 · سه نمونه: ['user-835549143', 'user-473233031', 'user-125467289']
n= 1,000 load factor= 9.90 میانگینِ گام= 6.03 بلندترین زنجیر= 20
n= 2,000 load factor= 19.80 میانگینِ گام= 10.88 بلندترین زنجیر= 30
n= 4,000 load factor= 39.60 میانگینِ گام= 20.85 بلندترین زنجیر= 53
n= 8,000 load factor= 79.21 میانگینِ گام= 40.56 بلندترین زنجیر= 98
میانگینِ گام در هر چهار سطر کمی بیشتر از نصفِ load factor است. و منطقش همان منطقِ فصلِ ۱ است: وقتی بهطورِ متوسط load factor جفت در هر bucket نشسته، جستوجوی خطی داخلِ همان bucket بهطورِ متوسط نصفشان را میبیند — بهعلاوهٔ گامِ اولی که همیشه لازم است.
یعنی جدولِ پر، هیچ جادویی ندارد: هر bucket خودش یک فهرستِ کوچک است و جستوجو در آن، همان جستوجوی خطیِ فصلِ ۱. جدول فقط کار را به size تکه شکسته.
🤔 اول حدس بزن: با ثابت ماندنِ اندازهٔ جدول، اگر تعدادِ کلیدها دو برابر شود میانگینِ گام چند برابر میشود؟ بنویسش، بعد جدول را ببین.
table([(n, lookup_cost(build_fixed(POOL[:n], FIXED), POOL[:n])[0]) for n in LADDER],
"میانگینِ گام", ",.2f")
n میانگینِ گام نسبت به سطر قبل
1,000 6.03 —
2,000 10.88 1.80
4,000 20.85 1.92
8,000 40.56 1.95
نزدیکِ 2 و رو به بالا رفتن به سمتِ 2. یعنی O(n) — همان مرتبهای که با جستوجوی خطیِ ساده هم داشتیم.
عددِ ۱۰۱ فقط یک ثابت است، و ثابت مرتبه را عوض نمیکند. جدولی که بزرگ نمیشود، hash table نیست؛ صد و یک فهرستِ کوچک است.
(ستونِ نسبت از 1.80 شروع میشود نه از 2.00، چون در سطرهای اول آن «یک گامِ اولِ» هر جستوجو هنوز سهمِ محسوسی از کل دارد. هرچه زنجیرها بلندتر میشوند، سهمش کمتر و نسبت به 2 نزدیکتر میشود.)
۳. جدولی که خودش را بزرگ میکند#
راهِ حل روشن است: نگذاریم load factor بالا برود. هر وقت از حدی گذشت، جدولِ بزرگتری میسازیم و همهچیز را دوباره جا میدهیم — چون خانهٔ هر کلید به len(buckets) بند است و با عوض شدنِ اندازه، عوض میشود. اسمِ این کار rehash است.
اندازهها را از یک فهرستِ آمادهٔ عددِ اول برمیداریم که هر کدام تقریباً دو برابرِ قبلی است — یکی بهخاطرِ قاعدهٔ فصلِ ۲، و یکی بهخاطرِ ترمِ ۲ فصلِ ۳: رشدِ ضربی، نه جمعی.
GROW_AT = 0.75
TABLE_SIZES = (11, 23, 47, 97, 199, 401, 809, 1_619, 3_251, 6_521, 13_043, 26_099)
BUCKETS, COUNT, STEP, MOVES = 0, 1, 2, 3
def grow_new():
"""[bucketها، تعدادِ کلید، شمارهٔ اندازهٔ فعلی، تعدادِ جابهجایی]"""
return [table_new(TABLE_SIZES[0]), 0, 0, 0]
def rehash(t):
"""اندازهٔ بعدی را میسازد و هر جفت را در خانهٔ تازهاش میگذارد."""
t[STEP] += 1
bigger = table_new(TABLE_SIZES[t[STEP]])
for bucket in t[BUCKETS]:
for pair in bucket:
bigger[poly_hash(pair[0]) % len(bigger)].append(pair)
t[MOVES] += 1
t[BUCKETS] = bigger
def grow_put(t, key, value):
"""درج، و بزرگ کردنِ جدول بهمحضِ اینکه load factor از GROW_AT رد شود."""
bucket = t[BUCKETS][poly_hash(key) % len(t[BUCKETS])]
for pair in bucket:
if pair[0] == key:
pair[1] = value
return
bucket.append([key, value])
t[COUNT] += 1
if t[COUNT] > GROW_AT * len(t[BUCKETS]) and t[STEP] + 1 < len(TABLE_SIZES):
rehash(t)
def build_growing(keys):
t = grow_new()
for k in keys:
grow_put(t, k, 1)
return t
for n in LADDER:
t = build_growing(POOL[:n])
average, worst = lookup_cost(t[BUCKETS], POOL[:n])
print(f"n={n:>6,} اندازهٔ جدول={len(t[BUCKETS]):>6,}"
f" load factor={n / len(t[BUCKETS]):>5.2f}"
f" میانگینِ گام={average:>5.2f} بلندترین زنجیر={worst:>3}")
n= 1,000 اندازهٔ جدول= 1,619 load factor= 0.62 میانگینِ گام= 1.33 بلندترین زنجیر= 5
n= 2,000 اندازهٔ جدول= 3,251 load factor= 0.62 میانگینِ گام= 1.28 بلندترین زنجیر= 4
n= 4,000 اندازهٔ جدول= 6,521 load factor= 0.61 میانگینِ گام= 1.31 بلندترین زنجیر= 5
n= 8,000 اندازهٔ جدول=13,043 load factor= 0.61 میانگینِ گام= 1.32 بلندترین زنجیر= 6
load factor در هر چهار سطر حولِ 0.62 ثابت مانده، و بههمراهش میانگینِ گام هم. بلندترین زنجیر با هشت برابر شدنِ کلیدها از ۵ به ۶ رفت — یعنی تقریباً هیچ.
🤔 اول حدس بزن: ستونِ نسبتِ این میانگین چه عددی میدهد؟ جوابت را بنویس، بعد جدول را ببین.
table([(n, lookup_cost(build_growing(POOL[:n])[BUCKETS], POOL[:n])[0]) for n in LADDER],
"میانگینِ گام", ",.2f")
n میانگینِ گام نسبت به سطر قبل
1,000 1.33 —
2,000 1.28 0.97
4,000 1.31 1.02
8,000 1.32 1.01
0.97، 1.02، 1.01. نزدیکِ یک، یعنی O(1): هزینهٔ یک جستوجو به تعدادِ کلیدهای داخلِ جدول بستگی ندارد.
این همان عنوانِ ترم است و حالا با عدد پشتیبانی میشود. و مقایسهاش با جدولِ بخشِ ۲ را در یک سطر بنویس: در n = 8,000 جدولِ ثابت 40.56 گام میخواست و جدولِ بزرگشونده 1.32 — بیش از سی برابر کمتر، با همان کلیدها و همان تابعِ hash.
۴. rehash رایگان نیست#
هر بار که جدول بزرگ میشود، همهٔ جفتها جابهجا میشوند. شمردهایمشان.
table([(n, build_growing(POOL[:n])[MOVES]) for n in LADDER], "جابهجایی", ",d")
n جابهجایی نسبت به سطر قبل
1,000 1,194 —
2,000 2,409 2.02
4,000 4,848 2.01
8,000 9,739 2.01
2.01: کلِ کارِ همهٔ rehashها روی هم، خطی است — نه درجهدو. و عددِ مطلقش هم گویاست: برای هشت هزار کلید، حدودِ نُه هزار و هفتصد جابهجایی. یعنی بهازای هر درج، تقریباً یک و یکچهارم جابهجاییِ اضافه.
دلیلش دقیقاً همان چیزی است که ترمِ ۲ فصلِ ۳ دربارهٔ list نشان داد: چون هر اندازه دو برابرِ قبلی است، جابهجاییهای گذشته روی هم از یک برابرِ اندازهٔ فعلی بیشتر نمیشوند. یک درجِ تک ممکن است خیلی گران باشد — همان درجی که rehash را راه میاندازد — ولی میانگینِ بلندمدت ثابت میماند. این همان amortised است.
table([(n, 1000 * clock(lambda keys=POOL[:n]: build_growing(keys), repeat=3))
for n in LADDER], "زمانِ ساخت (ms)", ",.1f")
n زمانِ ساخت (ms) نسبت به سطر قبل
1,000 3.5 —
2,000 7.4 2.12
4,000 14.5 1.95
8,000 28.2 1.94
ساعت هم میگوید ساختنِ جدول خطی است. یعنی n درج، هر کدام با هزینهٔ ثابتِ amortised.
📏 اندازه بگیر: چه چیزی با چه چیزی مقایسه شد؟ یک
hash tableبا اندازهٔ ثابت، در برابرِ همان ساختار با سیاستِ بزرگشدن — با کلیدهای کاملاً یکسان و همان تابعِhash. در کدام بازهٔn؟ ۱٬۰۰۰ تا ۸٬۰۰۰ کلید؛ جدولِ ثابت ۱۰۱ خانه و جدولِ بزرگشونده از ۱۱ خانه شروع میکند و در سقفِGROW_AT = 0.75میماند. با چند تکرار، و کمینه یا میانگین؟ جدولهای گام و جابهجایی یک اجرا، چون شمارشاند و قطعی؛ جدولِ زمان سه تکرار بهعلاوهٔ گرمکننده، کمینه.
✅ چک کن:
GROW_ATرا از0.75به4.0ببر و فقط جدولِ بخشِ ۳ را دوباره بگیر. میانگینِ گام باید از حدودِ1.3به حدودِ2.2برود و ستونِ نسبت باید هنوز نزدیکِ1بماند — چون جدول همچنان بزرگ میشود، فقط دیرتر. اگر ستونِ نسبت به2رفت، احتمالاً بهجایGROW_ATشرطِt[STEP] + 1 < len(TABLE_SIZES)را دست زدهای و جدول از یک جایی به بعد اصلاً بزرگ نمیشود.
🤖 از دستیارت بپرس: «در یک
hash tableباchaining، چراload factorمهمتر از تعدادِ کلیدهاست؟» بعد این را هم بپرس: «اگر بهجای دو برابر کردنِ اندازه، هر بار صد خانه اضافه کنم، کلِ کارِrehashها چه شکلی رشد میکند؟» — جوابِ درستO(n²)است و باید بتواند بگوید چرا؛ اگر دستیارت گفت «فرقی نمیکند»، جدولِ بخشِ ۴ را با همان تغییر بگیر و جلویش بگذار.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
hash table |
هَش تیبل | ساختاری که جای هر کلید را از hashش حساب میکند |
bucket |
باکِت | یک خانهٔ جدول، که هر تعداد جفت میتواند داشته باشد |
chaining |
چینینگ | نگه داشتنِ کلیدهای همخانه در یک فهرستِ کوچک، کنارِ هم |
load factor |
لود فَکتور | نسبتِ تعدادِ کلیدها به تعدادِ خانهها |
rehash |
ریهَش | ساختنِ جدولِ بزرگتر و جا دادنِ دوبارهٔ همهٔ کلیدها |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
جدولِ بخشِ ۳ میگوید میانگینِ گام 1.32 است. فصلِ بعد همان ساختار را با کلیدهایی پر میکند که کسی عمداً برایش ساخته و همان عدد به 256.50 میرسد.
آنجا سه پرسشِ متفاوت را از هم جدا میکنیم — بدترین حالت، حالتِ متوسط، و حالتی که واقعاً داری — و میبینیم چرا گزارش کردنِ فقط یکی از این سه، گمراهکننده است. و یک جدول هم میآید که میانگینش 4.17 است و بدترین گامش 53؛ همان جدولی که اگر فقط میانگینش را گزارش کنی، هیچ چیزِ مهمی نگفتهای.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.