哈希表：碰撞、装载率与扩容

用用户编号查找资料时，问题是“这个键对应什么值”，而不是“第几个元素是什么”。哈希表先把键转换成整数，再据此选出数组中的起始位置，减少逐个比较的工作。Open Data Structures 的哈希表一章介绍了两种常见实现：分离链接法和线性探测。

数据结构地图帮助按操作选型；这里要弄清楚的是：多个键落到同一位置后，查找为什么还能正确，删除为什么不能随手清空，以及“期望常数时间”包含哪些条件。数组和容量的背景见数组与动态数组。

映射、集合与哈希表

映射保存唯一键到值的对应关系，提供按键读取、插入或更新、删除等操作。集合只保存成员，提供加入、删除和成员测试。两者描述的是接口；哈希表描述的是实现。平衡搜索树也能实现映射或集合，但键需要能按一致的全序比较，操作成本和支持的顺序也不同。

CPython 的实现 FAQ说明，CPython 的字典采用可调整大小的哈希表。Python 中怎样处理缺失键、遍历和合并，见字典与按键组织的状态。下面用一个小型映射追踪存储过程；同样的碰撞处理也可用于集合，只需省去值。

哈希值决定起点，相等性决定是不是同一个键

记键的整数哈希值为 $h(k)$，容量为 $m$。一种简单的起始位置计算方式是 $h(k)\bmod m$。两个不同键可能有相同的完整哈希值，也可能只有取模后的起点相同；这两种情况都需要处理碰撞。

Open Data Structures 对哈希码的要求是：相等的键必须得到相同哈希值；不同键得到相同哈希值的概率应尽量小。碰撞时仍需比较键。把哈希值直接当作唯一编号，会把不同键误合并。

Python 的可哈希对象定义要求哈希值在对象生命周期内不变，且相等对象的哈希值一致。用于相等性和哈希计算的字段应保持稳定，否则旧条目可能留在原位置，而新查询从另一位置开始；即使哈希值没变，相等性变化也可能破坏键的唯一性。字符串和由可哈希元素组成的元组是常见选择；列表不可哈希，元组里含列表也不可哈希。自定义对象是否可变，与是否可哈希不能简单画等号；默认按对象身份比较的实例可以是可哈希的。

Python 数据模型还说明，字符串和字节串的哈希默认带随机盐：同一进程内保持稳定，跨进程不保证相同。这有助于抵御刻意制造碰撞的输入，但不能消除所有坏情况，也不能让自定义的恒定哈希函数变得高效。需要持久化的标识应单独保存，不能依赖内置哈希值。

两种存储方式

分离链接法在数组的每个桶里保存一组条目。查找先定位桶，再在桶内比较键；删除找到的条目即可。链表是一种桶内表示，也可以用其他列表结构。

开放寻址中的线性探测把条目放在同一个数组里，每个槽至多一个条目。起点被占用时依次检查后续槽，越过末尾后回到零。查找必须沿着同样的探测顺序进行。

问题	分离链接法	开放寻址（线性探测）
碰撞后放在哪里	同一个桶的列表中	后面的可用槽中
如何查找	比较桶内的键	按探测顺序比较槽内的键
如何删除	从桶内列表移除	本文采用删除标记，保留探测路径
空间与访问	桶内存储有额外开销；链式节点需要间接访问	需要空槽；连续探测有局部性，但可能形成长簇

线性探测中，相邻的已占槽会形成簇。更多键撞到簇内时，簇会继续变长；这称为主聚集。实际表现取决于哈希分布与探测规则，不能只看元素总数。

一次包含删除的碰撞追踪

设容量 $m=8$，整数键采用教学用的 $h(k)=k$。按顺序插入键 5、13、21，值分别为 A、B、C。三个键的起点都是 5。这个刻意制造碰撞的规则便于手算；它没有提供均匀分布的性能条件，也不复现 CPython 的探测算法。

用 EMPTY 表示本轮建表后从未存过条目的槽，用 DEL 表示曾有条目、后来被删除的槽。

操作	检查的槽	结果
插入 5	5	放入槽 5
插入 13	5、6	放入槽 6
插入 21	5、6、7	放入槽 7
删除 13	5、6	槽 6 改为 DEL
查找 21	5、6、7	越过 DEL，在槽 7 找到 C
查找 29	5、6、7、0	槽 0 为 EMPTY，确认不存在
把 21 更新为 C2	5、6、7	更新槽 7，保留槽 6 的标记
插入 29	5、6、7、0	确认不存在后，复用槽 6

若删除 13 时把槽 6 改成 EMPTY，查找 21 会在槽 6 提前结束，错误地报告不存在。删除标记的作用是让查询继续；插入可以记住第一个删除槽，但必须继续寻找已有的相等键，避免把更新误做成重复插入。

下面的 Python 3 程序完整执行这条追踪，并把剩余条目重新插入容量为 16 的表。键是整数，值是字符串；get 用 None 表示缺失。put 返回目标槽、原先是否已有该键、检查过的槽；若键不存在且没有空槽或删除槽可用，则抛出 OverflowError，满表中的已有键仍可更新。重建在结尾显式执行，自动增长策略见“扩容为什么能摊销”。每次探测最多检查整张表一次。

EMPTY = None
DELETED = object()


def locate(table, key):
    first_deleted = None
    visited = []
    for step in range(len(table)):
        index = (key + step) % len(table)
        visited.append(index)
        entry = table[index]
        if entry is EMPTY:
            target = index if first_deleted is None else first_deleted
            return target, False, visited
        if entry is DELETED:
            if first_deleted is None:
                first_deleted = index
        elif entry[0] == key:
            return index, True, visited
    return first_deleted, False, visited


def put(table, key, value):
    index, found, visited = locate(table, key)
    if index is None:
        raise OverflowError("table full")
    table[index] = (key, value)
    return index, found, visited


def get(table, key):
    index, found, visited = locate(table, key)
    return (table[index][1] if found else None), visited


def delete(table, key):
    index, found, visited = locate(table, key)
    if found:
        table[index] = DELETED
    return found, visited


def snapshot(table):
    return ["EMPTY" if x is EMPTY else "DEL" if x is DELETED
            else x[0] for x in table]


table = [EMPTY] * 8
for key, value in [(5, "A"), (13, "B"), (21, "C")]:
    print("put", key, put(table, key, value))
print("slots", snapshot(table))
print("delete", 13, delete(table, 13))
print("slots", snapshot(table))
print("get", 21, get(table, 21))
print("get", 29, get(table, 29))
print("update", 21, put(table, 21, "C2"))
print("put", 29, put(table, 29, "D"))
print("slots", snapshot(table))
larger = [EMPTY] * 16
for entry in table:
    if entry is not EMPTY and entry is not DELETED:
        put(larger, *entry)
print("resized", snapshot(larger))
print("get", 21, get(larger, 21))

输出：

put 5 (5, False, [5])
put 13 (6, False, [5, 6])
put 21 (7, False, [5, 6, 7])
slots ['EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 5, 13, 21]
delete 13 (True, [5, 6])
slots ['EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 5, 'DEL', 21]
get 21 ('C', [5, 6, 7])
get 29 (None, [5, 6, 7, 0])
update 21 (7, True, [5, 6, 7])
put 29 (6, False, [5, 6, 7, 0])
slots ['EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 5, 29, 21]
resized ['EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 5, 21, 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 'EMPTY', 29, 'EMPTY', 'EMPTY']
get 21 ('C2', [5, 6])

容量变成 16 后，5、21、29 的起点分别是 5、5、13。按旧槽顺序重新插入后，它们分别位于 5、6、13；查找 21 只需检查 5、6。扩容要重新计算位置，不能把旧数组原样复制后只补上空槽。

装载率与删除标记

令 $n$ 为有效条目数、$m$ 为桶数或槽数，装载率为 $\alpha=n/m$。分离链接法的平均桶长就是这个比值，且可以大于 1。在适当的随机哈希模型下，查找的期望成本为 $O(1+\alpha)$；保持装载率有界，才能得到期望 $O(1)$。平均桶长较短仍不排除某个桶很长。

开放寻址还要跟踪删除标记。令 $d$ 为删除标记数，$q=n+d$ 为非空槽数。上例删除前 $n=3$，所以 $\alpha=3/8=0.375$；删除后 $n=2$、$d=1$，有效装载率降为 $2/8=0.25$，非空槽比例仍为 $q/m=3/8=0.375$。查找无法在 DEL 停下，因此仅看有效条目数会低估探测负担。

Open Data Structures 的线性探测实现维持 $m\ge 2q$，即至少一半的槽为 EMPTY；其分析先假设哈希位置独立、均匀分布，再讨论适用于线性探测的表格哈希。这个条件下，排除重建成本的查找、插入和删除为期望 $O(1)$。半满是该实现的策略，不是所有哈希表或 Python 字典的通用阈值。

重建只重新插入有效条目，并清掉删除标记。需要更多空间时扩大容量；删除标记过多时，也可以在同一容量重建。本例插入 29 后已无标记；扩到 16 后装载率为 $3/16=0.1875$，而键 5 与 21 仍然碰撞。

扩容为什么能摊销

设另一张表从容量 4 开始，只做新键插入，并在下一次插入会超过半满时把容量翻倍。插入 20 个键时，在插入第 3、5、9、17 个键之前扩容，分别重新插入 2、4、8、16 个已有条目。重插共 $2+4+8+16=30$ 次，加上 20 次新条目写入，总共 50 次条目放置。这不是耗时或探测次数：碰撞、扫描旧表、初始化新数组和哈希计算仍需另外计入。

这些重插数量构成几何级数。对从空表开始的 $N$ 次插入，这种策略的重插数量小于 $2N$；数组初始化和扫描的总规模也随 $N$ 线性增长。在每次放置的期望成本有界时，总工作为期望 $O(N)$，所以插入为期望摊销 $O(1)$。这个推理与动态数组的几何增长相通，但哈希表还要恢复每个键的查找位置。

“期望”描述哈希随机性下的平均成本，“摊销”把偶尔重建的成本分摊到一串操作上，见时间复杂度。在容量与条目数同阶、哈希和比较成本固定、探测期望成本有界时，一次重建为期望 $O(n)$；触发它的插入仍可能有明显的延迟。若所有键都聚集到一起，线性探测的逐个重插甚至可能做平方级探测。

如果支持缩容，应把增长和缩小的阈值拉开，避免反复插入、删除一个键就反复重建。Open Data Structures 的实现超过半数非空槽时重建，有效条目少于容量的八分之一时也重建，再选取至少为 $3n$ 的最小二次幂容量。

常数时间还要付哪些成本

对普通的链接或探测实现，合适的哈希分布、受控的装载率、固定成本的键处理，使查找和不含重建的删除具有期望 $O(1)$ 成本；有合适重建策略的插入及会重建的删除，采用期望摊销界。严重碰撞时，单次查找可能检查 $O(n)$ 个条目；对于开放寻址的全表扫描，更精确地说是 $O(m)$，只有当 $m=O(n)$ 时才能写成 $O(n)$。

键本身的成本也要计算。若哈希键 $k$ 花费 $H(k)$，检查 $p$ 个槽，并对候选键做相等性比较，则可把查找成本写成：

$$T(k)=H(k)+O(p)+\sum_{j\in C}E(k,k_j).$$

这里 $C$ 是实际比较过的候选条目，$E(k,k_j)$ 是一次相等性比较的成本。删除标记也计入 $p$，但不属于 $C$。扫描整个长度为 $L$ 的键来计算哈希需要 $O(L)$ 工作；比较两个长键也可能读到末尾。减少候选条目，不会自动消除这些工作。重复使用已有哈希缓存能减少计算，前提是键稳定且实现确实保存并使用了缓存。

需要顺序或范围时

Python 的映射契约保证 Python 3.7 及之后的字典保留插入顺序。插入顺序与按键排序是两个需求；哈希桶位置本身也不表达大小关系。

主要需求	可选结构	要计入的成本
反复按完整键查找、去重或计数	哈希映射或哈希集合	哈希、碰撞、空余容量与重建
静态数据中找排序位置或范围边界	有序数组加二分搜索	先排序；查询边界需 $O(\log n)$ 次比较，列出 $r$ 个结果另需 $O(r)$；Python bisect提供边界查找
经常更新，同时查询前驱、后继或范围	平衡搜索树	维护平衡；典型范围查询为 $O(\log n+r)$，假设比较成本固定

查“键 21 是否存在”适合哈希表；查“所有位于 10 到 30 之间的键”时，普通哈希表通常需要扫描条目，或另建有序索引。搜索算法地图把这些需求放在同一张表中，便于先决定要维护什么信息，再选查询方式。

我的阅读 · 打开过的笔记会记在当前浏览器里。