flowchart LR K["请求关键字"] --> H["计算散列值"] H --> R["路由到分片"] R --> S1["分片 A"] R --> S2["分片 B"] R --> S3["分片 C"]
第 5 章 散列
Hashing
引入
假设一个系统保存了 100 万个用户名，现在要判断 alice 是否存在。
最直接的方法是从头比较；如果已经排序，可以二分查找。但这两种思路本质上都还在“搜索”。
如果我们能根据 alice 本身计算出一个位置，例如：
alice → hash(alice) → 桶 38127
那么查找就可能从“不断比较”变成“先计算地址，再检查少量位置”。
能不能让关键字（key）自己告诉我们它大概应该存在哪里？
这种“由关键字直接定位”的需求无处不在
类似的问题反复出现在：
- 编程语言字典：通过变量名或对象属性名快速定位值（value）
- 网页缓存：通过网址或缓存关键字判断结果是否已经存在
- 数据库与键值存储：通过关键字访问记录
- 前缀缓存：部分大语言模型服务系统会对词元块或前缀计算散列值，用于判断能否复用已有缓存块
这些系统共享同一个诱人的目标：接近 \(O(1)\) 的按关键字访问。
但“计算地址”马上带来另一个问题：不同关键字可能算到同一个位置。于是本章真正的主线不是“学一个散列函数（hash function）”，而是理解 映射（mapping）、碰撞（collision）、装载因子（load factor）和碰撞解决（collision resolution）如何共同决定散列表的真实性能。
本章路线图
学习目标
完成本章后，应能回答四个问题：
- 为什么散列能把查找从“比较”变成“计算地址”
- 为什么碰撞不可避免
- 开放寻址和拉链法如何处理碰撞
- 装载因子、删除和再散列如何影响真实性能
散列映射
从查找问题开始
同样的数据，目标是查找 24：
\[ [10,\ 11,\ 12,\ 17,\ 24,\ 13] \]
散列表的基本图像
先插入 10，再插入 17。二者都有 \(H(key)=3\)，因此第二次插入必须沿着探测序列继续找空桶。查找 17 时，也必须走同一条路径。
散列函数
演示：取余散列
设：
\[ H(x) = x \bmod 7 \]
哈希的分布规律
这里使用20个桶，500个球
先播放前10次插入观察碰撞，再直接看 500 次插入后的涨落
桶数有限时，多个关键字落入同一桶是概率事件。
多次投球后，不会完美均匀，在均值附近涨落。
装载因子
装载因子：
\[ \alpha = \frac{n}{b} \]
其中 \(n\) 是元素个数，\(b\) 是桶数。
低装载因子：
- 空桶更多
- 探测更短
- 空间开销更大
高装载因子：
- 空间利用率更高
- 碰撞更频繁
- 更需要再散列
散列函数一：取余法
\[ H(key)=key \bmod M \]
常见做法是让 \(M\) 取不超过表长的较大质数。
质数不能消灭碰撞，但能减少某些周期性输入造成的集中分布。
为什么常选质数
散列函数二：平方取中法
平方取中法先计算 \(key^2\)，再取中间若干位作为地址。
\[ \begin{array}{r} \phantom{00000}101101 \\ \times\phantom{000}101101 \\ \hline \phantom{00000}101101 \\ \phantom{000}10110100 \\ \phantom{00}101101000 \\ 10110100000 \\ \hline 11111101001 \end{array} \qquad 11111101001 \Rightarrow 111\color{#1266d6}{1110}1001 \]
取中间 4 位得到 1110。竖式的意义是：平方后的中间位同时受原关键字的高位和低位影响，因此比“只取低位”更不容易继承输入模式。
它适合低位或高位分布不均的场景。核心目的不是平方本身，而是让关键字的多位信息共同影响地址。
散列函数三：乘法散列
\[ H(key)=\lfloor M \cdot ((A \cdot key) \bmod 1) \rfloor \]
其中 \(0<A<1\)。
常见选择之一是 \(A \approx 0.618\)。
它利用小数部分打散输入中的简单模式。
字符串散列：简单求和的问题
private static void requireTableSize(int tableSize) {
if (tableSize <= 0) {
throw new IllegalArgumentException("table size must be positive");
}
}
static int hashSum(String key, int tableSize) {
requireTableSize(tableSize);
int hash = 0;
for (int i = 0; i < key.length(); i++) {
hash += key.charAt(i);
}
return Math.floorMod(hash, tableSize);
}requireTableSize(…) 只验证表长能否作为合法散列模数；失败时立即阻止后续槽位计算。
桶数必须为正，取模才有合法地址空间；这个前置条件一旦成立，后面的散列结果都能安全映射到表内。
hashSum(…) 把整数关键字映射到表槽；最终下标必须始终落在合法表长范围内。
简单求和把所有字符贡献压成一个总数，却完全丢掉字符位置；因此换序字符串会得到同一散列值，短字符串也只会使用很小一段数值空间。
floorMod 只负责把累计值压进合法桶范围；它不能补回前面已经丢失的信息，所以散列质量取决于累计方式本身。
字符串散列：多项式滚动
hashString(…) 把字符串逐字符累积成散列值，使顺序信息参与最终槽位计算。
每读入一个字符都先把已有散列值乘 37，再加入新字符；于是同一个字符出现在不同位置会获得不同权重，字符串顺序真正进入散列结果。
最后的
floorMod 只把已经充分混合的整数映射到桶下标；与简单求和相比，关键改进发生在混合阶段，而不是取模阶段。
散列函数的多维分析
| 维度 | 问题 | 典型风险 |
|---|---|---|
| 均匀性 | 是否把关键字分散到不同桶 | 聚集、长探测链 |
| 速度 | 每次计算是否足够快 | 常数因子过大 |
| 稳定性 | 相同关键字是否稳定映射 | 难以复现或调试 |
| 抗模式 | 能否处理有规律的输入 | 周期性冲突 |
| 安全性 | 是否容易被构造碰撞 | 拒绝服务攻击 |
碰撞
碰撞处理总览
开放寻址：
- 元素仍然放在数组里
- 冲突后继续探测
- 典型方法：线性、二次、双散列
拉链法：
- 桶中挂链表或容器
- 冲突元素留在同一个桶
- 删除更直接
本章重点比较开放寻址和拉链法。
开放寻址
线性探测
若 \(H(key)=d\)，且位置 \(d\) 已被占用，则依次检查：
\[ d+1, d+2,\ldots,m-1,0,1,\ldots,d-1 \]
线性探测的平均查找长度
插入序列：
\[ 10,\ 11,\ 12,\ 17 \]
成功查找比较次数：
\[ 1,\ 1,\ 1,\ 4 \]
这里开始用 平均查找长度（Average Search Length，ASL） 衡量查找代价。对成功查找来说，\(ASL_{succ}\) 就是“把表中每个已存在关键字成功找到时所需的比较/探测次数”取平均。
\[ ASL_{succ}=\frac{7}{4}=1.75 \]
聚集问题
线性探测容易形成连续占用区。不同关键字的探测路径会合并，使之后的插入和查找越来越慢。
线性探测的插入
使用 \(H(k)=k\bmod 11\)，依次插入 80, 40, 65, 24, 58, 35。
线性探测：平均查找长度
平均查找长度用来衡量平均查找代价。这里计算的是成功查找的平均查找长度：对表中每个已经存在的关键字，统计从它的初始桶开始，沿线性探测序列直到找到它一共比较/探测了多少次，再对这些次数取平均。
先列出每个关键字的初始桶：
\[ H(80)=3,\ H(40)=7,\ H(65)=10,\ H(24)=2,\ H(58)=3,\ H(35)=2 \]
线性探测后的成功查找比较次数是：
\[ 1,\ 1,\ 1,\ 1,\ 2,\ 4 \]
因此：
\[ ASL_{succ}=\frac{1+1+1+1+2+4}{6}=\frac{10}{6} \]
这个例子要观察的是：同义词并不只是“落在同一个初始桶的关键字”。线性探测会把相邻冲突链合并，形成更大的聚集区（cluster）。
字符串散列：只看首字母的风险
考虑一个只看首字母的散列函数：
\[ hash(key)=ord(key[0])-ord('A') \]
Burke、Broad、Blum 都落在 B；Attlee、Alton 都落在 A；Ekers、Ederly 都落在 E。
这说明一个重要工程原则：
- 如果散列函数只看输入的一小部分，很多不同关键字会被压到少数桶里。
- 即使桶很多，信息没有被充分使用，也会浪费地址空间。
- 字符串散列要让每个字符的位置都影响结果，这就是多项式滚动散列的动机。
删除与扩容
删除不能简单清空
如果删除探测链中间的元素时直接设为空，后面的元素可能再也查不到。
这里 \(H(11)=11\bmod 7=4\)。查找 11 必须沿着从 4 开始的探测链继续走，不能在 24 原来的位置提前停止。
代码 1：状态与表项定义
EMPTY / OCCUPIED / DELETED 不是实现细节：EMPTY 能证明探测链到此结束，DELETED 只能表示“可复用但不能停止”，两者语义必须分开。
Slot 把散列表槽中的关键字、值与占用状态绑定在一起，避免删除后语义混淆。
每个槽位把业务数据和状态绑在一起；新槽默认
EMPTY，只有 OCCUPIED 状态的关键字和值才算当前有效记录，墓碑位置不会被当作真实元素。
代码 2：类接口
private static <Key> List<Slot<Key>> newTable(int capacity) {
ArrayList<Slot<Key>> result = new ArrayList<>(capacity);
for (int i = 0; i < capacity; i++) {
result.add(new Slot<>());
}
return result;
}
private static int nextPrime(int value) {
int candidate = Math.max(3, value);
if (candidate % 2 == 0) {
candidate++;
}
while (!isPrime(candidate)) {
candidate += 2;
}
return candidate;
}
private static boolean isPrime(int value) {
if (value < 2) {
return false;
}
if (value % 2 == 0) {
return value == 2;
}
for (int divisor = 3; (long) divisor * divisor <= value; divisor += 2) {
if (value % divisor == 0) {
return false;
}
}
return true;
}
OpenAddressingHashTable(int capacity) {
this(capacity, Objects::hashCode);
}
OpenAddressingHashTable(int capacity, ToIntFunction<? super Key> hasher) {
if (capacity < 3) {
throw new IllegalArgumentException("capacity must be at least 3");
}
this.hasher = Objects.requireNonNull(hasher, "hasher");
table = newTable(nextPrime(capacity));
}newTable(…) 建立一个满足初始表示不变量的空结构，供后续更新操作使用。
开放寻址需要每个数组位置都是真实
Slot 对象；初始化整张表后，所有位置都以 EMPTY 开始，探测逻辑才能统一按三态处理。
nextPrime(…) 找到不小于给定值的下一个素数，作为开放定址表扩容后的新容量。
nextPrime 从请求容量向上找质数，并跳过无意义的偶数候选；这里的目标是给探测序列更少的周期性结构，而不是“质数保证无碰撞”。
isPrime(…) 判断候选容量是否为素数；只需检查到平方根即可排除全部非平凡因子。
isPrime 只检查到平方根，并在排除偶数后只试奇数因子；它服务于容量选择，不进入每次散列表查找的热路径。
OpenAddressingHashTable(…) 构造满足该数据结构初始不变量的对象；后续操作都以这个初始状态为前提。
简化构造器只提供默认散列函数，把真正的容量与散列策略初始化集中到一个入口，避免两套构造逻辑产生不同不变量。
OpenAddressingHashTable(…) 构造满足该数据结构初始不变量的对象；后续操作都以这个初始状态为前提。
完整构造器固定同一个散列函数，并把请求容量提升到质数后一次性建表；之后插入、查找、删除必须共享这两项规则，探测路径才一致。
代码 3：散列函数
hash(…) 把任意关键字的散列值规范到主表合法下标；插入、查找和删除都必须从同一个初始桶出发。
把整数散列值映射到初始桶；插入、查找、删除都从这里出发，才能沿同一条探测链找到同一个关键字。
代码 4：寻找槽位
private int findSlot(Key key) {
int firstDeleted = -1;
int start = hash(key);
for (int probe = 0; probe < table.size(); probe++) {
int position = (start + probe) % table.size();
Slot<Key> slot = table.get(position);
if (slot.state == SlotState.EMPTY) {
return firstDeleted >= 0 ? firstDeleted : position;
}
if (slot.state == SlotState.DELETED) {
if (firstDeleted < 0) {
firstDeleted = position;
}
} else if (Objects.equals(slot.key, key)) {
return position;
}
}
return firstDeleted;
}findSlot(…) 按探测序列寻找关键字或第一个可用槽；返回结果决定查找与插入的落点。
从初始桶开始最多探测一整圈，同时只记住遇到的第一个墓碑；这个状态足以同时回答“关键字是否已存在”和“若不存在应放哪里”。
真正的
EMPTY 表示这条探测链从未越过这里，因此关键字不可能藏在后面；若之前见过墓碑就优先复用墓碑，否则当前 EMPTY 就是插入位置。
DELETED 只能作为候选空位，不能终止查找；继续向后若遇到同一关键字的 OCCUPIED 槽，必须返回旧位置更新值，避免产生重复关键字。
整表走完仍未命中时，只能复用先前记录的墓碑；若连墓碑也没有，返回 -1 表示当前表已无可插入槽。
代码 5：插入
boolean insert(Key key, int value) {
int position = findSlot(key);
if (position >= 0 && table.get(position).state == SlotState.OCCUPIED) {
Slot<Key> slot = table.get(position);
slot.key = key;
slot.value = value;
return true;
}
if ((size + 1.0) / table.size() > MAX_LOAD_FACTOR) {
rehash();
}
return insertWithoutResize(key, value);
}
private boolean insertWithoutResize(Key key, int value) {
int position = findSlot(key);
if (position < 0) {
return false;
}
Slot<Key> slot = table.get(position);
if (slot.state != SlotState.OCCUPIED) {
size++;
}
slot.key = key;
slot.value = value;
slot.state = SlotState.OCCUPIED;
return true;
}
private void rehash() {
List<Slot<Key>> oldTable = table;
table = newTable(nextPrime(oldTable.size() * 2));
size = 0;
for (Slot<Key> slot : oldTable) {
if (slot.state == SlotState.OCCUPIED) {
if (!insertWithoutResize(slot.key, slot.value)) {
throw new IllegalStateException("rehash failed");
}
}
}
}insert(…) 把新数据纳入当前结构；操作结束时必须恢复该结构原有的不变量。
先用
findSlot 区分“已有关键字”与“真正新增”：命中已有记录只更新值，不能增加 size，也不需要为一次覆盖操作扩容。
只有新增关键字才预测下一次负载因子；超过阈值先扩容，再重新寻找插入位置，避免高装载率把探测链拖长。
insertWithoutResize(…) 把新数据纳入当前结构；操作结束时必须恢复该结构原有的不变量。
insertWithoutResize 只在当前表写入：复用 EMPTY/DELETED 时增加 size，写入后槽位统一变为 OCCUPIED。
rehash(…) 申请更大表并重新插入所有有效关键字；旧槽下标不能直接复制到新表。
再散列先切换到更大的空表并把
size 清零；旧槽位下标已经失效，不能按原位置复制记录。
只把旧表中的
OCCUPIED 记录重新插入；每个关键字都按新容量重算初始桶，墓碑自然消失，最终 size 也由有效记录重新累计。
代码 6：查找
OptionalInt find(Key key) {
int start = hash(key);
for (int probe = 0; probe < table.size(); probe++) {
int position = (start + probe) % table.size();
Slot<Key> slot = table.get(position);
if (slot.state == SlotState.EMPTY) {
return OptionalInt.empty();
}
if (slot.state == SlotState.OCCUPIED && Objects.equals(slot.key, key)) {
return OptionalInt.of(slot.value);
}
}
return OptionalInt.empty();
}find(…) 根据当前结构的不变量定位目标；未命中时返回失败结果而不破坏结构。
查找必须从与插入相同的初始桶出发，并沿同一线性探测序列前进；否则表中已有关键字也可能变成“不可达”。
只有真正
EMPTY 才证明插入过程从未越过这里，因此可以立即判定不存在；DELETED 不能提供这个结论，必须继续向后探测。
遇到同一关键字的
OCCUPIED 槽就立即返回值；这一刻已经得到唯一目标，不需要继续检查冲突链后面的槽位。
若完整探测一圈仍未命中，说明所有可能位置都已排除；最终返回空结果，而墓碑从未被错误地当成终止证据。
代码 7：删除
boolean erase(Key key) {
int start = hash(key);
for (int probe = 0; probe < table.size(); probe++) {
int position = (start + probe) % table.size();
Slot<Key> slot = table.get(position);
if (slot.state == SlotState.EMPTY) {
return false;
}
if (slot.state == SlotState.OCCUPIED && Objects.equals(slot.key, key)) {
slot.key = null;
slot.state = SlotState.DELETED;
size--;
return true;
}
}
return false;
}erase(…) 从当前结构移除一个目标；操作结束时其余元素仍必须满足原来的表示不变量。
删除必须复用查找的同一初始桶与探测序列；只有这样才能保证“查得到的关键字一定也删得到”。
遇到
EMPTY 就能确定目标不存在；DELETED 或别的 OCCUPIED 关键字都不能提前停止，因为目标可能仍在冲突链后面。
命中后清掉关键字、写成
DELETED 并减少 size；墓碑保留探测链连续性，所以后面的冲突元素仍然可达。
若完整探测一圈仍没有命中，所有可能位置都已经检查过；此时返回
false 才是“目标不存在”的最终结论。
二次探测
二次探测让探测距离按平方变化：
\[ H_i(k)=(H(k)+i^2)\bmod m \]
二次探测的分析
| 维度 | 线性探测 | 二次探测 |
|---|---|---|
| 探测路径 | 连续相邻 | 跳跃式 |
| 主聚集 | 明显 | 缓解 |
| 缓存局部性 | 更好 | 稍弱 |
| 约束 | 简单 | 依赖表长和装载因子 |
二次探测不是“线性探测的无条件升级”，它换来了不同的约束。
双散列
双散列使用第二个散列函数决定步长：
\[ H_i(k)=(H_1(k)+i\cdot H_2(k))\bmod m \]
常见选择：
\[ H_2(k)=R-(k\bmod R) \]
双散列演示
\[ H_1(k)=k\bmod 7,\quad H_2(k)=5-(k\bmod 5),\quad H_i(k)=(H_1(k)+i\cdot H_2(k))\bmod 7 \]
双散列的约束
步长必须能够覆盖表中所有位置。
若 \(\gcd(H_2(k),m)\ne 1\)，探测序列可能只访问表的一部分。
因此表长常取质数，第二个散列函数的步长也要和表长互质。下面的 7 桶例子中，\(R=5\)，每个非零步长都能覆盖全表。
再散列
当装载因子过高时，散列表需要扩容，并对每个有效关键字重新计算新表地址。
代码 8：再散列
rehash(…) 申请更大表并重新插入所有有效关键字；旧槽下标不能直接复制到新表。
扩容先保留旧表，再换成更大的空表并把
size 清零；容量变化后原槽位下标已经没有意义，不能原地搬运。
只重放旧表中的已占用记录，并按新容量重新计算每个关键字的初始桶；墓碑不会被复制，因此再散列同时完成扩容和探测链清理。
拉链法
拉链法
拉链法让每个桶保存一个链表或其他容器。
拉链法：Java 结构
static final class SeparateChainingHashTable<Key> {
private final List<LinkedList<Entry<Key>>> buckets;
private final ToIntFunction<? super Key> hasher;
private int size;
SeparateChainingHashTable(int bucketCount) {
this(bucketCount, Objects::hashCode);
}
SeparateChainingHashTable(int bucketCount, ToIntFunction<? super Key> hasher) {
requireTableSize(bucketCount);
this.hasher = Objects.requireNonNull(hasher, "hasher");
buckets = new ArrayList<>(bucketCount);
for (int i = 0; i < bucketCount; i++) {
buckets.add(new LinkedList<>());
}
}
void put(Key key, int value) {
LinkedList<Entry<Key>> bucket = bucket(key);
ListIterator<Entry<Key>> iterator = bucket.listIterator();
while (iterator.hasNext()) {
Entry<Key> entry = iterator.next();
if (Objects.equals(entry.key(), key)) {
iterator.set(new Entry<>(key, value));
return;
}
}
bucket.addLast(new Entry<>(key, value));
size++;
}
OptionalInt find(Key key) {
for (Entry<Key> entry : bucket(key)) {
if (Objects.equals(entry.key(), key)) {
return OptionalInt.of(entry.value());
}
}
return OptionalInt.empty();
}
boolean erase(Key key) {
ListIterator<Entry<Key>> iterator = bucket(key).listIterator();
while (iterator.hasNext()) {
if (Objects.equals(iterator.next().key(), key)) {
iterator.remove();
size--;
return true;
}
}
return false;
}
int size() {
return size;
}
private LinkedList<Entry<Key>> bucket(Key key) {
int index = Math.floorMod(hasher.applyAsInt(key), buckets.size());
return buckets.get(index);
}
}SeparateChainingHashTable 让同一散列槽的关键字共享一个桶，冲突只在桶内继续处理。
buckets 保存各桶的链，hasher 决定桶位置，size 只统计逻辑记录数。
简化构造器只接收桶数，并把默认散列器
Objects::hashCode 交给完整构造器；两条初始化路径最终建立同一表示。
SeparateChainingHashTable(…) 构造满足该数据结构初始不变量的对象；后续操作都以这个初始状态为前提。
初始化时为每个桶建立独立链表；碰撞只让目标链变长，不会形成跨桶探测链。
put(…) 把新数据纳入当前结构；操作结束时必须恢复该结构原有的不变量。
put 只扫描目标链：同一关键字原地更新，不改变元素数；扫描结束仍未命中才追加新记录，并把 size 加一。
find(…) 根据当前结构的不变量定位目标；未命中时返回失败结果而不破坏结构。
find 的候选集合就是一条桶链；命中直接返回，否则走完这条链即可证明目标不存在，不需要再访问其他桶。
erase(…) 从当前结构移除一个目标；操作结束时其余元素仍必须满足原来的表示不变量。
erase 可以直接从链表移除节点并减少 size；删除不会截断其他关键字的查找路径，所以完全不需要墓碑。
size(…) 只报告当前逻辑规模，不应触发结构遍历或修改。
size() 返回逻辑记录数，而不是桶数或链表节点容量；只有真正新增和成功删除才改变它。
bucket(…) 只读取当前结构中由参数指定的结果，不改变结构状态。
bucket(key) 集中完成“关键字 → 桶”的映射；put、find、erase 共用同一个入口，保证碰撞记录始终落在同一条链上。
多维比较
| 维度 | 开放寻址 | 拉链法 |
|---|---|---|
| 存储结构 | 单个数组 | 桶数组 + 链表或容器 |
| 缓存局部性 | 通常较好 | 节点分散时较差 |
| 删除 | 需要墓碑或重排 | 链表删除直接 |
| 高装载因子 | 性能下降明显 | 可承受 \(\alpha>1\) |
| 迭代稳定性 | 扩容会移动元素 | 扩容也会重分桶 |
| 工程风险 | 探测链变长 | 指针和内存分配开销 |
前沿连接：大规模系统中的散列
散列不仅用于单机查找，也用于分布式系统。
Redis 关键字查找、字典扩容、渐进式再散列
PostgreSQL 散列连接（hash join）、散列聚合（hash aggregate）、索引访问
Kafka 按关键字分区，把消息路由到对应分区
Python dict / set 是语言级核心结构
一致性散列（consistent hashing）、虚拟节点（virtual node）和分片迁移，都是把“关键字到位置”的思想扩展到多台机器上。
前沿连接：安全与可靠性
散列表的平均 \(O(1)\) 依赖输入不是恶意构造。
在公开服务中，如果攻击者能制造大量碰撞，散列表可能退化为 \(O(n)\)。
现代运行时和框架通常会考虑：
- 随机化哈希种子
- 限制单桶长度
- 碰撞过多时切换结构
散列表的可靠性条件
散列表快，是因为它把“查找”转化为“地址计算”。
它可靠，是因为工程实现同时处理了：
- 散列函数质量
- 碰撞策略
- 装载因子
- 删除语义
- 再散列
代码 9：main 函数
main(…) 只负责串联示例输入与数据结构操作，不属于本页要分析的核心算法。
这个入口用一次最小闭环验证表的公共语义：两个关键字经同一插入路径进入结构，再用相同散列与探测规则找回其中一个值。
代码 10：Java 工程入口
HashTableDemo 只是把本章散列操作串成可运行示例，不承担新的散列算法。
HashTableDemo 持有一张长期存在的开放寻址表；连续操作共享同一批槽位和同一套墓碑/负载因子状态，而不是每次调用重新建表。
run(…) 只组织演示流程，把若干数据结构操作按示例顺序执行。
run 依次制造“两个有效记录 → 删除其中一个”的状态变化，用来验证删除后结构仍保持可继续插入和查找的散列表不变量。
工程选型
代码之后：统一分析框架
现在回到算法层面：一张散列表不能只问“平均是不是 \(O(1)\)”，还要同时问六个问题。
| 维度 | 关键问题 | 对应内容 |
|---|---|---|
| 正确性 | 插入、查找、删除是否沿同一条可达路径 | findSlot、find、墓碑 |
| 平均性能 | 随机输入下探测长度多长 | 装载因子、平均查找长度 |
| 最坏性能 | 能否退化到 \(O(n)\) | 聚集、恶意碰撞 |
| 空间成本 | 桶、墓碑、链表节点是否浪费 | 开放寻址与拉链法 |
| 局部性 | 处理器缓存是否友好 | 数组连续性、链表指针跳转 |
| 可维护性 | 扩容、泛型、异常路径是否清楚 | rehash、模板参数 |
开放寻址：三种探测策略比较
线性探测
- 公式最简单
- 缓存局部性最好
- 最容易产生一次聚集（primary clustering）
二次探测
- 跳跃距离逐渐变大
- 缓解一次聚集
- 依赖表长、装载因子和探测公式
双散列
- 步长由第二个散列函数决定
- 探测路径更像“伪随机排列”
- 必须保证步长与表长互质
成功查找与失败查找
成功查找的代价来自“这个关键字插入时走了多远”。
失败查找的代价来自“从初始桶出发，要走到哪里才能确认不存在”。
开放寻址中：
- 遇到已占用槽且关键字不同：继续探测。
- 遇到墓碑槽：继续探测，因为目标可能在墓碑后面。
- 遇到真正的空槽：可以停止，说明插入时不可能越过这个空桶。
因此删除逻辑不是实现细节，而是查找正确性的一部分。
装载因子、再散列与均摊（amortized）成本
一种常见经验是：当表项数超过表长的约 70% 时触发再散列。工程实现中阈值不是唯一答案：
- 开放寻址通常选择较低阈值，例如
0.5到0.85，因为探测长度会随 \(\alpha\) 急剧上升。 - 拉链法可以允许 \(\alpha>1\)，但链长或桶内结构会影响常数。
- 一次再散列（
rehash）是 \(O(n)\)，但如果容量按比例增长，多次插入的均摊成本仍可接近 \(O(1)\)。
要注意：再散列必须对每个关键字重新计算地址，不能把旧桶原样搬过去。
散列函数质量：不仅是“均匀”
好的散列函数至少要考虑：
- 均匀性：不同关键字是否尽量分散到不同桶。
- 速度：计算散列值的常数成本是否过高。
- 稳定性：同一关键字在同一运行策略下是否可复现。
- 抗模式：连续整数、相同前缀字符串、固定步长输入是否会集中。
- 安全性：攻击者是否能构造大量碰撞。
入门例子常直接计算 key mod m，但真实工程中会先把关键字混合成高质量散列值，再映射到桶下标。
拉链法的多维分析
拉链法把“继续找下一个桶”改成“在同一个桶内部查找”。
优点：
- 删除更直接，不需要墓碑。
- 装载因子可以超过 1。
- 表扩容前的性能退化更平滑。
代价：
- 节点分散，缓存局部性往往不如开放寻址。
- 每个节点有额外指针或容器开销。
- 如果单桶过长，仍然会退化，需要扩容、树化或安全哈希。
工程选型：什么时候用哪一种
| 场景 | 更常见选择 | 原因 |
|---|---|---|
| 小对象、读写频繁、追求缓存局部性 | 开放寻址 | 数据连续，常数小 |
| 删除频繁、元素较大、装载因子波动大 | 拉链法 | 删除简单，扩容压力较低 |
| 面向公开输入的服务 | 带随机化或防御策略的实现 | 避免碰撞攻击 |
| 需要稳定迭代顺序 | 普通散列表不一定合适 | 扩容会改变桶位置 |
| 分布式分片 | 一致性散列或最高随机权重散列（rendezvous hashing） | 节点变化时减少迁移 |
本章小结
- 散列查找先计算桶地址，把线性比较问题转化为按关键字直接定位的期望常数时间访问。
- 因为关键字空间通常远大于桶数组，碰撞不是异常，而是必须由设计主动处理的常态。
- 开放寻址在数组内继续探测，拉链法在桶内挂接节点；二者的查找路径和删除语义不同。
- 装载因子决定探测长度或链长；删除必须保持查找可达性，再散列则通过扩容重建地址分布。
本章习题
- 习题 1：给定输入： \(\{10, 17, 24, 11, 18, 25\}\) 散列函数： \(h(x)=x\bmod 7\) 分别画出拉链法、线性探测、二次探测和双散列结果。双散列使用 \(h2(x)=5-(x\bmod 5)\)。
- 习题 2：设散列表为 HT[7]，散列函数： \(H(key)=key\bmod 7\) 用线性开地址法解决冲突，插入关键码序列： \(9, 16, 23, 2, 30, 37\) 求散列表、成功查找的平均查找长度，以及拉链法结构。
- 习题 3：给定输入： \(\{4371,1323,6173,4199,4344,9679,1989\},\quad h(x)=x\bmod 10\) 分别给出拉链法、线性探测、二次探测、双散列结果。双散列使用： \(h2(x)=7-(x\bmod 7)\) 注意这个设置中的一个关键约束：表长是 10，不是质数；双散列步长可能与 10 不互质，因此不一定能访问全表。
- 习题 4：设： \(HT[13],\quad H(key)=key\bmod 13\) 插入序列： \(12,23,45,57,20,03,78,31,15,36\)
延伸阅读
致谢
谢谢
sqlite@nju.edu.cn
https://slab-nju.cn
https://slab-nju.cn
石守谦
