درهم سازی فاخته – به زبان ساده

در این مطلب، «درهم سازی فاخته» (Cuckoo Hashing) که به آن درهم سازی کوکو نیز گفته می‌شود، مورد بررسی قرار گرفته و پیاده‌سازی آن در زبان‌های «سی‌پلاس‌پلاس» (++C)، «جاوا» (Java) و «سی‌شارپ» (#C) انجام شده است. شایان ذکر است، پیش از این در مطلب «تابع هش یا درهم سازی (Hash Function) چیست؟ — به زبان ساده» به مفهوم «درهم‌سازی» (Hash) پرداخته شد. به طور کلی، سه عملیات پایه وجود دارد که باید به وسیله یک «جدول درهم‌سازی» (Hash Table) (یا یک دیکشنری) پشتیبانی شود.

• Lookup(key)‎: در صورتی که «کلید» (Key) در «جدول» (Table) وجود داشته باشد، «درست» (True) و در غیر این صورت، «غلط» (False) بازگردانده می‌شود.
• Insert(key)‎: عنصر «key» را در صورتی که تاکنون نمایش داده نشده باشد، به جدول اضافه می‌کند.
• Delete(key)‎: این دستور، «key» را از جدول حذف می‌کند.

فیلم آموزش مروری بر توابع Hash و خطر تصادم در آن ها (رایگان) در فرادرس

کلیک کنید

امکان وقوع تصادم حتی در صورتی که یک جدول بزرگ برای ذخیره‌سازی کلیدها موجود باشد، وجود دارد. در واقع، «مساله تاریخ تولد» (Birthday Problem) یا «پارادوکس تولد» (Birthday Paradox) در اینجا مصداق دارد. با تنها ۲۳ نفر، احتمال آنکه دو نفر دارای روز تولد یکسانی باشند، ۵۰ درصد است. سه استراتژی کلی برای حل تصادم درهم‌سازی وجود دارد.

• آدرس‌دهی بسته یا زنجیری (Closed addressing یا Chaining): عناصر دارای تصادم را در یک ساختار داده موقت مانند یک لیست لینکی یا درخت جستجوی دودویی ذخیره می‌کند.
• آدرس‌دهی باز (Open Addressing): این امکان را فراهم می‌کند که عناصر از سطل هدف خود سر ریز شوند و به فضای دیگری بریزند.

اگرچه، راهکار بالا هزینه جستجوی (lookup) مورد انتظار O(1)‎ را فراهم می‌کند، هزینه بدترین حالت مورد نظر جستجو در آدرس‌دهی باز (با کاوش خطی) از درجه Ω(log n)‎ و در آدرس‌دهی زنجیری ساده برابر با Θ(log n / log log n)‎ است. برای حذف شکاف زمان مورد انتظار و زمان مورد انتظار بدترین حالت، دو راهکار قابل استفاده است.

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

درهم سازی فاخته

درهم سازی کوکو (Cuckoo Hashing) ایده چند انتخابی و موقعیت‌دهی مجدد را با هم پیاده‌سازی و بدترین زمان جستجوی O(1) ‎ را تضمین می‌کند.

چند انتخابی: به یک کلید، دو انتخاب h1(key)‎ و h2(key)‎ برای استقرار داده می‌شود.

موقعیت‌دهی مجدد: هنگامی اتفاق می‌افتد که h1(key)‎ و h2(key)‎ از پیش به کار گرفته شده باشند. این موضوع، با مساله تقلید پرنده فاخته حل می‌شود. فاخته، دیگر تخم‌مرغ‌ها یا فاخته‌های جوان را وقتی که تخم‌گذاری می‌کند، از لانه خارج می‌کند.

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

در غیر این صورت، کلید قدیمی‌تر، کلید دیگری را جا به جا می‌کند. این کار تا زمانی ادامه پیدا می‌کند که «رویه» (Procedure) یک موقعیت خالی پیدا کند یا وارد یک چرخه شود. در شرایط چرخه، تابع‌های درهم‌سازی جدید انتخاب می‌شوند و کل ساختار داده «درهم‌سازی مجدد» (Rehashed) می‌شود. درهم‌سازی‌های مجدد ممکن است پیش از موفقیت الگوریتم کوکو لازم باشند.

فیلم آموزش الگوریتم بهینه سازی ملخ GOA و پیاده سازی آن در متلب MATLAB در فرادرس

کلیک کنید

• درج از درجه O(1)‎ با احتمال بالا است، حتی وقتی احتمال درهم‌سازی مجدد در نظر گرفته می‌شود، تا هنگامی که عدد کلیدها زیر نیمی از ظرفیت جدول هش نگه داشته می‌شود (برای مثال، عامل بارگذاری زیر ٪۵۰ است) درج از همین درجه خواهد بود.
• حذف در بدترین حالت نیز از درجه O(1)‎ است. زیرا نیاز به بررسی دو موقعیت در جدول درهم‌سازی دارد.

روش کار الگوریتم بالا، به صورت زیر است.

ورودی:

{20, 50, 53, 75, 100, 67, 105, 3, 36, 39}

تابع هش:

کار با درج ۲۰ در موقعیت ممکن برای آن در اولین جدولی که به وسیله h1(20)‎ تعبیه شده، انجام می‌شود.

بعدی: ۵۰

بعدی: ۵۳. داریم که h1(53) = 9. اما ۲۰ در حال حاضر در ۹ قرار دارد. ۵۳ در جدول ۱ و ۲۰ در جدول ۲ در h2(20)‎ قرار داده می‌شود.

بعدی: ۷۵. داریم که h1(75) = 9. اما ۵۳ در حال حاضر در ۹ قرار دارد. ۷۵ در جدول ۱ و ۵۳ در جدول ۲ در h2(53)‎ قرار می‌گیرد.

بعدی: ۱۰۰. h1(100) = 1.

بعدی: ۶۷. داریم که h1(67) = 1. اما، ۱۰۰ در حال حاضر در آنجا در ۱ قرار دارد. ۶۷ در جدول ۱ و ۱۰۰ در جدول ۲ قرار داده می‌شود.

بعدی: ۱۰۵. داریم که h1(105) = 6. اما ۵۰ در حال حاضر در آنجا و در ۶ قرار دارد. ۱۰۵ در جدول ۱ و ۵۰ در جدول ۲ در h2(50) = 4 قرار می‌گیرد. اکنون، ۵۳ جایگزین شده است.  h1(53) = 9. اکنون، ۷۵ جا به جا شده است. h2(75) = 6.

بعدی ۳. داریم که h1(3) = 3.

بعدی: ۳۶. داریم که h1(36) = 3 و h2(3) = 0.

بعدی: ۳۹. داریم که h1(39) = 6 و h2(105) = 9 و h1(100) = 1 و h2(67) = 6 و h1(75) = 9 و h2(53) = 4 و h1(50) = 6 و h2(39) = 3.

در اینجا، کلید جدید ۳۹، بعدا در فراخوانی‌های بازگشتی جا به جا شده است تا ۱۰۵ را جایگذاری کند که جا به جا شده است.

درهم سازی فاخته در ++C

درهم سازی کوکو (فاخته) در جاوا

درهم سازی فاخته در #C

خروجی قطعه کدهای بالا به صورت زیر است.

Final hash tables:
- 100 - 36 - - 50 - - 75 - 
3 20 - 39 53 - 67 - - 105 - 

105 unpositioned
Cycle present. REHASH.
Final hash tables:
- 67 - 3 - - 39 - - 53 - 
6 20 - 36 50 - 75 - - 100 -

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

البته در این حالت، سرعت جستجو و درج، قربانی می‌شوند. برای مثال، اگر از سه تابع هش استفاده شود، امن است که ۹۱٪ بارگذاری شود و همچنان در مرزهای مورد نظر کار کند.

اگر نوشته بالا برای شما مفید بوده است، آموزش‌های زیر نیز به شما پیشنهاد می‌شوند:

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

^^