Hash tables
أحنا درسنا كذا طريقة عشان نعمل search علي أي element زي
linear search: و كان لازم نعدي علي كل element لحد ما نوصل للtarget بتاعنا و في ال worst case هياخدعدد n steps لو الarray حجمها n
binary search: بنوصل لل target يتاعنا بعد log(n) time لكن كان بيقابلنا مشكلة أن في ال adds/ removes ال array لازم كانت نفضل مترتبة فهياخد time n عشان نعمل shift لل elements
BST: و النوع دة كان بيحللنا المشكلة دي فكان ممكن نعمل search/ add/ remove in log(n) time
و كل الأنواع دي كل ما عدد ال elements تزيد بيزيد معاها وقت أو سرعة ال search
عشان كدة أحنا هنتعلم نوع جديد اسمه hashing
*************************
يعني إيه Hashing
بدل ما نعمل traverse علي الarray أو الtree و نضيع وقت عشان نوصل للelement اللي عايزينه, مجرد هنحسب مكان ال element في ال table و بكدة هنوصله في خطوة واحدة و مهما عدد الelements تزيد… وقت ال search/ add/ remove بيكون ثابت.
الصورة دي عبارة عن element X هيعدي علي function اسمها hash function هتحسبله مكانه في الtable اللي هنسميه hash table .
زي ما أحنا شايفين ال hash function اللي عندنا عبارة عن h(X) = X
يعني لو عندنا مثلا رقم 10 هنخزنه في arr[10]و لو عندنا رقم 999 هنخزنه في arr[999]و بكدة هنقدر نوصل لأي رقم في خطوة واحدة و بكل سهولة
لكن لو تلحظوا هتلاقوا أن الموضوع دة في عيب, إيه هو يا تري؟
لنفرض إننا عايزين نخزن رقمين اللي هما مثلا 1 & 998
فكدة ال 1 هنخزنها في [1] arr و ال 998 هنخزنها في arr[998]
يانهار أبيض! هنعمل array حجمها 999 عشان نخزن رقمين!مش هينفع, عارفين ليه؟
عشان ال memory من جبنا :D :P
طيب إزاي نعالج الموضوع دة؟
مجرد نغير ال hash function
إيه رأيكوا نخليها كدة :
h(X) = X mod 2 ----> ال 2 دي ال capacity
و كدة ال 1 & 999 هيتخزنه فين؟
ال1 : %2 = 1 1 -------> فهنخزنها في arr[1]
و ال998: 998%2 = 0 -------> فهنخزنها في arr[0]
و دمتم سالمين! :D
في الحقيقة مادمناش سالمين أوي يعني, عارفين ليه؟
عشان فيه عيب تاني, خدوا دقيقتين عشان تكتشفوه!
..... بعد دقيقتين:
إفرضوا أحنا عايزين نخزن رقمين 4 & 8
هيتخزنوا فين؟
ال4: 4%2 = 0 --------->فهنخزنها فيه arr[0]
ال8: 8%2 = 0 ---------> يا سلام باردو هنخزنها فيه arr[0]
طبعا مش هينفع نخزن رقمين في نفس المكان
و الحالة دي بنسميها collision
لكن ماتقلقوش لكل مشكلة حل و مشكلتنا فيها أكتر من حل زي:
linear probing -1
open- addressing -2
chaining -3
linear probing -1
هنعمل “circular” linear search (يعني لو وصلنا لنهاية الtable و لسة ما وجدناش مكان فاضي هنروح لأول ال table و نكمل بحث
) هيبدأ من المكان اللي حصل فيه collision و ينتهي أول ما يلاقي مكان فاضي و ال element اللي حصله collision هيتحط في المكان الفاضي دة.
open- addressing( jumping) -2
الطريقة دي شبه الlinear probing لكن بدل ما نعمل “circular” linear search كل ما يحصل collision هنعمل الآتي:
لو مثلا عايزين نضيف رقم 282 و ال 31= capacity
زي ما عرفنا هنحسب مكانه كدة:
h(282) = 282 % 31 = 3
طيب لو المكان 3 محجوز, هنضيف عليها 12
3+21 = 4
و لو المكان 4 محجوز نطرح 12 من ال 3
3-21 = 2
و لو باردو محجوز نضيف 22 علي ال3
3+ 22 = 7
و لو المكان 7 محجوز نطرح 22 من ال 3
3-22 = 30 و هكذا لحد ما نلاقي المكان فاضي
يعنيI + 12, I - 12, I + 22, I - 22, I + 32, I - 32, I + 42, …
طيب ندي مثال عشان الصورة توضح:
عايزين نضيف 620, 64, 128, 467, 777, 35, 127& 282
H (620) = 620 % 31 = 0
H (64) = 64 % 31 = 2
H (128) = 128 % 31 = 4
H (467) = 467 % 31 = 2 --> 2+ 1= 3
H (777) = 777 % 31 = 2--> 2+1 =3 -->2-1 = 1
H (35) = 35 % 31 = 4--> 4+1 = 5
H (127) = 127 % 31 = 3--> 3+1 = 4--> 3-1 = 2--> 3+ 4 = 7
H (282) = 282 % 31 = 3--> 3+1 = 4--> 3-1 = 2--> 3+4 = 7--> 3-4 = 30
اللي مستغرب من أن 3-4 = 30 عشان ناقص دي يعني نقص من ال index يعني بدل ما كان ال element هيتحط في arr[3] هنحطه دلوقتي في arr[30]
Chaining -3
و الطريقة دي بيكون ال hash table عبارة عن array of linked lists
هكذا:
و ال hash function في حالة ال strings هتكون كدة:
H(name) = name[0] – ‘a’
الASCII code بتاع ال a = 97 و ال b = 98 و … فالكلمة اللي هتبدأ بحرف ال a هنحطها في arr[0] و اللي هتبدأ بحرف ال b هنحطها في arr[1] و هكذا...
*****************************
طيب بعد ما عرفنا يعني إيه hashing و المشاكل اللي قبلتنا و حلولها هنعرف إزاي نعمل
Search:
مش دايما الواحد بيعمل search عشان يتأكد أن ال element موجود, عادة عشان نحصل علي مزيد من المعلومات, زي في القاموس بنبحث علي الكلمة عشان نعرف معناها, عشان كدة عادة ال Data مقسومة لجزئين: Key & value
ال key هو الجزء اللي بنحدد من خلاله ال location
و فيه مثال تاني أما ندوس double click علي file و بكدة ال file path هو ال key و المحتوي ال file هو ال value
فأحنا دلوقتي هنعمل struct فيها ال key & value
و نستخدم ال hash function عشان نجيب مكان ال element لو المكان دة فيه ال element المطلوب يبقي ال search تم بنجاح و هنرجعله ال struct كلها و لو لأ نبدأ نعمل “circular” linear search لحد ما نلاقي المطلوب أو نرجع للمكان اللي بدأنا منه و دة معناه أن ال element مش موجود في ال hash table
Insert:
هناخد ال struct من ال user و نستخدم ال hash function عشان نجيب مكان ال element اللي هيتحط فيه لو المكان دة فاضي يبقي هنحط ال struct كلها في المكان دة لو لأ نبدأ نعمل “circular” linear search علي أول مكان فاضي يقابلنا.
بعد ما تكتب ال code بنفسك, هيكون مسموحلك نبص علي الcode
لو عايز PDF file للكلام دة نزله من هنا
References:
ADTs, Data Structures, and Problem Solving with C++
Video# 7--> MIT algos … download it from here