الگوریتم Cuckoo Hashing چیست و چگونه کار می‌کند؟

Cuckoo Hashing یک روش برای پیاده‌سازی Hash Table است که هدف اصلی آن حل مسئله‌ی Collision یا برخورد بین کلیدهاست.

در یک جدول هش معمولی ممکن است دو کلید مختلف به یک موقعیت یکسان نگاشت شوند. روش‌هایی مانند Chaining و Open Addressing برای حل این مشکل وجود دارند، اما Cuckoo Hashing رویکرد متفاوتی دارد: هر کلید چند موقعیت احتمالی دارد و اگر موقعیت موردنظر اشغال باشد، کلید جدید می‌تواند کلید قبلی را از جای خود بیرون کند.

نام این الگوریتم از رفتار پرنده فاخته (Cuckoo) گرفته شده است؛ برخی گونه‌های این پرنده تخم خود را در لانه‌ی پرندگان دیگر قرار می‌دهند و جوجه‌ی فاخته ممکن است تخم‌های دیگر را از لانه بیرون بیندازد. Cuckoo Hashing نیز تقریباً از همین ایده استفاده می‌کند.

مسئله Collision در Hash Table

فرض کنید یک Hash Table داریم و تابع هش ما موقعیت یک کلید را مشخص می‌کند:

index = hash(key)

اگر دو کلید مختلف به یک index برسند، Collision اتفاق می‌افتد.

برای مثال:

hash(20) = 3
hash(45) = 3

هر دو کلید می‌خواهند در خانه‌ی شماره 3 قرار بگیرند.

Cuckoo Hashing برای کاهش این مشکل معمولاً از دو تابع هش استفاده می‌کند:

h1(key)
h2(key)

بنابراین هر کلید حداقل دو موقعیت احتمالی برای ذخیره شدن دارد.

ایده اصلی Cuckoo Hashing

فرض کنید می‌خواهیم کلید A را وارد جدول کنیم.

ابتدا موقعیت آن را با تابع اول محاسبه می‌کنیم:

h1(A)

اگر آن خانه خالی باشد، A همان‌جا قرار می‌گیرد.

اما اگر خانه توسط B اشغال شده باشد، A جای B را می‌گیرد و B باید به موقعیت جایگزین خود منتقل شود.

A → h1(A)
B → h2(B)

اگر محل دوم B نیز اشغال باشد، همین فرآیند دوباره تکرار می‌شود.

این عملیات را می‌توان به شکل ساده زیر تصور کرد:

Insert A
   ↓
Position occupied by B
   ↓
A replaces B
   ↓
Move B to its alternative position
   ↓
Repeat if necessary

یک مثال ساده

فرض کنید دو تابع هش داریم:

h1(x) = x % 5
h2(x) = (x / 5) % 5

و قصد داریم چند مقدار را وارد جدول کنیم.

برای مقدار 10:

h1(10) = 0

پس 10 در موقعیت صفر قرار می‌گیرد.

حالا اگر مقدار دیگری نیز بخواهد در موقعیت صفر قرار گیرد، می‌تواند مقدار 10 را بیرون کند. سپس 10 با استفاده از h2 موقعیت دوم خود را پیدا می‌کند.

در نتیجه برخلاف Chaining، لازم نیست برای هر خانه یک Linked List یا ساختار جانبی نگهداری کنیم.

جستجو در Cuckoo Hashing

یکی از مهم‌ترین مزایای این روش، سرعت جستجو است.

برای پیدا کردن یک کلید x فقط کافی است موقعیت‌های احتمالی آن را بررسی کنیم:

h1(x)
h2(x)

اگر از دو تابع هش استفاده شده باشد، حداکثر دو خانه بررسی می‌شوند.

بنابراین در شرایط مناسب پیچیدگی جستجو برابر است با:

O(1)

و نکته مهم این است که تعداد مکان‌های مورد بررسی محدود است.

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

فرآیند کلی Insert را می‌توان به صورت زیر نوشت:

1. h1(key) را محاسبه کن
2. اگر خانه خالی بود، key را قرار بده
3. اگر خانه اشغال بود، کلید قبلی را بیرون کن
4. key جدید را جایگزین کن
5. برای کلید بیرون‌شده موقعیت جایگزین را پیدا کن
6. این فرآیند را تا پیدا شدن خانه خالی ادامه بده

اما یک مشکل مهم وجود دارد: ممکن است این جابه‌جایی‌ها وارد Cycle شوند.

مشکل Cycle

فرض کنید جابه‌جایی کلیدها به شکل زیر اتفاق بیفتد:

A → B → C → A → B → C → ...

در این حالت هیچ خانه‌ی خالی پیدا نمی‌شود و الگوریتم دائماً بین چند موقعیت حرکت می‌کند.

برای جلوگیری از این اتفاق معمولاً تعداد جابه‌جایی‌ها محدود می‌شود.

مثلاً:

MAX_KICKS = 50

اگر بعد از 50 جابه‌جایی هنوز کلید قرار نگرفته باشد، می‌توان عملیات Rehashing انجام داد.

Rehashing چیست؟

در Rehashing معمولاً یکی از این کارها انجام می‌شود:

• انتخاب توابع هش جدید
• ساخت جدول بزرگ‌تر
• درج دوباره کلیدهای موجود

بنابراین هزینه‌ی یک درج خاص ممکن است زیاد شود، اما در شرایط معمول عملکرد کلی همچنان بسیار مناسب است.

پیاده‌سازی ساده با JavaScript

نمونه‌ی ساده‌شده‌ای از ایده Cuckoo Hashing:

class CuckooHashTable {
  constructor(size = 11) {
    this.size = size;
    this.table1 = new Array(size).fill(null);
    this.table2 = new Array(size).fill(null);
  }

  hash1(key) {
    return key % this.size;
  }

  hash2(key) {
    return Math.floor(key / this.size) % this.size;
  }

  search(key) {
    const i1 = this.hash1(key);
    const i2 = this.hash2(key);

    return this.table1[i1] === key || this.table2[i2] === key;
  }

  insert(key) {
    let current = key;
    let table = 1;
    const maxKicks = this.size * 2;

    for (let i = 0; i < maxKicks; i++) {
      if (table === 1) {
        const index = this.hash1(current);

        if (this.table1[index] === null) {
          this.table1[index] = current;
          return true;
        }

        [current, this.table1[index]] = [this.table1[index], current];
        table = 2;
      } else {
        const index = this.hash2(current);

        if (this.table2[index] === null) {
          this.table2[index] = current;
          return true;
        }

        [current, this.table2[index]] = [this.table2[index], current];
        table = 1;
      }
    }

    return false;
  }
}

این کد برای درک مفهوم الگوریتم ساده شده است. در یک پیاده‌سازی Production باید Rehashing، تغییر اندازه جدول، توابع هش مناسب و مدیریت Load Factor نیز در نظر گرفته شوند.

پیچیدگی زمانی

در حالت معمول می‌توان عملکرد را تقریباً به صورت زیر در نظر گرفت:

| عملیات | پیچیدگی معمول | |---|---| | Search | O(1) | | Delete | O(1) | | Insert | O(1) به صورت مورد انتظار | | Rehash | O(n) |

مزیت اصلی Cuckoo Hashing این است که جستجو فقط تعداد بسیار محدودی از موقعیت‌ها را بررسی می‌کند.

Cuckoo Hashing در مقایسه با Chaining

در Separate Chaining هر خانه می‌تواند شامل مجموعه‌ای از عناصر باشد. بنابراین جستجو ممکن است نیازمند بررسی چند عنصر باشد.

اما در Cuckoo Hashing هر کلید فقط در یکی از چند موقعیت مشخص قرار می‌گیرد.

Chaining:
index → A → B → C → D

Cuckoo Hashing:
h1(key) OR h2(key)

به همین دلیل Cuckoo Hashing می‌تواند برای سیستم‌هایی که سرعت Lookup اهمیت زیادی دارد گزینه‌ی جذابی باشد.

مزایا

مهم‌ترین مزایای Cuckoo Hashing عبارت‌اند از:

• جستجوی بسیار سریع
• پیچیدگی مورد انتظار O(1)
• تعداد محدود دسترسی برای Lookup
• عدم نیاز به Linked List در هر Bucket
• رفتار مناسب برای برخی ساختارهای داده با تعداد زیاد Query

محدودیت‌ها

این روش بدون مشکل نیست:

• عملیات Insert از Search پیچیده‌تر است.
• ممکن است Cycle ایجاد شود.
• گاهی Rehashing ضروری است.
• کیفیت توابع Hash اهمیت زیادی دارد.
• بالا رفتن Load Factor می‌تواند درج را دشوار کند.

Cuckoo Hashing کجا کاربرد دارد؟

این الگوریتم زمانی جذاب است که تعداد Lookupها زیاد باشد و سرعت جستجو اهمیت بالایی داشته باشد.

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

• سیستم‌های Cache
• ساختارهای In-Memory
• پردازش شبکه
• سیستم‌های با Lookup سریع
• برخی ساختارهای مرتبط با Database و Storage
• سیستم‌هایی که Predictable Lookup اهمیت دارد

ایده‌ی Cuckoo Hashing همچنین پایه‌ای برای ساختارهای دیگری مانند Cuckoo Filter شده است.

Cuckoo Filter چیست؟

Cuckoo Filter یک ساختار داده احتمالی برای تست عضویت است و از ایده‌های Cuckoo Hashing استفاده می‌کند. این ساختار در برخی سناریوها به عنوان جایگزینی برای Bloom Filter مطرح می‌شود و قابلیت‌هایی مانند حذف عناصر را نیز بهتر پشتیبانی می‌کند.

جمع‌بندی

Cuckoo Hashing یکی از جالب‌ترین روش‌های مدیریت Collision در Hash Table است. ایده‌ی اصلی آن ساده است: هر کلید چند خانه‌ی احتمالی دارد و اگر خانه‌ای اشغال باشد، کلید جدید می‌تواند عنصر قبلی را بیرون کرده و آن را به محل جایگزین منتقل کند.

این طراحی باعث می‌شود عملیات Search بسیار سریع و قابل پیش‌بینی باشد، هرچند Insert می‌تواند پیچیده‌تر شود و در بعضی شرایط به Rehashing نیاز داشته باشد.

اگر Hash Table را یاد گرفته‌اید و با روش‌هایی مانند Chaining و Open Addressing آشنا هستید، Cuckoo Hashing قدم مناسبی برای درک عمیق‌تر طراحی ساختارهای داده و تکنیک‌های پیشرفته‌ی Hashing است.