Hashing Advanced Data Structure PDF

‫ر‬ Advanced data structure Hashing ‫ؤر‬ ‫ر‬  ‫الفكرة هنا ايه ؟! عندي مجموعة عناصر (ارقام) عايز اخزنها في ‪Array‬‬ ‫بمعنى ‪ :‬لو اعطانا مجموعة ارقام زيي ‪:‬‬...

‫ر‬ Advanced data structure Hashing ‫ؤر‬ ‫ر‬  ‫الفكرة هنا ايه ؟! عندي مجموعة عناصر (ارقام) عايز اخزنها في ‪Array‬‬ ‫بمعنى ‪ :‬لو اعطانا مجموعة ارقام زيي ‪:‬‬ ‫𝟑𝟏 ‪𝟐𝟔 , 𝟑𝟎 , 𝟕𝟎 , 𝟒𝟓 ,‬‬ ‫و طلب مننا تخزينهم في ‪ Array‬و حددلنا الطريقة اللي هنتبع خطواتها عشان نخزن العناصر دي ‪..‬‬ ‫يعني فيه أنواع او طرق لل ‪ Hasing‬؟! اه فيه ‪..‬و الدكتور هيذكرلنا في السؤال نستخدم أي نوع او‬ ‫طريقة للحل لو هنحلها مقالي ‪..‬طيب هما ايه ؟!‬ ‫انواعه ال ‪: Hasing‬‬ ‫‪Open‬‬ ‫‪Close‬‬ ‫‪Addressing‬‬ ‫‪Type of‬‬ ‫‪Addressing‬‬ ‫‪(Close‬‬ ‫‪(Open‬‬ ‫)‪hashing‬‬ ‫‪hashing‬‬ ‫)‪hashing‬‬ ‫‪Double‬‬ ‫‪hashing‬‬ ‫‪Linear‬‬ ‫‪Quadritic‬‬ ‫‪probing‬‬ ‫‪Seperated‬‬ ‫‪probing‬‬ ‫‪chning‬‬ ‫هنفهم كل نوع منهم و هنعرف نحلهم ازاي ‪...‬لكن الزم نعرف األول ان فيه حاجة اسمها ال ‪Hash function‬‬ ‫‪...‬دي زيي قانون كده بنطبقه عشان نعرف الرقم ده هنحطه في أي خانة ‪...‬يعني هتساعدنا اكيد في الحل ‪..‬‬ ‫نبدأ بأول نوع في ال ‪ Open Addressing‬و هو ال ‪:‬‬ ‫‪Linear probing‬‬ ‫هيجيلنا مجموعة ارقام زيي ‪:‬‬ ‫𝟒𝟑 ‪𝟕𝟎 , 𝟓𝟎 , 𝟖𝟎 , 𝟑𝟎 , 𝟏𝟖 ,‬‬ ‫بس األرقام اللي هيديهالنا ؟! ال ‪..‬هيدينا حاجتين كمان ‪...‬‬ ‫الطريقة او نوع ال ‪ hashing‬اللي هنحل بيه‬ ‫‪01‬‬ ‫‪..‬‬ ‫‪ 02‬حجم ال ‪ Array‬اللي هنخزن فيها األرقام دي ‪...‬طيب لو مذكرش الحجم في السؤال؟! هنفترض احنا‬ ‫ان حجمها بيساوي عدد األرقام اللي ادهالنا في السؤال‬  ‫في مسألتنا دي قالنا نحلها ‪ Linear probing‬و حجم ال ‪ array‬هو ‪... 8‬‬ ‫خطوات الحل ‪:‬‬ ‫احنا قلنا من شوية ان ال ‪ Hash function‬بتاعة النوع ده او أي نوع عموما الزم نعرفها عشان نعرف‬ ‫نحل بيها صح ؟! طيب ايه هي ال ‪ Hash function‬بقى او هي بتنص على ايه ؟!‬ ‫𝑒𝑢𝑙𝑎𝑣 ‪ℎ ൫𝑘𝑒𝑦൯ = 𝑘𝑒𝑦 𝑚𝑜𝑑 𝑙𝑒𝑛𝑔𝑡ℎ = ℎ𝑎𝑠ℎ‬‬ ‫القيمة او الرقم‬ ‫)‪(%‬‬ ‫حجم ال ‪... array‬و‬ ‫رقم ال ‪ index‬اللي‬ ‫اللي عايز اضيفه‬ ‫ده ممكن يبقى معطى‬ ‫بيطلعلي من المعادلة‬ ‫او اننا نجيبه من عدد‬ ‫العناصر اللي عندنا‬ ‫هي زيي القانون كده ثابتة بنتبعها عشان نعرف نحل المسألة ‪...‬طيييب ‪....‬هنطبقها ازاي بقى في الحل‬ ‫بتاعنا ؟!‬ ‫ارقام‬ ‫‪index‬‬‫الخطوة األولى ‪ :‬هنرسم ال ‪ array‬بتاعتنا اللي هنحط فيها القيم و نكتب‬ ‫ال‬ ‫للتذكير ‪ :‬الزم نراعي ال ‪( length‬الحجم) و ده يا بيبقى مذكور في السؤال يا احنا بنجيبه من‬ ‫عدد العناصر اللي في السؤال‬ ‫‪7‬‬ ‫‪6‬‬ ‫‪5‬‬ ‫‪4‬‬ ‫‪3‬‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫طبعا عارفين ان ال ‪ index‬يبدأ من ‪0‬‬  ‫الخطوة الثانية هنبدأ نحط كل رقم في خانته الصحيحة ‪...‬طيب ازااي ؟! عن طريق اننا ناخد كل‬ ‫اللي‬ ‫قيمة و نطبق عليها ال ‪ Hash function‬و الناتج اللي هيطلع هيكون ده رقم ال‬ ‫هنحط فيه القيمة دي ‪...‬بمعنى ‪:‬‬ ‫هنمسك اول قيمة هنخزنها ‪...‬رقم ‪... 70‬هنعتبرها هي ال ‪ Kay‬و نعوض بيها في ال ‪Hash function‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪70‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪( 8‬و دي ثابتة طول المسألة ألن الحجم طبيعي مش هيتغير)‬ ‫𝟔 = 𝟖 ‪𝒉 ሺ𝟕𝟎ሻ = 𝟕𝟎 %‬‬ ‫هنروح نحط الرقم ‪ 70‬بقى في ‪ index‬رقم ‪6‬‬ ‫‪7‬‬ ‫𝟎𝟕‬ ‫‪6‬‬ ‫‪5‬‬ ‫‪4‬‬ ‫‪3‬‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫كده خزننا اول قيمة ‪...‬نكمل و نخزن تاني قيمة ‪...‬رقم ‪50‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪50‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪8‬‬ ‫𝟐 = 𝟖 ‪𝒉 ሺ𝟓𝟎ሻ = 𝟓𝟎 %‬‬ ‫هنروح نحط الرقم ‪ 50‬بقى في ‪ index‬رقم ‪2‬‬  ‫‪7‬‬ ‫𝟎𝟕‬ ‫‪6‬‬ ‫‪5‬‬ ‫‪4‬‬ ‫‪3‬‬ ‫𝟎𝟓‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫كده خزننا ثاني قيمة ‪...‬نكمل و نخزن ثالت قيمة ‪...‬رقم ‪80‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪80‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪ 8‬زيي ما هي‬ ‫𝟎 = 𝟖 ‪𝒉 ሺ𝟖𝟎ሻ = 𝟖𝟎 %‬‬ ‫هنروح نحط الرقم ‪ 80‬بقى في ‪ index‬رقم ‪0‬‬ ‫‪7‬‬ ‫𝟎𝟕‬ ‫‪6‬‬ ‫‪5‬‬ ‫‪4‬‬ ‫‪3‬‬ ‫𝟎𝟓‬ ‫‪2‬‬ ‫‪c‬‬ ‫‪1‬‬ ‫𝟎𝟖‬ ‫‪0‬‬ ‫كده خزننا ثالث قيمة ‪...‬نكمل و نخزن رابع قيمة ‪...‬رقم ‪30‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪80‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪ 8‬زيي ما هي‬  ‫𝟔 = 𝟖 ‪𝒉 ሺ𝟑𝟎ሻ = 𝟑𝟎 %‬‬ ‫لو رحنا نضيف الرقم ‪ 30‬في خانة رقم ‪ 6‬هنالقي ان هي فيها رقم اوريدي ‪...‬وهنا مينفعش نضيف‬ ‫قيمتين في نفس الخانة ‪...‬‬ ‫لما يحصل كده ده بنسميه (تعارض)طيب لما بيحصل تعارض بنعمل ايه ؟! بكل بساطة بنروح نعمل تغير في‬ ‫ال ‪ Hash function‬عشان نقدر نضيف الرقم ‪...‬بمعنى !!‬ ‫بدال م تبقى ال ‪ Hash function‬كده ‪:‬‬ ‫‪ℎ ሺ30ሻ = 30 % 8 = 6‬‬ ‫هنجمع ‪ i‬على قيمة ال ‪ key‬يعني هتبقى كده ‪:‬‬ ‫? = 𝟖 ‪𝒉 ሺ𝟑𝟎ሻ = ሺ𝟑𝟎 + 𝒊ሻ %‬‬ ‫ايه هي ال ‪ i‬دي ؟!‬ ‫هي عدد مرات التعارض اللي حصلت للرقم ده ‪...‬بمعنى !! الرقم ده اول مرة يحصله تعارض صح ؟! ف هنا‬ ‫ال ‪ i‬هتبقى ب ‪... 1‬طيب لو حصل تعارض تاني ؟! قيمة ال ‪ i‬هتبقى ب ‪ 2‬و هكذا بقى لحد ما نالقيله‬ ‫مكان‬ ‫بالتعويض بقى عن ال ‪ i‬ب ‪: 1‬‬ ‫𝟕 = 𝟖 ‪𝒉 ሺ𝟑𝟎ሻ = ሺ𝟑𝟎 + 𝒊ሻ %‬‬ ‫بما ان الخانة رقم ‪ 7‬فاضية ف هنحط فيها عادي رقم ‪30‬‬ ‫𝟎𝟑‬ ‫‪7‬‬ ‫𝟎𝟕‬ ‫‪6‬‬ ‫‪5‬‬ ‫‪4‬‬ ‫‪3‬‬ ‫𝟎𝟓‬ ‫‪2‬‬ ‫‪1‬‬ ‫𝟎𝟖‬ ‫‪0‬‬ ‫طيب للعلم بس ‪...‬بمجرد ما حطينا الرقم خالص بنرجع لل ‪ Hash function‬األصلية بتاعتا عادي جدا ‪...‬‬  ‫كده خزننا رابع قيمة ‪...‬نكمل و نخزن خامس قيمة ‪...‬رقم ‪18‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪18‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪ 8‬زيي ما هي‬ ‫𝟐 = 𝟖 ‪𝒉 ሺ𝟏𝟖ሻ = 𝟏𝟖 %‬‬ ‫هنا حصل تعارض برضو ‪...‬ف هنلجئ على طول لل ‪ Hash function‬البديلة ‪...‬‬ ‫? = 𝟖 ‪𝒉 ሺ𝟏𝟖ሻ = ሺ𝟏𝟖 + 𝒊ሻ %‬‬ ‫و ألنه اول تعارض يحصل للرقم ‪ 18‬ف قيمة ال ‪ i‬هتبقى ب ‪... 1‬‬ ‫𝟑 = 𝟖 ‪𝒉 ሺ𝟏𝟖ሻ = ሺ𝟏𝟖 + 𝟏ሻ %‬‬ ‫بما ان الخانة رقم ‪ 3‬فاضية ف هنحط فيها عادي رقم ‪18‬‬ ‫𝟎𝟑‬ ‫‪7‬‬ ‫𝟎𝟕‬ ‫‪6‬‬ ‫‪5‬‬ ‫‪4‬‬ ‫𝟖𝟏‬ ‫‪3‬‬ ‫𝟎𝟓‬ ‫‪2‬‬ ‫‪1‬‬ ‫𝟎𝟖‬ ‫‪0‬‬ ‫نخزن بقى اخر قيمة اللي هي ‪: 34‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪34‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪ 8‬زيي ما هي‬ ‫𝟐 = 𝟖 ‪𝒉 ሺ𝟑𝟒ሻ = 𝟑𝟒 %‬‬  ‫هنا حصل تعارض برضو ‪...‬ف هنلجئ على طول لل ‪ Hash function‬البديلة ‪...‬‬ ‫? = 𝟖 ‪𝒉 ሺ𝟑𝟒ሻ = ሺ𝟑𝟒 + 𝒊ሻ %‬‬ ‫و ألنه اول تعارض يحصل للرقم ‪ 34‬ف قيمة ال هتبقى ب ‪... 1‬‬ ‫𝟑 = 𝟖 ‪𝒉 ሺ𝟑𝟒ሻ = ሺ𝟑𝟒 + 𝟏ሻ %‬‬ ‫حصل تعارض للمرة التانية !! ألن الخانة رقم ‪ 3‬مليانة ‪...‬ف المرة دي قيمة ال ‪ i‬هتبقى ب ‪ 2‬بقى ‪..‬‬ ‫𝟒 = 𝟖 ‪𝒉 ሺ𝟑𝟒ሻ = ሺ𝟑𝟒 + 𝟐ሻ %‬‬ ‫بما ان الخانة رقم ‪ 4‬فاضية ف هنحط فيها عادي رقم ‪34‬‬ ‫𝟎𝟑‬ ‫‪7‬‬ ‫𝟎𝟕‬ ‫‪6‬‬ ‫‪5‬‬ ‫𝟒𝟑‬ ‫‪4‬‬ ‫𝟖𝟏‬ ‫‪3‬‬ ‫𝟎𝟓‬ ‫‪2‬‬ ‫‪1‬‬ ‫𝟎𝟖‬ ‫‪0‬‬ ‫و بكدا خزنا كل القيم بال ‪ ! Linear probing‬و كده انتهى الحل ‪..‬‬ ‫ؤ‬  ‫نشوف تاني نوع بقى من ال ‪ Open Addressing‬و هو ال ‪:‬‬ ‫‪Quadritic probing‬‬ ‫هيجيلنا مجموعة ارقام زيي ‪:‬‬ ‫𝟗𝟒 ‪𝟐𝟓 , 𝟑𝟎 , 𝟏𝟕 , 𝟏𝟏𝟓 ,‬‬ ‫بس األرقام اللي هيديهالنا ؟! ال ‪..‬هيدينا حاجتين كمان برضو نفس النوع األول ‪...‬‬ ‫الطريقة او نوع ال ‪ hashing‬اللي هنحل بيه‬ ‫‪01‬‬ ‫‪..‬‬ ‫‪ 02‬حجم ال ‪ Array‬اللي هنخزن فيها األرقام دي ‪...‬طيب لو مذكرش الحجم في السؤال؟! هنفترض احنا‬ ‫ان حجمها بيساوي عدد األرقام اللي ادهالنا في السؤال‬ ‫في مسألتنا دي قالنا نحلها ‪ Quadritic probing‬و حجم ال ‪ array‬هو ‪. 6‬‬ ‫خطوات الحل ‪:‬‬ ‫هنستخدم نفس ال ‪ Hash function‬بتاعتنا اللي عرفناها عادي جدا‪...‬‬ ‫𝑒𝑢𝑙𝑎𝑣 ‪ℎ ൫𝑘𝑒𝑦൯ = 𝑘𝑒𝑦 𝑚𝑜𝑑 𝑙𝑒𝑛𝑔𝑡ℎ = ℎ𝑎𝑠ℎ‬‬ ‫الخطوة األولى ‪ :‬هنرسم ال ‪ array‬بتاعتنا اللي هنحط فيها القيم و نكتب ارقام‬ ‫ال‬ ‫للتذكير ‪ :‬الزم نراعي ال ‪( length‬الحجم) و ده يا بيبقى مذكور في السؤال يا احنا بنجيبه من‬ ‫عدد العناصر اللي في السؤال‬ ‫‪5‬‬ ‫‪4‬‬ ‫‪3‬‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪0‬‬  ‫الخطوة الثانية هنبدأ نحط كل رقم في خانته الصحيحة ‪...‬عن طريق اننا ناخد كل قيمة و نطبق‬ ‫عليها ال ‪ Hash function‬و الناتج اللي هيطلع هيكون ده رقم ال‪ index‬اللي هنحط فيه‬ ‫القيمة دي ‪...‬بمعنى ‪:‬‬ ‫هنمسك اول قيمة هنخزنها ‪...‬رقم ‪... 25‬هنعتبرها هي ال ‪ Kay‬و نعوض بيها في ال ‪Hash function‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪25‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪( 6‬و دي ثابتة طول المسألة ألن الحجم طبيعي مش هيتغير)‬ ‫𝟏 = 𝟔 ‪𝒉 ሺ𝟐𝟓ሻ = 𝟐𝟓 %‬‬ ‫هنروح نحط الرقم ‪ 25‬بقى في ‪ index‬رقم ‪1‬‬ ‫‪5‬‬ ‫‪4‬‬ ‫‪3‬‬ ‫‪2‬‬ ‫𝟓𝟐‬ ‫‪1‬‬ ‫‪0‬‬ ‫كده خزننا اول قيمة ‪...‬نكمل و نخزن تاني قيمة ‪...‬رقم ‪30‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪30‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪6‬‬ ‫𝟎 = 𝟔 ‪𝒉 ሺ𝟐𝟓ሻ = 𝟑𝟎 %‬‬ ‫هنروح نحط الرقم ‪ 30‬بقى في ‪ index‬رقم ‪0‬‬ ‫‪5‬‬ ‫‪4‬‬ ‫‪3‬‬ ‫‪2‬‬ ‫𝟓𝟐‬ ‫‪1‬‬ ‫𝟎𝟑‬ ‫‪0‬‬  ‫كده خزننا ثاني قيمة ‪...‬نكمل و نخزن ثالث قيمة ‪...‬رقم ‪17‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪17‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪6‬‬ ‫𝟓 = 𝟔 ‪𝒉 ሺ𝟏𝟕ሻ = 𝟏𝟕 %‬‬ ‫هنروح نحط الرقم ‪ 17‬بقى في ‪ index‬رقم ‪5‬‬ ‫𝟕𝟏‬ ‫‪5‬‬ ‫‪4‬‬ ‫‪3‬‬ ‫‪2‬‬ ‫𝟓𝟐‬ ‫‪1‬‬ ‫𝟎𝟑‬ ‫‪0‬‬ ‫كده خزننا ثالث قيمة ‪...‬نكمل و نخزن رابع قيمة ‪...‬رقم ‪115‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪115‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪6‬‬ ‫𝟏 = 𝟔 ‪𝒉 ሺ𝟏𝟏𝟓ሻ = 𝟏𝟏𝟓 %‬‬ ‫هنا حصل تعارض !! هنلجئ ل ‪ Hash function‬تانية لكن الفرق بقى ان هما بدال م نزود ‪...i‬ال هنزود ‪i2‬‬ ‫بدال م تبقى ال ‪ Hash function‬كده ‪:‬‬ ‫⋯ = 𝟔 ‪𝒉 ሺ𝟏𝟏𝟓ሻ = 𝟏𝟏𝟓 %‬‬ ‫هنجمع ‪ i2‬على قيمة ال ‪ key‬يعني هتبقى كده ‪:‬‬ ‫?= 𝟔 ‪𝒉 ሺ𝟏𝟏𝟓ሻ = ൫𝟏𝟏𝟓 + 𝒊𝟐 ൯%‬‬ ‫ايه هي ال ‪ i2‬دي ؟!‬ ‫نفس معنى ال ‪ i‬بالضبط قبل كده بس تربيع بقى ‪...‬هي عدد مرات التعارض اللي حصلت للرقم ده ‪...‬بمعنى‬ ‫!! الرقم ده اول مرة يحصله تعارض صح ؟! ف هنا ال ‪ i‬هتبقى ب ‪... 1‬طيب لو حصل تعارض تاني ؟! قيمة‬ ‫ال ‪ i‬هتبقى ب ‪ 2‬و هكذا بقى لحد ما نالقيله مكان‬  ‫بالتعويض بقى عن ال ‪ i‬ب ‪: 1‬‬ ‫𝟐 = 𝟔 ‪𝒉 ሺ𝟏𝟏𝟓ሻ = ൫𝟏𝟏𝟓 + 𝟏𝟐 ൯%‬‬ ‫هنروح نحط الرقم ‪ 115‬بقى في ‪ index‬رقم ‪2‬‬ ‫𝟕𝟏‬ ‫‪5‬‬ ‫‪4‬‬ ‫‪3‬‬ ‫𝟓𝟏𝟏‬ ‫‪2‬‬ ‫𝟓𝟐‬ ‫‪1‬‬ ‫𝟎𝟑‬ ‫‪0‬‬ ‫كده خزننا رابع قيمة ‪...‬نكمل و نخزن خامس و اخر قيمة ‪...‬رقم ‪49‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪49‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪6‬‬ ‫𝟏 = 𝟔 ‪𝒉 ሺ𝟒𝟗ሻ = 𝟒𝟗 %‬‬ ‫هنا حصل تعارض برضو ‪...‬ف هنلجئ على طول لل ‪ Hash function‬البديلة ‪...‬‬ ‫𝟐 = 𝟔 ‪𝒉 ሺ𝟒𝟗ሻ = ൫𝟒𝟗 + 𝟏𝟐 ൯%‬‬ ‫هنالحظ انه ستيل فيه تعارض !! خانة رقم ‪ 2‬مليانة ‪...‬ف هنلجئ تاني لل ‪ Hash function‬لكن المرة دي‬ ‫قيمة ال ‪ i‬هتبقى ب ‪( 2‬ألن ده تاني تعارض حصل مع نفس الرقم )‬ ‫𝟓 = 𝟔 ‪𝒉 ሺ𝟒𝟗ሻ = ൫𝟒𝟗 + 𝟐𝟐 ൯%‬‬ ‫حصل تعارض للمرة التالتة !!! ف قيمة ال ‪ i‬هتبقى ‪: 3‬‬ ‫𝟒 = 𝟔 ‪𝒉 ሺ𝟒𝟗ሻ = ൫𝟒𝟗 + 𝟑𝟐 ൯%‬‬ ‫هنروح نحط الرقم ‪ 49‬بقى في ‪ index‬رقم ‪4‬‬  ‫𝟕𝟏‬ ‫‪5‬‬ ‫𝟗𝟒‬ ‫‪4‬‬ ‫‪3‬‬ ‫𝟓𝟏𝟏‬ ‫‪2‬‬ ‫𝟓𝟐‬ ‫‪1‬‬ ‫𝟎𝟑‬ ‫‪0‬‬ ‫و بكدا خزنا كل القيم بال ‪ !Quadritic probing‬و كده انتهى الحل ‪..‬‬ ‫نشوف ثالث نوع بقى من ال ‪ Open Addressing‬و هو ال ‪:‬‬ ‫‪Double hashing‬‬ ‫المسألة بتاعتها هتبقى لفظية شوية ‪..‬لسبب و نعرف ليه ‪..‬ممكن تبقى كده ‪:‬‬ ‫‪Assume aninitially empty hash table with 11 entries in which hash function uses division‬‬ ‫‪method , show contents of hash table after adding keys :‬‬ ‫𝟒𝟑 ‪𝟔𝟕 , 𝟖𝟏𝟓 , 𝟒𝟔 , 𝟑𝟗 , 𝟐 , 𝟗𝟎𝟏 ,‬‬ ‫‪*double hashing with f(key) = (key *3) % 7‬‬ ‫هنا هيدينا بقى حاجة زيادة عن النوعين اللي فاتوا ‪:‬‬ ‫‪ 01‬الطريقة او نوع ال ‪ hashing‬اللي هنحل بيه‬ ‫‪..‬‬ ‫‪ 02‬حجم ال ‪ Array‬اللي هنخزن فيها األرقام دي ‪...‬طيب لو مذكرش الحجم في السؤال؟! هنفترض احنا‬ ‫ان حجمها بيساوي عدد األرقام اللي ادهالنا في السؤال‬ ‫‪ 03‬في نوع ال ‪ Double hashing‬بيدينا هو ‪ Hash function‬جاهزة من عنده نستخدمها لما يحصل‬ ‫تعارض‬ ‫في مسألتنا دي قالنا نحلها ‪Double hashing‬و حجم ال ‪array‬هو‪..‬قالنا في السؤال انه ‪.. 11‬‬  ‫خطوات الحل ‪:‬‬ ‫زيي ما قلنا قبل شوية ‪...‬احنا هنطبق ال ‪ Hash function‬بتاعتنا اللي احنا عارفينها عاادي جدا ‪..‬اللي هي ‪:‬‬ ‫𝒆𝒖𝒍𝒂𝒗 𝒉𝒔𝒂𝒉 = 𝒉𝒕𝒈𝒏𝒆𝒍 𝒅𝒐𝒎 𝒚𝒆𝒌 = ‪𝒉 ൫𝒌𝒆𝒚൯‬‬ ‫و لما يحصل تعارض مفيش بقى ‪ Hash function‬ثابتة نلجئ لها زي األنواع اللي فاتت ال النوع ده مميز شوية‬ ‫‪...‬هو بيدينا ال ‪ Hash function‬اللي هنستخدمها‬ ‫و هنا طبعا ال ‪ Hash function‬اللي ادهالنا هي ‪:‬‬ ‫𝟕 ‪𝒇 ൫𝒌𝒆𝒚൯ = ሺ𝒌𝒆𝒚 ∗ 𝟑ሻ%‬‬ ‫الخطوة األولى ‪ :‬هنرسم ال ‪ array‬بتاعتنا اللي هنحط فيها القيم و نكتب ارقام‬ ‫ال‬ ‫للتذكير ‪ :‬الزم نراعي ال ‪( length‬الحجم) و ده يا بيبقى مذكور في السؤال يا احنا بنجيبه من‬ ‫عدد العناصر اللي في السؤال‬ ‫‪10‬‬ ‫‪9‬‬ ‫‪8‬‬ ‫‪7‬‬ ‫‪6‬‬ ‫‪5‬‬ ‫‪4‬‬ ‫‪3‬‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫الخطوة الثانية هنبدأ نحط كل رقم في خانته الصحيحة ‪...‬طيب ازااي ؟! نفسسس بالضبط ما‬ ‫عملن قبل كده ‪...‬عن طريق اننا ناخد كل قيمة و نطبق عليها ال ‪ Hash function‬و الناتج‬ ‫اللي هيطلع هيكون ده رقم ال ‪ array‬اللي هنحط فيه القيمة دي ‪...‬بمعنى ‪:‬‬ ‫هنمسك اول قيمة هنخزنها ‪...‬رقم ‪... 67‬هنعتبرها هي ال ‪ Kay‬و نعوض بيها في ال ‪Hash function‬‬  ‫يعني هنعوض عن ال ‪ Key‬ب‪67‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪( 11‬هو أعطاها لنا في السؤال)‬ ‫𝟏 = 𝟏𝟏 ‪𝒉 ሺ𝟔𝟕ሻ = 𝟔𝟕 %‬‬ ‫الخانة رقم ‪ 1‬فاضية ف هنحط فيها الرقم ‪ 67‬عادي‬ ‫‪10‬‬ ‫‪9‬‬ ‫‪8‬‬ ‫‪7‬‬ ‫‪6‬‬ ‫‪5‬‬ ‫‪4‬‬ ‫‪3‬‬ ‫‪2‬‬ ‫𝟕𝟔‬ ‫‪1‬‬ ‫‪0‬‬ ‫كده خزننا اول قيمة ‪...‬نكمل و نخزن ثاني قيمة ‪...‬رقم ‪815‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪815‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪ 11‬زيي ما هي‬ ‫𝟏 = 𝟏𝟏 ‪𝒉 ሺ𝟖𝟏𝟓ሻ = 𝟖𝟏𝟓 %‬‬ ‫هنا حصل تعارض برضو ‪...‬ف هنلجئ على طول لل ‪ Hash function‬البديلة اللي ادهالنا في السؤال ‪...‬‬ ‫لما نطبقها هتطلع كده ‪:‬‬ ‫𝟐 = 𝟕 ‪𝒉 ሺ𝟖𝟏𝟓ሻ = ሺ𝟖𝟏𝟓 ∗ 𝟑ሻ %‬‬ ‫الخانة رقم ‪ 2‬فاضية ف هنحط فيها الرقم ‪ 815‬عادي‬  ‫‪10‬‬ ‫‪9‬‬ ‫‪8‬‬ ‫‪7‬‬ ‫‪6‬‬ ‫‪5‬‬ ‫‪4‬‬ ‫‪3‬‬ ‫𝟓𝟏𝟖‬ ‫‪2‬‬ ‫𝟕𝟔‬ ‫‪1‬‬ ‫‪0‬‬ ‫كده خزننا ثاني قيمة ‪...‬نكمل و نخزن ثالث قيمة ‪...‬رقم ‪46‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪46‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪ 11‬زيي ما هي‬ ‫𝟐 = 𝟏𝟏 ‪𝒉 ሺ𝟒𝟔ሻ = 𝟒𝟔 %‬‬ ‫هنا حصل تعارض برضو ‪...‬ف هنلجئ على طول لل ‪ Hash function‬البديلة اللي ادهالنا في السؤال ‪...‬‬ ‫لما نطبقها هتطلع كده ‪:‬‬ ‫𝟓 = 𝟕 ‪𝒉 ሺ𝟒𝟔ሻ = ሺ𝟒𝟔 ∗ 𝟑ሻ %‬‬ ‫الخانة رقم ‪ 5‬فاضية ف هنحط فيها الرقم ‪ 46‬عادي‬  ‫‪10‬‬ ‫‪9‬‬ ‫‪8‬‬ ‫‪7‬‬ ‫‪6‬‬ ‫𝟔𝟒‬ ‫‪5‬‬ ‫‪4‬‬ ‫‪3‬‬ ‫𝟓𝟏𝟖‬ ‫‪2‬‬ ‫𝟕𝟔‬ ‫‪1‬‬ ‫‪0‬‬ ‫كده خزننا ثالث قيمة ‪...‬نكمل و نخزن رابع قيمة ‪...‬رقم ‪39‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪39‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪ 11‬زيي ما هي‬ ‫𝟔 = 𝟏𝟏 ‪𝒉 ሺ𝟑𝟗ሻ = 𝟑𝟗 %‬‬ ‫الخانة رقم ‪ 6‬فاضية ف هنحط فيها‬ ‫‪10‬‬ ‫الرقم ‪ 39‬عادي‬ ‫‪9‬‬ ‫‪8‬‬ ‫‪7‬‬ ‫𝟗𝟑‬ ‫‪6‬‬ ‫𝟔𝟒‬ ‫‪5‬‬ ‫‪4‬‬ ‫‪3‬‬ ‫𝟓𝟏𝟖‬ ‫‪2‬‬ ‫𝟕𝟔‬ ‫‪1‬‬ ‫‪0‬‬  ‫كده خزننا رابع قيمة ‪...‬نكمل و نخزن خامس قيمة ‪...‬رقم ‪2‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪2‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪ 11‬زيي ما هي‬ ‫𝟐 = 𝟏𝟏 ‪𝒉 ሺ𝟐ሻ = 𝟐 %‬‬ ‫هنا حصل تعارض برضو ‪...‬ف هنلجئ على طول لل ‪ Hash function‬البديلة اللي ادهالنا في السؤال ‪...‬‬ ‫لما نطبقها هتطلع كده ‪:‬‬ ‫𝟔 = 𝟕 ‪𝒉 ሺ𝟐ሻ = ሺ𝟐 ∗ 𝟑ሻ %‬‬ ‫حصل تعارض تااني ‪...‬لكن لو تالحظا مفيش هنا متغير نزوده كل مرة ب ‪ 1‬صح !زي ال ‪ i‬صح !! عشان كده‬ ‫هنقول ان القيمة دي مش هتتحط‬ ‫ده في كل المسائل اللي بتتحل ‪ Double hashing‬؟! اه ‪...‬مجرد م بنعوض بال ‪ Hash function‬اللي ادهالنا‬ ‫و مطلعتلناش خانة فاضية هتقول ع طول ان الرقم ده ملوش مكان ‪(not allocate)...‬‬ ‫يعني كده رقم ‪ 2‬مش هنضيفها ؟! ايوا‬ ‫طيب نخزن الرقم اللي بعد ال‪ 2‬و هو رقم ‪901‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪901‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪ 11‬زيي ما هي‬ ‫𝟑 = 𝟏𝟏 ‪𝒉 ሺ𝟗𝟎𝟏ሻ = 𝟗𝟎𝟏 %‬‬ ‫‪10‬‬ ‫الخانة رقم ‪ 3‬فاضية ف هنحط فيها‬ ‫الرقم ‪ 901‬عادي‬ ‫‪9‬‬ ‫‪8‬‬ ‫‪7‬‬ ‫𝟗𝟑‬ ‫‪6‬‬ ‫𝟔𝟒‬ ‫‪5‬‬ ‫‪4‬‬ ‫𝟏𝟎𝟗‬ ‫‪3‬‬ ‫𝟓𝟏𝟖‬ ‫‪2‬‬ ‫𝟕𝟔‬ ‫‪1‬‬ ‫‪0‬‬  ‫فاضل كده اخر رقم نخزنه ‪...‬هو رقم ‪34‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪34‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪ 11‬زيي ما هي‬ ‫𝟏 = 𝟏𝟏 ‪𝒉 ሺ𝟑𝟒ሻ = 𝟑𝟒 %‬‬ ‫هنا حصل تعارض برضو ‪...‬ف هنلجئ على طول لل ‪ Hash function‬البديلة اللي ادهالنا في السؤال ‪...‬‬ ‫لما نطبقها هتطلع كده ‪:‬‬ ‫𝟒 = 𝟕 ‪𝒉 ሺ𝟑𝟒ሻ = ሺ𝟑𝟒 ∗ 𝟑ሻ %‬‬ ‫الخانة رقم ‪ 4‬فاضية ف هنحط فيها‬ ‫الرقم ‪ 34‬عادي‬ ‫‪10‬‬ ‫‪9‬‬ ‫‪8‬‬ ‫‪7‬‬ ‫𝟗𝟑‬ ‫‪6‬‬ ‫𝟔𝟒‬ ‫‪5‬‬ ‫𝟒𝟑‬ ‫‪4‬‬ ‫𝟏𝟎𝟗‬ ‫‪3‬‬ ‫𝟓𝟏𝟖‬ ‫‪2‬‬ ‫𝟕𝟔‬ ‫‪1‬‬ ‫‪0‬‬ ‫خلصنا األرقام !! يبقى خلصت المسألة ‪...‬‬  ‫كده خلصنا أنواع ال ‪ Open Addressing‬نيجي بقى‬ ‫ألول و اخر نوع في ال ‪Close Addressing‬‬ ‫‪Seperated chning‬‬ ‫الفكرة هنا او اإلختالف فيين ؟! في النوع ده نقدر نخزن اكتر من قيمة في الخانة الواحدة ‪...‬بعكس كل األنواع‬ ‫اللي فاتت ‪...‬طيب هو ده اإلختالف الوحيد ؟! ال ‪...‬في النوع ده بنخزن القيم اه ‪...‬لكن برة الخانة مش‬ ‫جواها ‪...‬هنشوف ازاي بعد شوية ‪:‬‬ ‫هيجيلنا مجموعة ارقام زيي ‪:‬‬ ‫𝟕𝟔 ‪𝟑𝟗 , 𝟒𝟔 , 𝟑𝟒 , 𝟗𝟎𝟏 , 𝟖𝟏𝟓 ,‬‬ ‫بس األرقام اللي هيديهالنا ؟! ال ‪..‬هيدينا حاجتين كمان برضو نفس النوع األول ‪...‬‬ ‫الطريقة او نوع ال ‪ hashing‬اللي هنحل بيه‬ ‫‪01‬‬ ‫‪..‬‬ ‫‪ 02‬حجم ال ‪ Array‬اللي هنخزن فيها األرقام دي ‪...‬طيب لو مذكرش الحجم في السؤال؟! هنفترض احنا‬ ‫ان حجمها بيساوي عدد األرقام اللي ادهالنا في السؤال‬ ‫في مسألتنا دي قالنا نحلها ‪ Seperated chning‬و حجم ال ‪ array‬هو‪. 11‬‬ ‫خطوات الحل ‪:‬‬ ‫هنستخدم نفس ال ‪ Hash function‬بتاعتنا اللي عرفناها عادي جدا‪...‬‬ ‫𝒆𝒖𝒍𝒂𝒗 𝒉𝒔𝒂𝒉 = 𝒉𝒕𝒈𝒏𝒆𝒍 𝒅𝒐𝒎 𝒚𝒆𝒌 = ‪𝒉 ൫𝒌𝒆𝒚൯‬‬ ‫طيب هيكون فيه ‪ Hash function‬بديلة في النوع ده ؟! ال‪..‬الن ببساطة احنا ينفع نخزن كذا قيمة في الخانة‬ ‫فيها !‬ ‫الواحدة ف مش هيحصل تعارض اصال يخلينا نحتاج ‪Hash function‬‬ ‫الخطوة األولى ‪ :‬هنرسم ال ‪ array‬بتاعتنا اللي هنحط فيها القيم و نكتب ارقام‬ ‫ال‬ ‫للتذكير ‪ :‬الزم نراعي ال ‪( length‬الحجم) و ده يا بيبقى مذكور في السؤال يا احنا بنجيبه من‬ ‫عدد العناصر اللي في السؤال‬  ‫‪10‬‬ ‫‪9‬‬ ‫‪8‬‬ ‫‪7‬‬ ‫‪6‬‬ ‫‪5‬‬ ‫‪4‬‬ ‫‪3‬‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫الخطوة الثانية هنبدأ نحط كل رقم في خانته الصحيحة ‪...‬طيب ازااي ؟! نفسسس بالضبط ما‬ ‫عملن قبل كده ‪...‬عن طريق اننا ناخد كل قيمة و نطبق عليها ال ‪ Hash function‬و الناتج‬ ‫اللي هيطلع هيكون ده رقم ال ‪ array‬اللي هنحط فيه القيمة دي ‪...‬بمعنى ‪:‬‬ ‫هنمسك اول قيمة هنخزنها ‪...‬رقم ‪... 39‬هنعتبرها هي ال ‪ Kay‬و نعوض بيها في ال ‪Hash function‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪39‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪11‬‬ ‫𝟔 = 𝟏𝟏 ‪𝒉 ሺ𝟑𝟗ሻ = 𝟑𝟗 %‬‬ ‫هنضيف رقم ‪ 39‬في خانة رقم ‪6‬‬ ‫طيب هنخزنها ازااي ؟! ليها طريقة خاصة و هي ‪:‬‬ ‫هنيجي عند الخانة اللي هنخزن فيها الرقم ‪:‬‬ ‫هنا مبنضفش حاجة ‪..‬‬ ‫و نعمل كده ‪:‬‬ ‫هنخزن‬ ‫الرقم هنا‬  ‫هيبقى شكلها كده بعد ما نخزن رقم ‪: 36‬‬ ‫‪10‬‬ ‫‪9‬‬ ‫‪8‬‬ ‫‪7‬‬ ‫𝟗𝟑‬ ‫‪6‬‬ ‫‪5‬‬ ‫‪4‬‬ ‫‪3‬‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪0‬‬ ‫خزنا اول قيمة ‪...‬نخزن تاني قيمة بقى اللي هي رقم ‪46‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪46‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪ 11‬زيي ما هي‬ ‫𝟐 = 𝟏𝟏 ‪𝒉 ሺ𝟒𝟔ሻ = 𝟒𝟔 %‬‬ ‫هنضيف رقم ‪46‬‬ ‫‪10‬‬ ‫في الخانة رقم ‪2‬‬ ‫‪9‬‬ ‫‪8‬‬ ‫‪7‬‬ ‫𝟗𝟑‬ ‫‪6‬‬ ‫‪5‬‬ ‫‪4‬‬ ‫‪3‬‬ ‫𝟔𝟒‬ ‫‪2‬‬ ‫‪1‬‬ ‫‪0‬‬  ‫خزنا ثاني قيمة ‪...‬نخزن ثالث قيمة بقى اللي هي رقم ‪34‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪34‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪ 11‬زيي ما هي‬ ‫𝟏 = 𝟏𝟏 ‪𝒉 ሺ𝟑𝟒ሻ = 𝟑𝟒 %‬‬ ‫هنضيف رقم ‪34‬‬ ‫في الخانة رقم ‪1‬‬ ‫‪10‬‬ ‫‪9‬‬ ‫‪8‬‬ ‫‪7‬‬ ‫𝟗𝟑‬ ‫‪6‬‬ ‫‪5‬‬ ‫‪4‬‬ ‫‪3‬‬ ‫𝟔𝟒‬ ‫‪2‬‬ ‫𝟒𝟑‬ ‫‪1‬‬ ‫‪0‬‬ ‫خزنا ثالث قيمة ‪...‬نخزن رابع قيمة بقى اللي هي رقم ‪901‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪901‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪ 11‬زيي ما هي‬ ‫𝟑 = 𝟏𝟏 ‪𝒉 ሺ𝟗𝟎𝟏ሻ = 𝟗𝟎𝟏 %‬‬ ‫هنضيف رقم ‪901‬‬ ‫في الخانة رقم ‪3‬‬  ‫‪10‬‬ ‫‪9‬‬ ‫‪8‬‬ ‫‪7‬‬ ‫𝟗𝟑‬ ‫‪6‬‬ ‫‪5‬‬ ‫‪4‬‬ ‫𝟏𝟎𝟗‬ ‫‪3‬‬ ‫𝟔𝟒‬ ‫‪2‬‬ ‫𝟒𝟑‬ ‫‪1‬‬ ‫‪0‬‬ ‫خزنا رابع قيمة ‪...‬نخزن خامس قيمة بقى اللي هي رقم ‪815‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪815‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪ 11‬زيي ما هي‬ ‫𝟏 = 𝟏𝟏 ‪𝒉 ሺ𝟖𝟏𝟓ሻ = 𝟖𝟏𝟓 %‬‬ ‫هنضيف رقم ‪815‬‬ ‫في الخانة رقم ‪1‬‬ ‫طيب هنضيفها ازاي جمب القيمة األولى دي ؟!‬ ‫هنيجي عند الخانة اللي هنخزن فيها الرقم ‪:‬‬ ‫و هنضيف مستطيل جديد ‪..‬يعني كده ‪:‬‬  ‫هيبقى شكلها كده بعد ما نخزن رقم ‪: 815‬‬ ‫‪10‬‬ ‫‪9‬‬ ‫‪8‬‬ ‫‪7‬‬ ‫𝟗𝟑‬ ‫‪6‬‬ ‫‪5‬‬ ‫‪4‬‬ ‫𝟏𝟎𝟗‬ ‫‪3‬‬ ‫𝟔𝟒‬ ‫‪2‬‬ ‫𝟓𝟏𝟖‬ ‫𝟒𝟑‬ ‫‪1‬‬ ‫‪0‬‬ ‫خزنا خامس قيمة ‪...‬نخزن سادس و اخر قيمة بقى اللي هي رقم ‪67‬‬ ‫يعني هنعوض عن ال ‪ Key‬ب ‪67‬‬ ‫و هنعوض عن ال ‪ length‬ب ‪ 11‬زيي ما هي‬ ‫𝟏 = 𝟏𝟏 ‪𝒉 ሺ𝟔𝟕ሻ = 𝟔𝟕 %‬‬ ‫هنضيف رقم ‪67‬‬ ‫في الخانة رقم ‪1‬‬ ‫‪10‬‬ ‫‪9‬‬ ‫‪8‬‬ ‫‪7‬‬ ‫𝟗𝟑‬ ‫‪6‬‬ ‫‪5‬‬ ‫‪4‬‬ ‫𝟏𝟎𝟗‬ ‫‪3‬‬ ‫𝟔𝟒‬ ‫‪2‬‬ ‫𝟕𝟔‬ ‫𝟓𝟏𝟖‬ ‫𝟒𝟑‬ ‫‪1‬‬ ‫‪0‬‬