هذا المقال يتطلب مستوى: متوسط. لو انت مبتدئ، متقلقش — بدأنا بمثال بسيط قبل التفاصيل العلمية.
لو بتدوّر على عنصر في list فيها 10 مليون عنصر عنصر عنصر، انت بتفحص في المتوسط 5 مليون عنصر. الـ dict في Python بيوصل لنفس العنصر في خطوة واحدة تقريبًا، سواء العناصر 10 أو 10 مليون. الفرق ده مش سحر، اسمه Hash Table، وفهمه بيغيّر طريقة كتابتك للكود.
المشكلة باختصار
أي بحث في مصفوفة غير مرتّبة بيكلّفك O(n): كل ما البيانات تكبر، الزمن يكبر معاها خطيًا. لو عندك API بيتشيك إن المستخدم موجود في قائمة 200 ألف اسم في كل request، انت بتدفع تكلفة فحص نص القائمة في المتوسط لكل نداء. المطلوب طريقة توصلك للقيمة من غير ما تمر على باقي العناصر أصلًا.
المفهوم بمثال: أدراج المكتبة المرقّمة
تخيّل مكتبة فيها مليون كتاب. لو دوّرت على كتاب رف رف، هتقعد ساعات. لكن لو عند الباب فيه قاعدة بسيطة: «خُد أول حرفين من اسم الكتاب، اجمع رقمهم، والباقي على عدد الأدراج بيقولك رقم الدرج». دلوقتي أي كتاب بتعرف درجه على طول من اسمه، من غير ما تبص على باقي الأدراج.
القاعدة دي هي «دالة الـ hash». الدرج هو الـ «bucket». انت مابتدوّرش — انت بتحسب المكان وتروحله مباشرة. ده بالظبط اللي بيحصل جوّه الـ dict.
الشرح العلمي: hash ثم mod ثم bucket
الـ Hash Table عبارة عن مصفوفة من الخانات (buckets). لمّا تضيف مفتاح، بيحصل التالي بالتفاصيل:
- دالة
hash(key)بتحوّل المفتاح لعدد صحيح كبير وثابت لنفس المدخل. - العملية
hash(key) % len(buckets)بتحوّل العدد ده لرقم خانة داخل المصفوفة. - القيمة بتتخزّن في الخانة دي. وقت الاسترجاع، نفس الحساب بيوصّلك لنفس الخانة في خطوة واحدة.
عشان كده التعقيد المتوسط للإضافة والبحث والحذف هو O(1): مفيش مرور على باقي العناصر، فيه حساب واحد وقفزة واحدة. الافتراض هنا إن دالة الـ hash بتوزّع المفاتيح بشكل شبه منتظم، وإن الجدول مش مزدحم — ودي نقطة هنرجعلها.
القياس بالأرقام: list مقابل dict
الكود ده بيقارن البحث الخطي في list بالبحث في dict على نفس البيانات. شغّله بنفسك:
import time
N = 10_000_000
data_list = list(range(N))
data_dict = {i: True for i in range(N)}
target = N - 1 # اسوا حالة للبحث الخطي: اخر عنصر
# بحث خطي O(n)
t = time.perf_counter()
found = target in data_list
linear_ms = (time.perf_counter() - t) * 1000
# بحث في hash table O(1)
t = time.perf_counter()
found = target in data_dict
hash_us = (time.perf_counter() - t) * 1_000_000
print(linear_ms, "ms", hash_us, "microseconds")
نتيجة تقريبية على جهاز عادي: الـ list بياخد حوالي 180 مللي ثانية، والـ dict بياخد أقل من ميكروثانية (أقل من 0.001 مللي ثانية). يعني فرق بعشرات آلاف المرات، وبيكبر كل ما N تكبر. الأرقام بتختلف حسب الجهاز، بس النسبة هي اللي تهمّك.
