جدول درهم‌سازی با کاوش خطی

هر کلید در خانه‌ی key mod m می‌نشیند؛ اگر پر بود، خانه‌های بعدی را یکی‌یکی امتحان می‌کند تا جای خالی پیدا شود.

جدول درهم‌سازی کلیدها را در آرایه‌ای به اندازه‌ی m نگه می‌دارد و جای هر کلید را با یک تابع درهم‌سازی حساب می‌کند؛ اینجا h(k) = k mod m. اگر آن خانه پر بود (برخورد)، در «آدرس‌دهی باز» خانه‌ی دیگری از خود جدول امتحان می‌شود. در کاوش خطی، خانه‌های h(k)+1، h(k)+2، … به ترتیب امتحان می‌شوند.

ادامه‌ی توضیح ↓

زمان: O(1) per insert on average when the table is not too full
حافظه: O(m)
CLRS، بخش ۱۱.۴
هوروویتز–ساهنی، فصل ۸
جانسون‌باو، فصل ۳

ورودی:

n=9خروجی PDF

نُه کلید در جدول ۱۱ خانه‌ای؛ چند برخورد پیش می‌آید و کلیدها کنار هم خوشه می‌سازند.

def hash_insert_all(keys):
m = 11
table = [None] * m
for key in keys:
i = 0
while True:
j = (key + i) % m
if table[j] is None:
table[j] = key
break
i = i + 1
return table

ناوردا: هر کلید در اولین خانه‌ی خالیِ دنباله‌ی h(k), h(k)+1, … (به پیمانه‌ی m) نشسته است.

شروع اجرا

متغیرهای محلی

نارنجی = در همین گام عوض شد

`keys` list

10223141528178859

Call stack

hash_insert_all()خط 1

گام ۱ از ۹۶

رشد تعداد عملیات با اندازه‌ی ورودی

میانگین ۱۲ گراف تصادفی برای هر n (با seed ثابت). نشانگر توخالی = ورودی فعلی.

collision
ورودی فعلی (n=9)

نمایش به شکل جدول

n	collision
4	0.3
6	2.6
8	3.9
10	11

توضیح

ایده

خوشه‌بندی اولیه

کاوش خطی ساده است ولی یک ضعف دارد: کلیدها پشت سر هم خوشه می‌سازند و هر کلیدی که به هر جای خوشه برسد، باید تا انتهای آن برود؛ پس خوشه‌ها بزرگ‌تر و بزرگ‌تر می‌شوند. ورودی «یک خوشه» این را نشان می‌دهد. کاوش مربعی و درهم‌سازی دوگانه این مشکل را کم می‌کنند.

هزینه

اگر جدول خیلی پر نباشد (ضریب بار α = n/m کمتر از حدود ۰٫۷)، هر درج به‌طور متوسط O(1) کاوش دارد. با پر شدن جدول، تعداد کاوش‌ها تند بالا می‌رود.

در trace به چه چیزی نگاه کنی

خانه‌های خط‌چین خالی‌اند؛ key بالای جدول کلیدی است که درج می‌شود و فلش j خانه‌ی در حال کاوش.
شمار collision را در «بدون برخورد»، «مثال به سبک کتاب» و «یک خوشه» مقایسه کن.