Hash Table
A hash table maps keys to bucket locations using a hash function. It aims for very fast average lookup, insertion and deletion.
ابدأ بهذا النموذج الذهني
A hash table maps keys to bucket locations using a hash function. It aims for very fast average lookup, insertion and deletion.
كيف يعمل، بلا مصطلحات زائدة
The hash function converts a key into an index-like value.
Different keys may collide, so the implementation needs a collision strategy such as chaining or open addressing.
اقرأ الخوارزمية كسلسلة من القرارات
Hash the key.
Map the hash to a bucket.
Resolve collisions and compare actual keys.
A user id can be hashed to a bucket; the bucket then stores or finds the actual user entry.
class HashTable {
constructor(size = 16) {
this.buckets = Array.from({ length: size }, () => []);
}
hash(key) {
let h = 0;
for (const ch of String(key)) h = (h * 31 + ch.charCodeAt(0)) >>> 0;
return h % this.buckets.length;
}
}لا تحفظ الصياغة. تتبع الحالة التي تتغير في كل سطر واربطها بالثابت الموضح أعلاه.
avg O(1), worst O(n)
Do not quote this complexity mechanically. Ask which operation or input dimension it describes, then derive the cost from the loops, recursion depth, data-structure operations and any preprocessing assumptions.
مناسب لـ
- Choose it when its dominant operations match your workload.
- Compare memory overhead as well as Big-O.
ما الذي يسوء عادةً
- Calling average O(1) a guaranteed worst-case O(1).
- Ignoring key equality and collision handling.
صيغة إجابة احترافية
Explain average O(1), collisions, load factor and resizing. Those details distinguish a strong answer from 'it is just a key-value map'.
What problem does Hash Table solve?
A hash table maps keys to bucket locations using a hash function. It aims for very fast average lookup, insertion and deletion.
ماذا يجب أن أذكر عن التعقيد؟
Its typical cost here is avg O(1), worst O(n), but a complete answer should connect that cost to the representation, input constraints and the dominant operations.
ما الخطأ الأكثر شيوعاً؟
Calling average O(1) a guaranteed worst-case O(1).