哈希表如何处理冲突、负载因子和调整大小？

Question

Accepted Answer

两个不同的键可能会哈希到**同一个桶** — **冲突**。哈希表通过解决冲突和在桶变得拥挤之前进行**调整大小**来保持平均 O(1)，由**负载因子**控制。

## 冲突解决

```text
Separate chaining: each bucket holds a list
  [3] -> ("cat",9) -> ("rat",2)   # both hashed to 3

Open addressing: probe to the next free slot
  hash=3 taken -> try 4 -> try 5 ... (linear probing)
```

## 负载因子和调整大小

```text
load factor α = number_of_entries / number_of_buckets
α rises -> more collisions -> slower lookups
When α exceeds a threshold (e.g. 0.75):
  -> allocate a bigger array (usually 2x)
  -> REHASH every existing key into new buckets
```

```python
# Conceptual resize
def _resize(self):
    old = self.buckets
    self.buckets = [None] * (len(old) * 2)
    for entry in all_entries(old):
        self._insert(entry.key, entry.value)   # rehash into new array
```

## 复杂度

| 操作 | 平均 | 最坏 |
|---|---|---|
| lookup / insert / delete | O(1) | O(n) |
| 单次调整大小 | — | O(n) |
| insert（摊销，包括调整大小） | O(1) | — |

调整大小是 O(n) 但发生很少，所以它**摊销到每次插入 O(1)**。

## 权衡

- **链接法**：简单，性能优雅降级，但需要额外指针且缓存局部性差。
- **开放寻址法**：缓存友好且紧凑，但对高负载因子敏感，需要小心删除（墓碑）。

## 为什么这很重要

这些内部机制解释了*为什么*哈希映射平均速度快，但仍可能飙升至 O(n) — 这对性能关键代码和对抗性输入（哈希洪泛）防护至关重要。

理解负载因子也解释了实际库暴露的内存/速度调优旋钮。

操作	平均	最坏
lookup / insert / delete	O(1)	O(n)
单次调整大小	—	O(n)
insert（摊销，包括调整大小）	O(1)	—