ملخص

مراجعة النقاط الرئيسية

• بمعطى مفتاح إدخال key، يستطيع جدول التجزئة استرجاع القيمة value المقابلة في زمن $O(1)$، وهي كفاءة عالية جداً.
• تتضمن عمليات جدول التجزئة الشائعة الاستعلام وإضافة أزواج المفتاح-القيمة وحذفها واجتياز جدول التجزئة.
• تُسند دالة التجزئة المفتاح key إلى فهرس في المصفوفة، بما يتيح الوصول إلى الدلو المقابل واسترجاع القيمة value.
• قد ينتهي مفتاحان مختلفان إلى الفهرس نفسه في المصفوفة بعد التجزئة، مما يؤدي إلى نتائج استعلام خاطئة. وتُعرف هذه الظاهرة بتصادم التجزئة.
• كلما كبرت سعة جدول التجزئة، انخفض احتمال تصادمات التجزئة. لذلك، يمكن لتوسيع جدول التجزئة أن يخفف تصادمات التجزئة. وكما في توسيع المصفوفة، يكلّف توسيع جدول التجزئة كثيراً.
• يعبّر عامل الحِمل (load factor)، المعرّف بأنه عدد العناصر مقسوماً على عدد الدلاء، عن مدى شدة تصادمات التجزئة، ويُستخدم غالباً شرطاً لتفعيل توسيع جدول التجزئة.
• تعالج السلسلة المنفصلة تصادمات التجزئة بتخزين جميع العناصر المتصادمة في القائمة المترابطة نفسها. غير أن القوائم المترابطة الطويلة إفراطاً قد تخفّض كفاءة الاستعلام، ويمكن تحسينها بتحويل القوائم المترابطة إلى أشجار حمراء-سوداء.
• تعالج العنونة المفتوحة تصادمات التجزئة عبر السبر المتعدد. ويستخدم السبر الخطي خطوة ثابتة لكنه لا يستطيع حذف العناصر ويكون عرضة للتكتل. أما التجزئة المزدوجة فتستخدم دوال تجزئة متعددة للسبر، مما يقلل التكتل مقارنةً بالسبر الخطي لكنه يزيد التكلفة الحسابية.
• تعتمد لغات البرمجة المختلفة تطبيقات متنوعة لجداول التجزئة. فمثلاً يستخدم HashMap في Java السلسلة المنفصلة، بينما يستخدم dict في Python العنونة المفتوحة.
• في جداول التجزئة، نرغب في خوارزميات تجزئة تتمتع بالحتمية والكفاءة العالية والتوزيع المنتظم. وفي مجال التشفير، ينبغي أن تتمتع خوارزميات التجزئة أيضاً بمقاومة التصادم وتأثير الانهيار الجليدي.
• تستخدم خوارزميات التجزئة عادةً أعداداً أولية كبيرة كمقياس لتعظيم انتظام توزيع قيم التجزئة وتقليل تصادمات التجزئة.
• تشمل خوارزميات التجزئة الشائعة MD5 وSHA-1 وSHA-2 وSHA-3. ويُستخدم MD5 غالباً في فحوص سلامة الملفات، بينما يُستخدم SHA-2 عادةً في التطبيقات والبروتوكولات الآمنة.
• تقدّم لغات البرمجة عادةً خوارزميات تجزئة مدمجة لأنواع البيانات لحساب فهارس الدلاء في جداول التجزئة. وبصورة عامة، لا تكون قابلة للتجزئة إلا الكائنات غير القابلة للتغيير.

أسئلة وأجوبة

س: متى يتدهور التعقيد الزمني لجدول التجزئة إلى $O(n)$؟

قد يتدهور التعقيد الزمني لجدول التجزئة إلى $O(n)$ عند شدة تصادمات التجزئة. وعندما تكون دالة التجزئة جيدة التصميم والسعة محددة على نحو ملائم والتصادمات موزعة بالتساوي، يكون التعقيد الزمني $O(1)$. ونحن نعتبر عادةً التعقيد الزمني $O(1)$ عند استخدام جداول التجزئة المدمجة في لغات البرمجة.

س: لِمَ لا نستخدم دالة التجزئة $f(x) = x$؟ فبذلك تختفي التصادمات.

في ظل دالة التجزئة $f(x) = x$، يقابل كل عنصر فهرس دلو فريد، وهو ما يكافئ مصفوفة. غير أن فضاء الإدخال أكبر عادةً بكثير من فضاء الخرج (طول المصفوفة)، لذا تكون الخطوة الأخيرة في دالة التجزئة غالباً أخذ باقي قسمة الناتج على طول المصفوفة. بعبارة أخرى، هدف جدول التجزئة هو إسقاط فضاء حالات أكبر إلى فضاء أصغر مع توفير كفاءة استعلام $O(1)$.

س: لِمَ يمكن أن تكون جداول التجزئة أكثر كفاءة من المصفوفات أو القوائم المترابطة أو الأشجار الثنائية، مع أن جداول التجزئة مبنية باستخدام هذه البنى؟

أولاً، تتمتع جداول التجزئة بكفاءة زمنية أعلى لكن بكفاءة مكانية أقل. فجزء كبير من ذاكرة جدول التجزئة يبقى دون استخدام.

ثانياً، لا تكون جداول التجزئة أكثر كفاءة زمنية إلا في حالات استخدام محددة. فإذا أمكن تنفيذ وظيفة ما بالتعقيد الزمني نفسه باستخدام مصفوفة أو قائمة مترابطة، فهي عادةً أسرع من استخدام جدول تجزئة. ويعود ذلك إلى أن حساب دالة التجزئة يكلّف جهداً إضافياً، مما يكبّر المعامل الثابت في التعقيد الزمني.

وأخيراً، قد يتدهور التعقيد الزمني لجداول التجزئة. فمثلاً في السلسلة المنفصلة، نجري عمليات البحث في قائمة مترابطة أو شجرة حمراء-سوداء، وما زال ذلك عرضة للتدهور إلى زمن $O(n)$.

س: هل تعاني التجزئة المزدوجة أيضاً من عيب تعذّر حذف العناصر مباشرةً؟ وهل يمكن إعادة استخدام المساحة المعلَّمة كمحذوفة؟

التجزئة المزدوجة شكل من أشكال العنونة المفتوحة، وجميع طرق العنونة المفتوحة تعاني عيب تعذّر حذف العناصر مباشرةً؛ إذ تتطلب تعليم العناصر كمحذوفة. والمساحات المعلَّمة يمكن إعادة استخدامها. وعند إدراج عناصر جديدة في جدول التجزئة، إذا أشارت دالة التجزئة إلى موضع معلَّم كمحذوف، فيمكن للعنصر الجديد استخدام ذلك الموضع. وبذلك يُحافظ على تسلسل السبر في جدول التجزئة مع ضمان استخدام المساحة بكفاءة.

س: لِمَ تحدث تصادمات التجزئة أثناء عملية البحث في السبر الخطي؟

أثناء عملية البحث، تشير دالة التجزئة إلى الدلو وزوج المفتاح-القيمة المقابلين. فإذا لم يتطابق المفتاح key، دلّ ذلك على حدوث تصادم تجزئة. لذلك يواصل السبر الخطي البحث بخطوة محددة سلفاً حتى يعثر على زوج المفتاح-القيمة الصحيح أو يفشل البحث.

س: لِمَ يمكن لتوسيع جدول التجزئة أن يخفف تصادمات التجزئة؟

تتضمن الخطوة الأخيرة في دالة التجزئة غالباً أخذ باقي قسمة الناتج على طول المصفوفة $n$، لإبقاء الخرج ضمن نطاق فهارس المصفوفة. وعند التوسيع يتغير طول المصفوفة $n$، وقد تتغير أيضاً الفهارس المقابلة للمفاتيح. وبذلك قد تتوزع المفاتيح التي كانت تُسند سابقاً إلى الدلو نفسه على عدة دلاء بعد التوسيع، مما يخفف تصادمات التجزئة.

س: إذا كان الهدف وصولاً فعّالاً، فَلِمَ لا نستخدم مصفوفة مباشرةً؟

عندما تكون قيم المفتاح key أعداداً صحيحة متصلة ضمن نطاق صغير، تكون المصفوفة فعلاً خياراً بسيطاً وفعّالاً. لكن عندما يكون المفتاح key من نوع آخر، مثل سلسلة نصية، نحتاج إلى دالة تجزئة تُسند المفتاح key إلى فهرس في المصفوفة ثم نخزّن العنصر في مصفوفة الدلاء. وهذه البنية بالتحديد هي جدول التجزئة.