Cuckoo Hashing هي تقنية لمعالجة مشكلة التصادم Collision داخل Hash Table. تعتمد الفكرة على استخدام دالتي Hash أو أكثر، بحيث يمتلك كل مفتاح عدة مواقع محتملة.
إذا كان الموقع الأول فارغاً، يتم تخزين المفتاح مباشرة. أما إذا كان مشغولاً، فيمكن للمفتاح الجديد إزاحة المفتاح الموجود وإجباره على الانتقال إلى موقعه البديل.
الفكرة الأساسية
لكل مفتاح x موقعان محتملان مثلاً:
h1(x)
h2(x)عند إدخال مفتاح جديد، يتم فحص الموقع الأول. إذا كان مشغولاً، تتم إزاحة العنصر الموجود ونقله إلى موقعه الثاني.
A يدخل الموقع
↓
الموقع يحتوي على B
↓
A يستبدل B
↓
B ينتقل إلى موقع بديلالبحث
للبحث عن مفتاح لا نحتاج إلى فحص الجدول بالكامل، بل نفحص المواقع المحتملة فقط:
h1(key)
h2(key)ولهذا تكون عملية البحث عادةً:
O(1)مشكلة الدورات
قد تؤدي عمليات الإزاحة المتكررة إلى دورة:
A → B → C → A → B → Cلذلك تحدد التطبيقات العملية عدداً أقصى من عمليات الإزاحة. إذا تجاوزت العملية هذا الحد، يتم تنفيذ Rehashing.
Rehashing
قد يتضمن Rehashing إنشاء جدول أكبر، اختيار دوال Hash جديدة وإعادة إدخال العناصر الموجودة.
التعقيد الزمني
| العملية | التعقيد المعتاد | |---|---| | Search | O(1) | | Delete | O(1) | | Insert | Expected O(1) | | Rehash | O(n) |
المزايا
- سرعة عالية جداً في البحث
- عدد محدود من المواقع التي يجب فحصها
- عدم الحاجة إلى Linked List لكل Bucket
- مناسب للأنظمة التي تنفذ عمليات Lookup كثيرة
العيوب
- عملية الإدخال أكثر تعقيداً
- إمكانية حدوث Cycle
- الحاجة أحياناً إلى Rehashing
- الاعتماد الكبير على جودة دوال Hash
- انخفاض كفاءة الإدخال عند ارتفاع Load Factor
الاستخدامات
يمكن استخدام الأفكار المرتبطة بـ Cuckoo Hashing في هياكل البيانات داخل الذاكرة، أنظمة Cache، الشبكات والأنظمة التي تحتاج إلى عمليات Lookup سريعة.
كما أن هذه التقنية مرتبطة ببنية أخرى تسمى Cuckoo Filter، وهي بنية احتمالية لاختبار عضوية العناصر ويمكن مقارنتها مع Bloom Filter.
الخلاصة
Cuckoo Hashing تقدم طريقة ذكية لمعالجة التصادمات في Hash Table. بدلاً من الاحتفاظ بسلسلة طويلة من العناصر، يمتلك كل مفتاح عدداً صغيراً من المواقع المحتملة، ويمكن إزاحة العناصر عند حدوث التصادم.
أهم نقاط قوتها هي سرعة البحث، بينما تتمثل التحديات الرئيسية في تعقيد الإدخال وإمكانية حدوث الدورات والحاجة أحياناً إلى Rehashing.