ما هو الـ Hash Table وهل هو سريع فعلًا في البحث ؟
السلام عليكم ورحمة الله وبركاته
الفهرس
المقدمة
في عالم هياكل البيانات، لدينا شيء يدعى الـ Hash Table
وهو يعد من أهم الـ Data Structre
من حيث البحث لأنه كما يقال فأنه يستطيع سريع جدا في البحث بمعدل O(1)
لكن هل فعلًا هو سريع في البحث ؟
سأجيب عن هذا السؤال بسؤال ... لما لا نقوم ببناءه ونرى بأنفسنا ؟
أولًا عندما نبدأ ببناء الـ Hash Table
يجب أن نعرف ما هى الـ Hash Function
لأن الـ Hash Table
يعتمد على دالة مهمة تدعى Hash Function
وهي ببساطة تقوم بتحويل قيم معينة إلى قيم رقمية محصورة في مجال معين وسنفهم هذا بالتفصيل تاليًا
لكن قبل أن أبدأ علي أن أتأكد أنك تعرف الـ %
أو ما يسمى بـ Modulus
أو الـ Remainder
وهو باقي قسمة العدد
في حالة أنك لا تعرقها فأنصحك بقراءة هذا المقال العمليات الحسابية في البرمجة وأنتقل إلى الجزء الذي يتحدث عن الـ Modulus
على أي حال لنبدأ بالشرح
ما هي الـ Hash Function ؟
الـ Hash Function هي ببساطة دالة تستطيع تحويل قيم معينة سواء أرقام أو نصوص إلى قيم رقمية محصورة في مجال معين تحدده أنت بنفسك
عن طريق استخدام الـ %
لنأخذ مثال بسيط على الـ Hash Function
function hashFunction(key: number) {
return key % 7;
}
لاحظ أن الـ Hash Function
تقوم بتحويل القيمة إلى قيمة بين 0
و 6
فقط لأن نستخدم % 7
بالتالي القيم ستكون من 0
إلى 6
أمثلة على استخدام الـ Hash Function
hashFunction(532); // 0
hashFunction(123); // 4
hashFunction(100); // 2
ورقم 7
ليس مقصود بذاته يمكنك تغييره إلى أي رقم تريده على حسب الحاجة
أو يمكنك تحويل الـ Hash Function
إلى دالة عامة
function hashFunction(key: number, size: number) {
return key % size;
}
جميل ... لكن ما الفائدة ؟
هذا ما سنجاوبه تاليًا
ما فائدة الـ Hash Function ؟
حسنًا رأينا كيف أن الـ Hash Function
بسيطة جدًا ولكن ما فائدتها ؟
الفائدة الرئيسية للـ Hash Function
هي عملية تحويل أو Mapping
لقيم عشوائية إلى قيم محددة ومحصورة في مجال معين
وهذا يساعدنا في تخزين القيم في مكان معين في الذاكرة والوصول إليها بسرعة
على سبيل المثال لنفترض أن لدينا أراي بحجم 7
تمثل أيام الأسبوع
وكل عنصر في الأراي يحتوي على اسم اليوم وقائمة بالمهام التي يجب القيام بها في ذلك اليوم
const days = [
{
name: "Saturday",
tasks: []
},
{
name: "Sunday",
tasks: []
},
{
name: "Monday",
tasks: []
},
{
name: "Tuesday",
tasks: []
},
{
name: "Wednesday",
tasks: []
},
{
name: "Thursday",
tasks: []
},
{
name: "Friday",
tasks: []
}
]
الآن لنفترض أننا لدينا مجموعة من المهام وليكن 100
مهمة وهذه المهام تأتي بترتيب تسلسلي
ونريد توزيع هذه المهام على أيام الأسبوع بنوع من التوازن
const tasks = [
{
id: 1,
name: "Task 1"
},
{
id: 2,
name: "Task 2"
},
// ...
{
id: 100,
name: "Task 100"
}
]
هنا يأتي دور الـ Hash Function
حيث يمكننا استخدامها لتحويل رقم المهمة أي كان هو إلى رقم بين 0
و 6
ومن ثم توزيع المهام على أيام الأسبوع
function hashFunction(key: number, size: number) {
return key % size;
}
وبعد ذلك يمكننا توزيع المهام على أيام الأسبوع بسهولة
function distributeTasks(tasks: string[]) {
for (let i = 0; i < tasks.length; i++) {
const dayIndex = hashFunction(tasks[i].id, days.length);
days[dayIndex].tasks.push(tasks[i].id);
}
}
لنحلل ما الذي حدث هنا
الدالة distributeTasks
تقوم بتوزيع المهام على أيام الأسبوع بناءً على الـ Hash Function
التي تقوم بتحويل id
المهمة إلى رقم بين 0
و 6
ومن ثم توزيع المهمة على اليوم المحدد الذي تم تحديده بالـ Hash Function
- المهمة
Task 1
ستوزع على يوم1
أي يوم الأحد لأن1 % 7 = 1
- المهمة
Task 2
ستوزع على يوم2
أي يوم الإثنين لأن2 % 7 = 2
- المهمة
Task 3
ستوزع على يوم3
أي يوم الثلاثاء لأن3 % 7 = 3
- ...
- المهمة
Task 6
ستوزع على يوم6
أي يوم الجمعة لأن6 % 7 = 6
- المهمة
Task 7
ستوزع على يوم0
أي يوم السبت لأن7 % 7 = 0
- المهمة
Task 8
ستوزع على يوم1
أي يوم الأحد لأن8 % 7 = 1
- ...
- المهمة
Task 98
ستوزع على يوم4
أي يوم الأربعاء لأن98 % 7 = 4
- المهمة
Task 99
ستوزع على يوم5
أي يوم الخميس لأن99 % 7 = 5
- المهمة
Task 100
ستوزع على يوم6
أي يوم الجمعة لأن100 % 7 = 6
- وهكذا
لاحظ أن الـ Hash Function
تقوم بتوزيع المهام بشكل متوازن إلى حد ما على أيام الأسبوع فكل يوم يحتوي على عدد متقارب من المهام
تقريبًا يوجد 14
مهمة على كل يوم وهذا يعتبر توزيع متوازن
لكن هذا ليس بالضرورة أنها ستوزع المهام بشكل مثالي في كل مرة لأن الأمر يعتمد على البيانات والأرقام التي تأتي إلى الـ Hash Function
وكيف تقوم أنت باستخدامها
لكن هذا مثال بسيط جدًا وسنرى أمثلة أخرى على الـ Hash Function
عندما نبدأ ببناء الـ Hash Table
ملاحظة: الـ
Implemntation
الخاص بالـHash Function
ليس ثابتًا ويمكنك تغييرها حسب الحاجة
ماذا لو كان القيمة المراد تحويلها نص ؟
الدالة السابقة تعمل فقط على الأرقام ولكن ماذا لو كانت القيمة نص ؟ أي string
وكما قلنا الـ Hash Function
يختلف الـ Implemntation
حسب الحاجة
بالتالي أنت الذي تحدد كيف تريد تحويل القيمة إلى رقم ولكن هناك طريقة شائعة لتحويل النصوص إلى أرقام وهي بأخذ قيمة الـ ASCII
الخاص بكل حرف جمعها مع بعضها البعض
function hashFunction(key: string, size: number) {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash += key.charCodeAt(i);
}
return hash % size;
}
في هذه الحالة، ستقوم الدالة بتحويل النص إلى قيمة رقمية بجمع قيم الـ ASCII
لكل حرف في النص ومن ثم تقوم بتقسيم القيمة على size
للحصول على قيمة بين 0
و size - 1
يمكنك تجربة الدالة مع النصوص المختلفة لترى كيف تعمل
hashFunction("hello", 7); // 0
hashFunction("world", 7); // 6
hashFunction("i am ahmed", 7); // 4
هنا في المثال الأول تم تحويل النص "hello"
إلى القيمة 532
عن طريق جمع قيم الـ ASCII
لكل حرف في النص هكذا 104 + 101 + 108 + 108 + 111 = 532
حيث h = 104
و e = 101
وهكذا
ثم قمنا بعمل المعادلة 532 % 7 = 2
للحصول على القيمة النهائية
وهكذا مع النصوص الأخرى
ما هو الـ Hash Table ؟
الـ Hash Table
هو ببساطة Data Structre
كغيرها لتخزين البيانات ولكن بطريقة معينة تعتمد على الـ Hash Function
بالتالي تمتاز الـ Hash Table
بسرعة البحث والتخزين قد تصل غالبًا إلى O(1)
ببساطة الـ Hash Table
هي ببساطة أراي من الـ Linked List
بالتالي كل عنصر في الأراي هو عبارة عن الـ Linked List
أو Dynamic Array
قد تقول أنه هكذا يشبه الـ Graph
ولكن الفرق هنا هو في طريقة توزيع وتخزين البيانات
فالـ Hash Table
تعتمد على الـ Hash Function
لتحديد مكان تخزين البيانات
فمثًلا لنفترض أن لدينا الـ Hash Table
بحجم 5
const hashTable : LinkedList[] = Array.from({ length: 5 }, () => new LinkedList());
لكن لتبسيط الشرح سنقوم بتخزين العناصر في الـ Hash Table
بدون استخدام الـ Linked List
بل نستخدم الشيء الذي يحاكي الـ Linked List
في اللغة التي نستخدمها
وبالطبع نحن نستخدم TypeScript
لذلك سنستخدم الـ Array
ولو كنت تستخدم Java
فسيكون الـ ArrayList
وهكذا
const hashTable : Array<number[]> = Array.from({ length: 5 }, () => []);
ولدينا الـ Hash Function
البسيطة التي تقوم بتحويل القيم إلى قيم بين 0
و size - 1
function hashFunction(key: number, size: number) {
return key % size;
}
الآن لضرب مثال بسيط سنقول أن لدينا المهام ونريد تخزينها في الـ Hash Table
const tasks = [
{
id: 1,
name: "Task 1"
},
{
id: 2,
name: "Task 2"
},
// ...
{
id: 100,
name: "Task 3"
}
];
هنا سنقوم بتوزيع المهام على الـ Hash Table
بناءً على الـ Hash Function
لذا سنرسل الـ id
إلى الـ Hash Function
ومن ثم ستخبرنا الـ Hash Function
بالمكان الذي ينتمي إليه الـ id
for (let i = 0; i < tasks.length; i++) {
const index = hashFunction(tasks[i].id, hashTable.length);
hashTable[index].push(tasks[i].id);
}
هكذا ما الذي حدث بالظبط ؟
أريدك أن تتخيل شكل الـ Hash Table
بعد توزيع المهام عليها
0: [5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 55, 60, 65, 70, 75, 80, 85, 90, 95, 100]
1: [1, 6, 11, 16, 21, 26, 31, 36, 41, 46, 51, 56, 61, 66, 71, 76, 81, 86, 91, 96]
2: [2, 7, 12, 17, 22, 27, 32, 37, 42, 47, 52, 57, 62, 67, 72, 77, 82, 87, 92, 97]
3: [3, 8, 13, 18, 23, 28, 33, 38, 43, 48, 53, 58, 63, 68, 73, 78, 83, 88, 93, 98]
4: [4, 9, 14, 19, 24, 29, 34, 39, 44, 49, 54, 59, 64, 69, 74, 79, 84, 89, 94, 99]
هنا ستجد أن كل عنصر في الـ Hash Table
متساوية والأهم من ذلك فكرة أنك قسمت مجموعة من العناصر على عدة أقسام
هذا يساعد في عملية البحث
كل قسم يسمى Bucket
وهو يحتوي على مجموعة من العناصر
فمثلًا الآن إذا أردنا البحث عن المهمة رقم 65
ما الذي سنقوم به ؟ هل نبحث عنها عنصر عنصر ؟ أكيد لا، ما فائدة الـ Hash Function
إذا ؟ وتوزيع العناصر على عدة أقسام ؟
نحن لدينا رقم 65
ونريد أن نعرف هل هو موجود في الـ Hash Table
أم لا
أولًا نحتاج إلى أي قسم ينتمي إليه الرقم 65
وهنا يأتي دور الـ Hash Function
لأن كل index
في الـ Hash Table
يمكنك تخيله على أنه قسم يحتوي على مجموعة من العناصر
والـ Hash Function
تقوم بتحديد القسم الذي ينتمي إليه كل عنصر
لذا سنستخدم الـ Hash Function
لمعرفة القسم الذي ينتمي إليه الرقم 65
ثم نقوم بالبحث عن الرقم 65
في هذا القسم فقط
const index = hashFunction(65, hashTable.length);
const task = hashTable[index].find((task) => task === 65);
if (task) {
console.log("Task found");
} else {
console.log("Task not found");
}
لكن هنا يأتي السؤال الأهم ... هل فعلًا الـ Hash Table
سريع في البحث ؟
لاحظ أننا كأن لدينا 100
مهمة وقمنا بتوزيعها على 5
أقسام فقط وكل قسم يحتوي على 20
مهمة
ثم عندما أردنا البحث عن مهمة معينة قمنا بالبحث في قسم واحد فقط
لذا هذه الخطوة hashFunction(65, hashTable.length)
جعلتنا نقلص نطاق البحث من 100
إلى 20
فقط
هنا كأنك قللت عدد العناصر التي تبحث إلى الخُمس
فبدلًا من أن تبحث في 5
أقسام أصبحت تبحث في قسم واحد فقط من العناصر
تخيل لو زودنا عدد الأقسام ... أقصد زودنا حجم الـ Hash Table
إلى 10
0: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100]
1: [1, 11, 21, 31, 41, 51, 61, 71, 81, 91]
2: [2, 12, 22, 32, 42, 52, 62, 72, 82, 92]
3: [3, 13, 23, 33, 43, 53, 63, 73, 83, 93]
4: [4, 14, 24, 34, 44, 54, 64, 74, 84, 94]
5: [5, 15, 25, 35, 45, 55, 65, 75, 85, 95]
6: [6, 16, 26, 36, 46, 56, 66, 76, 86, 96]
7: [7, 17, 27, 37, 47, 57, 67, 77, 87, 97]
8: [8, 18, 28, 38, 48, 58, 68, 78, 88, 98]
9: [9, 19, 29, 39, 49, 59, 69, 79, 89, 99]
لاحظ أننا لو أردنا البحث عن الرقم 65
سنقوم بالبحث في قسم واحد فقط وهو القسم 5
بدلًا من أن نبحث في 10
مجموعات أصبحنا نبحث في مجموعة واحدة فقط
دالة الـ Hash Function
وطريقة توزيع العناصر في الـ Hash Table
تساعد في تقليل نطاق البحث بشكل كبير
ما هي الـ Time Complexity للـ Hash Table ؟
حسنًا الآن نعرف أن الـ Hash Table
سريع في البحث والتخزين بسبب طريقته في توزيع البيانات
لكن عندما يأتي السؤال عن الـ Time Complexity
للـ Hash Table
ماذا نقول ؟
ستجد معظم الأشخاص يقولون بكل فخر أن الـ Time Complexity
للـ Hash Table
هو O(1)
والبعض على استحياء يقول غاليبًا أو تقريبًا O(1)
إذا توافرت بعض الشروط
لكن هل هذا صحيح ؟
حسنًا من الناحية الغالبة فإن الـ Time Complexity
للـ Hash Table
هو O(1)
لكن هذا يعتمد على العديد من العوامل والشروط
لذا في بعض الأحيان قد تجد أن الـ Time Complexity
للـ Hash Table
تكون O(n)
والسبب ؟
غاليبًا يكون السبب في الـ hash function
وفي طريقتها في توزيع البيانات ويعتمد على نوعية البيانات التي ستقوم بتوزيعها
فعلى سبيل المثال تخيل أن الـ 100
عنصر التي قمنا بتوزيعها على الـ Hash Table
كل عنصر يقبل القسمة على 5
بالتالي ستجد أن الـ Hash Table
ستكون بهذا الشكل
0: [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, 130, 140, 150, 160, 170, 180, 190, 200, 210, 220, 230, 240, 250, 260, 270, 280, 290, 300, 310, 320, 330, 340, 350, 360, 370, 380, 390, 400, 410, 420, 430, 440, 450, 460, 470, 480, 490, 500]
1: []
2: []
3: []
4: []
5: [5, 15, 25, 35, 45, 55, 65, 75, 85, 95, 105, 115, 125, 135, 145, 155, 165, 175, 185, 195, 205, 215, 225, 235, 245, 255, 265, 275, 285, 295, 305, 315, 325, 335, 345, 355, 365, 375, 385, 395, 405, 415, 425, 435, 445, 455, 465, 475, 485, 495]
6: []
7: []
8: []
9: []
ستجد أن توزيع العناصر في الـ Hash Table
ليس متوازنًا على الإطلاق
فلديك 50
في الـ index
رقم 0
و 50
في الـ index
رقم 5
بالتالي هنا نفسهم أنه فعلًا في بعض الأحيان قد تكون الـ Time Complexity
للـ Hash Table
هي O(n)
وهذا يعتمد على طبيعة البيانات والـ Hash Function
وطريقة توزيع البيانات
هل يمكننا تحسين الـ Hash Table ؟
السؤال يجب أن يكون هل يمكننا تحسين الـ Hash Function
؟
لأن الـ Hash Function
هي البنية الأساسية للـ Hash Table
وهي التي تقوم بتوزيع البيانات
بالتالي توزيع البيانات بشكل متوازن يحسن من أداء الـ Hash Table
في الحقيقة هناك العديد من الـ Hash Function
المعروفة والتي تقوم بتوزيع البيانات بشكل متوازن
ويوجد أبحاث كثيرة حول الـ Hash Function
وكيفية تحسينها
من أبرزها هو أن تجعل الـ Hash Function
تعتمد على الـ Prime Number
أي استخدام الأعداد الأولية في حساب باقي القسمة
لأنه من النادر أن تجد مجموعة من الأرقام المختلفة تقبل القسمة على العدد الأولي
هنا سنحتاج لجعل حجم الـ Hash Table
يكون عدد أولي وهذا الأمر من الأمور الشائعة في الـ Hash Table
وهو أن تحاول جعل حجم الـ Hash Table
يكون عدد أولي لتحسين أداء الـ Hash Table
لنفترض أن لدينا 100
عنصر ونريد توزيعها على الـ Hash Table
ونريد أن يكون حجم الـ Hash Table
عدد أولي
const hashTable : Array<number[]> = Array.from({ length: 11 }, () => []);
const values = Array.from({ length: 100 }, (_, i) => i + 1);
for (let i = 0; i < values.length; i++) {
const index = hashFunction(values[i], hashTable.length);
hashTable[index].push(values[i]);
}
هنا ستجد أن الـ Hash Table
ستكون بهذا الشكل
0: [11, 22, 33, 44, 55, 66, 77, 88, 99]
1: [1, 12, 23, 34, 45, 56, 67, 78, 89, 100]
2: [2, 13, 24, 35, 46, 57, 68, 79, 90]
3: [3, 14, 25, 36, 47, 58, 69, 80, 91]
4: [4, 15, 26, 37, 48, 59, 70, 81, 92]
5: [5, 16, 27, 38, 49, 60, 71, 82, 93]
6: [6, 17, 28, 39, 50, 61, 72, 83, 94]
7: [7, 18, 29, 40, 51, 62, 73, 84, 95]
8: [8, 19, 30, 41, 52, 63, 74, 85, 96]
9: [9, 20, 31, 42, 53, 64, 75, 86, 97]
10: [10, 21, 32, 43, 54, 65, 76, 87, 98]
حسنًا لكن ماذا لو كل العناصر العناصر تقبل القسمة على الرقم 5
فماذا سيحدث ؟
const values = Array.from({ length: 100 }, (_, i) => (i + 1) * 5);
ستجد أن الـ Hash Table
ستكون بهذا الشكل
0: [55, 110, 165, 220, 275, 330, 385, 440, 495]
1: [45, 100, 155, 210, 265, 320, 375, 430, 485]
2: [35, 90, 145, 200, 255, 310, 365, 420, 475]
3: [25, 80, 135, 190, 245, 300, 355, 410, 465]
4: [15, 70, 125, 180, 235, 290, 345, 400, 455]
5: [5, 60, 115, 170, 225, 280, 335, 390, 445, 500]
6: [50, 105, 160, 215, 270, 325, 380, 435, 490]
7: [40, 95, 150, 205, 260, 315, 370, 425, 480]
8: [30, 85, 140, 195, 250, 305, 360, 415, 470]
9: [20, 75, 130, 185, 240, 295, 350, 405, 460]
10: [10, 65, 120, 175, 230, 285, 340, 395, 450]
لاحظ أن النتيجة أصبحت أفضل والتوزيع أصبح متوازنًا أكثر من السابق
بسبب أن حجم الـ Hash Table
هو عدد أولي
هل هذا يعني أن الـ Hash Table
سيكون دائمًا سريع ؟
لا لأنك ستجد أن لو كل العناصر تقبل القسمة على الرقم الأولي الذي اخترته أي لو كل الأرقام كانت من مضاعفات الرقم الأولي
ستجد أن التوزيع سينحصر في Bucket
واحدة أي index
واحد فقط
const values = Array.from({ length: 100 }, (_, i) => (i + 1) * 11); // same prime number as the hash table size
ستجد أن الـ Hash Table
ستكون بهذا الشكل
0: [11, 22, 33, 44, 55, 66, 77, 88, 99, 110, 121, 132, 143, 154, 165, 176, 187, 198, 209, 220, 231, 242, 253, 264, 275, 286, 297, 308, 319, 330, 341, 352, 363, 374, 385, 396, 407, 418, 429, 440, 451, 462, 473, 484, 495, 506, 517, 528, 539, 550, 561, 572, 583, 594, 605, 616, 627, 638, 649, 660, 671, 682, 693, 704, 715, 726, 737, 748, 759, 770, 781, 792, 803, 814, 825, 836, 847, 858, 869, 880, 891, 902, 913, 924, 935, 946, 957, 968, 979, 990, 1001, 1012, 1023, 1034, 1045, 1056, 1067, 1078, 1089, 1100]
1: []
2: []
3: []
4: []
5: []
6: []
7: []
8: []
9: []
10: []
هكذا عدنا إلى البحث العادي O(n)
وإلى نفس المشكلة
هل يوجد Hash Function مثالية ؟
الإجابة القصيرة هي لا
لأن الـ Hash Function
تعتمد على البيانات والأرقام التي تقوم بتوزيعها وعلى المثال الذي تتعامل معه
وكما قلت يوجد أبحاث ونظريات قائمة على الـ Hash Function
وكيفية تحسينها وتوزيع البيانات بشكل متوازن في كل الحالات
ومن أشهرها
Division Method
: وهي الطريقة التي قمنا بتطبيقها في الأمثلة السابقة وهي ببساطة استخدام باقي القسمة لتوزيع البياناتn % size
Folding Method
: وهي طريقة تقوم بتقسيم القيمة إلى أجزاءchunk
ومن ثم تقوم بجمع الأجزاء مع بعضها البعض وتقوم بتقسيم الناتج على حجم الـHash Table
function hashFunction(key: number, size: number) { const keyString = key.toString(); let hash = 0; for (let i = 0; i < keyString.length; i += 2) { const chunk = keyString.slice(i, i + 2); hash += parseInt(chunk); } return hash % size; }
Multiplication Method
: وهي طريقة تقوم بضرب القيمة في رقم عشوائي ثم تأخذ الجزء العشري من الناتج وتقوم بضربه في حجم الـHash Table
ثم تأخذ الجزء الصحيح من الناتجfloor(size * (n * A % 1))
حيثA
هو رقم عشوائي بين0
و1
وأحيانا يكونA
هو النسبة الذهبية0.6180339887
أو يتم حسابه هكذاA = (Math.sqrt(5) - 1) / 2
function hashFunction(key: number, size: number) { const A = (Math.sqrt(5) - 1) / 2; return Math.floor(size * (key * A % 1)); }
وناتج التوزيع يكون متوازنًا بشكل كبير حتى لو كانت البيانات تقبل القسمة على الرقم الأولي مثل الأمثلة السابقة
وهذه الطريقة تحل كل المشاكل التي واجتهتنا في الأمثلة السابقةUniversal Hashing
: وهي طريقة تقوم بإنشاء العديد من الـHash Function
وتقوم بتطبيق الـHash Function
المناسبة حسب الحالة
وهذه الطريقة تعتبر من أفضل الطرق لتوزيع البيانات بشكل متوازنfunction hashFunction(key: number, size: number) { const a = Math.floor(Math.random() * size); const b = Math.floor(Math.random() * size); return ((a * key + b) % size); }
وله عدة أشكال وطرق للتطبيقه ولا يحتصر على الشكل الذي كتبته
Bitwise Hashing
الأمر وصل حتى استخدام العمليات على مستوى الـBit
لتوزيع البيانات
وبالطبع هذه طريقة لها أشكال ومعادلات أخرىMid-Square Method
MurmurHash
Cryptographic Hashing
... إلخ
هذه بعض الطرق المعروفة لتوزيع البيانات في الـ Hash Table
وهناك العديد من الطرق الأخرى بالطبع
بناء كلاس الـ Hash Table
كختام دعونا نجمع الـ Hash Table
في كلاس واحد
class HashTable {
private hashTable: Array<number[]>;
constructor(size: number = 17) {
this.hashTable = Array.from({ length: size }, () => []);
}
private hash(key: number) {
const A = (Math.sqrt(5) - 1) / 2;
return Math.floor(this.hashTable.length * (key * A % 1));
}
public set(key: number) {
const index = this.hash(key);
this.hashTable[index].push(key);
}
public get(key: number) {
const index = this.hash(key);
return this.hashTable[index].find((value) => value === key);
}
}
هنا عملنا كلاس الـ Hash Table
وهو مثل ما شرحناه لا يوجد شيء جديد
وعملنا دالة الـ hash
بطريقة الـ Multiplication Method
لتوزيع البيانات بطريقة متوازنة لمعظم الحالات
وطبعًا استخدام الكلاس بسيط جدًا
const hashTable = new HashTable(11);
hashTable.set(5);
hashTable.set(10);
hashTable.get(5); // 5
hashTable.get(7); // undefined
مثال بسيط لاستخدام الـ Hash Table كـ Cache
أريد أن اريكم مثال بسيط يساعد على ترسيخ فكرة كيف يمكنك الاستفادة من الـ Hash Table
بطريقة مختلفة
طالما أن الـ Hash Table
سريع في البحث والتخزين فلماذا لا نستفيد من هذه السرعة في بعض الأمور كـ Cache
بسيط داخل الكود
فلنفترض أن لدينا مجموعة من المستخدمين
const users = [
{
id: 1,
name: "User 1",
teamId: 1
},
{
id: 2,
name: "User 2",
teamId: 1
},
{
id: 3,
name: "User 3",
teamId: 2
},
{
id: 4,
name: "User 4",
teamId: 3
},
{
id: 5,
name: "User 5",
teamId: 3
}
];
هنا لنفترض اننا نريد احضار بيانات الـ Team
للمستخدمين
ولنفترض أننا لدينا دالة تدعى getTeamById
تقوم بإحضار بيانات الـ Team
بناءً على الـ id
ومن أجل محاكاة الوقت الذي نستغرقه في الـ API
سنقوم بإضافة setTimeout
لمدة 1
ثانية لمحاكاة وقت الـ Request
والـ Response
const getTeamById = (id: number) => {
return new Promise((resolve, reject) => {
setTimeout(() => {
const team = {
id: id,
name: `Team ${id}`
}
resolve(team);
}, 1000);
});
}
كيف نحضر بيانات كل فريق ؟
ستقول لي بسيطة نقوم بعمل for
لكل المستخدمين ونحضر بيانات الـ Team
لكل مستخدم
بالتالي أظنك ستكتب الكود التالي
const getUsersWithTeams = async () => {
const usersWithTeams = [];
for (let i = 0; i < users.length; i++) {
const team = await getTeamById(users[i].teamId);
usersWithTeams.push({
...users[i],
team
});
}
return usersWithTeams;
}
ما المشكلة في هذا الكود ؟
المشكلة أنك لو نظرت إلى البيانات التي بداخل الـ users
ستجد أن هناك مستخدمين ينتمون لنفس الفريق
بالتالي ستقوم بعمل Request
لنفس الفريق أكثر من مرة وبالتالي سنحصل على تكرار للبيانات واهدار لوقت لكل Request
زائد
بالتالي إذا حللنا ما حدث سنجد أن الأمور تسير كالتالي:
- المستخدم الأول:
teamId: 1
- سينتظر ثانية - المستخدم الثاني:
teamId: 1
- سينتظر ثانية أخرى ليحضر فريق أحضرناه من قبل - المستخدم الثالث:
teamId: 2
- سينتظر ثانية - المستخدم الرابع:
teamId: 3
- سينتظر ثانية - المستخدم الخامس:
teamId: 3
- سينتظر ثانية أخرى ليحضر فريق أحضرناه من قبل
إجمالي الوقت سيكون 5
ثواني أو أكثر بجسب عدد المستخدمين وعدد الفرق
وتخيل لو لديك 100
شخص كلهم ينتمون لنفس الفريق ستنتظر 100
ثانية أو أكثر لتحضر نفس الفريق 100
مرة
الحل باستخدام Hash Table كـ Cache
const getUsersWithTeams = async () => {
const teamsCache = new HashTable(17); // prime number
const usersWithTeams = [];
for (let i = 0; i < users.length; i++) {
const teamId = users[i].teamId;
// Check if the team is in the Cache
if (!teamsCache.has(teamId)) {
// If not, get the team and store it in the Cache
const team = await getTeamById(teamId);
teamsCache.set(teamId, team);
}
// else get the team from the Cache
usersWithTeams.push({
...users[i],
team: teamsCache.get(teamId)
});
}
return usersWithTeams;
}
كيف يعمل الحل الجديد؟
- المستخدم الأول:
teamId: 1
- يحضر الفريق ويخزنه فيCache
(ثانية واحدة) - المستخدم الثاني:
teamId: 1
- يجد الفريق فيCache
(لحظيًا) - المستخدم الثالث:
teamId: 2
- يحضر الفريق ويخزنه (ثانية واحدة) - المستخدم الرابع:
teamId: 3
- يحضر الفريق ويخزنه (ثانية واحدة) - المستخدم الخامس:
teamId: 3
- يجد الفريق فيCache
(لحظيًا)
إجمالي الوقت أصبح 3 ثواني فقط بدلاً من 5 ثواني
لنجرب الكود:
console.time('Without Cache');
const result1 = await getUsersWithoutCache();
console.timeEnd('Without Cache');
// Without Cache: ~5000ms
console.time('With Cache');
const result2 = await getUsersWithTeams();
console.timeEnd('With Cache');
// With Cache: ~3000ms
هذا مثال بسيط على كيفية استخدام Hash Table
كـ Cache
بالطبع يوجد حلول مختلفة لحل المشكلة بشكل مختلف عن طريق أننا نحضر القيم الـ unique
فقط الخاصة بالـ Team
ونقوم باحضارها
لكن أردت أن أظهر لك كيف يمكنك استخدام الـ Hash Table
في حل المشكلات لا أكثر
الختام
في النهاية الـ Hash Table
هو Data Structure
مميزة ومفيدة وأيضًا سريعة
أحببت في هذه المقالة أن أشرح لك ما هو الـ Hash Table
عن طريق بماءه بشكل عملي وبسيط
وبالطبع قد تجد طرق مختلفة لبناء وتحسين الـ Hash Table
لكن تذكر أن الأساس يظل هو الأساس
وأساس الـ Hash Table
هو الـ Hash Function
وطريقة توزيع البيانات فيه
أتمنى أن تكون قد استفدت من هذه المقالة وأن تكون قد فهمت الـ Hash Table
بشكل أفضل