Hash Table: ليه القاموس بيلاقي أي مفتاح في خطوة واحدة مهما كبر حجمه

هذا المقال يتطلب مستوى: متوسط. لو انت مبتدئ، متقلقش — بدأنا بمثال بسيط قبل التفاصيل العلمية.

لو بتدوّر على عنصر في list فيها 10 مليون عنصر عنصر عنصر، انت بتفحص في المتوسط 5 مليون عنصر. الـ dict في Python بيوصل لنفس العنصر في خطوة واحدة تقريبًا، سواء العناصر 10 أو 10 مليون. الفرق ده مش سحر، اسمه Hash Table، وفهمه بيغيّر طريقة كتابتك للكود.

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

أي بحث في مصفوفة غير مرتّبة بيكلّفك O(n): كل ما البيانات تكبر، الزمن يكبر معاها خطيًا. لو عندك API بيتشيك إن المستخدم موجود في قائمة 200 ألف اسم في كل request، انت بتدفع تكلفة فحص نص القائمة في المتوسط لكل نداء. المطلوب طريقة توصلك للقيمة من غير ما تمر على باقي العناصر أصلًا.

المفهوم بمثال: أدراج المكتبة المرقّمة

تخيّل مكتبة فيها مليون كتاب. لو دوّرت على كتاب رف رف، هتقعد ساعات. لكن لو عند الباب فيه قاعدة بسيطة: «خُد أول حرفين من اسم الكتاب، اجمع رقمهم، والباقي على عدد الأدراج بيقولك رقم الدرج». دلوقتي أي كتاب بتعرف درجه على طول من اسمه، من غير ما تبص على باقي الأدراج.

القاعدة دي هي «دالة الـ hash». الدرج هو الـ «bucket». انت مابتدوّرش — انت بتحسب المكان وتروحله مباشرة. ده بالظبط اللي بيحصل جوّه الـ dict.

الشرح العلمي: hash ثم mod ثم bucket

الـ Hash Table عبارة عن مصفوفة من الخانات (buckets). لمّا تضيف مفتاح، بيحصل التالي بالتفاصيل:

1. دالة hash(key) بتحوّل المفتاح لعدد صحيح كبير وثابت لنفس المدخل.
2. العملية hash(key) % len(buckets) بتحوّل العدد ده لرقم خانة داخل المصفوفة.
3. القيمة بتتخزّن في الخانة دي. وقت الاسترجاع، نفس الحساب بيوصّلك لنفس الخانة في خطوة واحدة.

عشان كده التعقيد المتوسط للإضافة والبحث والحذف هو O(1): مفيش مرور على باقي العناصر، فيه حساب واحد وقفزة واحدة. الافتراض هنا إن دالة الـ hash بتوزّع المفاتيح بشكل شبه منتظم، وإن الجدول مش مزدحم — ودي نقطة هنرجعلها.

القياس بالأرقام: list مقابل dict

الكود ده بيقارن البحث الخطي في list بالبحث في dict على نفس البيانات. شغّله بنفسك:

import time

N = 10_000_000
data_list = list(range(N))
data_dict = {i: True for i in range(N)}

target = N - 1   # اسوا حالة للبحث الخطي: اخر عنصر

# بحث خطي O(n)
t = time.perf_counter()
found = target in data_list
linear_ms = (time.perf_counter() - t) * 1000

# بحث في hash table O(1)
t = time.perf_counter()
found = target in data_dict
hash_us = (time.perf_counter() - t) * 1_000_000

print(linear_ms, "ms", hash_us, "microseconds")

نتيجة تقريبية على جهاز عادي: الـ list بياخد حوالي 180 مللي ثانية، والـ dict بياخد أقل من ميكروثانية (أقل من 0.001 مللي ثانية). يعني فرق بعشرات آلاف المرات، وبيكبر كل ما N تكبر. الأرقام بتختلف حسب الجهاز، بس النسبة هي اللي تهمّك.

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

دالة الـ hash مش مضمونة تدّي رقم خانة مختلف لكل مفتاح. ساعات مفتاحين مختلفين بيطلّعوا نفس الخانة. ده اسمه «تصادم» (collision)، وهو طبيعي مش عُطل.

أشهر طريقتين للتعامل معاه:

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

الكود ده بيبني hash table بسيط بالـ chaining عشان تشوف الفكرة شغّالة:

class SimpleHashMap:
    def __init__(self, size=8):
        self.buckets = [[] for _ in range(size)]

    def _index(self, key):
        return hash(key) % len(self.buckets)

    def put(self, key, value):
        bucket = self.buckets[self._index(key)]
        for i, (k, _) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)   # تحديث
                return
        bucket.append((key, value))        # اضافة او تصادم

    def get(self, key):
        bucket = self.buckets[self._index(key)]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(key)

m = SimpleHashMap()
m.put("ahmed", 90)
m.put("mona", 27)
print(m.get("ahmed"))   # 90

الـ Load Factor: ليه الجدول بيكبّر نفسه

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

الـ trade-off هنا واضح: بتكسب بحث ثابت السرعة، بتخسر ذاكرة (خانات فاضية محجوزة) وعملية resize تقيلة بين الحين والآخر. عشان كده الإضافة O(1) في المتوسط المُستهلَك مش في كل مرة بالظبط — العملية اللي بتعمل resize لوحدها بتاخد O(n)، بس بتتوزّع على باقي العمليات.

متى لا تستخدم Hash Table

• لو محتاج ترتيب أو نطاقات (range queries) زي «كل القيم بين 10 و50»: الـ hash table مابيحتفظش بترتيب منطقي، استخدم شجرة بحث متوازنة أو مصفوفة مرتّبة.
• لو البيانات صغيرة جدًا (عشرات العناصر): البحث الخطي ممكن يبقى أسرع عمليًا بسبب بساطته وعدم وجود overhead للحساب.
• لو المفاتيح مش قابلة للـ hashing بثبات (كائنات قابلة للتعديل في Python زي list): مينفعش تستخدمها كمفتاح أصلًا.
• لو الذاكرة مقيّدة جدًا: الخانات الفاضية المحجوزة تكلفة حقيقية.

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

افتح أي مكان في كودك بتعمل فيه if x in my_list جوّه حلقة، والـ list دي بتتعاد كل مرة. حوّلها لـ set أو dict مرة واحدة قبل الحلقة، وقيس الفرق بـ time.perf_counter(). لو الـ list أكبر من بضع مئات عنصر وبتتفحّص بكثرة، التحويل ده لوحده بيقلب زمن التنفيذ من ثوانٍ لأجزاء من الثانية.

المصادر

• Python Documentation — Time Complexity (dict / set average O(1)): wiki.python.org/moin/TimeComplexity
• CPython Source — Objects/dictobject.c: github.com/python/cpython/blob/main/Objects/dictobject.c
• Cormen et al., Introduction to Algorithms (CLRS) — Chapter 11: Hash Tables.
• Wikipedia — Hash table: en.wikipedia.org/wiki/Hash_table
• Python Docs — Built-in Functions: hash(): docs.python.org/3/library/functions.html#hash