ما هو الـ Hash Table وهل هو سريع فعلًا في البحث ؟

السلام عليكم ورحمة الله وبركاته

وقت القراءة: ≈ 15 دقيقة

المقدمة

في عالم هياكل البيانات، لدينا شيء يدعى الـ 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

لاحظ أن الـ 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 وكيفية تحسينها وتوزيع البيانات بشكل متوازن في كل الحالات

ومن أشهرها

هذه بعض الطرق المعروفة لتوزيع البيانات في الـ 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 زائد

بالتالي إذا حللنا ما حدث سنجد أن الأمور تسير كالتالي:

  1. المستخدم الأول: teamId: 1 - سينتظر ثانية
  2. المستخدم الثاني: teamId: 1 - سينتظر ثانية أخرى ليحضر فريق أحضرناه من قبل
  3. المستخدم الثالث: teamId: 2 - سينتظر ثانية
  4. المستخدم الرابع: teamId: 3 - سينتظر ثانية
  5. المستخدم الخامس: 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;
}

كيف يعمل الحل الجديد؟

  1. المستخدم الأول: teamId: 1 - يحضر الفريق ويخزنه في Cache (ثانية واحدة)
  2. المستخدم الثاني: teamId: 1 - يجد الفريق في Cache (لحظيًا)
  3. المستخدم الثالث: teamId: 2 - يحضر الفريق ويخزنه (ثانية واحدة)
  4. المستخدم الرابع: teamId: 3 - يحضر الفريق ويخزنه (ثانية واحدة)
  5. المستخدم الخامس: 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 بشكل أفضل