هذا المقال يتطلب مستوى: مبتدئ
القاموس (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)
على جهاز عادي بتطلع نتيجة قريبة من: القائمة حوالي 8 ملي ثانية، والـ set أقل من 0.001 ملي ثانية. يعني فرق في حدود آلاف المرات، والفرق بيكبر كل ما البيانات تكبر.
ولو عايز تربط مفتاح بقيمة، استخدم dict:
users = {"ahmed": 30, "sara": 25, "omar": 41}
print(users["sara"]) # 25 — وصول في خطوة واحدة
سيناريو واقعي: عندك API بيستقبل 50 ألف طلب في الدقيقة، وكل طلب بيتأكد إن الإيميل موجود في قائمة 200 ألف مستخدم. لو استخدمت list، كل طلب ممكن يقرأ 200 ألف عنصر. حوّلها لـ set مرة واحدة عند بداية التشغيل، والتأكد بيبقى خطوة واحدة لكل طلب.
الـ trade-off: بتكسب إيه وبتخسر إيه
بتكسب: بحث وإضافة وحذف بمتوسط O(1) بدل O(n). ده المكسب الأساسي.
بتخسر: ذاكرة أكتر. كل عنصر في الـ set أو الـ dict بياخد overhead زيادة مقارنة بالقائمة، لأن الجدول بيسيب خانات فاضية عشان يقلّل التصادمات. لو عندك مليون عنصر، الفرق ممكن يبقى عشرات الميجابايت. الافتراض إن عندك ذاكرة كافية، وغالبًا ده مش مشكلة على السيرفرات الحديثة.
حاجة كمان: المفتاح لازم يكون قابل للهاش (hashable). في بايثون، الأرقام والنصوص والـ tuple تنفع كمفاتيح، لكن الـ list مش بتنفع لأنها قابلة للتغيير.
متى لا تستخدمه
لو البيانات صغيرة جدًا (عشرة عناصر مثلًا)، الفرق مهمل والقائمة أبسط وأخف في الذاكرة. ولو محتاج ترتيب مرتّب حسب القيمة عشان تعمل بحث بالمدى (كل الأرقام بين 10 و50)، جدول الهاش مش أداتك، استخدم بنية مرتّبة زي شجرة أو قائمة مرتّبة. جدول الهاش بيجاوب على سؤال واحد بسرعة: "هل ده موجود، وفين؟" مش "رتّبهملي".
الخطوة التالية
روح على أبطأ حتة في كودك بتعمل x in my_list جوه حلقة. حوّل my_list لـ set مرة واحدة قبل الحلقة، وأعد القياس بـ time.perf_counter(). لو الزمن نزل، يبقى المشكلة كانت البحث الخطي.
المصادر
- توثيق بايثون الرسمي — هياكل البيانات (Lists, Dicts, Sets): docs.python.org/3/tutorial/datastructures.html
- Python Wiki — تعقيد زمن العمليات (TimeComplexity: list vs set/dict): wiki.python.org/moin/TimeComplexity
- Wikipedia — Hash table (الهاش، التصادم، فتح العنونة، معامل التحميل): en.wikipedia.org/wiki/Hash_table