جدول درهم‌سازی با زنجیره
هر خانه‌ی جدول یک لیست است و کلیدهایی که به یک خانه درهم می‌شوند پشت هم در همان لیست می‌روند؛ برخورد هیچ‌وقت جا را پر نمی‌کند.
تابع درهم‌سازی h(key) = key mod m هر کلید را به یکی از m خانه می‌برد. دو کلید ممکن است به یک خانه بروند (برخورد). در روش زنجیره‌ای هر خانه یک لیست است و همه‌ی کلیدهای آن خانه در همان لیست قرار می‌گیرند.
- زمان:
O(1 + n/m) on average per operation - حافظه:
O(n + m) - CLRS، بخش ۱۱.۲
- هوروویتز–ساهنی، فصل ۸
- جانسون‌باو، فصل ۳
ده کلید در جدول ۷ خانه‌ای؛ چند برخورد پیش می‌آید و زنجیره‌ها بلندتر می‌شوند.
def hash_chaining(keys):m = 7table = [[] for _ in range(m)]for key in keys:slot = key % mtable[slot].append(key)longest = max(len(chain) for chain in table)return table
شروع اجرا
جدول هنوز خالی است.
متغیرهای محلی
نارنجی = در همین گام عوض شد
keys list
Call stack
- hash_chaining()خط 1
توضیح
ایده
تابع درهم‌سازی h(key) = key mod m هر کلید را به یکی از m خانه می‌برد. دو کلید ممکن است به یک خانه بروند (برخورد). در روش زنجیره‌ای هر خانه یک لیست است و همه‌ی کلیدهای آن خانه در همان لیست قرار می‌گیرند.
هزینه
با ضریب بار α = n / m (میانگین طول زنجیره‌ها)، جست‌وجو به‌طور میانگین O(1 + α) است، به شرطی که تابع درهم‌سازی کلیدها را خوب پخش کند. اگر همه به یک خانه بروند، جست‌وجو O(n) می‌شود (ورودی «همه در یک خانه»).
مقایسه با آدرس‌دهی باز
در کاوش خطی کلیدها در خود جدول می‌نشینند و جدول ممکن است پر شود؛ اینجا جدول هیچ‌وقت پر نمی‌شود، ولی برای لیست‌ها حافظه‌ی اضافه لازم است.
در trace به چه چیزی نگاه کنی
- هر سطر جدول یک خانه است؛ سطری که همین الان کلید گرفت رنگی می‌شود.