13. جداول التجزئة (Hash Tables) (ربط المفاتيح بالقيم)

تعد جداول التجزئة (المعروفة أيضاً باسم Dictionaries أو Hash Maps) واحدة من أقوى هياكل البيانات والأكثر استخداماً على نطاق واسع نظراً لسرعتها.

المفهوم

يخزن جدول التجزئة البيانات في مصفوفة، ولكنه يستخدم دالة خاصة تسمى دالة التجزئة (hash function) لربط المفتاح المدخل (مثل الاسم) بـ فهرس رقمي حيث يتم تخزين القيمة المقابلة (مثل رقم الهاتف).

الأداء

من الناحية المثالية، توفر جداول التجزئة أداءً يقارب O(1) (وقتاً ثابتاً) لـ:

1. الإدراج (Insertion)
2. الحذف (Deletion)
3. البحث (Lookup)

تعتمد هذه الكفاءة على وجود دالة تجزئة جيدة تقلل من التضاربات (collisions) (المفاتيح المتعددة التي ترتبط بنفس الفهرس)، والتي سنتناولها لاحقاً.