HashMap للمبتدئ: ليه dict بيلاقي قيمة في 0.5 ميكروثانية

import time

N = 1_000_000
target_key = "user_999000"

# طريقة HashMap (dict في Python)
phonebook_dict = {f"user_{i}": f"010{i:08d}" for i in range(N)}

start = time.perf_counter()
value = phonebook_dict[target_key]
elapsed_dict = (time.perf_counter() - start) * 1_000_000
print(f"dict: {value} في {elapsed_dict:.2f} ميكروثانية")

# طريقة list (Linear Search)
phonebook_list = [(f"user_{i}", f"010{i:08d}") for i in range(N)]

start = time.perf_counter()
for k, v in phonebook_list:
    if k == target_key:
        value = v
        break
elapsed_list = (time.perf_counter() - start) * 1000
print(f"list: {value} في {elapsed_list:.2f} ميلي ثانية")

print(f"الفرق: {(elapsed_list * 1000) / elapsed_dict:.0f}x")

أرقام النتيجة على لابتوب MacBook Air M2 (نتيجة فعلية، مش تقدير):

• dict lookup: ~0.4 ميكروثانية
• list lookup: ~32 ميلي ثانية
• الفرق: ~80,000 ضعف

وعلى مليون عنصر، الفرق ده بيبان في الفاتورة وفي تجربة المستخدم. لو endpoint بيتنده مليون مرة في اليوم، الفرق بين 0.4 ميكروثانية و 32 ميلي ثانية معناه 8 ساعات CPU زيادة يوميًا.

متى الـ Hash Function بتفشل

HashMap بيحقق O(1) في المتوسط، مش في كل مرة. لو دالة الـ Hash بترجع نفس الرقم لمفاتيح كتير (Collision)، الـ buckets بتزدحم، والبحث بيبطل ثابت.

Python بيحل المشكلة دي بـ Open Addressing وdoubling الـ buckets لما تمتلئ، بس فيه حالات استثنائية ممكن تخلي الزمن O(n) في أسوأ سيناريو. عمليًا، مع Python 3.7+، ده نادر جدًا.

Trade-offs الحقيقية

كل قرار له ثمن. مع HashMap:

اللي بتكسبه:

• زمن lookup ثابت بمتوسط O(1).
• insert وdelete سريعين بنفس الزمن.
• كود أنظف وأسهل في القراءة.

اللي بتدفعه:

• ذاكرة أكتر. dict في Python بياخد حوالي 240 بايت لكل عنصر، مقابل 56 بايت في list.
• الترتيب الحسابي مش مضمون. Python 3.7+ بيحفظ ترتيب الإدراج لكنه مش بيرتب القيم تلقائيًا.
• الـ hash function ليها تكلفة CPU صغيرة في كل عملية.
• الـ keys لازم تكون immutable (string, int, tuple). list مش ممكن تكون key.

متى لا تستخدم HashMap

HashMap مش الحل لكل حاجة. متستخدمهوش في الحالات دي:

• محتاج بيانات مرتبة (مثلاً: أعلى 10 طلاب بالدرجة): استخدم Sorted Container أو heap.
• أقل من 100 عنصر: list بيكون أسرع لأن الـ CPU cache بيخدمه أحسن، وعملية الـ hash نفسها بياخد وقت.
• محتاج بحث بـ prefix أو substring: HashMap بيبحث بمفتاح كامل بس. استخدم Trie للـ autocomplete.
• ذاكرة محدودة جدًا (microcontrollers مثلاً): الـ overhead مش مبرر.
• محتاج بحث بنطاق (range query زي "كل المستخدمين بين 18 و 25 سنة"): استخدم B-Tree.

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

افتح Python على جهازك دلوقتي، انسخ الكود فوق، شغله مرة بـ N=1000 ومرة بـ N=10_000_000. سجّل الزمن في الحالتين. لو dict ثابت في الزمن وlist بيتضاعف خطيًا، فهمت HashMap عمليًا قبل ما تقرأ أي كتاب عنه.

مصادر

• Python docs — Mapping Types: docs.python.org/3/library/stdtypes.html#mapping-types-dict
• CPython source — dictobject.c: github.com/python/cpython/blob/main/Objects/dictobject.c
• Cormen, Leiserson, Rivest, Stein — "Introduction to Algorithms" 4th edition, الفصل 11 (Hash Tables).
• Raymond Hettinger talk — "Modern Python Dictionaries": youtube.com/watch?v=npw4s1QTmPg