موضوع مقاله: درهم‌سازی کوکو | مخاطب: عمومی | لحن: دانشنامه‌ای | ساختار: عنوان، مقدمه، 3 بخش، جمع‌بندی | مقاله: | # درهم‌سازی کوکو | مقدمه: درهم‌سازی کوکو، یکی از شیوه‌های پیاده‌سازی جداول درهم سازی در علوم رایانه می‌باشد که برای حل مشکل برخورد عناصر در جدول، از آدرس‌دهی باز استفاده می‌کند. | ## بخش 1: درهم‌سازی کوکو | این پرنده، هنگامی که از یکی از تخم‌هایش جوجه ای بیرون آید، تخم‌های قدیمی تر یا جوجه‌های جوان تر را به بیرون لانه هل می‌دهد، در این روند نیز ممکن است درج عناصر جدید، موجب جابه‌جایی عناصر دیگر شود. زمان اجرای این الگوریتم برای یافتن یک عنصر در جدول، در بدترین حالت، زمان ثابت ، و در درج و حذف عناصر به صورت سرشکن، زمان ثابت می‌باشد. کاربرد با توجه به تضمین این الگوریتم از جستجوی عناصر در بدترین حالت، در زمان ثابت ، این الگوریتم در صنایعی که به پاسخ سریع و آنی احتیاج دارند استفاده می‌شود. برای مثال یکی از انواع این جدول درهم‌سازی به نام ++Cuckoo در شبکه‌های کامپیوتری استفاده می‌شود. انواع الگوریتم‌های مختلفی از درهم‌سازی کوکو با اهداف کاهش تعداد بازسازی جدول و افزایش استفادهٔ مفید از حافظه ارائه شده‌اند. برای مثال استفاده از سه تابع درهم‌سازی می‌تواند باعث شود ضریب بارگذاری الگوریتم به ۹۱٪ برسد یا امکان ذخیره‌سازی دو کلید در هر خانه از جدول این ضریب را به بالای ۸۰٪ می‌رساند (این الگوریتم، درهم‌سازی کوکوی جعبه ای نام دارد) هم‌چنین می‌توان از برخی پیاده‌سازی‌های درهم‌سازی کوکو، برای رایانش موازی و اجرا در پردازنده‌های چند هسته ای و واحدهای پردازش گرافیکی به عنوان الگوریتمی چند ریسمانی اشاره کرد. عمل‌کرد در درهم‌سازی کوکو، برای ذخیرهٔ عناصر از دو جدولِ هم‌اندازهٔ و به طول و دو تابع درهم‌سازی مجزایِ استفاده می‌شود. هر عنصر با کلید یا در خانهٔ در جدولِ یا در خانهٔ در جدول ذخیره خواهد شد (هر عنصر تنها در یک جدول ذخیره می‌شود نه در هردو جدول). | ## بخش 2: درهم‌سازی کوکو | جستجو عناصر در جدول با توجه به ساختارِ جدول، رویهٔ جستجوی وجود یا عدم وجود یک عنصر هم‌چون ، آن است که ابتدا خانهٔ در جدولِ را بررسی کرده، در صورتی که عنصر در آن وجود نداشت، خانهٔ در جدول را بررسی می‌کنیم، در صورتی که عنصر آنجا هم نبود، در جدول درهم‌سازی وجود ندارد. این موضوع از اصلی‌ترین برتری‌های درهم‌سازی کوکو نسبت به شیوه‌های دیگر درهم سازی با حافظهٔ خطی، هم‌چون آدرس‌دهی باز به کمک، جستجویِ خطی می‌باشد. حذف عناصر از جدول برای حذف یک عنصر از جدول، کافیست ابتدا آن عنصر را در جدول یافته و بعد با جای آن مقدارِ خالی قرار دهیم (در روش‌های آدرس‌دهی باز، از یک مقدار مشخص برای مشخص کردن خالی بودن یک خانه از جدول استفاده می‌شود که با آن مقدارِ خالی می‌گویند). این رویه از لحاظ زمان عمل‌کرد و تعداد دسترسی به حافظه، مشابه جستجوی عناصر در جدول می‌باشد. درج عناصر در جدول به هنگام درج یک عنصر به جدول، در صورتی که یکی از خانه‌های در جدولِ یا در جدول خالی بودند، مشکلی وجود ندارد و را در جایگاه خالی قرار می‌دهیم. اما در صورتی که هردو خانه توسط عناصر قبلیِ موجود در جدول اشغال شده بودند، عنصر را در یکی از خانه‌های اشغال شده قرار می‌دهیم و عنصر قدیمی موجود در آن جایگاه را تلاش می‌کنیم در جدول به همین صورت درج کنیم. در واقع در این الگوریتم به صورت حریصانه تلاش می‌کنیم که عناصر قدیمی موجود در جدول را از جایگاهشان در بخش دوم جدول، به جایگاهشان در بخش اول جدول جابه‌جا کنیم، و بالعکس، تا جا برای عنصر جدید درج شده در جدول آزاد شود. جایگزین=تصویر مراحل درج یک عنصر جدید در جدول درهم‌سازی کوکو|وسط|بی‌قاب|815x815پیکسل مشکل این شیوهٔ حریصانه آن است که ممکن است هنگام جابه‌جایی کلیدهای قبلی به جایگاه دیگرشان در یک حلقهٔ بی پایان مثل مثال زیر بیافتیم یا این که تعداد عملیات‌های جابه‌جاییمان بسیار زیاد شود، می‌توان نشان داد که در صورتی که باشد ( طول جدول‌ها و تعداد عناصر موجود در جدول و یک عدد مثبت است) احتمال این که این اتفاق رخ دهد برابر می‌باشد. | ## بخش 3: درهم‌سازی کوکو | در این صورت تنها راه آن است که در صورت رخ داد این مشکلات، تمام جدول را از نو بسازیم و عنصر جدید را در جدول درج کنیم. برای حل هر دو مشکل ذکر شده، در الگوریتم در صورتی که تعداد عملیات‌های جابه جایی از یک عدد مشخص چون بیشتر شد، جدول را درجا با کمک دو تابع درهم سازی جدید بازسازی می‌کنیم. فضای اشغال شده در حافظه این شیوهٔ درهم‌سازی، برای ذخیره شدن در رایانه به ضریبی خطی از تعداد عناصر موجود در جدول ، خانه از حافظه احتیاج خواهد داشت. بدین منظور برای حفظ این خاصیتِ جدول، عملیات حذف و درج عناصر در جدول را کمی تغییر می‌دهند. این ایده همان ایدهٔ دوبرابر کردن/ نصف کردن معمول است که در بسیاری از الگوریتم‌ها به کار می‌رود. به هنگام حذف عناصر از جدول، در صورتی که اندازهٔ جدول بیش از اندازه بزرگ‌تر از تعداد خانه‌های اشغال شدهٔ جدول بود، جدول را از نو، با اندازه ای کوچکتر (مثلاً نصف) بازسازی می‌کنند. این کار باعث می‌شود که عملیات حذف یک عنصر از جدول، گاهی هزینهٔ زمانی بیشتری داشته باشد، اما نشان داده می‌شود که با این حال حذف یک عنصر از جدول به صورت سرشکن، زمان ثابت می‌باشد.به هنگام درج عنصری جدید در جدول، در صورتی که اندازهٔ جدول بیش از حد به تعداد خانه‌های اشغال شدهٔ جدول نزدیک بود، جدول را از نو، با اندازه ای بزرگتر (مثلاً دوبرابر) بازسازی می‌کنند. | ## جمع‌بندی | این کار نیز موجب می‌شود که فرایندهای درج در جدول، بعضاً هزینه زمانی بیشتری داشته باشند، اما نشان داده می‌شود که با این حال درج یک عنصر در جدول به صورت سرشکن، زمان ثابت به طول خواهد انجامید.