元数据卡
- 前置知识：哈希表基本原理（上一页）
- 预计时间：12 分钟
- 完成标志：能理解链地址法和开放地址法，知道负载因子的作用
冲突不可避免
即使最好的哈希函数，两个不同的 key 也可能映射到同一个数组下标。这叫哈希冲突。
解决冲突主要有两种方法。
方法一：链地址法 Separate Chaining
每个数组槽不直接存值，而是存一个链表。冲突的元素追加到链表末尾。
数组:
[0] → (key1, val1) → (key2, val2) ← key1 和 key2 映射到同一下标
[1] → (key3, val3)
[2] →python
class HashTableChaining:
def __init__(self, capacity=16):
self.capacity = capacity
self.table = [[] for _ in range(capacity)]
self.size = 0
def _hash(self, key):
return hash(key) % self.capacity
def put(self, key, value):
index = self._hash(key)
for i, (k, v) in enumerate(self.table[index]):
if k == key:
self.table[index][i] = (key, value) # 更新
return
self.table[index].append((key, value)) # 新增
self.size += 1优点：实现简单，删除方便 缺点：链表太长时退化成 O(n)
方法二：开放地址法 Open Addressing
不额外用链表，而是冲突时在数组里找下一个空位。
python
class HashTableOpenAddr:
def __init__(self, capacity=16):
self.capacity = capacity
self.table = [None] * capacity
self.size = 0
def _hash(self, key):
return hash(key) % self.capacity
def put(self, key, value):
index = self._hash(key)
while self.table[index] is not None:
if self.table[index][0] == key:
self.table[index] = (key, value) # 更新
return
index = (index + 1) % self.capacity # 线性探测
self.table[index] = (key, value)
self.size += 1线性探测就是冲突后依次往后找空位。如果第 3 个槽被占了，就看第 4 个，第 5 个……直到找到空位。
优点：空间利用率高 缺点：容易产生"聚集"——连续被占的槽越来越多
负载因子与扩容
哈希表不能无限制地往里塞数据。负载因子（load factor） 是已存元素 / 总容量。
python
load_factor = size / capacity- 负载因子 0.5：容量用了一半
- 负载因子 0.75：Java HashMap 的默认阈值
- 负载因子接近 1：冲突概率大增，性能崩溃
当负载因子超过阈值时，哈希表需要扩容（rehash）：
- 创建一个更大的数组（通常是 2 倍）
- 把旧数组的所有元素重新计算哈希，放入新数组
python
def _resize(self):
old_table = self.table
self.capacity *= 2
self.table = [[] for _ in range(self.capacity)]
self.size = 0
for bucket in old_table:
for key, value in bucket:
self.put(key, value)扩容是 O(n) 的操作，但平均分摊到每次插入，仍然是 O(1)。这叫摊还分析。
真实世界的哈希表
| 语言 | 实现 | 冲突解决 | 负载因子 | 备注 |
|---|---|---|---|---|
| Java HashMap | 数组 + 链表/红黑树 | 链地址 | 0.75 | 链表>8 转红黑树 |
| Python dict | 数组 + 开放地址 | 开放地址 | 2/3 | 伪随机探测序列 |
| C++ unordered_map | 数组 + 链表 | 链地址 | 1.0 | 逐个桶链式存储 |
旅人笔记
冲突不可避免。链地址法用链表兜底（简单），开放地址法在数组里找空位（省空间）。负载因子控制扩容时机——太小浪费空间，太大影响性能。扩容是 O(n) 但平均下来仍然是 O(1)。
→ 下一步：二叉树
哈希表适合精确查找——给我一个 key，立刻拿到值。但如果你需要按顺序遍历数据呢？