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

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

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

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

تاریخچه

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

کاربرد

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

برای مثال یکی از انواع این جدول درهم‌سازی به نام ++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$ در جدول درهم‌سازی وجود ندارد.

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

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$را در یکی از خانه‌های اشغال شده قرار می‌دهیم و عنصر قدیمی موجود در آن جایگاه را تلاش می‌کنیم در جدول به همین صورت درج کنیم. در واقع در این الگوریتم به صورت حریصانه تلاش می‌کنیم که عناصر قدیمی موجود در جدول را از جایگاهشان در بخش دوم جدول، به جایگاهشان در بخش اول جدول جابه‌جا کنیم، و بالعکس، تا جا برای عنصر جدید درج شده در جدول آزاد شود. به عنوان مثال تصویر زیر فرایند یک درج را نشان می‌دهد.

مشکل این شیوهٔ حریصانه آن است که ممکن است هنگام جابه‌جایی کلیدهای قبلی به جایگاه دیگرشان در یک حلقهٔ بی پایان مثل مثال زیر بیافتیم یا این که تعداد عملیات‌های جابه‌جاییمان بسیار زیاد شود، می‌توان نشان داد که در صورتی که $r\geqslant (1+\epsilon )n$باشد ($r$ طول جدول‌ها و $n$ تعداد عناصر موجود در جدول و $\epsilon$یک عدد مثبت است) احتمال این که این اتفاق رخ دهد برابر $O(1/n)$می‌باشد.

در این صورت تنها راه آن است که در صورت رخ داد این مشکلات، تمام جدول را از نو بسازیم و عنصر جدید $x$ را در جدول درج کنیم.

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

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

این روند حریصانه به صورت شبه‌کد زیر که به قالب زبان پایتون نوشته شده‌است قابل بیان است:

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$ برابر $\lceil 3\times \log _{1+\varepsilon }r\rceil$انتخاب شود ($r$ طول جدول‌ها و $\epsilon$یک عدد مثبت است که به ازای آن $r\geqslant (1+\epsilon )n$باشد)، عملیات درج هر عنصر در جدول زمان سرشکن ثابت $O(1)$ طول خواهد کشید.

فضای اشغال شده در حافظه

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

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

جستارهای مربوط

1. درهم‌سازی دوگانه
2. توابع درهم‌سازی کامل