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).