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

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 (لابتوب عادي):

الفرق هنا حوالي 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