درهم‌سازی کوکو کیست؟ توضیح بده.
درهم‌سازی کوکو، یکی از شیوه‌های پیاده‌سازی جداول درهم سازی در علوم رایانه می‌باشد که برای حل مشکل برخورد عناصر در جدول، از آدرس‌دهی باز استفاده می‌کند.نام این الگوریتم با توجه به شباهتش به برخی رفتارهای پرندهٔ کوکو انتخاب شده‌است. این پرنده، هنگامی که از یکی از تخم‌هایش جوجه ای بیرون آید، تخم‌های قدیمی تر یا جوجه‌های جوان تر را به بیرون لانه هل می‌دهد، در این روند نیز ممکن است درج عناصر جدید، موجب جابه‌جایی عناصر دیگر شود.زمان اجرای این الگوریتم برای یافتن یک عنصر در جدول، در بدترین حالت، زمان ثابت "formula_1"، و در درج و حذف عناصر به صورت سرشکن، زمان ثابت formula_1 می‌باشد.تاریخچه.این الگوریتم نخستین بار در سال ۲۰۰۱ میلادی توسط "Rasmus Pagh" و "Flemming Friche Rodler" معرفی شد. سپس در سال ۲۰۰۳ میلادی توسط "Luc Devroye" و "Pat Morin" آنالیزهای گسترده‌تری روی آن انجام شد. از آن پس نیز انواع مختلفی از آن برای کاربردهای مختلف در صنعت ارائه شده‌است.کاربرد.با توجه به تضمین این الگوریتم از جستجوی عناصر در بدترین حالت، در زمان ثابت "formula_1"، این الگوریتم در صنایعی که به پاسخ سریع و آنی احتیاج دارند استفاده می‌شود.برای مثال یکی از انواع این جدول درهم‌سازی به نام "++Cuckoo" در شبکه‌های کامپیوتری استفاده می‌شود.هم‌چنین می‌توان به یک مدل ساده شده از درهم‌سازی کوکو به نام "Skewed-Associative Cache" اشاره کرد که در برای پیاده‌سازی "Cache"ها در برخی واحدهای پردازش مرکزی به کار می‌رود.انواع.الگوریتم‌های مختلفی از درهم‌سازی کوکو با اهداف کاهش تعداد بازسازی جدول و افزایش استفادهٔ مفید از حافظه ارائه شده‌اند.برای مثال استفاده از سه تابع درهم‌سازی می‌تواند باعث شود ضریب بارگذاری الگوریتم به ۹۱٪ برسد یا امکان ذخیره‌سازی دو کلید در هر خانه از جدول این ضریب را به بالای ۸۰٪ می‌رساند (این الگوریتم، درهم‌سازی کوکوی جعبه ای نام دارد)هم‌چنین می‌توان از برخی پیاده‌سازی‌های درهم‌سازی کوکو، برای رایانش موازی و اجرا در پردازنده‌های چند هسته ای و واحدهای پردازش گرافیکی به عنوان الگوریتمی چند ریسمانی اشاره کرد.عمل‌کرد.در درهم‌سازی کوکو، برای ذخیرهٔ عناصر از دو جدولِ هم‌اندازهٔ formula_4 و formula_5 به طول formula_6 و دو تابع درهم‌سازی مجزایِ formula_7 استفاده می‌شود. هر عنصر با کلید formula_8 یا در خانهٔ formula_9 در جدولِ formula_4 یا در خانهٔ formula_11 در جدول formula_5 ذخیره خواهد شد (هر عنصر تنها در یک جدول ذخیره می‌شود نه در هردو جدول).جستجو عناصر در جدول.با توجه به ساختارِ جدول، رویهٔ جستجوی وجود یا عدم وجود یک عنصر هم‌چون formula_8 ، آن است که ابتدا خانهٔ formula_9 در جدولِ formula_4 را بررسی کرده، در صورتی که عنصر formula_8 در آن وجود نداشت، خانهٔ formula_11 در جدول formula_5 را بررسی می‌کنیم، در صورتی که عنصر formula_8 آنجا هم نبود، formula_8 در جدول درهم‌سازی وجود ندارد.این رویه به کمک شبه‌کد زیر که در قالب زبان پایتون نوشته شده‌است قابل بیان است:def lookup(x): return T1[h1(x)] == x or T2[h2(x)] == xدر این رویه که در بدترین حالت، زمان ثابت formula_1 به طول خواهد انجامید، تضمین می‌شود برای یافتن یک عنصر در جدول، حداکثر دو بار دسترسی به حافظه رخ بدهد. این موضوع از اصلی‌ترین برتری‌های درهم‌سازی کوکو نسبت به شیوه‌های دیگر درهم سازی با حافظهٔ خطی، هم‌چون آدرس‌دهی باز به کمک، جستجویِ خطی می‌باشد.حذف عناصر از جدول.برای حذف یک عنصر از جدول، کافیست ابتدا آن عنصر را در جدول یافته و بعد با جای آن مقدارِ خالی قرار دهیم (در روش‌های آدرس‌دهی باز، از یک مقدار مشخص برای مشخص کردن خالی بودن یک خانه از جدول استفاده می‌شود که با آن مقدارِ خالی می‌گویند). این رویه از لحاظ زمان عمل‌کرد و تعداد دسترسی به حافظه، مشابه جستجوی عناصر در جدول می‌باشد.درج عناصر در جدول.به هنگام درج یک عنصر formula_8 به جدول، در صورتی که یکی از خانه‌های formula_9 در جدولِ formula_4 یا formula_11 در جدول formula_5 خالی بودند، مشکلی وجود ندارد و formula_8 را در جایگاه خالی قرار می‌دهیم. اما در صورتی که هردو خانه توسط عناصر قبلیِ موجود در جدول اشغال شده بودند، عنصر formula_8را در یکی از خانه‌های اشغال شده قرار می‌دهیم و عنصر قدیمی موجود در آن جایگاه را تلاش می‌کنیم در جدول به همین صورت درج کنیم. در واقع در این الگوریتم به صورت حریصانه تلاش می‌کنیم که عناصر قدیمی موجود در جدول را از جایگاهشان در بخش دوم جدول، به جایگاهشان در بخش اول جدول جابه‌جا کنیم، و بالعکس، تا جا برای عنصر جدید درج شده در جدول آزاد شود. به عنوان مثال تصویر زیر فرایند یک درج را نشان می‌دهد.مشکل این شیوهٔ حریصانه آن است که ممکن است هنگام جابه‌جایی کلیدهای قبلی به جایگاه دیگرشان در یک حلقهٔ بی پایان مثل مثال زیر بیافتیم یا این که تعداد عملیات‌های جابه‌جاییمان بسیار زیاد شود، می‌توان نشان داد که در صورتی که formula_29باشد (formula_6 طول جدول‌ها و formula_31 تعداد عناصر موجود در جدول و formula_32یک عدد مثبت است) احتمال این که این اتفاق رخ دهد برابر formula_33می‌باشد.در این صورت تنها راه آن است که در صورت رخ داد این مشکلات، تمام جدول را از نو بسازیم و عنصر جدید formula_8 را در جدول درج کنیم.برای حل هر دو مشکل ذکر شده، در الگوریتم در صورتی که تعداد عملیات‌های جابه جایی از یک عدد مشخص چون formula_35بیشتر شد، جدول را درجا با کمک دو تابع درهم سازی جدید بازسازی می‌کنیم.این روند حریصانه به صورت شبه‌کد زیر که به قالب زبان پایتون نوشته شده‌است قابل بیان است: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)نشان داده می‌شود در صورتی که مقدار formula_35 برابر formula_37انتخاب شود (formula_6 طول جدول‌ها و formula_32یک عدد مثبت است که به ازای آن formula_29باشد)، عملیات درج هر عنصر در جدول زمان سرشکن ثابت formula_1 طول خواهد کشید.فضای اشغال شده در حافظه.این شیوهٔ درهم‌سازی، برای ذخیره شدن در رایانه به ضریبی خطی از تعداد عناصر موجود در جدول (formula_31)، خانه از حافظه احتیاج خواهد داشت. بدین منظور برای حفظ این خاصیتِ جدول، عملیات حذف و درج عناصر در جدول را کمی تغییر می‌دهند. این ایده همان ایدهٔ دوبرابر کردن/ نصف کردن معمول است که در بسیاری از الگوریتم‌ها به کار می‌رود.به هنگام حذف عناصر از جدول، در صورتی که اندازهٔ جدول بیش از اندازه بزرگ‌تر از تعداد خانه‌های اشغال شدهٔ جدول بود، جدول را از نو، با اندازه ای کوچکتر (مثلاً نصف) بازسازی می‌کنند. این کار باعث می‌شود که عملیات حذف یک عنصر از جدول، گاهی هزینهٔ زمانی بیشتری داشته باشد، اما نشان داده می‌شود که با این حال حذف یک عنصر از جدول به صورت سرشکن، زمان ثابت formula_1 می‌باشد.به هنگام درج عنصری جدید در جدول، در صورتی که اندازهٔ جدول بیش از حد به تعداد خانه‌های اشغال شدهٔ جدول نزدیک بود، جدول را از نو، با اندازه ای بزرگتر (مثلاً دوبرابر) بازسازی می‌کنند. این کار نیز موجب می‌شود که فرایندهای درج در جدول، بعضاً هزینه زمانی بیشتری داشته باشند، اما نشان داده می‌شود که با این حال درج یک عنصر در جدول به صورت سرشکن، زمان ثابت formula_1 به طول خواهد انجامید.