تخيل عندك دليل تليفون:
الـ Hash Table نفس الفكرة: بيحول الـ Key لـ index مباشرة!
الـ Hash Function هي اللي بتحول الـ Key لـ index:
مثال بسيط: hash(key) = مجموع ASCII values % حجم الـ array
O(1)*
O(1)*
O(1)*
* Average case - في حالة عدم وجود collisions كتير
التصادمات - المشكلة الكبيرة!
لما key مختلفة يجيلها نفس الـ index!
كل bucket فيها linked list من العناصر
لو حصل collision، ضيف العنصر في الـ list
لو المكان مشغول، دور على مكان فاضي
Linear Probing: جرب المكان التالي
Load Factor = عدد العناصر ÷ حجم الـ array
n = عدد العناصر، m = حجم الـ table
λ < 0.5
ممتاز! 🚀
0.5 ≤ λ ≤ 0.7
مقبول ⚠️
λ > 0.7
محتاج resize! 🔴
💡 ليه مهم؟
كل ما الـ Load Factor زاد، كل ما الـ collisions زادت!
عشان كده لما يوصل لـ 0.7، بنعمل resize (نضاعف
الحجم).
Enter a key and value, then insert.
class HashTable {
constructor(size = 10) {
this.buckets = new Array(size).fill(null).map(() => []);
this.size = size;
this.count = 0;
}
// Hash Function
hash(key) {
let hash = 0;
for (let char of String(key)) {
hash = (hash + char.charCodeAt(0)) % this.size;
}
return hash;
}
// Insert O(1)
set(key, value) {
const idx = this.hash(key);
const bucket = this.buckets[idx];
const existing = bucket.find(p => p[0] === key);
if (existing) existing[1] = value;
else { bucket.push([key, value]); this.count++; }
}
// Search O(1)
get(key) {
const idx = this.hash(key);
const pair = this.buckets[idx].find(p => p[0] === key);
return pair ? pair[1] : undefined;
}
}