4.2 哈希冲突与扩容

前置：哈希表基础，约 45 分钟。本节比较链地址与开放寻址，重点推清线性探测的停止条件、墓碑删除，以及几何扩容在散列与负载假设下为何能带来预期摊还 O(1) 的插入成本。

多个 key 落入同一 bucket

假设 A 和 I 经过哈希后得到同一个 bucket 下标。链地址法把两项留在同一 bucket 的容器里；开放寻址法则沿探测序列寻找另一个槽位。

冲突本身无法消失，数据结构需要规定冲突发生后怎样继续，以及何时能确定 key 不存在。

冲突为何无法靠“更好的函数”消除

假设表只有 m 个桶，key 的可能取值却多于 m。按照鸽巢原理，至少两个 key 会进入同一桶。好的哈希函数会让常见输入分布得更均匀，减少拥挤；它无法为无限 key 提供无限桶。

冲突处理必须同时回答三件事：

1. 新 key 放在哪里？
2. 查询从哪里开始，又在什么条件下停止？
3. 删除一个 key 后，怎样保证其他 key 仍能被找到？

两条主路线

维度	链地址法	开放寻址法
桶内存储	每个桶可保存多条映射	全部映射都放在主数组中
冲突后动作	在同一桶内继续比较	按探测序列寻找其他槽位
删除	从桶容器移除目标	需要墓碑、回移或重新插入等策略
负载因子	可以大于 1	活跃元素数量不能超过槽位数量
局部性	取决于桶结构	连续数组通常更有利于缓存
主要风险	单桶过长	聚集、墓碑累积、探测变长

这里比较的是设计家族。具体库可能使用不同布局、元数据和优化，不应仅凭类型名推断内部实现。

链地址法：把同桶 key 留在一起

上一页实现的桶可以表示成：

bucket[1]
  ├── ("A", "apple note")
  └── ("I", "ink note")

查询 "I" 时，哈希函数只负责抵达 bucket[1]。随后逐项执行 key 相等比较。删除 "A" 不会切断 "I" 的查找路径，因为两条映射都由桶容器直接管理。

设 n 为元素数量，m 为桶数量，链地址法的负载因子是：

alpha = n / m

在简单均匀散列假设下，一个桶的期望长度为 alpha，查找还需常数次定位，因此预期成本为 O(1+alpha)。alpha 受到常数上界约束时，桶内预期比较次数也受到常数上界约束。若输入集中到同一桶，操作仍会退化到 O(n)。

开放寻址：沿探测序列找位置

开放寻址只使用主数组中的槽位。线性探测从起始桶开始，依次检查：

start, (start + 1) % capacity, (start + 2) % capacity, ...

容量为 8，"A"、"I"、"Q" 都从槽 1 开始时，插入过程如下：

插入 A: [ ·, A, ·, ·, ·, ·, ·, · ]
插入 I: [ ·, A, I, ·, ·, ·, ·, · ]
插入 Q: [ ·, A, I, Q, ·, ·, ·, · ]

连续占用的区域叫 cluster（聚集区）。后来的 key 即使起点不同，只要落入这段区域，也要经过更多槽位。线性探测实现简单，却容易出现 primary clustering。

删除为什么不能直接写成空槽

接着上面的状态查询 "Q"：从槽 1 看见 A，再看槽 2 的 I，最后在槽 3 找到 Q。

若删除 A 时把槽 1 直接改成“从未使用”，查询 Q 会在槽 1 提前停止，错误地报告缺失：

错误删除 A: [ ·, ·, I, Q, ·, ·, ·, · ]
                 ↑ 查询从这里误判探测链结束

一个常见方案是写入 DELETED 墓碑：

墓碑删除 A: [ ·, ×, I, Q, ·, ·, ·, · ]
                 ↑ 查询越过 ×，插入可以复用 ×

槽位因此有三种状态：

• EMPTY：从未使用。查询可以停止。
• OCCUPIED：保存一条映射。比较 key。
• DELETED：曾经使用。查询继续，插入可把它记为候选位置。

一份可执行的线性探测表

下面的教学实现只接受字符串 key。每轮探测最多检查 capacity 个槽位，满表查询不会陷入无限循环；插入前检查活跃负载，必要时扩容。它没有自动清理墓碑；下面会用这个限制说明只看活跃元素数为什么不够。演示中的 max_load=1.0 允许填满表，便于测试终止条件，不代表推荐的性能配置。

EMPTY = object()
DELETED = object()

def stable_hash(key):
    if not isinstance(key, str):
        raise TypeError("this teaching map accepts string keys only")
    value = 0
    for char in key:
        value = (value * 31 + ord(char)) & 0xFFFFFFFF
    return value

class LinearProbingMap:
    def __init__(self, capacity=8, max_load=0.7):
        if capacity <= 0:
            raise ValueError("capacity must be positive")
        if not 0 < max_load <= 1:
            raise ValueError("max_load must be in (0, 1]")
        self._keys = [EMPTY] * capacity
        self._values = [None] * capacity
        self._size = 0
        self._max_load = max_load

    @property
    def capacity(self):
        return len(self._keys)

    def __len__(self):
        return self._size

    def _indices(self, key):
        start = stable_hash(key) % self.capacity
        for offset in range(self.capacity):
            yield (start + offset) % self.capacity

    def _find_existing(self, key):
        for index in self._indices(key):
            stored_key = self._keys[index]
            if stored_key is EMPTY:
                return None
            if stored_key is not DELETED and stored_key == key:
                return index
        return None

    def _insert_without_resize(self, key, value):
        first_deleted = None
        for index in self._indices(key):
            stored_key = self._keys[index]
            if stored_key is DELETED and first_deleted is None:
                first_deleted = index
            elif stored_key is EMPTY:
                target = first_deleted if first_deleted is not None else index
                self._keys[target] = key
                self._values[target] = value
                self._size += 1
                return

        if first_deleted is not None:
            self._keys[first_deleted] = key
            self._values[first_deleted] = value
            self._size += 1
            return
        raise RuntimeError("hash table is full")

    def _resize(self, new_capacity):
        old_entries = [
            (key, self._values[index])
            for index, key in enumerate(self._keys)
            if key is not EMPTY and key is not DELETED
        ]
        self._keys = [EMPTY] * new_capacity
        self._values = [None] * new_capacity
        self._size = 0
        for key, value in old_entries:
            self._insert_without_resize(key, value)

    def put(self, key, value):
        existing = self._find_existing(key)
        if existing is not None:
            self._values[existing] = value
            return

        if (self._size + 1) / self.capacity > self._max_load:
            new_capacity = self.capacity * 2
            while (self._size + 1) / new_capacity > self._max_load:
                new_capacity *= 2
            self._resize(new_capacity)

        self._insert_without_resize(key, value)

    def get(self, key):
        index = self._find_existing(key)
        if index is None:
            raise KeyError(key)
        return self._values[index]

    def remove(self, key):
        index = self._find_existing(key)
        if index is None:
            raise KeyError(key)
        value = self._values[index]
        self._keys[index] = DELETED
        self._values[index] = None
        self._size -= 1
        return value

table = LinearProbingMap(8, max_load=1.0)
table.put("A", "apple")
table.put("I", "ink")
table.put("Q", "quartz")
table.remove("A")

assert table.get("I") == "ink"
assert table.get("Q") == "quartz"
assert len(table) == 2
table.put("Q", "updated quartz")
assert len(table) == 2
assert table.get("Q") == "updated quartz"
table.put("Y", None)
assert table._keys[1] == "Y"
assert table.get("Y") is None

代码里的三个不变量

1. _indices 最多生成 capacity 个位置，查询与插入都能终止。
2. _find_existing 遇到 EMPTY 才能判定缺失，遇到 DELETED 必须继续。
3. _resize 只搬运活跃映射，墓碑不会进入新表。

put 先查询已有 key，再判断扩容。更新 value 不增加元素数量，也不应因为“即将插入一个新 key”而错误扩容。先查完整探测路径还能避免另一种错误：若看到墓碑就马上插入，后面可能已经有同一个 key，表内就出现了重复映射。_insert_without_resize 因而是一个只供“已确认 key 缺失”或重建时使用的内部方法。

负载因子不只有一个含义

通常写作 alpha = n / m，其中 n 是活跃映射数，m 是桶或槽位数。两种策略对 alpha 的容忍度不同：

• 链地址允许 alpha > 1，因为一个桶能保存多条映射；alpha 增大会拉长桶内搜索。
• 开放寻址要求活跃元素不超过槽位。alpha 越接近 1，可用空槽越少，探测往往越长。

墓碑还会带来第二个指标：占用因子 (n+t)/m，其中 t 是墓碑数。墓碑会延长查询路径，即使活跃负载 n/m 已经很低。例如填满 8 个槽位再删除 7 项：

sparse = LinearProbingMap(8, max_load=1.0)
for key in "ABCDEFGH":
    sparse.put(key, key)
for key in "ABCDEFG":
    sparse.remove(key)
assert len(sparse) == 1
assert all(key is not EMPTY for key in sparse._keys)
assert sparse._find_existing("missing") is None

只剩一项，但没有 EMPTY，失败查询仍会扫描全部 8 个槽位。教学类尚未按占用因子重建，因此不能为任意长期增删负载承诺预期 O(1)。改进时可以记录墓碑数量并做同容量重建；不必每次都扩大表。

Java HashMap 的默认负载因子是 0.75。这个数字是该类的默认时间/空间折中，不是所有哈希表都应采用的常数。Python、C++ 库和其他开放寻址实现有各自的公开契约与实现选择。

扩容为什么必须重新放置元素

桶下标依赖容量：

index = hash_code % capacity

容量从 8 变成 16 后，旧下标不能直接沿用。实现需要创建新数组，并按新容量重新定位每个活跃 key。这个过程常被称为 rehash，但不一定需要重新计算 key 的原始哈希值；具体取决于实现是否缓存哈希。

先分开分配、扫描和重插。新旧容量分别为 m_new、m_old，初始化新数组和扫描旧数组需要 Θ(m_new+m_old)。本例还会重算各 key 的哈希，并在新表中探测位置。

若哈希操作按常数计、散列分布合理，容量与活跃元素量同阶，重建的预期成本是 Θ(n)。从空表、固定初始容量开始，以固定倍数扩容，连续插入 n 个元素期间的预期迁移工作形成几何级数：

1 + 2 + 4 + ... < 2n

于是预期总工作为 Θ(n)，得到预期摊还 O(1) 插入。这里同时用了概率模型和整段序列分析，二者不能省略。

最坏碰撞下，本例重新插入 n 个同起点 key 要探测 1+2+...+n = n(n+1)/2 个槽位，重建可达 Θ(n²)，并非只做 n 次常数搬运。几何扩容不会消除这笔碰撞成本。

实时系统若不能接受单次长暂停，可以选择增量迁移、预留容量或其他数据结构；普通业务代码则常根据预计元素量提前设置容量。

复杂度速查

令 n 为活跃映射数、m 为容量。以下把 key 操作算作常数，并假设散列分布适合对应策略。线性探测还要求占用因子与 1 保持固定距离；仅限制 n/m 不够。

操作	分布良好、负载受控时	最坏情况	主要原因
链地址查询	预期 O(1)	O(n)	所有 key 进入同一桶
线性探测查询	预期 O(1)	O(m)	聚集区、墓碑或满表
不扩容的线性探测插入	预期 O(1)	O(m)	确认缺失与寻找插入位，各最多扫描 m 槽
重建/扩容，m 与 n 同阶	预期 Θ(n)，按序列摊还后 O(1)	Θ(n²) 可发生	重插时也可能严重碰撞
删除	预期 O(1)	链地址 O(n)；线性探测 O(m)	先定位，再移除或写墓碑
空间	O(m + n) 或 O(m)	同阶	取决于策略与元数据

哈希 key 本身若长度为 L，表操作还要加上哈希和相等比较的成本。复杂度表不能替代对 key 类型与输入来源的说明。

标准库契约怎么读

类型	可以依赖的公开事实	不宜凭空假设
Python dict	key 必须可哈希；保留插入顺序	固定桶布局、固定字符串哈希值
Java HashMap	默认负载因子 0.75；允许 null；不保证顺序；非同步	所有版本都采用同一内部节点策略
C++ std::unordered_map	以桶、哈希器和 key 等价谓词定义；多数操作平均常数、最坏线性	某种具体链表布局由标准强制规定

扩容还可能影响迭代器或遍历顺序。C++ 标准明确规定 rehash 会使迭代器失效并改变桶分配，但保留元素引用和指针；Java 与 Python 有各自的修改期间遍历规则。保存迭代器、引用或视图跨越结构修改前，应查看对应版本文档。

常见错误

探测时用对象身份比较 key

Python 的 is 检查对象身份，映射 key 通常需要 == 的值相等语义。"same" 的两个独立对象可以相等，却未必是同一对象。

循环直到找到空位，却不限制步数

满表没有 EMPTY。探测最多检查 capacity 个槽位，随后应报告缺失、触发扩容或抛出明确错误。

删除时写回 EMPTY

这会截断其他碰撞 key 的查找链。使用墓碑时，查询越过墓碑，插入记录第一个可复用墓碑。

扩容后复制旧下标

桶下标依赖新容量。必须按新表规则重新插入活跃映射。

把 0.75 当作理论定律

阈值取决于冲突策略、缓存布局、内存预算和延迟目标。0.75 是 Java HashMap 的默认值之一，不是跨语言答案。

只统计活跃元素，忽略墓碑

墓碑多时，失败查询仍会穿过很长的探测链。实现通常需要周期性重建或同时跟踪占用槽位。

调试顺序

1. 给 EMPTY、OCCUPIED 和 DELETED 画出不同符号。
2. 构造三组同起点 key，逐步记录每次探测位置。
3. 删除聚集区首元素，再查询后面的 key。
4. 填满小表，确认缺失查询能够结束。
5. 更新已有 key，确认 size 不变且不会误扩容。
6. 触发一次扩容，逐项核对旧映射。
7. 分析成本时区分普通操作、单次扩容与摊还序列。

动手验证探测链

难度	任务	验收点
基础	手算 A、I、Q 的线性探测	标出起点、聚集区和停止条件
基础	重现错误删除	能解释 EMPTY 为何截断查询
进阶	统计墓碑数量	占用因子过高时执行同容量重建
进阶	实现二次探测	证明探测序列能否覆盖所选容量
工程	压测不同负载	同时记录吞吐、尾延迟和内存

从精确 key 查询继续到有序查询

开放寻址真正难写的是查找路径：EMPTY 代表这条路径从未继续，查询可以停止；DELETED 只代表旧元素离开，后面的碰撞元素仍可能存在。扩容则要按新容量重新放置所有活跃映射。在散列和负载假设成立时，单次重建预期 Θ(n)，固定倍数增长才让整段插入的预期迁移工作保持线性；严重碰撞下重插仍可能平方退化。

把空槽、墓碑和活跃槽位画成探测序列后，查找停止条件就清楚了。哈希表擅长按精确 key 找值，却不负责回答“下一个更大的 key 在哪里”；这类有序查询继续看二叉树。

官方参考

• Princeton Algorithms：哈希表与探测分析
• Python Data Model: hashable keys
• Java SE 17 HashMap
• C++ unordered associative container requirements