نمایش مبدأ برای درهم‌سازی کوکو

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

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

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

== تاریخچه ==
این الگوریتم نخستین بار در سال ۲۰۰۱ میلادی توسط ''Rasmus Pagh'' و ''Flemming Friche Rodler'' معرفی شد.<ref name=":0">{{یادکرد وب|نویسنده=Rasmus Pagh و Flemming Friche Rodler|کد زبان=en|تاریخ=|وبگاه=|نشانی=http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.25.4189|عنوان=مقالهٔ درهم سازی کوکو}}</ref> سپس در سال ۲۰۰۳ میلادی توسط ''Luc Devroye'' و ''Pat Morin'' آنالیزهای گسترده‌تری روی آن انجام شد.<ref>{{یادکرد وب|نویسنده=Pat Morin و Luc Devroy|کد زبان=en|تاریخ=|وبگاه=|نشانی=http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.8.8867&rep=rep1&type=pdf|عنوان=مقالهٔ آنالیز دقیق‌تری از درهم‌سازی کوکو}}</ref> از آن پس نیز انواع مختلفی از آن برای کاربردهای مختلف در صنعت ارائه شده‌است.

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

برای مثال یکی از انواع این جدول درهم‌سازی به نام ''++Cuckoo'' در [[شبکه رایانه‌ای|شبکه‌های کامپیوتری]] استفاده می‌شود.<ref>{{یادکرد وب|نویسنده=Nicolas Le Scouarnec|کد زبان=en|تاریخ=|وبگاه=|نشانی=https://arxiv.org/pdf/1712.09624.pdf|عنوان=مقالهٔ درهم‌سازی کوکو ++ :کاربردها در شبکه‌های کامپیوتری}}</ref>

هم‌چنین می‌توان به یک مدل ساده شده از درهم‌سازی کوکو به نام ''Skewed-Associative Cache'' اشاره کرد که در برای پیاده‌سازی ''Cache''ها در برخی [[واحد پردازش مرکزی|واحدهای پردازش مرکزی]] به کار می‌رود.<ref>{{یادکرد وب|نویسنده=|کد زبان=en|تاریخ=|وبگاه=|نشانی=http://www.irisa.fr/caps/PROJECTS/Architecture/|عنوان=Cache Architecture- Skewed-Associative Caches}}</ref>

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

برای مثال استفاده از سه تابع درهم‌سازی می‌تواند باعث شود ضریب بارگذاری الگوریتم به ۹۱٪ برسد<ref name=":2">{{یادکرد وب|نویسنده=Michael Mitzenmacher|کد زبان=|تاریخ=|وبگاه=|نشانی=http://www.eecs.harvard.edu/~michaelm/postscripts/esa2009.pdf|عنوان=مقالهٔ سوالاتی در مورد درهم‌سازی کوکو}}</ref> یا امکان ذخیره‌سازی دو کلید در هر خانه از جدول این ضریب را به بالای ۸۰٪ می‌رساند (این الگوریتم، درهم‌سازی کوکوی جعبه ای نام دارد)<ref>{{یادکرد وب|نویسنده=Christoph Weidling و Martin Dietzfelbinger|کد زبان=en|تاریخ=|وبگاه=|نشانی=https://www.sciencedirect.com/science/article/pii/S0304397507001570?via=ihub|عنوان=مقالهٔ Balanced allocation and dictionaries with tightly packed constant size bins}}</ref>

هم‌چنین می‌توان از برخی پیاده‌سازی‌های درهم‌سازی کوکو، برای [[رایانش موازی]] و اجرا در [[پردازنده چندهسته‌ای|پردازنده‌های چند هسته ای]] و [[واحد پردازش گرافیکی|واحدهای پردازش گرافیکی]] به عنوان [[الگوریتم‌های چندریسمانی|الگوریتمی چند ریسمانی]] اشاره کرد.<ref name=":2"/>

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

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

این رویه به کمک [[شبه‌کد]] زیر که در قالب زبان [[پایتون (زبان برنامه‌نویسی)|پایتون]] نوشته شده‌است قابل بیان است:<syntaxhighlight lang="python3" line="1">
def lookup(x):
    return T1[h1(x)] == x or T2[h2(x)] == x

</syntaxhighlight>در این رویه که در بدترین حالت، زمان ثابت <math>O(1)</math> به طول خواهد انجامید، تضمین می‌شود برای یافتن یک عنصر در جدول، حداکثر دو بار دسترسی به [[RAM|حافظه]] رخ بدهد. این موضوع از اصلی‌ترین برتری‌های درهم‌سازی کوکو نسبت به شیوه‌های دیگر درهم سازی با حافظهٔ خطی، هم‌چون آدرس‌دهی باز به کمک، جستجویِ خطی می‌باشد.<ref name=":0"/>

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

=== درج عناصر در جدول ===
به هنگام درج یک عنصر <math>x</math> به جدول، در صورتی که یکی از خانه‌های  <math>h_1(x)</math> در جدولِ <math>T_1</math> یا  <math>h_2(x)</math> در جدول <math>T_2</math> خالی بودند، مشکلی وجود ندارد و <math>x</math> را در جایگاه خالی قرار می‌دهیم. اما در صورتی که هردو خانه توسط عناصر قبلیِ موجود در جدول اشغال شده بودند، عنصر <math>x</math>را در یکی از خانه‌های اشغال شده قرار می‌دهیم و عنصر قدیمی موجود در آن جایگاه را تلاش می‌کنیم در جدول به همین صورت درج کنیم. در واقع در این الگوریتم به صورت [[الگوریتم حریصانه|حریصانه]] تلاش می‌کنیم که عناصر قدیمی موجود در جدول را از جایگاهشان در بخش دوم جدول، به جایگاهشان در بخش اول جدول جابه‌جا کنیم، و بالعکس، تا جا برای عنصر جدید درج شده در جدول آزاد شود. به عنوان مثال تصویر زیر فرایند یک درج را نشان می‌دهد.
[[پرونده:Cucko hashing-insertion sample step by step.png|جایگزین=تصویر مراحل درج یک عنصر جدید در جدول درهم‌سازی کوکو|وسط|بی‌قاب|815x815پیکسل]]
مشکل این شیوهٔ حریصانه آن است که ممکن است هنگام جابه‌جایی کلیدهای قبلی به جایگاه دیگرشان در یک حلقهٔ بی پایان مثل مثال زیر بیافتیم یا این که تعداد عملیات‌های جابه‌جاییمان بسیار زیاد شود، می‌توان نشان داد که در صورتی که <math>r \geqslant (1 + \epsilon)n</math>باشد (<math>r</math> طول جدول‌ها و <math>n</math> تعداد عناصر موجود در جدول و <math>\epsilon</math>یک عدد مثبت است) احتمال این که این اتفاق رخ دهد برابر <math>O(1/n)</math>می‌باشد.<ref name=":1">{{یادکرد وب|نویسنده=Charles Chen از دانشگاه Stanford|کد زبان=en|تاریخ=|وبگاه=|نشانی=https://cs.stanford.edu/~rishig/courses/ref/l13a.pdf|عنوان=مقالهٔ نگاهی به درهم‌سازی کوکو}}</ref>

در این صورت تنها راه آن است که در صورت رخ داد این مشکلات، تمام جدول را از نو بسازیم و عنصر جدید <math>x</math> را در جدول درج کنیم.
[[پرونده:Cuckoo hashing-infinite insertion loop.png|جایگزین=تصویر حلقهٔ بی‌نهایت ایجاد شده در درج عنصر جدید در جدول درهم‌سازی کوکو|وسط|بندانگشتی|383x383پیکسل|در جدول درهم‌سازی کوکو نشان داده شده در تصویر، درج عنصر جدید x به جدول امکان ندارد و جابه‌جایی عناصر قبلی کمکی به آزاد شدن خانه‌ای خالی برای عنصر x نخواهد کرد، چرا که این جابه‌جایی تا بی‌نهایت تکرار شده و جایگاهی برای x خالی نخواهد شد.]]
برای حل هر دو مشکل ذکر شده، در الگوریتم در صورتی که تعداد عملیات‌های [[جابه‌جایی|جابه جایی]] از یک عدد مشخص چون <math>MaxLoopSize</math>بیشتر شد، جدول را درجا با کمک دو تابع درهم سازی جدید بازسازی می‌کنیم.

این روند حریصانه به صورت شبه‌کد زیر که به قالب زبان پایتون نوشته شده‌است قابل بیان است:<syntaxhighlight lang="python3" line="1">
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)
</syntaxhighlight>نشان داده می‌شود در صورتی که مقدار <math>MaxLoopSize</math> برابر <math>\lceil3\times\log_{1+\varepsilon}r\rceil</math>انتخاب شود (<math>r</math> طول جدول‌ها و <math>\epsilon</math>یک عدد مثبت است که به ازای آن <math>r \geqslant (1 + \epsilon)n</math>باشد)، عملیات درج هر عنصر در جدول زمان سرشکن ثابت <math>O(1)</math> طول خواهد کشید.<ref name=":1"/>

== فضای اشغال شده در حافظه ==
این شیوهٔ درهم‌سازی، برای ذخیره شدن در رایانه به ضریبی خطی از تعداد عناصر موجود در جدول (<math>n</math>)، خانه از حافظه احتیاج خواهد داشت. بدین منظور برای حفظ این خاصیتِ جدول، عملیات حذف و درج عناصر در جدول را کمی تغییر می‌دهند. این ایده همان ایدهٔ دوبرابر کردن/ نصف کردن معمول است که در بسیاری از الگوریتم‌ها به کار می‌رود.<ref name=":0"/>

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

== جستارهای مربوط ==
# [[درهم‌سازی دوگانه]]
# [[:en:Perfect hash function|توابع درهم‌سازی کامل]]

== منابع ==
<references group=""/>

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