Hash Table
جدول التجزئة Hash Table
جدول التجزئة يخزّن أزواج مفتاح-قيمة مع وصول شبه فوري O(1) بالمتوسط، عبر دالة تجزئة تحوّل المفتاح لفهرس بمصفوفة داخلية.
دالة التجزئة (hash function) تحوّل أي مفتاح لفهرس صحيح بمصفوفة داخلية، فيصبح الإدراج والبحث والحذف بمتوسط O(1) بدل المرور على كل العناصر. عند تصادم مفتاحين على نفس الفهرس (Collision)، تُعالَج إما بالتسلسل (Chaining — قائمة بكل خانة) أو بالعنونة المفتوحة (Open Addressing — البحث عن خانة فارغة تالية).
الصياغة
table = {}
table[key] = value # إدراج O(1) بالمتوسط
value = table[key] # بحث O(1) بالمتوسط
del table[key] # حذف O(1) بالمتوسط📄 مثال
word_count = {}
text = ["تفاح", "موز", "تفاح", "عنب", "تفاح"]
for word in text:
word_count[word] = word_count.get(word, 0) + 1 # O(1) لكل عملية
print(word_count) # {'تفاح': 3, 'موز': 1, 'عنب': 1}أهم النقاط
| النقطة | الوظيفة |
|---|---|
| التعقيد الزمني (متوسط) | O(1) للإدراج والبحث والحذف |
| التعقيد الزمني (أسوأ حالة) | O(n) عند تصادمات كثيرة جدًا (دالة تجزئة سيئة أو حمل زائد على الجدول) |
| الترتيب الداخلي | لا يحافظ على أي ترتيب طبيعي للمفاتيح (بعكس BST أو Trie) |
💡 نصائح عملية
- أي مسألة عن 'عدّ التكرارات' أو 'هل يوجد عنصر مكرّر؟' أو 'أسرع بحث بمفتاح' — فكّر بجدول تجزئة أولًا قبل أي حل آخر
⚠️ أخطاء شائعة
- استخدام حلقتين متداخلتين O(n²) لمسائل مثل 'هل يوجد زوج مجموعه X' بدل جدول تجزئة يحلّها بـ O(n)
خصائص ذات صلة
🎓 تريد فهم الصورة الكاملة خطوة بخطوة؟ ابدأ من مسار DSA الكامل بالعربي.