ما هو جدول التجزئة (Hash Table) وكيف يعمل؟ شرح مبسّط بالأمثلة
جدول التجزئة (Hash Table) هو هيكل بيانات يخزّن المعلومات على شكل أزواج «مفتاح ← قيمة»، ويتيح لك الوصول إلى أي قيمة تقريبًا بخطوة واحدة بدل البحث عنصرًا عنصرًا. الفكرة الأساسية بسيطة: بدل أن نبحث في القائمة كلها، نمرّر المفتاح على دالة رياضية تُسمّى «دالة التجزئة»، فتُعطينا مباشرة رقم الخانة التي يجب أن نضع فيها القيمة أو نقرأها منها. لهذا السبب يقال إن الإدخال والبحث والحذف تتم في «زمن ثابت» متوسطًا، أي (O(1، وهو ما يجعل الجدول العمود الفقري لأشياء نستخدمها يوميًا مثل القواميس في لغات البرمجة، وذاكرة التخزين المؤقت (Cache)، وفهارس قواعد البيانات.
لتقريب الصورة، تخيّل خزانة معاطف في مسرح. لديك قصاصة عليها رقم (المفتاح)، وبدل أن تفتّش كل العلّاقات، الرقم نفسه يدلّك على الخانة الصحيحة فورًا. دالة التجزئة هنا هي «قاعدة تحويل الرقم إلى موقع خانة».
كيف يعمل جدول التجزئة خطوة بخطوة
- تبدأ بمصفوفة (Array) من الخانات الفارغة، وليكن حجمها مثلًا 16 خانة.
- عند إضافة زوج مثل ("الاسم" ← "أحمد")، تُمرَّر كلمة «الاسم» على دالة التجزئة فتُنتج رقمًا كبيرًا.
- يُؤخذ باقي قسمة هذا الرقم على حجم الجدول (عملية modulo) لنحصل على رقم خانة ضمن المدى المتاح، فتُخزَّن القيمة هناك.
- عند القراءة لاحقًا، نُعيد الحساب نفسه على المفتاح ذاته، فنصل مباشرة إلى الخانة ونسترجع القيمة دون مرور على بقية العناصر.
الشرط الجوهري هنا أن دالة التجزئة حتمية: المفتاح نفسه يعطي دائمًا الخانة نفسها. لو تغيّرت النتيجة بين مرة وأخرى، لما استطعنا العثور على ما خزّناه.
دالة التجزئة: ما الذي يجعلها «جيدة»؟
دالة التجزئة الجيدة تتصف بثلاث خصائص:
- التوزيع المتساوي: توزّع المفاتيح على الخانات بانتظام حتى لا تمتلئ خانة وتبقى غيرها فارغة.
- السرعة: يجب أن تُحسب بسرعة، لأنها تُنفَّذ في كل عملية إدخال أو بحث.
- الحساسية للتغيير: أي فرق بسيط في المفتاح («سعر» مقابل «سعرة») يجب أن ينتج مواقع مختلفة.
ملاحظة مهمة: دالة التجزئة المستخدمة في هياكل البيانات ليست نفسها دوال التجزئة الأمنية مثل SHA-256. الأولى هدفها السرعة والتوزيع، والثانية هدفها الأمان ومقاومة العكس. لا تخلط بينهما.
التصادمات وكيفية معالجتها
مهما كانت الدالة جيدة، سيأتي مفتاحان مختلفان ويقعان على الخانة نفسها؛ هذا ما يُسمّى التصادم (Collision)، وهو أمر حتمي لا خلل. الطريقتان الأشهر لمعالجته:
| الطريقة | كيف تعمل | متى تناسبك |
|---|---|---|
| التسلسل المنفصل (Separate Chaining) | كل خانة تحمل قائمة صغيرة تضم كل العناصر المتصادمة فيها | الأبسط والأكثر شيوعًا، ويتحمّل الامتلاء بمرونة |
| العنونة المفتوحة (Open Addressing) | عند التصادم يُبحث عن أقرب خانة فارغة تالية وتُوضع فيها القيمة | يوفّر الذاكرة ويستفيد من الـCache، لكنه يتطلب إبقاء الجدول غير ممتلئ |
مؤشّر مهم اسمه عامل التحميل (Load Factor) = عدد العناصر ÷ عدد الخانات. كلما ارتفع اقتربت العمليات من البطء. لهذا تقوم معظم اللغات تلقائيًا بعملية «إعادة التوزيع» (Rehashing): مضاعفة حجم الجدول وإعادة توزيع العناصر عندما يتجاوز التحميل حدًّا معيّنًا (غالبًا نحو 0.7).
متى أختار جدول التجزئة؟
| الهيكل | أفضل استخدام | نقطة الضعف |
|---|---|---|
| جدول التجزئة | بحث وإدخال سريع بمفتاح فريد | لا يحفظ ترتيب العناصر |
| المصفوفة | وصول بالفهرس الرقمي وترتيب ثابت | البحث بقيمة بطيء |
| الشجرة المتوازنة | الحاجة إلى ترتيب مرتّب ومجالات | أبطأ من التجزئة في البحث المباشر |
باختصار: إذا كان سؤالك «هل هذا المفتاح موجود، وما قيمته؟» فجدول التجزئة هو الخيار الأمثل. أما إذا كنت تحتاج العناصر مرتّبة أو تريد أصغر/أكبر قيمة، فالشجرة أنسب.
أين تجده في لغات البرمجة؟
الجميل أنك تستخدم جداول التجزئة يوميًا دون أن تبنيها بنفسك:
- بايثون: النوع
dict. - جافا:
HashMap. - C++:
unordered_map. - جافاسكربت: الكائن
Objectوالبنية الأحدثMap.
نصيحة عملية وخطأ شائع: لا تستخدم كائنًا قابلًا للتغيير (مثل قائمة متغيّرة) مفتاحًا في الجدول. إذا تغيّر محتواه بعد الإدخال، تتغيّر نتيجة دالة التجزئة، فيضيع العنصر ولا يعود بالإمكان العثور عليه. استخدم دائمًا مفاتيح ثابتة (نصوص، أرقام، أو أنواع غير قابلة للتعديل).
الأسئلة الشائعة
هل جدول التجزئة سريع دائمًا؟ في المتوسط نعم، بزمن ثابت (O(1. لكن في أسوأ الحالات (تصادمات كثيرة أو دالة سيئة) قد يتدهور الأداء إلى (O(n. الدالة الجيدة وإعادة التوزيع تُبعِدان هذا الاحتمال عمليًا.
ما الفرق بين المفتاح والقيمة؟ المفتاح هو ما تبحث به (مثل اسم مستخدم)، والقيمة هي المعلومة المخزّنة المرتبطة به (مثل بيانات ذلك المستخدم). كل مفتاح فريد ويشير إلى قيمة واحدة.
لماذا لا يحافظ الجدول على ترتيب الإضافة؟
لأن الموقع يُحدَّد بحساب دالة التجزئة لا بترتيب الإدخال. إن احتجت الترتيب، استعمل بنية مخصّصة مثل LinkedHashMap في جافا أو اعتمد على ترتيب الإدراج المضمون في قواميس بايثون الحديثة.
هل التصادم يعني خطأً في الكود؟ لا إطلاقًا. التصادم سلوك متوقّع، وكل جدول تجزئة جاهز يعالجه داخليًا؛ دورك فقط اختيار مفاتيح مناسبة.