درهم‌سازی کوکو

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

نام این الگوریتم با توجه به شباهتش به برخی رفتارهای پرندهٔ کوکو انتخاب شده‌است. این پرنده، هنگامی که از یکی از تخم‌هایش جوجه ای بیرون آید، تخم‌های قدیمی تر یا جوجه‌های جوان تر را به بیرون لانه هل می‌دهد، در این روند نیز ممکن است درج عناصر جدید، موجب جابه‌جایی عناصر دیگر شود.

زمان اجرای این الگوریتم برای یافتن یک عنصر در جدول، در بدترین حالت، زمان ثابت *<math>O(1)</math>*، و در درج و حذف عناصر به صورت سرشکن، زمان ثابت O(1) می‌باشد.

## تاریخچه
این الگوریتم نخستین بار در سال ۲۰۰۱ میلادی توسط *Rasmus Pagh* و *Flemming Friche Rodler* معرفی شد. سپس در سال ۲۰۰۳ میلادی توسط *Luc Devroye* و *Pat Morin* آنالیزهای گسترده‌تری روی آن انجام شد. از آن پس نیز انواع مختلفی از آن برای کاربردهای مختلف در صنعت ارائه شده‌است.

## کاربرد
با توجه به تضمین این الگوریتم از جستجوی عناصر در بدترین حالت، در زمان ثابت *<math>O(1)</math>*، این الگوریتم در صنایعی که به پاسخ سریع و آنی احتیاج دارند استفاده می‌شود.

برای مثال یکی از انواع این جدول درهم‌سازی به نام *++Cuckoo* در شبکه‌های کامپیوتری استفاده می‌شود.

هم‌چنین می‌توان به یک مدل ساده شده از درهم‌سازی کوکو به نام *Skewed-Associative Cache* اشاره کرد که در برای پیاده‌سازی *Cache*ها در برخی واحدهای پردازش مرکزی به کار می‌رود.

## انواع
الگوریتم‌های مختلفی از درهم‌سازی کوکو با اهداف کاهش تعداد بازسازی جدول و افزایش استفادهٔ مفید از حافظه ارائه شده‌اند.

برای مثال استفاده از سه تابع درهم‌سازی می‌تواند باعث شود ضریب بارگذاری الگوریتم به ۹۱٪ برسد یا امکان ذخیره‌سازی دو کلید در هر خانه از جدول این ضریب را به بالای ۸۰٪ می‌رساند (این الگوریتم، درهم‌سازی کوکوی جعبه ای نام دارد)

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

## عمل‌کرد
در درهم‌سازی کوکو، برای ذخیرهٔ عناصر از دو جدولِ هم‌اندازهٔ T_1 و T_2 به طول r و دو تابع درهم‌سازی مجزایِ h_1 , h_2 : U \rightarrow \{0,...,r-1\} استفاده می‌شود. هر عنصر با کلید x یا در خانهٔ h_1(x) در جدولِ T_1 یا در خانهٔ h_2(x) در جدول T_2 ذخیره خواهد شد (هر عنصر تنها در یک جدول ذخیره می‌شود نه در هردو جدول).

### جستجو عناصر در جدول
با توجه به ساختارِ جدول، رویهٔ جستجوی وجود یا عدم وجود یک عنصر هم‌چون x ، آن است که ابتدا خانهٔ h_1(x) در جدولِ T_1 را بررسی کرده، در صورتی که عنصر x در آن وجود نداشت، خانهٔ h_2(x) در جدول T_2 را بررسی می‌کنیم، در صورتی که عنصر x آنجا هم نبود، x در جدول درهم‌سازی وجود ندارد.

این رویه به کمک شبه‌کد زیر که در قالب زبان پایتون نوشته شده‌است قابل بیان است:
```python3
def lookup(x):
    return T1[h1(x)] == x or T2[h2(x)] == x
```
در این رویه که در بدترین حالت، زمان ثابت O(1) به طول خواهد انجامید، تضمین می‌شود برای یافتن یک عنصر در جدول، حداکثر دو بار دسترسی به حافظه رخ بدهد. این موضوع از اصلی‌ترین برتری‌های درهم‌سازی کوکو نسبت به شیوه‌های دیگر درهم سازی با حافظهٔ خطی، هم‌چون آدرس‌دهی باز به کمک، جستجویِ خطی می‌باشد.

### حذف عناصر از جدول
برای حذف یک عنصر از جدول، کافیست ابتدا آن عنصر را در جدول یافته و بعد با جای آن مقدارِ خالی قرار دهیم (در روش‌های آدرس‌دهی باز، از یک مقدار مشخص برای مشخص کردن خالی بودن یک خانه از جدول استفاده می‌شود که با آن مقدارِ خالی می‌گویند). این رویه از لحاظ زمان عمل‌کرد و تعداد دسترسی به حافظه، مشابه جستجوی عناصر در جدول می‌باشد.

### درج عناصر در جدول
به هنگام درج یک عنصر x به جدول، در صورتی که یکی از خانه‌های  h_1(x) در جدولِ T_1 یا  h_2(x) در جدول T_2 خالی بودند، مشکلی وجود ندارد و x را در جایگاه خالی قرار می‌دهیم. اما در صورتی که هردو خانه توسط عناصر قبلیِ موجود در جدول اشغال شده بودند، عنصر xرا در یکی از خانه‌های اشغال شده قرار می‌دهیم و عنصر قدیمی موجود در آن جایگاه را تلاش می‌کنیم در جدول به همین صورت درج کنیم. در واقع در این الگوریتم به صورت حریصانه تلاش می‌کنیم که عناصر قدیمی موجود در جدول را از جایگاهشان در بخش دوم جدول، به جایگاهشان در بخش اول جدول جابه‌جا کنیم، و بالعکس، تا جا برای عنصر جدید درج شده در جدول آزاد شود. به عنوان مثال تصویر زیر فرایند یک درج را نشان می‌دهد.
جایگزین=تصویر مراحل درج یک عنصر جدید در جدول درهم‌سازی کوکو|وسط|بی‌قاب|815x815پیکسل
مشکل این شیوهٔ حریصانه آن است که ممکن است هنگام جابه‌جایی کلیدهای قبلی به جایگاه دیگرشان در یک حلقهٔ بی پایان مثل مثال زیر بیافتیم یا این که تعداد عملیات‌های جابه‌جاییمان بسیار زیاد شود، می‌توان نشان داد که در صورتی که r \geqslant (1 + \epsilon)nباشد (r طول جدول‌ها و n تعداد عناصر موجود در جدول و \epsilonیک عدد مثبت است) احتمال این که این اتفاق رخ دهد برابر O(1/n)می‌باشد.

در این صورت تنها راه آن است که در صورت رخ داد این مشکلات، تمام جدول را از نو بسازیم و عنصر جدید x را در جدول درج کنیم.
جایگزین=تصویر حلقهٔ بی‌نهایت ایجاد شده در درج عنصر جدید در جدول درهم‌سازی کوکو|وسط|بندانگشتی|383x383پیکسل|در جدول درهم‌سازی کوکو نشان داده شده در تصویر، درج عنصر جدید x به جدول امکان ندارد و جابه‌جایی عناصر قبلی کمکی به آزاد شدن خانه‌ای خالی برای عنصر x نخواهد کرد، چرا که این جابه‌جایی تا بی‌نهایت تکرار شده و جایگاهی برای x خالی نخواهد شد.
برای حل هر دو مشکل ذکر شده، در الگوریتم در صورتی که تعداد عملیات‌های جابه جایی از یک عدد مشخص چون MaxLoopSizeبیشتر شد، جدول را درجا با کمک دو تابع درهم سازی جدید بازسازی می‌کنیم.

این روند حریصانه به صورت شبه‌کد زیر که به قالب زبان پایتون نوشته شده‌است قابل بیان است:
```python3
def insert(x):
    if lookup(x):
        return
    if not table[h2(x)]:        # if cell h2(x) of table was empty
        table[h2(x)] = x
        return
    hold = x
    index = h1(x)
    for i in range(0,MAX_LOOP_SIZE):
        if not table[index]:    # if cell index of table was empty
            table[index] = hold
            return
        table[index], hold = hold, table[index]
        if index == h1(hold):
            index = h2(hold)
        else:
            index = h1(hold)
    rehash(table)
    insert(x)
```
نشان داده می‌شود در صورتی که مقدار MaxLoopSize برابر \lceil3\times\log_{1+\varepsilon}r\rceilانتخاب شود (r طول جدول‌ها و \epsilonیک عدد مثبت است که به ازای آن r \geqslant (1 + \epsilon)nباشد)، عملیات درج هر عنصر در جدول زمان سرشکن ثابت O(1) طول خواهد کشید.

## فضای اشغال شده در حافظه
این شیوهٔ درهم‌سازی، برای ذخیره شدن در رایانه به ضریبی خطی از تعداد عناصر موجود در جدول (n)، خانه از حافظه احتیاج خواهد داشت. بدین منظور برای حفظ این خاصیتِ جدول، عملیات حذف و درج عناصر در جدول را کمی تغییر می‌دهند. این ایده همان ایدهٔ دوبرابر کردن/ نصف کردن معمول است که در بسیاری از الگوریتم‌ها به کار می‌رود.

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

## جستارهای مربوط
# درهم‌سازی دوگانه
# توابع درهم‌سازی کامل

## منابع


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