درهم سازی کوکو، یکی از شیوه های پیاده سازی جداول درهم سازی در علوم رایانه می باشد که برای حل مشکل برخورد عناصر در جدول، از آدرس دهی باز استفاده می کند.
نام این الگوریتم با توجه به شباهتش به برخی رفتارهای پرندهٔ کوکو انتخاب شده است. این پرنده، هنگامی که از یکی از تخم هایش جوجه ای بیرون آید، تخم های قدیمی تر یا جوجه های جوان تر را به بیرون لانه هل می دهد، در این روند نیز ممکن است درج عناصر جدید، موجب جابه جایی عناصر دیگر شود.
زمان اجرای این الگوریتم برای یافتن یک عنصر در جدول، در بدترین حالت، زمان ثابت 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 → { 0 , . . . , r − 1 } استفاده می شود. هر عنصر با کلید x یا در خانهٔ h 1 ( x ) در جدولِ T 1 یا در خانهٔ h 2 ( x ) در جدول T 2 ذخیره خواهد شد ( هر عنصر تنها در یک جدول ذخیره می شود نه در هردو جدول ) .
این نوشته برگرفته از سایت ویکی پدیا می باشد، اگر نادرست یا توهین آمیز است، لطفا گزارش دهید: گزارش تخلفنام این الگوریتم با توجه به شباهتش به برخی رفتارهای پرندهٔ کوکو انتخاب شده است. این پرنده، هنگامی که از یکی از تخم هایش جوجه ای بیرون آید، تخم های قدیمی تر یا جوجه های جوان تر را به بیرون لانه هل می دهد، در این روند نیز ممکن است درج عناصر جدید، موجب جابه جایی عناصر دیگر شود.
زمان اجرای این الگوریتم برای یافتن یک عنصر در جدول، در بدترین حالت، زمان ثابت 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 → { 0 , . . . , r − 1 } استفاده می شود. هر عنصر با کلید x یا در خانهٔ h 1 ( x ) در جدولِ T 1 یا در خانهٔ h 2 ( x ) در جدول T 2 ذخیره خواهد شد ( هر عنصر تنها در یک جدول ذخیره می شود نه در هردو جدول ) .
wiki: درهم سازی کوکو