Hash Table
哈希表
哈希核心时间 均摊 O(1)空间 O(n)
把键映射到桶下标。平均常数时间的插入、查找、删除；冲突用拉链或开放寻址解决。
动画
0
∅
1
∅
2
∅
3
∅
4
∅
5
∅
哈希表：key → hash(key) % m，定位桶。
1 / 6
讲解
去重、计数、索引、缓存。几乎所有语言的 dict / Map 都是它。
- 01index = hash(key) % capacity。
- 02冲突：拉链法把同桶元素串成链表（或红黑树）。
- 03装载因子过高时扩容并 rehash，保持均摊 O(1)。
- 04查找时先定位桶，再比较 key 是否相等。
易错点
- 最坏情况全部撞车退化成 O(n)，依赖哈希质量。
- 可变对象作 key 被修改后会丢。
代码
const map = new Map();
map.set(class="text-ok">"cat", class="text-accent">1);
map.set(class="text-ok">"dog", class="text-accent">2);
const hit = map.get(class="text-ok">"cat"); // class="text-accent">1
map.has(class="text-ok">"owl"); // false