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

• 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 شغّال: خلي الاصطدام يحصل قدامك

شغّل الكود ده مرّة بـ 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.