الـ HashMap.get(key) اللي بياخد عادةً 80 نانو ثانية ممكن يطوّل فجأة لـ 8 ثواني على نفس الـ map وبنفس عدد العناصر. المشكلة مش في حجم البيانات، المشكلة في اصطدام الهاش (Hash Collision). المقال ده هيفكّلك ليه ده بيحصل، إزاي مهاجم ممكن يستغله لإسقاط سيرفر كامل، وإمتى لازم تقلق من الموضوع فعلاً.

Hash Collisions: ليه الـ HashMap بيتحوّل من O(1) لـ O(N) فجأة

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

كل الكود اللي بيستخدم dict في Python أو HashMap في Java بيفترض إن get و put بياخدوا وقت ثابت. في 99% من الحالات ده صحيح. لكن الـ 1% الباقية بتشمل حالتين خطيرتين: hash function ضعيفة بتوزّع العناصر بشكل سيء، أو مهاجم بيبعت مفاتيح متعمّدة كلها بتنزل في نفس الـ bucket. النتيجة: CPU بيتكهرب في loop خطّي جوّا bucket واحد.

تخيّل مكتبة فيها 10 أدراج: الفكرة لطفل عنده 7 سنين

افرض إن عندك مكتبة فيها 10 أدراج مرقّمة من 0 لـ 9. كل ما تيجي تحط كتاب، بتبص على أول حرف من اسمه وبتقرر الدرج رقم كام. لو الكتاب اسمه "أحمد" تحطه في درج 3، ولو اسمه "سارة" تحطه في درج 7. العملية سهلة: "أدّيني كتاب أحمد"، ببص على الحرف الأول، أفتح درج 3، ألاقيه. ثانية واحدة.

دلوقتي تخيّل إن فيه 100 كتاب كلهم بيبدأوا بحرف "أ". إيه اللي بيحصل؟ درج 3 بقى فيه 100 كتاب، والباقي فاضيين. لما تقوللي "هات كتاب أحمد"، مبقتش تفتح الدرج وتلاقيه؛ لازم تقرا عنوان كل كتاب في الدرج لحد ما تلاقيه. بدل ثانية بقت دقيقة. ده بالظبط اللي بيحصل في HashMap.

الشرح العلمي: Hash Function و Bucket Array

الـ HashMap في الخلفية عبارة عن مصفوفة (array) من الـ buckets — بالظبط زي الأدراج. كل bucket فيه مكان لعنصر أو لسلسلة (linked list) من العناصر. لما بتعمل map.put("ahmed", 42)، بيحصل 3 خطوات:

1. الـ hash function بتاخد المفتاح "ahmed" وبترجّع رقم صحيح كبير (مثلًا 0x8A3F1C).
2. الرقم ده بيتقسم على عدد الـ buckets باستخدام index = hash % capacity. الناتج هو رقم الدرج.
3. العنصر بيتحط في الدرج ده. لو الدرج فاضي، الإدخال O(1). لو فيه عنصر قبلك (اصطدام)، بتتضاف في نهاية سلسلة الـ bucket.

الـ get بيمشي بنفس المنطق: hash → index → ابحث في الـ bucket. التعقيد المتوقّع O(1 + n/k) حيث n عدد العناصر و k عدد الـ buckets. طول ما n/k (اللي اسمه load factor) صغير، الأداء ثابت. لكن لما كل الـ n ينزلوا في bucket واحد، n/k بيساوي n فعليًا، والـ lookup بقى O(N).

Chaining و Open Addressing: إزاي الـ runtime بيحلّ الاصطدام

فيه استراتيجيتين أساسيتين لتعامل الـ HashMap مع الاصطدام:

• Separate Chaining: كل bucket فيه linked list. لو في اصطدام، العنصر بيتضاف في آخر السلسلة. ده اللي Java 8+ بيستخدمه، بس مع تحسين مهم: لو السلسلة طالت أكتر من 8 عناصر، بتتحوّل لـ Red-Black Tree علشان تبقى O(log n) بدل O(n) — ده اسمه "treeification".
• Open Addressing: لو الـ bucket مشغول، بندوّر على أقرب bucket فاضي بخوارزمية probing (linear, quadratic, double hashing). ده اللي Python dict بيستخدمه.

كود Java شغّال: خلي الاصطدام يحصل قدامك

import java.util.HashMap;

public class CollisionDemo {
    // كلاس مفتاح hashCode ثابت = كل العناصر هتنزل bucket واحد
    static class BadKey {
        private final int id;
        BadKey(int id) { this.id = id; }
        @Override public int hashCode() { return 1; }
        @Override public boolean equals(Object o) {
            return o instanceof BadKey && ((BadKey) o).id == this.id;
        }
    }

    public static void main(String[] args) {
        HashMap<BadKey, Integer> map = new HashMap<>();
        int N = 50_000;
        long t1 = System.nanoTime();
        for (int i = 0; i < N; i++) map.put(new BadKey(i), i);
        long t2 = System.nanoTime();
        for (int i = 0; i < N; i++) map.get(new BadKey(i));
        long t3 = System.nanoTime();
        System.out.printf("put: %d ms, get: %d ms%n",
            (t2 - t1) / 1_000_000, (t3 - t2) / 1_000_000);
    }
}

شغّل الكود ده مرّة بـ hashCode() = 1 ومرّة بـ hashCode() = id. على لابتوب عادي: مع الـ hashCode الثابت، الـ 50K إدخال بتاخد حوالي 5.5 ثانية والـ get نفسها حوالي 4.2 ثانية. مع hashCode صحيح: كلاهما بيخلصوا في أقل من 40 مللي ثانية. الفرق حوالي 100×.

HashDoS: لما الاصطدام بقى ثغرة أمنية

في 2011 اتعملت ورقة بحثية (Klink & Wälde, 28C3) أثبتت إن أغلب اللغات الشائعة — PHP، Python، Java، Node.js، Ruby — كان عندها hash functions ثابتة وقابلة للتنبؤ. ده معناه إن مهاجم يقدر يحضّر قائمة مفاتيح كلها بتدي نفس الـ hash، ويبعتهم في POST body واحد. السيرفر يفضل يعمل insert في نفس الـ bucket ويدخل في loop خطّي يستهلك CPU كامل لدقائق.

النتيجة كانت ثغرة CVE-2011-4815 في OpenJDK و CVE-2012-2739 في PHP. الحل اللي طبّقته المنصّات بعدها: hash randomization — استخدام seed عشوائي يتغيّر مع كل تشغيل للعملية، عشان المهاجم ما يقدرش يتنبّأ بالنتيجة. Python 3.3+ بيعمل ده افتراضيًا، و Java 8 أضاف treeification كطبقة حماية.

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

• HashMap سليم، 1M عنصر: متوسط get ≈ 80–120 ns.
• HashMap كل عناصره في bucket واحد، 50K عنصر (Java 8 قبل treeify): get ≈ 80–120 µs (1000× أبطأ).
• نفس الـ HashMap بعد treeification في Java 8+: get ≈ 1–2 µs (تحسّن ~50× مقارنة بالسلسلة، بس لسه أبطأ 15× من الحالة السليمة).
• استهلاك ذاكرة إضافي بسبب Tree nodes: ~2× حجم الـ linked list nodes.

trade-offs ومتى تقلق

HashMap لسه أفضل structure للـ lookup في 99% من الحالات. لكن فيه 3 سيناريوهات لازم تراعيها:

• مفاتيح جاية من input خارجي غير موثوق: زي parameters من URL أو body في API عام. هنا الـ randomization اللي في اللغة بتحميك، لكن متستخدمش String.hashCode() كأساس لأي caching layer بنيته بإيدك — استخدم SipHash أو xxHash.
• كائنات بتعمل لها hashCode() بإيدك: لو نسيت تضمّن الحقول المميّزة، كل الـ instances هتتصادم. القاعدة: لو ضمّنت حقل في equals، لازم تضمّنه في hashCode.
• Load factor عالي جدًا: لو سبت load factor يوصل 0.9+، حتى مع hash ممتاز الأداء بيبوظ. القيم الافتراضية (Java: 0.75، Python: ~0.66) مختارة لسبب.

متى لا تستخدم HashMap أصلًا

HashMap مش دايمًا الحل الصح:

• لو محتاج ترتيب: استخدم TreeMap (Java) أو SortedDict. الـ lookup هيبقى O(log n) بس الترتيب مضمون.
• لو الـ dataset صغير جدًا (< 16 عنصر): ArrayList مع linear search ممكن يكون أسرع فعلاً بسبب cache locality.
• لو بتعمل lookup بـ prefix (زي autocomplete): استخدم Trie، مش HashMap.
• لو البيانات read-heavy وثابتة: perfect hashing أو minimal perfect hash بتدي O(1) مضمون بدون اصطدامات.

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

افتح أي كلاس عندك في production بتستخدمه كمفتاح في HashMap أو Set، وشوف الـ hashCode(). لو مش موجود أو بيرجّع ثابت أو مش بيغطّي الحقول اللي في equals، ده أول bug لازم يتصلّح. في Java استخدم Objects.hash(field1, field2)، في Python استخدم __hash__ = lambda self: hash((self.a, self.b)). قياس بسيط بـ JMH أو timeit بعد التعديل هيوريك الفرق.

مصادر

• Klink, A. & Wälde, J. — "Efficient Denial of Service Attacks on Web Application Platforms" — 28th Chaos Communication Congress, 2011.
• OpenJDK HashMap Source — java.util.HashMap (TREEIFY_THRESHOLD = 8) — openjdk.org.
• Python PEP 456 — Secure and interchangeable hash algorithm (hash randomization by default from 3.3+).
• CVE-2011-4815 (OpenJDK) و CVE-2012-2739 (PHP) — nvd.nist.gov.
• CPython dictobject.c — implementation of open addressing with perturbation (github.com/python/cpython).
• Aumasson, J.-P. & Bernstein, D.J. — "SipHash: a fast short-input PRF" — 2012.