هذا المقال يتطلب مستوى: مبتدئ
القاموس (Hash Table): إزاي بايثون يلاقي أي قيمة في خطوة واحدة
لو بتبحث عن عنصر جوه قائمة فيها مليون صف، إنت بتقرأ الصفوف واحد واحد لحد ما توصله. القاموس (dict) والـ set في بايثون بيلاقيوا العنصر في خطوة واحدة تقريبًا، مهما كبرت البيانات. المكسب ده اسمه جدول الهاش، وهتفهمه هنا بالتفصيل وتعرف امتى تستخدمه وامتى لأ.
المشكلة باختصار
البحث الخطي بيكبر مع حجم البيانات. مليون صف يعني لحد مليون خطوة في أسوأ حالة. ده تمام على 100 عنصر، بس بيتعلّق على الملايين. السؤال: نقدر نلاقي القيمة من غير ما نمرّ على كل العناصر؟ الإجابة أيوة، وده بالظبط اللي بيعمله جدول الهاش.
مثال بسيط: مكتب المعاطف
تخيّل مطعم كبير فيه مكتب لاستلام المعاطف. لو المكتب بيرصّ المعاطف ورا بعض، لما تيجي تاخد معطفك الموظف هيدوّر في كل المعاطف لحد ما يلاقيه. ده البحث الخطي.
بس المكتب الشاطر بيعمل حاجة تانية: بيديك تذكرة عليها رقم، مثلًا 27. المعطف بيتحطّ في الخانة رقم 27 بالظبط. لما ترجع، الموظف بيروح للخانة 27 على طول ويطلعلك معطفك في خطوة واحدة. مش مهم عدد المعاطف 50 ولا 5000، الوقت واحد.
الرقم اللي على التذكرة هو المفتاح، والدالة اللي بتحوّل اسمك لرقم خانة هي دالة الهاش. جدول الهاش بيشتغل بالظبط كده.
الشرح العلمي: إزاي بيشتغل فعلاً
جدول الهاش بياخد المفتاح (اسم، رقم، نص) ويمرّره على دالة اسمها hash function. الدالة بتطلّع رقم، والرقم ده بيتحوّل لموقع خانة جوه مصفوفة في الذاكرة. القيمة بتتخزّن في الخانة دي. لما تدوّر على نفس المفتاح، بايثون بيحسب نفس الرقم ويروح للخانة على طول، من غير ما يلفّ على باقي الخانات.
ساعات مفتاحين مختلفين بيطلّعوا نفس رقم الخانة. ده اسمه تصادم (collision). بايثون بيحلّه بطرق زي فتح العنونة (open addressing): بيدوّر على أقرب خانة فاضية. طول ما التصادمات قليلة، الوصول بيفضل قريب من خطوة واحدة.
الافتراض المهم هنا: إن دالة الهاش بتوزّع المفاتيح بشكل متساوٍ على الخانات. طول ما ده صحيح، متوسط زمن البحث بيكون O(1)، يعني ثابت مهما كبرت البيانات. في أسوأ حالة نظرية (كل المفاتيح تتصادم) بيبقى O(n)، لكنها نادرة جدًا عمليًا.
الكود: قِس الفرق بنفسك
خزّن مليون رقم في قائمة وفي set، ودوّر على آخر رقم في الاتنين وقيس الوقت.
import time
# مليون رقم
data_list = list(range(1_000_000))
data_set = set(data_list) # الـ set مبني على جدول هاش
target = 999_999
# بحث خطي في القائمة
t = time.perf_counter()
target in data_list
print("list:", time.perf_counter() - t)
# بحث بالهاش
t = time.perf_counter()
target in data_set
print("set :", time.perf_counter() - t)