در این فصل چه یاد میگیری#
تا حالا هر کلیدی که به set و dict دادهایم رشته یا عدد بوده. این فصل میپرسد چه چیزی اصلاً میتواند کلید باشد، و از یک خطای واقعی شروع میکند: TypeError: unhashable type: 'list'.
بعد قاعدهای را میبینی که پشتِ آن خطاست، و یک dict که سه بار درج میشود و آخرش یک عضو دارد. آخرِ فصل هم، با همان hash table دستسازِ فصلِ ۳، کلیدی را که بعد از درج عوض شده گم میکنیم — در حالی که خودش هنوز همانجا داخلِ bucket نشسته و کاملاً دیده میشود.

آخر این فصل میتوانی:
- بگویی
hashableبودن یعنی چه و چراlistنیست - قاعدهٔ همخوانیِ
__hash__و__eq__را با یک مثالِ اجراشدنی توضیح بدهی - کلیدِ مرکب بسازی و هزینهاش را اندازه بگیری
قبل از شروع#
از فصلِ ۲: hash بهعنوان تابعی که کلید را به عدد تبدیل میکند، و اینکه hash(1) و hash(1.0) و hash(True) یکیاند.
از فصلِ ۳: poly_hash، bucket و chaining. کدِ همان جدول اینجا دوباره میآید.
| اجرا | زمانِ تقریبی |
|---|---|
| CPU (پیشفرضِ Colab) | کمتر از یک دقیقه |
📓 نوتبوک: نوتبوک این فصل را در Colab باز کن — همهٔ کدهای این فصل آماده و بهترتیب داخلش هست.
۱. خطایی که همه یک بار میگیرند#
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}")
تا اینجا مشکلی نیست: 2
TypeError: unhashable type: 'list'
🔧 اگر کار نکرد: پیام دقیقاً میگوید چه چیزی کم است:
listقابلِhashگرفتن نیست. راهِ حل تقریباً همیشه یک نویسه است —[را به(عوض کن و همان محتوا در یکtupleمینشیند کهhashableاست. اگر محتوا باید تغییرپذیر بماند، آنوقت اصلاً نباید کلید باشد؛ باید مقدار باشد.
و همینجا سؤالِ اصلیِ فصل درمیآید: چرا tuple میتواند و list نمیتواند؟
۲. hashable یعنی چه#
فصلِ ۳ نشان داد جای هر کلید از hashش میآید. پس اگر hash یک کلید بعد از درج عوض شود، آن کلید در خانهٔ اشتباهی نشسته و دیگر پیدا نمیشود.
از این یک شرط درمیآید: چیزی میتواند کلید باشد که hashش در تمامِ عمرش ثابت بماند. پایتون این را با یک قاعدهٔ سادهتر تضمین میکند: چیزهایی که میشود تغییرشان داد، hashable نیستند. list تغییرپذیر است، tuple نیست. set تغییرپذیر است، رشته و عدد نیستند.
print("hash یک tuple:", hash(("a", 1)) == hash(("a", 1)))
try:
hash(("a", [1]))
except TypeError as err:
print(f"{type(err).__name__}: {err}")
hash یک tuple: True
TypeError: unhashable type: 'list'
سطرِ دوم مهمتر از سطرِ اول است. tuple خودش تغییرپذیر نیست، ولی میتواند چیزِ تغییرپذیری داخلش داشته باشد — و آنوقت خودش هم hashable نیست. hash یک tuple از hash عضوهایش ساخته میشود، پس عضوی که hash ندارد کلِ tuple را از کار میاندازد.
۳. قاعدهٔ همخوانی: اگر برابرند، hashشان هم باید یکی باشد#
پایتون دو کارِ جداگانه با یک کلید میکند: اول از hash جای bucket را پیدا میکند (پشتِ صحنه __hash__ صدا زده میشود)، بعد داخلِ آن bucket با == دنبالِ کلید میگردد (که __eq__ است). این دو باید با هم بخوانند، وگرنه ساختار میشکند:
اگر
a == bباشد، حتماً بایدhash(a) == hash(b)باشد.
خلافش لازم نیست: دو چیز میتوانند hash یکسان داشته باشند و برابر نباشند — که همان برخوردِ فصلِ ۲ است و chaining تکلیفش را روشن میکند.
پایتون خودش این قاعده را رعایت میکند، و یک نتیجهٔ عجیب دارد:
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))
1 == 1.0 == True ? True
hash(1), hash(1.0), hash(True): 1 1 1
dict بعد از سه درج: {1: 'سومی'}
طولش: 1
سه درج، یک عضو. 1 و 1.0 و True در پایتون با هم برابرند، پس از نظرِ dict یک کلیدند — هر سه به یک bucket میروند و == میگوید هماناند، پس فقط مقدار جایگزین میشود.
و کلیدِ باقیمانده 1 است، نه True: کلید از اولین درج میماند و فقط مقدار بهروز میشود. این دقیقاً همان کاری است که table_put ما در فصلِ ۳ میکرد — آنجا هم وقتی کلید پیدا میشد، pair[1] عوض میشد و pair[0] دستنخورده میماند.
۴. کلیدِ مرکب#
قاعدهٔ «تغییرناپذیر باشد» یک نتیجهٔ عملیِ مفید دارد: tuple کلیدِ مرکب میسازد. هر جا کلیدت یک چیز نیست و چند چیز است، بهجای چسباندنشان به هم در یک رشته، tupleشان کن.
grid = {}
grid[(0, 0)] = "خانهٔ شروع"
grid[(1, 2)] = "خانهٔ گنج"
grid[(2, 1)] = "خانهٔ تله"
print(grid)
print("کلیدِ (1, 2):", grid[(1, 2)], "· کلیدِ (2, 1):", grid[(2, 1)])
{(0, 0): 'خانهٔ شروع', (1, 2): 'خانهٔ گنج', (2, 1): 'خانهٔ تله'}
کلیدِ (1, 2): خانهٔ گنج · کلیدِ (2, 1): خانهٔ تله
(1, 2) و (2, 1) دو کلیدِ کاملاً متفاوتاند — همان چیزی که با چسباندن به رشته بهراحتی از دست میرفت. و ترتیبِ چاپ همان ترتیبِ درج است، چون dict ترتیبِ درج را نگه میدارد.
۵. کلیدی که بعد از درج عوض شود#
حالا نشان میدهیم اگر پایتون این قید را نمیگذاشت، چه اتفاقی میافتاد. hash table دستسازِ فصلِ ۳ چنین قیدی ندارد: poly_hash روی str(key) کار میکند و str یک list هم بهراحتی ساخته میشود. پس میشود یک list را در آن کلید کرد — و بعد عوضش کرد.
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])
قبل از تغییر : ('گنج', 1)
دنبالِ [1, 2] : (None, 1)
دنبالِ [1, 2, 3]: (None, 0)
ولی هنوز اینجاست: [[[[1, 2, 3], 'گنج']]]
سه سطرِ آخر را با هم بخوان؛ هر کدام نصفِ داستاناند.
[1, 2]پیدا نمیشود:hashهمان است، پس بهbucketدرست میرویم و یک گام هم برمیداریم — ولی جفتی که آنجاست دیگر با[1, 2]برابر نیست.[1, 2, 3]هم پیدا نمیشود: این بارhashعوض شده، پس اصلاً بهbucketاشتباهی میرویم که خالی است — صفر گام.- و مقدار هنوز سرِ جایش است. هیچ چیزی گم نشده و هیچ خطایی هم بلند نشده؛ فقط دیگر هیچ راهی به آن نیست.
این بدترین حالتی است که یک ساختارِ داده میتواند به تو بدهد: نه خطا، نه پیام، فقط دادهٔ غیرقابلِ دسترسی. و دقیقاً برای جلوگیری از همین است که پایتون list را از کلید بودن محروم میکند — قید، محدودیت نیست؛ ضمانت است.
۶. هزینهٔ کلیدِ مرکب#
کلیدِ tuple رایگان نیست: hash گرفتن از آن یعنی hash گرفتن از هر عضوش.
🤔 اول حدس بزن: اگر تعدادِ عضوهای
tupleدو برابر شود، تعدادِ گامهای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(("ab",) * length)[1])
for length in (250, 500, 1_000, 2_000)], "گامِ hash", ",d")
n گامِ hash نسبت به سطر قبل
250 1,500 —
500 3,000 2.00
1,000 6,000 2.00
2,000 12,000 2.00
2.00. n اینجا تعدادِ عضوهای tuple است، نه تعدادِ کلیدها. پس هزینهٔ hash با اندازهٔ کلید خطی است — همان نتیجهٔ فصلِ ۲، این بار برای کلیدِ مرکب.
نتیجهٔ عملی: کلیدِ کوچک نگه دار. یک tuple دوتایی عملاً رایگان است؛ یک tuple هزارتایی بهازای هر lookup هزار گام خرج میکند و آنوقت دیگر «هزینهٔ ثابت» حرفِ بیمعنایی است.
و حالا سؤالِ دیگر: با ثابت ماندنِ اندازهٔ کلید، آیا lookup با کلیدِ tuple هنوز به تعدادِ کلیدها بیاعتناست؟
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")
تعدادِ «بله» در همهٔ اندازهها یکی است؟ 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
نزدیکِ 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است»، خروجیِ بخشِ ۲ را جلویش بگذار.
واژههای تازهٔ این فصل#
| کلمه | تلفظ به حروف فارسی | یعنی چه |
|---|---|---|
hashable |
هَشِبل | چیزی که hash دارد و hashش هرگز عوض نمیشود |
| immutable | ایمیوتِبل | تغییرناپذیر؛ بعد از ساخته شدن عوض نمیشود |
__hash__ |
دانِدر هَش | کاری که پایتون برای گرفتنِ hash یک چیز صدا میزند |
__eq__ |
دانِدر ایکیو | کاری که پایتون برای مقایسهٔ دو چیز با == صدا میزند |
| composite key | کامپوزیت کی | کلیدی که از چند بخش ساخته شده، معمولاً یک tuple |
تمرینها
اول خودت فکر کن یا امتحان کن — بعد اینجا را باز کن.
در فصل بعد#
سه ترم شد و حالا وقتِ بهکار بردنش است. فصلِ بعد یک پیکرهٔ بزرگ از سند میگیرد و میپرسد کدامها تکراریاند — با سه روش، یک جدول، و یک تصمیمِ مستند.
دو روشِ اول هر دو O(n²) هستند و ستونِ نسبتشان نزدیکِ 4 است؛ روشِ سوم O(n) است و ستونِ نسبتش نزدیکِ 2. ولی نتیجهٔ اصلیِ آن فصل در جدول نیست: یک «امضای هوشمند» میسازیم که سریعتر است، هیچ خطایی نمیدهد، و از دوازده هزار متنِ یکتا فقط ۳٬۲۱۳تا را میبیند.
به آخر این فصل رسیدی!
اگر ساختی و جواب داد، این دکمه مال توست.