جداول هش توضیح داده شده: از آدرس‌دهی مستقیم تا آدرس‌دهی باز

ایده انگیزاننده: جداول آدرس‌دهی مستقیم

اگر جهان کلیدهای ممکن کوچک باشد، یک Direct-Address Table (جدول آدرس‌دهی مستقیم) یک راه‌حل ساده و بسیار سریع ارائه می‌دهد: یک آرایه که مستقیماً توسط خود کلید ایندکس می‌شود، جایی که هر اسلات عنصر با آن کلید را نگه می‌دارد (یا خالی است).

DIRECT-ADDRESS-SEARCH(T, k):
  T[k] را برگردان

DIRECT-ADDRESS-INSERT(T, x):
  T[x.key] = x

DIRECT-ADDRESS-DELETE(T, x):
  T[x.key] = NIL

هر عملیات در زمان O(1) اجرا می‌شود — به‌سرعتی که ممکن است. مشکل حافظه است: این نیازمند تخصیص یک آرایه به‌بزرگی کل جهان کلیدهای ممکن است، که هروقت جهان بزرگ باشد (مانند همه رشته‌های ممکن) یا وقتی فقط بخش کوچکی از کلیدهای ممکن واقعاً استفاده می‌شوند، غیرعملی است.

جداول هش: مبادله برخی تضمین‌ها برای صرفه‌جویی عظیم فضا

یک Hash Table (جدول هش) این مسئله فضا را با استفاده از یک آرایه بسیار کوچک‌تر به اندازه m، و یک Hash Function (تابع هش) h(k) که هر کلید از جهان بزرگ را به یک ایندکس در [0, m-1] نگاشت می‌کند، حل می‌کند. این به‌طور چشمگیری مصرف حافظه را کاهش می‌دهد، به قیمت یک مسئله جدید: از آنجا که بسیاری کلیدهای ممکن به همان مجموعه کوچک از ایندکس‌ها نگاشت می‌شوند، دو کلید متفاوت می‌توانند به همان اسلات هش شوند، رویدادی به نام Collision (برخورد).

مدیریت برخوردها با زنجیره‌بندی

Chaining (زنجیره‌بندی) برخوردها را با ذخیره همه عناصری که به همان اسلات هش می‌شوند در یک لیست پیوندی، که پیش‌تر در این مجموعه بحث شد، ریشه‌دار در آن اسلات، حل می‌کند.

CHAINED-HASH-INSERT(T, x):
  x را در ابتدای لیست T[h(x.key)] درج کن

CHAINED-HASH-SEARCH(T, k):
  یک عنصر با کلید k را در لیست T[h(k)] جستجو کن

CHAINED-HASH-DELETE(T, x):
  x را از لیست T[h(x.key)] حذف کن

درج همیشه O(1) است، چون صرفاً به ابتدای یک لیست اضافه می‌کند بدون نیاز به جستجو. جستجو و حذف به طول لیست بستگی دارند، که به این بستگی دارد چند کلید در آن اسلات خاص برخورد کرده‌اند.

تحلیل کارایی مورد انتظار

Load Factor (فاکتور بار) α = n/m را تعریف کن، میانگین تعداد عناصر به‌ازای هر اسلات، جایی که n تعداد عناصر ذخیره‌شده و m تعداد اسلات‌هاست. تحت فرض Simple Uniform Hashing (هشینگ یکنواخت ساده) — که هر کلید مشخص به‌طور برابر احتمال دارد به هر یک از m اسلات هش شود، مستقل از کلیدهای دیگر — طول مورد انتظار هر زنجیره دقیقاً α است.

زمان مورد انتظار برای یک جستجوی ناموفق: Θ(1 + α)
زمان مورد انتظار برای یک جستجوی موفق:     Θ(1 + α)

اگر m متناسب با n انتخاب شود (پس α = O(1))،
همه عملیات‌ها در زمان مورد انتظار Θ(1) اجرا می‌شوند

این نتیجه مستقیماً به تکنیک‌های تحلیل احتمالاتی که پیش‌تر در این مجموعه بحث شد متصل می‌شود: زمان جستجوی مورد انتظار هزینه O(1) محاسبه تابع هش را با طول زنجیره مورد انتظار ترکیب می‌کند، که تا زمانی که اندازه جدول متناسب با تعداد عناصر ذخیره‌شده رشد کند ثابت می‌ماند.

طراحی توابع هش خوب

کل تحلیل زمان-مورد-انتظار بالا به توزیع تقریباً یکنواخت کلیدها در سراسر اسلات‌ها توسط تابع هش بستگی دارد. یک تابع هش ضعیف‌انتخاب‌شده می‌تواند کارایی را به همان یک لیست پیوندی واحد تنزل دهد، Θ(n)، صرف‌نظر از تضمین‌های نظری، اگر بسیاری کلید به همان اسلات‌ها برخورد کنند.

روش تقسیم

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

h(k) = k mod m

این محاسبه‌اش سریع است اما به انتخاب m حساس است. انتخاب m به‌عنوان یک توان دو یک اشتباه رایج است، چون باعث می‌شود h(k) فقط به بیت‌های کم‌ارزش k بستگی داشته باشد، و بیت‌های با‌ارزش‌تر را کاملاً نادیده می‌گیرد، که می‌تواند توزیع ضعیفی برای الگوهای کلید خاص ایجاد کند. انتخاب m به‌عنوان یک عدد اول که خیلی نزدیک به یک توان دو نیست معمولاً توزیع‌های بهتر و یکنواخت‌تری در عمل تولید می‌کند.

روش ضرب

یک رویکرد جایگزین کلید را در یک ثابت A بین ۰ و ۱ ضرب می‌کند، بخش اعشاری را استخراج می‌کند، و آن را به اندازه جدول مقیاس می‌کند:

h(k) = ⌊m · (k · A mod 1)⌋

این روش این مزیت را دارد که مقدار خاص m برای کارایی‌اش حیاتی نیست، برخلاف روش تقسیم، که انعطاف‌پذیری بیشتری در انتخاب اندازه جدول (اغلب یک توان دو، برای راحتی پیاده‌سازی) می‌دهد.

آدرس‌دهی باز: یک جایگزین برای زنجیره‌بندی

Open Addressing (آدرس‌دهی باز) کاملاً از لیست‌های پیوندی اجتناب می‌کند، و همه عناصر را مستقیماً درون خود آرایه جدول هش ذخیره می‌کند. وقتی برخوردی رخ می‌دهد، الگوریتم به‌طور سیستماتیک اسلات‌های جایگزین را کاوش می‌کند تا یکی خالی پیدا شود، با دنبال کردن یک Probe Sequence (توالی کاوش) قطعی تعیین‌شده توسط کلید.

HASH-INSERT(T, k):
  i = 0
  تکرار کن:
      j = h(k, i)
      اگر T[j] == NIL:
          T[j] = k
          j را برگردان
      در غیر این صورت:
          i = i + 1
  تا i == m
  خطا "hash table overflow"

کاوش خطی

ساده‌ترین توالی کاوش، Linear Probing (کاوش خطی)، اسلات‌های پیاپی را پس از یک برخورد بررسی می‌کند:

h(k, i) = (h'(k) + i) mod m

این ساده است و کارایی کش خوبی دارد، که پیش‌تر در این مجموعه درباره سلسله‌مراتب حافظه بحث شد، چون مکان‌های حافظه پیاپی بررسی می‌شوند. با این حال، از Primary Clustering (خوشه‌بندی اولیه) رنج می‌برد: دنباله‌های طولانی از اسلات‌های اشغال‌شده پیاپی تمایل به شکل‌گیری دارند، چون هر کلیدی که به هرجایی درون یک خوشه هش شود آن را بیشتر گسترش می‌دهد، که برخوردهای آینده را به‌طور فزاینده محتمل‌تر می‌کند.

کاوش درجه‌دوم و هشینگ دوگانه

Quadratic Probing (کاوش درجه‌دوم) از یک تابع درجه‌دوم از شماره کاوش برای پخش بیشتر کاوش‌ها استفاده می‌کند:

h(k, i) = (h'(k) + c₁i + c₂i²) mod m

Double Hashing (هشینگ دوگانه) از یک تابع هش دوم و مستقل برای تعیین اندازه گام بین کاوش‌ها استفاده می‌کند، که معمولاً یکنواخت‌ترین توزیع را از میان سه رویکرد تولید می‌کند و در عمل نزدیک‌ترین به ایده‌آل نظری هشینگ یکنواخت است.

h(k, i) = (h₁(k) + i · h₂(k)) mod m

مسئله حذف در آدرس‌دهی باز

حذف در آدرس‌دهی باز ظریف‌تر از زنجیره‌بندی است. صرفاً علامت‌گذاری یک اسلات به‌عنوان خالی پس از حذف می‌تواند جستجوهای آینده را بشکند، چون توالی کاوش برای برخی کلید دیگر ممکن است به عبور از آن اسلات اکنون-خالی برای یافتن موقعیت واقعی‌اش جلوتر متکی باشد. راه‌حل استاندارد از یک نشانگر خاص DELETED متمایز از NIL استفاده می‌کند: جستجوها فراتر از یک نشانگر DELETED ادامه می‌یابند، اما درج‌ها می‌توانند آن اسلات را دوباره استفاده کنند.

ملاحظات عملی

پیاده‌سازی‌های جدول هش دنیای واقعی باید چند مسئله عملی فراتر از الگوریتم اصلی را مدیریت کنند. با رشد فاکتور بار به‌اندازه‌ای زیاد، کارایی تنزل می‌یابد، پس پیاده‌سازی‌ها معمولاً Rehash (دوباره‌هش) می‌کنند — یک جدول بزرگ‌تر تخصیص می‌دهند و هر عنصر را دوباره درج می‌کنند — وقتی فاکتور بار از یک آستانه، مانند ۰.۷۵، فراتر رود. این عملیات تغییر اندازه وقتی رخ می‌دهد گران است، اما به‌اندازه کافی به‌ندرت رخ می‌دهد (تقریباً دو برابر کردن اندازه جدول هر بار) که هزینه‌اش، وقتی میانگین‌گیری شود (یا Amortized (مستهلک)، مفهومی که بعداً در این مجموعه به‌طور عمیق بررسی می‌شود) در سراسر بسیاری درج، O(1) به‌ازای هر درج باقی می‌ماند.

چرا جداول هش این‌قدر گسترده استفاده می‌شوند

جداول هش زیربنای بسیاری از پیاده‌سازی‌های آرایه‌های انجمنی، دیکشنری، و مجموعه‌ای هستند که در تقریباً هر کتابخانه استاندارد زبان برنامه‌نویسی امروزی یافت می‌شوند. کارایی مورد انتظار O(1)شان برای جستجو، درج، و حذف، آن‌ها را به انتخاب پیش‌فرض هروقت جستجوی سریع مبتنی-بر-کلید مورد نیاز باشد تبدیل می‌کند، بهبود چشمگیری نسبت به O(log n) درخت‌های جستجوی متوازن، که بعداً در این مجموعه بحث می‌شوند، هروقت ترتیب کلیدها مورد نیاز نباشد و فقط جستجوی سریع اهمیت داشته باشد.