المستوى: مبتدئ — المقال ده مكتوب لحد لسه بادئ في البرمجة وسمع كلمة "Hash Map" أو "dict" ومش فاهم ليه الناس بتحبها. مش محتاج تعرف رياضيات، بس تعرف تكتب حلقة بسيطة.
الـ Hash Map: إزاي القاموس بيلاقي أي مفتاح في خطوة واحدة
لو عندك مليون مستخدم وعايز تلاقي واحد منهم بالإيميل، الـ Hash Map بيوصّلك له في خطوة واحدة تقريبًا، مش مليون خطوة. ده الفرق اللي بيخلّي كودك يشتغل في جزء من الثانية بدل ما يتجمّد.
المشكلة باختصار
تخيّل عندك قائمة فيها مليون إيميل، وعايز تعرف هل إيميل معيّن موجود ولا لأ. لو بتدوّر بحلقة عادية، الكمبيوتر بيقارن عنصر ورا عنصر. في أسوأ حالة بيعمل مليون مقارنة عشان سؤال واحد. لو بتسأل السؤال ده آلاف المرات، السيرفر بيقف. الـ Hash Map بيحل ده: بيديك الإجابة من غير ما يمشي على القائمة كلها.
الأول بمثال بسيط: خزانة المعاطف
تخيّل انت داخل مسرح، وقدام الباب في خزانة معاطف. لما بتسلّم معطفك، الموظف مبيحطّوش في أول مكان فاضي ويسيبك. لأ، هو بياخد رقم تذكرتك، يقول 27، وعلى طول بيعلّق المعطف في الشمّاعة رقم 27.
لما ترجع، انت مش بتدوّر على معطفك في كل الشمّاعات واحدة واحدة. بتدّي الموظف رقم 27، وهو بيروح للشمّاعة 27 دُغري. مش مهم الخزانة فيها 10 معاطف ولا 10 آلاف، الخطوة واحدة: من الرقم للمكان مباشرة.
الـ Hash Map بيشتغل بنفس الفكرة بالظبط. المفتاح (الإيميل مثلًا) هو زي التذكرة، والقيمة (بيانات المستخدم) هي المعطف. في حاجة في النص بتحوّل المفتاح لرقم مكان، وبتوديك له على طول.
دلوقتي بشكل علمي: دالة الـ hash والخانات
الـ Hash Map جوّاه مصفوفة (array) من الخانات، كل خانة ليها رقم فهرس (index). لما تضيف مفتاح، بيمر بخطوتين:
- دالة الـ hash: بتاخد المفتاح (نص أو رقم) وتطلّع منه رقم ثابت. مثلًا المفتاح
"ahmed"ممكن يطلّع الرقم 91. - باقي القسمة: بنقسم الرقم ده على عدد الخانات وناخد الباقي، فيطلع لنا رقم خانة صالح. لو عندنا 8 خانات:
91 % 8 = 3، يبقى المفتاح مكانه الخانة رقم 3.
وقت البحث بنعمل نفس الحساب بالظبط، فنوصل لنفس الخانة على طول من غير ما نلف على باقي الخانات. علشان كده بنقول إن التكلفة O(1)، يعني زمن ثابت لا علاقة له بحجم البيانات. الافتراض هنا إن دالة الـ hash بتوزّع المفاتيح بشكل جيد على الخانات؛ لو التوزيع وحش، القصة بتختلف (هنشوف ده تحت).
اقيس بنفسك: list مقابل dict
الكلام ده مش نظري. جرّب الكود ده في بايثون، هو بيدوّر على نفس القيمة مرة في قائمة (list) ومرة في قاموس (dict) فيه مليون عنصر:
import time
n = 1_000_000
data_list = list(range(n)) # قائمة عادية
data_set = set(range(n)) # مبنية على Hash
target = n - 1 # آخر عنصر: أسوأ حالة للقائمة
# البحث في القائمة: بيمشي عنصر ورا عنصر
start = time.perf_counter()
target in data_list
print("list :", round((time.perf_counter() - start) * 1000, 3), "ms")
# البحث في الـ set/dict: خطوة واحدة تقريبا
start = time.perf_counter()
target in data_set
print("set :", round((time.perf_counter() - start) * 1000, 3), "ms")
