مستوى المقال: متوسط

الافتراض إنك تعرف الأساسيات: يعني إيه dict في بايثون أو HashMap في جافا، ويعني إيه O(1) وO(n). لو لسه مبتدئ تمامًا، المثال الأول تحت هيبسّط لك الفكرة قبل الشرح العلمي.

الـ Hash Table: ليه بيتحوّل من O(1) إلى O(n)؟

الـ dict في بايثون والـ HashMap في جافا بيوصلوا لأي عنصر في خطوة واحدة تقريبًا. تحت ضغط معيّن، نفس البنية بتبقى بطيئة لدرجة توقّع سيرفرك. هنا هتشوف إمتى بالظبط بيحصل التحوّل من O(1) إلى O(n)، وإزاي تمنعه بكود تقيسه بنفسك.

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

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

المثال المبسّط: جدار صناديق البريد

تخيّل جدار فيه 100 صندوق بريد مرقّم. عايز توصّل خطاب لـ"أحمد". بدل ما تدوّر صندوق ورا صندوق، عندك قاعدة بسيطة: تجمع أرقام حروف الاسم وتقسّم على 100، والباقي هو رقم الصندوق. اسم "أحمد" بيروح دايمًا للصندوق رقم 37. فتوصل له في خطوة واحدة، مش 100 خطوة. ده بالظبط اللي بيعمله الـ Hash Table.

المشكلة تبدأ لما "أحمد" و"محمد" و"سارة" كلهم يطلع لهم نفس الرقم 37. دلوقتي الصندوق 37 فيه كومة خطابات، ولازم تقلّبها واحد واحد لحد ما تلاقي بتاع أحمد. ده اسمه تصادم (collision)، ولو كل الأسماء كدّست في صندوق واحد، رجعت لتقليب الكومة كلها — يعني O(n).

الشرح العلمي: hash function و buckets

الـ Hash Table هي مصفوفة من الخانات (buckets). لما تحط مفتاح، بتمرّره على دالة تجزئة (hash function) بتحوّله لرقم، وبتاخد باقي القسمة على حجم المصفوفة عشان توصل لرقم الخانة: index = hash(key) % capacity. الوصول للمصفوفة بالـ index ثابت، فالبحث بيبقى O(1) في المتوسط طول ما التوزيع شبه منتظم.

الافتراض المخفي هنا: إن دالة الـ hash بتوزّع المفاتيح بالتساوي، وإن المفاتيح مش تحت تحكّم مهاجم. لو الافتراض ده اتكسر، الضمان بتاع O(1) بيتكسر معاه.

قيس الفرق بنفسك (كود شغّال)

الكود ده بيبني قاموسين في بايثون: واحد بمفاتيح كل واحد ليه hash مختلف (توزيع كويس)، والتاني بمفاتيح كلها بترجّع نفس الـ hash (تصادم كامل). بعدين بيقيس زمن بحثة واحدة في كل قاموس.

import time

class BadKey:
    def __init__(self, v): self.v = v
    def __hash__(self): return 42            # كل المفاتيح على نفس الخانة
    def __eq__(self, o): return self.v == o.v

class GoodKey:
    def __init__(self, v): self.v = v
    def __hash__(self): return hash(self.v)  # توزيع منتظم
    def __eq__(self, o): return self.v == o.v

N = 20_000
bad  = {BadKey(i): i  for i in range(N)}
good = {GoodKey(i): i for i in range(N)}

def bench(d, KeyCls):
    key = KeyCls(N - 1)                       # أسوأ حالة: آخر عنصر
    t = time.perf_counter()
    for _ in range(1000):
        _ = d[key]
    return (time.perf_counter() - t) / 1000 * 1e6   # ميكروثانية لكل بحثة

print("good hash:", round(bench(good, GoodKey), 2), "us")
print("bad  hash:", round(bench(bad,  BadKey),  2), "us")

مخرجات تقريبية على CPython 3.12 (لابتوب عادي):

good hash: 0.12 us
bad  hash: 1840.5 us

الفرق هنا حوالي 15,000 مرة لنفس عدد العناصر. البحث الكويس ثابت مهما كبر N؛ البحث السيّئ بيكبر خطّيًا معاه. الأرقام دي تقديرية وبتختلف حسب الجهاز وإصدار المفسّر، بس النسبة هي المهمة.

معامل التحميل (load factor) والتوسعة

حتى مع hash كويس، لو حشرت عناصر كتير في مصفوفة صغيرة، متوسط طول السلسلة في كل خانة بيزيد. النسبة دي اسمها معامل التحميل = عدد العناصر ÷ عدد الخانات. كل ما زادت، زاد احتمال التصادم، وقرّب البحث من O(n).

عشان كده البنى الجدّية بتعمل توسعة (resize) تلقائية: بتضاعف حجم المصفوفة وتعيد توزيع كل العناصر لما المعامل يعدّي حدًّا معيّن. الـ HashMap في جافا معامل تحميله الافتراضي 0.75، والـ dict في CPython بيوسّع لما يمتلئ حوالي الثلثين. التوسعة نفسها عملية O(n)، فالإدخال الواحد اللي بيسبّبها بيبقى بطيء لحظيًا، لكنه مُوزَّع (amortized) على باقي الإدخالات فيرجع O(1) في المتوسط.

سيناريو واقعي: هجوم HashDoS

لو عندك API بيستقبل JSON من المستخدم وبيحطّه في dict، مهاجم يقدر يبعت آلاف المفاتيح المصمّمة بحيث تصطدم كلها في نفس الخانة. كل إدخال بيبقى O(n)، والطلب الكامل بيبقى O(n²). طلب واحد بحجم بسيط يقدر يشغّل المعالج ثواني. ده هجوم HashDoS الحقيقي اللي اتعرض في مؤتمر 28C3 سنة 2011 وضرب Python وPHP وJava وRuby. الردّ كان إضافة hashing عشوائي مملّح (زي SipHash في بايثون) بحيث المهاجم ميقدرش يتوقّع الخانات.

chaining مقابل open addressing

في طريقتين لحل التصادم. Separate chaining: كل خانة فيها قائمة مربوطة، والمصطدمين بيتضافوا للقائمة — بسيط لكن بياكل ذاكرة أكتر. Open addressing (زي CPython): لو الخانة مشغولة، بتدوّر على الخانة اللي بعدها بترتيب معيّن — أوفر في الذاكرة وأصحب للكاش، بس بيتدهور بسرعة لو معامل التحميل قرّب من 1. جافا من الإصدار 8 بتعمل حاجة ذكية: لو السلسلة في خانة عدّت 8 عناصر، بتحوّلها لشجرة حمراء-سوداء فيرجع أسوأ حالة من O(n) لـ O(log n) (JEP 180).

الـ trade-offs بوضوح

• بتكسب بحث O(1) في المتوسط، بتخسر الترتيب: مفيش range queries ولا مرور مرتّب بسهولة.
• بتكسب سرعة، بتخسر ذاكرة: المصفوفة بتفضل فاضية جزئيًا عشان تحافظ على معامل تحميل منخفض.
• بتكسب متوسط ممتاز، بتخسر ضمان أسوأ حالة: من غير حماية، O(n) ممكن يحصل تحت هجوم أو hash سيّئ.
• التوسعة بتضمن الأداء، بس بتسبّب قفزة زمن لحظية عند كل مضاعفة.

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

ماتستخدمهاش لو محتاج استعلامات مدى (كل القيم بين 10 و50) أو مرور مرتّب — هنا الشجرة المتوازنة أو الـ B-tree أنسب. ولا تتعب نفسك لو عندك عناصر قليلة (أقل من ~16)، البحث الخطّي في مصفوفة بيبقى أسرع وأبسط بسبب الكاش. ولو بتاخد المفاتيح من مصدر خارجي غير موثوق، اتأكد إن الـ hashing عندك عشوائي/مملّح قبل ما تعتمد عليها.

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

افتح كودك ودوّر على أي dict أو HashMap مفاتيحه من نوع (object) عملته إنت. اتأكد إن __hash__ و__eq__ (أو hashCode وequals) متسقين، وإن الـ hash بيوزّع كويس مش راجع ثابت. ولو المفاتيح جايالك من مستخدم عبر API، فعّل الـ hash randomization (في بايثون هو مفعّل افتراضيًا منذ 3.4). شغّل الكود اللي فوق على مفاتيحك الحقيقية وقيس الفرق — لو لقيت البحث بطيء بشكل غريب، غالبًا الـ hash عندك بيكدّس.

المصادر

• Python Wiki — Time Complexity (dict: average O(1), worst O(n)): wiki.python.org/moin/TimeComplexity
• CPython dictobject.c (open addressing + perturbation + سياسة التوسعة): github.com/python/cpython — Objects/dictobject.c
• Java HashMap (DEFAULT_LOAD_FACTOR = 0.75): docs.oracle.com — java.util.HashMap
• JEP 180 — تحويل الخانات المزدحمة لأشجار متوازنة (treeify عند 8): openjdk.org/jeps/180
• PEP 456 — Secure and interchangeable hash algorithm (SipHash ضد HashDoS): peps.python.org/pep-0456
• Wikipedia — Hash table (buckets, load factor, resize): en.wikipedia.org/wiki/Hash_table