المستوى: مبتدئ. المقال ده موجّه لحد لسه في بداية طريقه مع البرمجة وهياكل البيانات. مفيش شرط مسبق غير إنك تقدر تقرأ كود بسيط. في الآخر هتبقى فاهم إيه هو Hash Table، وليه بيلاقي أي قيمة في خطوة واحدة.

لو بتدوّر على قيمة جوّه مليون سجل، قدامك طريقتين. الأولى بتلفّ على السجلات واحد واحد لحد ما تلاقي اللي انت عايزه. التانية بتوصّلك للقيمة في خطوة واحدة، مهما كبر الحجم. التانية اسمها Hash Table (جدول الهاش)، وهي السبب الحقيقي إن dict في Python و Map في JavaScript بيبانوا كأنهم سحر.

Hash Table: السر وراء البحث في خطوة واحدة

الفكرة كلها بتتلخّص في جملة واحدة: بدل ما تدوّر على المكان، احسب المكان. تعالَ نوصل للجملة دي بالتفاصيل — بمثال بسيط الأول، وبعدين بالتعريف الدقيق وكود Python شغّال.

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

تخيّل متجر إلكتروني فيه 800 ألف منتج. كل ما زائر يفتح صفحة منتج، الكود بيدوّر على المنتج بالكود بتاعه (الـ SKU). لو المنتجات متخزّنة في قائمة (list) عادية، الكمبيوتر بيبدأ من أول عنصر ويقارن واحد واحد. في أسوأ حالة بيقارن 800 ألف مرة عشان يجيب منتج واحد.

ده اسمه البحث الخطي (Linear Search). تكلفته بتكبر مع البيانات: ضِعف البيانات يعني ضِعف الوقت. الـ Hash Table بيكسر العلاقة دي: وقت البحث بيفضل ثابت تقريبًا، سواء عندك ألف سجل أو عشرة ملايين. الافتراض هنا إنك بتدوّر بمفتاح محدّد (key) — مش بمدى ولا بترتيب. النقطة دي مهمة، وهنرجعلها في آخر المقال.

اشرحها بمثال: موظف الأمانات في صالة الأفراح

تخيّل صالة أفراح فيها مكتب أمانات. لما توصل، بتدّي شنطتك للموظف. الموظف ما بيحطّهاش في أول مكان فاضي يلاقيه. عنده 100 عمود مرقّمين من 0 لـ 99. بياخد اسمك، بيعمل عليه حسبة بسيطة بتطلّع رقم بين 0 و 99، والرقم ده هو العمود اللي هيعلّق عليه الشنطة.

لما ترجع تستلم، الموظف مش بيلفّ على المية عمود. بيعيد نفس الحسبة على اسمك، يطلعله نفس الرقم، يروح للعمود ده مباشرة. مية ضيف ولا ضيف واحد، نفس عدد الخطوات: حسبة واحدة ومشية واحدة.

الموظف ده بالظبط هو الـ Hash Table. القاعدة اللي بيحوّل بيها الاسم لرقم عمود اسمها دالة الهاش. والأعمدة المرقّمة هي مصفوفة (Array) بتتخزّن فيها البيانات. خلاص كده الصورة وضحت؟ يبقى نعرّفها بدقة.

التعريف العلمي: يعني إيه Hash Table

الـ Hash Table هيكل بيانات بيخزّن أزواج من النوع (مفتاح، قيمة). بيستخدم دالة هاش عشان تحسب — انطلاقًا من المفتاح — مكان (index) جوّه مصفوفة داخلية. بدل ما تدوّر على المفتاح، انت بتحسب مكانه على طول.

العمليات التلاتة الأساسية — الإضافة، البحث، الحذف — بتاخد في المتوسط زمنًا ثابتًا، يعني O(1): مش بيتأثر بعدد العناصر. ده مذكور في الفصل 11 من كتاب Introduction to Algorithms لـ Cormen وزملائه، تحت فرضية إن دالة الهاش بتوزّع المفاتيح بشكل منتظم على الخانات.

الفكرة نفسها قديمة. أول من اقترح استخدام الهاش للبحث السريع هو Hans Peter Luhn من شركة IBM في مذكرة داخلية سنة 1953. النهارده هي أساس dict في Python و Map في JavaScript و HashMap في Java.

دالة الهاش: القلب اللي بيحسب المكان

دالة الهاش هي قاعدة بتاخد مفتاح وتطلّع رقم. ليها 3 شروط: حتمية (نفس المفتاح يطلّع نفس الرقم كل مرة)، سريعة في الحساب، وبتوزّع المفاتيح على كل الخانات بالتساوي قدر الإمكان.

دي نسخة مبسّطة جدًا بتجمع القيم الرقمية لحروف المفتاح وتاخد باقي القسمة على حجم المصفوفة:

def simple_hash(key, table_size):
    total = 0
    for ch in key:
        total = total + ord(ch)   # اجمع القيمة الرقمية لكل حرف
    return total % table_size     # خلّي الناتج جوّه حدود المصفوفة

print(simple_hash("ahmed", 100))  # 11
print(simple_hash("sara", 100))   # 23

باقي القسمة (%) هو اللي بيضمن إن الرقم دايمًا يقع جوّه المصفوفة. لو المصفوفة 100 خانة، الناتج هيبقى بين 0 و 99 مهما كان طول الاسم. الدالة دي تعليمية بس — في الإنتاج اللغات بتستخدم دوال أقوى بكتير عشان التوزيع يطلع أحسن وأعدل.

التصادم: لما مفتاحين يقعوا في نفس الخانة

طب لو دالة الهاش طلّعت لمفتاحين مختلفين نفس الرقم؟ ده بيحصل، وبيحصل كتير. اسمه تصادم (Collision). وهو مش عيب في الكود — هو حتمية رياضية: المفاتيح الممكنة أكتر بكتير من عدد الخانات، فلازم اتنين أو أكتر يتشاركوا خانة واحدة.

في طريقتين مشهورتين للحل. الأولى التسلسل (Chaining): كل خانة بتشيل قائمة مترابطة صغيرة، والعناصر المتصادمة بتتعلّق فيها ورا بعض زي ما في الصورة فوق. التانية العنونة المفتوحة (Open Addressing): لو الخانة مشغولة، الجدول بيدوّر على أقرب خانة فاضية ويحط فيها.

القرار ده مش نظري. dict في Python مبني على العنونة المفتوحة — واضح ده في الكود المصدري لـ CPython، في ملف Objects/dictobject.c. بينما HashMap في Java بيستخدم التسلسل. لو التصادمات بقت كتير على نفس الخانة، البحث بيرجع بطيء — لكن ده استثناء مش القاعدة.

كود شغّال: dict في Python والفرق بالأرقام

أبسط تطبيق لجدول الهاش هتلاقيه في إيدك على طول: dict في Python.

phone = {}                        # جدول هاش فاضي
phone["ahmed"] = "0100-123-4567"  # المفتاح "ahmed" -> القيمة
phone["sara"]  = "0111-987-6543"

print(phone["sara"])              # 0111-987-6543  (خطوة واحدة)
print("ahmed" in phone)           # True

دلوقتي تعالَ نقيس الفرق فعليًا. هنقارن البحث في list (بحث خطي) بالبحث في set — والـ set هو جدول هاش بدون قيم:

import timeit

users_list = list(range(1_000_000))   # مليون عنصر في قائمة
users_set  = set(range(1_000_000))    # نفس المليون في جدول هاش
target = 999_999                      # أصعب حالة: آخر عنصر

t_list = timeit.timeit(lambda: target in users_list, number=100) / 100
t_set  = timeit.timeit(lambda: target in users_set,  number=100) / 100

print(f"list: {t_list * 1000:.2f} ms")   # ~9.80 ms
print(f"set:  {t_set * 1e6:.3f} us")     # ~0.04 us

على جهاز عادي بـ Python 3.11، البحث في القائمة أخد حوالي 9.8 مللي ثانية، والبحث في جدول الهاش أخد حوالي 0.04 ميكروثانية. الفرق أكتر من 200 ألف ضعف — على نفس البيانات ونفس الجهاز. والأهم: لو ضاعفت البيانات لـ 2 مليون، رقم القائمة هيتضاعف، ورقم جدول الهاش هيفضل تقريبًا زي ما هو.

الـ trade-offs: بتكسب إيه وبتخسر إيه

• بتكسب سرعة، بتخسر ذاكرة. جدول الهاش بيسيب خانات فاضية عمدًا عشان يقلّل التصادمات. CPython بيكبّر الجدول تلقائيًا عشان يحافظ على نسبة امتلاء أقل من الثلثين (مذكور في dictobject.c). يعني البنية بتاكل ذاكرة أكتر من قائمة مرصوصة.
• بتكسب O(1) في المتوسط، مش في أسوأ حالة. لو كل المفاتيح اتصادمت في خانة واحدة، البحث بيرجع O(n). ده بيحصل مع دالة هاش سيئة أو مع مدخلات خبيثة مقصودة.
• المفتاح لازم يكون قابلًا للهاش. في Python ميصحّش تستخدم list كمفتاح، لأنها قابلة للتعديل. المفاتيح لازم تكون ثابتة (immutable) زي النصوص والأرقام.
• مفيش ترتيب منطقي للخانات. ترتيب التخزين الداخلي بتحدّده دالة الهاش، مش قيمة المفتاح. (ملاحظة: dict في Python بيحافظ على ترتيب الإدخال من إصدار 3.7، لكن ده حاجة تانية غير الترتيب حسب القيمة).

نقطة أمان تستاهل الذكر: Python بيعمل عشوَأة للهاش (hash randomization) افتراضيًا عشان يصعّب على مهاجم يفتعل تصادمات تبطّئ السيرفر — التفصيل ده موثّق في PEP 456.

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

الـ Hash Table مش الحل لكل حاجة. سيبه في الحالات دي:

• لما تحتاج ترتيبًا أو استعلامًا بمدى. "هاتلي كل الطلبات بين تاريخين" أو "أصغر 10 قيم" — دول محتاجين بنية مرتّبة زي الشجرة المتوازنة (Balanced Tree)، مش جدول هاش.
• لما البيانات صغيرة جدًا. 20 عنصر؟ القائمة العادية أبسط وأخفّ، والفرق في السرعة مش هيحس بيه حد.
• لما بتدوّر بالقيمة مش بالمفتاح. جدول الهاش بيلاقي بسرعة بالمفتاح بس. البحث بالقيمة بيرجّعك للبحث الخطي.
• لما المفاتيح مش قابلة للهاش أو بتتغيّر بعد التخزين.

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

افتح أي ملف كود عندك ودوّر على نمط بالشكل ده: if x in my_list جوّه حلقة (loop). كل مرة بتنفّذ السطر ده، انت بتعمل بحثًا خطيًا كاملًا. حوّل my_list لـ set مرة واحدة قبل الحلقة، وسيب الباقي زي ما هو. بعدين قيس الزمن بـ timeit زي ما في المقال. لو لقيت تحسّنًا واضحًا، يبقى لقيت أول مكان يستاهل جدول هاش في كودك.

المصادر

• Cormen, Leiserson, Rivest, Stein — Introduction to Algorithms (الفصل 11: Hash Tables) — لتعريف الجدول، وزمن O(1) في المتوسط، والتصادم وطرق حلّه.
• توثيق Python الرسمي — صفحة Data Structures ونوع dict — لخصائص القاموس والمفاتيح القابلة للهاش.
• الكود المصدري لـ CPython — ملف Objects/dictobject.c — لاستخدام العنونة المفتوحة ونسبة الامتلاء أقل من الثلثين.
• PEP 456 — Secure and interchangeable hash algorithm — لعشوَأة الهاش في Python.
• Donald Knuth — The Art of Computer Programming, Vol. 3: Sorting and Searching — لتاريخ الهاش وإسهام Hans Peter Luhn سنة 1953.