المستوى: مبتدئ. المقال ده مكتوب لحد لسه بادئ، وكل مصطلح فيه متشرح بمثال بسيط الأول ثم بشكل علمي بعد كده.

لو بتدوّر على اسم جوه list فيها مليون عنصر، الكمبيوتر بيمر على العناصر واحد واحد لحد ما يلاقيه. الـ dictionary في Python بيوصل لنفس القيمة في خطوة واحدة تقريبًا، مهما كبر حجم البيانات. المقال ده هيوريك بالظبط ليه ده بيحصل، وإزاي تستغله.

جدول الهاش (Hash Table): الفكرة اللي ورا الـ Dictionary

الـ dictionary في Python، والـ object في JavaScript، والـ map في Go، كلهم مبنيين على نفس الهيكل: جدول الهاش (Hash Table). لو فهمت الفكرة مرة واحدة، هتفهم ليه البحث فيهم سريع جدًا، وليه أحيانًا بيبطّأ فجأة.

المشكلة باختصار

تخيّل نادي رياضي فيه 1000 خزانة مرقّمة من 0 لـ 999. لو الموظف عايز يلاقي خزانة عضو معيّن، عنده طريقتين. الطريقة الأولى: يفتح خزانة خزانة لحد ما يلاقي الاسم. لو الاسم في آخر خزانة، هيفتح 1000 خزانة. دي بالظبط طريقة الـ list.

الطريقة التانية: يكون فيه قاعدة ثابتة بتحوّل اسم العضو لرقم خزانة على طول. اسم «أحمد» بيتحول دائمًا لرقم 7، فالموظف بيروح للخزانة 7 دايركت من غير ما يدوّر. دي فكرة جدول الهاش.

علميًا: الـ list بتبحث بزمن O(n)، يعني الزمن بيكبر مع عدد العناصر. جدول الهاش بيبحث بزمن O(1) في المتوسط، يعني زمن شبه ثابت مهما كبر الحجم.

إزاي بيحصل ده فعلاً: دالة الـ Hash

القاعدة اللي بتحوّل المفتاح (الاسم) لرقم اسمها دالة الهاش (hash function). هي بتاخد أي مفتاح وترجّع رقم صحيح كبير. بعد كده بنعمل % size (باقي القسمة على حجم المصفوفة) علشان نخلي الرقم يقع جوه حدود المصفوفة.

1. المفتاح "ahmed" بيدخل دالة الهاش وبيطلع رقم كبير، يعني مثلًا 8493207.
2. بنعمل 8493207 % 1000 فيطلع 207، ده رقم الخانة.
3. بنحفظ القيمة في الخانة رقم 207. ولما نطلبها تاني، بنعيد نفس الحسبة ونروح للخانة 207 على طول.

المهم إن الدالة حتمية: نفس المفتاح بيطلّع نفس الرقم في كل مرة. ده اللي بيخلّي البحث في خطوة واحدة.

الفرق بالأرقام: قياس فعلي

الكلام ده مش نظري. الكود ده بيقارن البحث في list بالبحث في set (نفس بنية جدول الهاش) على مليون عنصر، باستخدام مكتبة timeit في Python 3.12:

import timeit

data_list = list(range(1_000_000))
data_set  = set(range(1_000_000))

target = 999_999  # أصعب حالة: العنصر في الآخر

t_list = timeit.timeit(lambda: target in data_list, number=100) / 100
t_set  = timeit.timeit(lambda: target in data_set,  number=100) / 100

print(f"list lookup: {t_list*1000:.4f} ms")
print(f"set  lookup: {t_set*1e9:.1f} ns")
# list lookup: ~8.0000 ms
# set  lookup: ~40.0 ns

الفرق هنا حوالي 200,000 ضعف. البحث في الـ list بياخد حوالي 8 مللي ثانية لأنه بيمر على العناصر واحد واحد. البحث في الـ set بياخد حوالي 40 نانوثانية لأنه بيروح للخانة مباشرة. والفرق ده بيكبر كل ما البيانات تكبر.

التصادم: لما مفتاحين يطلّعوا نفس الرقم

طب لو «sara» و«laila» الاتنين طلّعوا نفس الخانة رقم 1؟ ده اسمه تصادم (collision)، وهو مش خطأ، ده شيء طبيعي وبيحصل دايمًا. تخيّل إن خزانة واحدة فيها درج صغير، ولما يجي عضوين لنفس الخزانة بنحطهم في الدرج ورا بعض في قائمة صغيرة.

الأسلوب ده اسمه التسلسل (chaining): كل خانة بتشاور على قائمة مترابطة فيها كل المفاتيح اللي وقعت في نفس الـ index. وقت البحث بيروح للخانة، وبعدين يمشي على القائمة الصغيرة دي. طول ما القوائم قصيرة، البحث بيفضل قريب من O(1). لكن لو دالة الهاش وحشة وكل المفاتيح وقعت في خانة واحدة، القائمة بتبقى طويلة والبحث بيرجع O(n).

الـ Load Factor: ليه الجدول بيكبر لوحده

عشان القوائم متطولش، جدول الهاش بيراقب نسبة اسمها عامل التحميل (load factor) = عدد العناصر ÷ عدد الخانات. في CPython، لما النسبة دي تعدّي حوالي 2/3، الجدول بيعمل resize: بيكبّر المصفوفة (عادةً للضعف أو أكتر) ويعيد توزيع كل المفاتيح من جديد.

ده بيوضّح ليه إضافة عنصر واحد ممكن أحيانًا تاخد وقت أطول بكتير من المعتاد: في اللحظة دي بالذات الجدول بيعيد بناء نفسه. لكن بمتوسط العمليات (amortized) الإضافة بتفضل O(1).

الـ trade-offs اللي لازم تعرفها

• ذاكرة زيادة: جدول الهاش بيسيب خانات فاضية عمدًا علشان يقلّل التصادم. بتكسب سرعة، بتخسر ذاكرة (الجدول بياخد مساحة أكبر من عدد العناصر الفعلي).
• المفاتيح لازم تكون hashable: في Python، المفتاح لازم يكون غير قابل للتغيير زي str أو int أو tuple. list متنفعش كمفتاح لأنها بتتغير، وده هيرمي TypeError.
• مفيش ترتيب حسب القيمة: جدول الهاش مبيرتّبش العناصر ترتيب منطقي. لو محتاج تبحث عن «كل الأرقام بين 100 و200»، جدول الهاش مش هيساعدك.
• أسوأ حالة O(n): لو حصل هجوم متعمّد بمفاتيح كلها بتطلّع نفس الـ hash، الأداء بيتدهور. الافتراض هنا إن دالة الهاش بتوزّع المفاتيح بشكل عشوائي معقول.

متى لا تستخدم جدول الهاش

ماتلجأش له لو عندك عدد عناصر صغير جدًا (عشرات بس)، لأن البحث الخطي في list هيبقى أسرع عمليًا والفرق مش محسوس. وكمان متستخدموش لو محتاج استعلامات نطاق (range queries) أو محتاج البيانات مرتّبة دايمًا؛ هنا شجرة متوازنة (B-Tree) أو list مرتّبة أنسب بكتير. وأخيرًا، لو مفاتيحك بتتغير باستمرار أو مش hashable، الهيكل ده مش ليك.

الخطوة التالية

افتح أي كود عندك فيه if x in my_list جوه loop بيتكرر كتير، وحوّل الـ list دي لـ set بسطر واحد قبل الـ loop، وقيس الفرق بـ timeit. لو الكود كان بطيء بسبب البحث المتكرر، هتشوف تحسّن واضح فورًا. لو مشفتش فرق، يبقى البحث مش هو الـ bottleneck عندك، ودوّر في مكان تاني.

المصادر

• Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (CLRS)، الفصل 11: Hash Tables (تعريف الـ hashing والتصادم والتسلسل وزمن O(1) المتوسط).
• توثيق Python الرسمي — صفحة TimeComplexity على wiki.python.org (أزمنة عمليات list وset وdict).
• الكود المصدري لـ CPython — Objects/dictobject.c وملاحظات التنفيذ (load factor وآلية الـ resize).
• مسرد Python الرسمي — تعريف hashable على docs.python.org (شروط المفتاح الصالح).