29. التجزئة (Hashing) وحل التضارب (Collision Resolution)
لقد تعلمنا أن جداول التجزئة توفر تعقيداً زمنياً متوسطاً قدره O(1). تعتمد هذه الكفاءة بالكامل على التعامل مع التضاربات (collisions)—وهي الحالات التي تربط فيها دالة التجزئة مفتاحين مختلفين بنفس فهرس المصفوفة.
استراتيجية حل التضارب 1: التسلسل (Chaining)
- المفهوم: بدلاً من تخزين عنصر واحد في فهرس، يخزن الفهرس مرجعاً إلى قائمة مرتبطة (أو مصفوفة ديناميكية).
- كيف يعمل: عند حدوث تضارب، يتم ببساطة إضافة زوج المفتاح/القيمة الجديد إلى القائمة المرتبطة في ذلك الفهرس.
- المقايضة: يظل وقت البحث O(1) في المتوسط، ولكن إذا حدث الكثير من التضاربات، تصبح القائمة المرتبطة طويلة، مما يؤدي إلى تدهور الأداء نحو O(N) (البحث الخطي داخل القائمة).
الاستراتيجية 2: العنونة المفتوحة (Open Addressing - Probing)
- المفهوم: إذا حدث تضارب، يتم البحث عن الفتحة المفتوحة التالية المتاحة في المصفوفة الرئيسية.
- الفحص الخطي (Linear Probing): التحقق من الفهرس التالي (الفهرس + 1، الفهرس + 2، إلخ).
- الفحص التربيعي (Quadratic Probing): استخدام خطوة تربيعية (الفهرس + 1، الفهرس + 4، الفهرس + 9، إلخ).
- المقايضة: يتطلب معالجة دقيقة لعمليات الحذف، ويمكن أن يؤدي إلى 'التكتل (clustering)' إذا لم يتم تطبيقه جيداً.