一、起源:直接寻址的浪费与顺序查找的低效
查找是最基础的操作。在不引入额外结构的前提下,要让"按键取值"变快,只有两条路:把键直接当作地址,或者按某种顺序逐个比较。
1. 直接寻址表的空间问题
直接寻址的做法是让数组下标等于键本身:
DirectAddress(k) = T[k] // k 是键,T 是数组
这个方案在时间复杂度上无可挑剔——插入、查找、删除都是 O(1),因为没有任何比较与遍历。代价全部落在空间上,而且这个代价由键的取值域决定,而非由实际元素个数决定。
若键是 8 位学号,取值域是 10⁸,直接寻址表就要 10⁸ 个槽位。即便只存 100 个学生,也要按取值域分配空间,其中 99.9999% 的槽位是空的。键的取值域越大、越稀疏,浪费越严重。
只有当键的取值域本身很小(如月份 1 至 12、状态码)且分布稠密时,直接寻址才成立。
2. 顺序查找与二分查找的代价
另一条路是压缩存储、按需比较:
| 结构 | 查找 | 插入 | 删除 | 说明 |
|---|---|---|---|---|
| 无序数组 | O(n) | O(1) 尾部追加 | O(n) 搬移 | 查找必须扫描全部元素 |
| 有序数组 + 二分 | O(log n) | O(n) 搬移 | O(n) 搬移 | 需要元素可比较,且始终维持有序 |
| 链表 | O(n) | O(1) 头插 | O(n) 定位 | 指针追逐,缓存局部性差 |
二分查找把 O(n) 降到 O(log n),但它要求数据有序。维持有序的成本落在写入路径上:每次插入都要搬移元素,每次删除同样如此。也就是说,二分查找是用写入的线性代价换来查找的对数代价。
在"读多写少"的场景这已经足够好,但在读写都频繁的映射场景(缓存、索引、计数表)中,log n 仍是随规模上升的成本,而且一旦数据规模从千级进入百万级,log n 从 10 涨到 20,收益远不如直接做到 O(1)。
3. 用关键字计算位置的思想
散列表(Hash Table,又称哈希表)跳出了"比较"这个框架:
- 直接寻址的问题在于键的取值域远大于实际元素数
- 顺序查找的问题在于必须通过比较逐步缩小范围
散列表的做法是用一个函数把关键字映射到一个有限的地址区间,然后直接访问该地址:
address = H(key) // H 是散列函数,address ∈ [0, m)
T[address] // 存放在长度为 m 的桶数组中
这里的关键变化是:查找不再依赖比较,而是依赖一次计算。元素存放在什么位置由键决定,因此知道了键就等于知道了位置。理想情况下,一次散列计算加一次内存访问就完成查找,时间复杂度是 O(1)。
散列表并不引入新的逻辑结构,它实现的是映射(Map)与集合(Set)这两类抽象数据类型,只是用一种新的存储结构承载它们。作为 ADT 与存储结构的区分,以及映射在 ADT 体系中的位置,见 抽象数据类型(ADT)。
4. 核心矛盾:冲突不可避免
把问题抽象出来:键的取值域记作 U(可能非常大,甚至无限),桶数组的长度固定为 m。映射 H: U → [0, m) 必然是多对一的。
只要 |U| > m,就必然存在两个不同的键 k₁ ≠ k₂ 使得 H(k₁) = H(k₂)。这就是冲突(collision)。它不是实现缺陷,而是"压缩映射"这一前提的数学结果——除非桶数组的长度不小于键的取值域(那就退化成直接寻址了)。
因此散列表设计的全部工作,都围绕两件事展开:
- 让冲突尽量少、尽量均匀——即散列函数的质量问题;
- 让冲突发生后仍能正确工作,且代价可控——即冲突解决问题。
散列函数的均匀性只能改善平均情况,无法消除冲突。攻击者甚至能主动制造冲突(见本章第 6 小节)。这决定了散列表的两个复杂度指标必须分开看:
| 情形 | 复杂度 | 触发条件 |
|---|---|---|
| 平均(期望) | O(1) | 散列均匀,负载因子上界合理 |
| 最坏 | O(n) | 全部键落入同一桶;或恶意构造的同桶键 |
散列表的"快"是一个概率意义上的承诺,而不是绝对保证。理解这一点,后续所有取舍才有依据。
二、原理
1. 散列函数
散列函数 H 的任务是把任意键映射到 [0, m) 内的一个整数下标。
1.1 设计要求
| 要求 | 含义 | 违反后果 |
|---|---|---|
| 确定性 | 同一个键在任何时刻、任何进程内必须得到同一个散列值 | 存入后算出的位置与查找时不一致,元素取不出 |
| 均匀性 | 键域中的键映射到各桶的概率接近相等,且键的微小变化应引起散列值的大幅变化(雪崩) | 桶长分布不均,部分桶退化为长链 |
| 计算成本低 | 散列函数的开销要与查找本身相称,否则省下的比较被计算抵消 | 查找的实际常数变大 |
| 抗碰撞构造 | 在可能被外部输入影响的场景,散列值不能被攻击者预测与构造 | 可被主动制造冲突,退化为 O(n) |
前三条是通用要求,第四条只在"键来自不可信输入"时才需要——此时散列函数的选择从"性能问题"变成"安全问题",见本章第 6 小节。
1.2 常见构造方法
除留余数法。取关键字对某个数 p 的余数:
H(key) = key mod p // p 通常取不超过桶数组长度 m 的最大质数,或 m 本身
p 的取法直接影响质量。实践结论:
- p 取质数时分布最理想,尤其当键本身带有规律(连续整数、等差数列)时。
- p 取合数且含小质因子时分布变差。例如键是十进制整数时,p 取 10 的因子会让末位相同的键全部落同桶。
- p 取 2 的幂时,
key mod p等价于取 key 的低位,高位信息被完全丢弃。键的低位若有规律(如内存地址按 4 G 对齐、订单号以固定前缀结尾),冲突会集中。
乘法散列法。用一个常数 A 做乘法,取小数部分再放大:
H(key) = floor(m × frac(key × A)) // A 取 0 到 1 之间的常数,常用 0.618...(黄金比例)
它的优点是对 m 的取值不敏感,m 取 2 的幂或任意整数都能得到较均匀的分布,代价是多一次浮点乘法与取小数。当桶数组长度必须是 2 的幂(例如为了用位运算定位)而不想依赖键的低位时,这是一个可选方案。
其他经典方法:
| 方法 | 做法 | 适用 |
|---|---|---|
| 数字分析法 | 取键的若干位(选择分布最均匀的位)组成地址 | 键的位数固定且各位分布可预先统计,如身份证号 |
| 折叠法 | 把键切成等长段,各段相加作为地址 | 键位数较多且各位分布均匀 |
| 平方取中法 | 先平方,取中间若干位 | 键的各位都有贡献,中间位受全部位影响 |
1.3 字符串散列
字符串是最常见的键类型,需要一个逐字符累积的散列函数。通用形式是多项式滚动哈希:
H("c₀c₁...cₙ₋₁") = (c₀ × seedⁿ⁻¹ + c₁ × seedⁿ⁻² + ... + cₙ₋₁) mod m
递推实现顺序扫描一遍即可:
h = 0
for each char c in string:
h = h * seed + c
其中的乘数 seed 就是散列函数的名字来源:
| 名称 | seed | 说明 |
|---|---|---|
| BKDR Hash | 131、1313、13131、131313 | 选取一组固定乘数,逐位累积,实现简单、分布良好 |
| DJB2 | 33 | 也写作 h = h * 33 + c,同样可用移位实现 |
| FNV-1a | 先异或再乘(32 位取 16777619) | 位运算混合,雪崩性较好 |
Java String.hashCode | 31 | 见下 |
Java 的 31 进制。String.hashCode 使用 31 作为乘数:
public int hashCode() {
int h = 0;
for (byte v : value) {
h = 31 * h + (v & 0xff);
}
return h;
}
选 31 有两个原因:31 是奇素数,乘奇数不会丢失溢出信息,且能减少规律性冲突;同时 31 * h 可以被 JIT 优化为 (h << 5) - h,把乘法变成一次移位加一次减法。String 的不可变性还保证散列值在对象生命周期内恒定,这是它能作为可靠键的前提。其完整实现与键契约见 Java 集合框架实现原理 第 3.6 至 3.8 节。
随机化散列。Python 的 str、bytes 散列从较早期版本起改用 SipHash,并在进程启动时从操作系统取随机种子。同一字符串在不同进程内的 hash 值不同。这是为防御哈希碰撞攻击而做的取舍,代价是散列值不可跨进程持久化(因此不能把 hash(key) 的结果直接持久化当作键)。这一权衡与本章第 6 小节直接相关。
1.4 容量取 2 的幂与取模的取舍
桶数组长度 m 的取值,是散列函数之外的另一个关键选择。位运算与取模的等价关系是:
当 m = 2^k 时: hash % m == hash & (m - 1)
两者取舍如下:
| 方案 | 定位代价 | 对键低位的要求 | 扩容时的便利性 |
|---|---|---|---|
| m 取 2 的幂 | 一次位与,最快 | 要求低位分布均匀,否则必须加扰动 | 扩容后下标只可能在原下标或原下标 + 旧容量,可用一位判断完成拆分 |
| m 取质数 | 一次除法/取模,较慢 | 对低位规律不敏感,分布更稳 | 每个元素都要重新取模,无法用位判断 |
Java 的 HashMap 选择了 2 的幂,并用扰动函数补回低位质量:
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
把高 16 位异或到低 16 位,让原本被位与丢弃的高位信息参与下标计算。这一步针对的正是"键的低位相同、高位不同"这类规律性冲突。容量取 2 的幂带来的三个具体好处(位运算替代取模、扩容拆分只需判断一个位、避免出现永远无法访问的空桶),以及扰动函数的推导,见 Java 集合框架实现原理 第 3.1 至 3.2 节。
结论:位运算与取模是同一件事的两种代价分配方式。若键的散列值已经足够"随机"(如经过 SipHash、MurmurHash),取 2 的幂是最优选择;若键的散列值来自外部且低位不可控,取质数或先做扰动更稳妥。
1.5 质量对冲突率的影响
在两个前提下,桶长分布可以精确刻画:
- 散列函数把每个键独立、均匀地映射到 m 个桶之一;
- 每个桶的期望元素数为 α = n / m(即负载因子)。
此时某个桶中恰好有 k 个元素的概率服从二项分布,当 n 较大而 α 适中时可近似为泊松分布:
P(k) ≈ (α^k × e^(−α)) / k!
按此估算,在 α = 0.75 时(Java HashMap 的默认负载因子):
| 桶内元素数 k | 概率(近似) |
|---|---|
| 0 | 0.47 |
| 1 | 0.35 |
| 2 | 0.13 |
| 3 | 0.03 |
| 8 | 约 6×10⁻⁸ |
一个桶中聚到 8 个元素的概率在十亿分之一量级。这正是 Java 把"链表长度达到 8"设为树化阈值的依据——在理想散列下这个条件几乎不可能触发,树化只是为非理想散列与恶意构造准备的兜底。
散列质量差会从两个方向破坏这个分布:
- 分布不均。若散列函数把大量键挤入少量桶,这些桶的平均长度远大于 α,查找退化为遍历长链;其余桶长期为空,空间被浪费。
- 桶长方差变大。即使平均桶长不变,方差变大也意味着存在长尾——少数请求的耗时可达成百上千倍于平均值。这类问题在统计平均值上不明显,却会在延迟的 P99 上暴露。
衡量散列质量的实际指标是:空桶比例、平均桶长、最长桶长、桶长方差。这四项在第 3 小节的实测部分给出测量方式。
2. 冲突解决
冲突发生后,必须有一套办法确定"这个键到底放在哪里"。主流方案分两大类:把冲突元素放到桶外面(链地址法),或者继续在桶数组内部另找空位(开放寻址法)。
2.1 链地址法
做法是桶数组的每个槽位存一条链的头部,散列到同一位置的键依次挂在链上。
桶数组 T[0..m-1],每个 T[i] 是一个链表头
查找 key:
index = H(key)
遍历 T[index] 上的链表,用相等比较找到目标节点
基本原理与代价:
- 插入:头插或尾插,O(1)(尾插需要维护尾指针,或退化为 O(链表长))
- 查找:O(1 + α),α 为负载因子,即桶定位 O(1) 加链上平均 α 次比较
- 删除:先定位再断链,O(1 + α)
链地址法允许 α 大于 1,因为元素总数不受桶数量限制。这是它相对开放寻址法最重要的弹性。
链表与红黑树的结合。当散列函数被攻击或被严重破坏时,单条链可能长到使查找退化为 O(n)。Java 8 的 HashMap 的应对是:桶内节点数达到 8 且表容量不小于 64 时,把这条链转成红黑树,把最坏情况从 O(m) 降到 O(log m)。
| 常量 | 值 | 作用 |
|---|---|---|
TREEIFY_THRESHOLD | 8 | 链表节点数达到该值时尝试树化 |
UNTREEIFY_THRESHOLD | 6 | 树节点数降到该值时退化回链表 |
MIN_TREEIFY_CAPACITY | 64 | 允许树化的最小表容量 |
两个细节值得注意:容量小于 64 时,冲突的根因通常是表太短,此时不树化而是执行一次扩容,把元素摊开;退化阈值取 6 而非 8,是为了避免桶长稳定在 8 附近时反复在"链表↔树"之间抖动。完整逻辑见 Java 集合框架实现原理 第 3.4 节。
链结构的其他选择:用动态数组替代链表可改善缓存局部性;用跳表替代链表可把最坏查找降到 O(log m),但常数更大。工程实现中链表加红黑树是最常见的折中。
2.2 开放寻址法
做法是不使用外部链,所有元素都放在桶数组内部。当 H(key) 位置已被占用时,按一个探测序列继续寻找其他位置:
h(key, i) 是第 i 次探测的位置,i = 0, 1, 2, ...
查找 key:依次探测 h(key, 0), h(key, 1), ...,直到命中或遇到空槽
探测序列的构造方式决定了聚集程度与实现复杂度。
线性探测:步长固定为 1。
h(key, i) = (H(key) + i) mod m
- 优点:探测位置在内存中相邻,缓存友好;实现最简单。
- 缺点:一次聚集(primary clustering)。连续的占用区间会像雪球一样扩大——任何散列到该区间内任一位置的键,都要一路探测到区间末尾,于是区间越长,增长越快。这是开放寻址法最严重的性能隐患。
- 成功查找的平均探测次数约为
½ × (1 + 1/(1−α)),失败查找约为½ × (1 + 1/(1−α)²)。α 趋近 1 时后者发散,因此开放寻址法必须把负载因子压在较低水平(常见 0.5 至 0.7)。
平方探测:探测增量按平方增长。
h(key, i) = (H(key) + c₁i + c₂i²) mod m
取 c₁ = c₂ = 1/2 且 m 为 2 的幂时,序列可以覆盖表中所有槽位(这是"表长取 2 的幂"的一个额外收益)。平方探测缓解了线性探测的一次聚集,但仍存在二次聚集:散列到同一初始位置的键,探测序列完全相同,会互相争抢同一批位置。
双重散列:用第二个散列函数决定步长。
h(key, i) = (H₁(key) + i × H₂(key)) mod m
只要 H₂(key) 的结果与 m 互质,探测序列就能覆盖全表。双重散列的分布最接近理想的均匀散列,成功查找平均探测次数约为 (1/α) × ln(1/(1−α)),失败查找约为 1/(1−α)——比线性探测好得多。代价是每个键要算两次散列。
删除与墓碑标记。开放寻址法的删除不能简单地把槽位置空。原因在于探测链的连续性:若在探测链中间挖出一个空槽,后续键的查找会在这个空槽处提前判定"不存在",从而漏掉链上更远处的元素。
解决办法是引入一个区别于"从未使用"的第三种状态——墓碑(tombstone):
| 槽位状态 | 查找时的处理 | 插入时的处理 |
|---|---|---|
| 空(从未使用) | 查找终止,判定键不存在 | 可写入,可终止探测 |
| 墓碑(曾使用后删除) | 继续探测,不终止 | 可写入(复用该位置) |
| 占用 | 比较键,命中则返回 | 继续探测 |
墓碑的副作用是累积:删除越多,表中真正可用的空槽越少,探测链越长,性能随时间缓慢劣化。因此实现中通常记录墓碑数量,当其占比超过阈值时执行一次 rehash,把所有有效元素重新插入,顺带清空墓碑。
2.3 再散列法与公共溢出区
再散列法(多散列函数法)预备一组散列函数 H₁, H₂, ..., Hₖ。先算 H₁(key),若该位置被占用则改用 H₂(key),依次类推。它与开放寻址的探测序列在思路上相近,区别在于每次更换的是整个散列函数而非增量。仅在 H₁ 冲突比例很高时才有收益,实现上不如探测序列简洁。
公共溢出区的做法是把桶数组分为基本表与溢出表两部分:散列到基本表的键正常存放,所有发生冲突的键统一放入溢出表,溢出表内通常顺序查找。它的优点是基本表结构干净、实现简单;缺点是溢出表内部无散列,一旦溢出元素变多就退化为线性查找,且基本表与溢出表两次访问破坏局部性。适用于冲突比例长期很低的场景。
2.4 两种主要方法的对照
| 维度 | 链地址法 | 开放寻址法 |
|---|---|---|
| 元素存放位置 | 桶外的独立节点 | 全部在桶数组内 |
| 缓存友好性 | 差,链上节点在堆中离散分布 | 好,探测位置相邻,一次缓存行可覆盖多个槽 |
| 负载因子容忍度 | 可大于 1,弹性大 | 必须小于 1,通常不超过 0.7 |
| 删除代价 | 断链即可,O(1 + α) | 需要墓碑,且墓碑会累积,需定期 rehash 清理 |
| 指针开销 | 每元素一个 next 指针(含节点对象头) | 无指针,仅桶数组 |
| 额外内存 | 节点对象头与指针,元素越多开销越大 | 桶数组按容量分配,空槽按槽位大小浪费 |
| 最坏情况 | 退化为链表;可引入红黑树兜底 | 探测链拉长;无法用树结构兜底 |
| 哈希质量依赖 | 中等,冲突靠链吸收 | 高,冲突直接放大探测次数 |
| 典型实现 | Java HashMap、Redis 字典、多数语言运行时 | Python 字典、Go 语言 map、C++ absl 部分容器、PostgreSQL 哈希索引 |
选择思路是:若元素数量波动大、删除频繁、或需要承载不可控的键分布,链地址法更稳;若数据量可预估、以查找为主、且对缓存局部性与每元素内存敏感,开放寻址法更优。
3. 负载因子与扩容
3.1 负载因子的含义
负载因子(load factor)定义为元素数量与桶数量的比值:
α = n / m // n 为元素数,m 为桶数组长度
它同时刻画了两个成本:
- α 越大,冲突越频繁,平均查找代价越高;
- α 越小,空桶越多,空间浪费越大。
不同实现对 α 的容忍度不同,这是因为两种冲突解决方法的机制不同:
| 实现 | 默认负载因子 | 定值依据 |
|---|---|---|
Java HashMap | 0.75 | 空间与冲突的折中;泊松分布下桶长达到 8 的概率约 6×10⁻⁸ |
Java HashSet | 0.75 | 底层即 HashMap |
Python dict | 约 2/3 | 开放寻址,需要在探测代价与空间之间收紧 |
Go map | 6.5 / 8 ≈ 0.81 | 桶内可存 8 个键值对,溢出桶单独挂链 |
| Redis 字典 | 1.0(有子进程时不扩容) | 增量式 rehash,可用内存优先 |
Java 的 0.75 可以这样理解:它是"再多放一个元素就扩容"的临界点,取值过高会让冲突率明显上升,取值过低会让 table 中约一半以上槽位长期为空。
3.2 扩容倍数与再散列成本
当 n / m 超过阈值时,必须改变 m。改变 m 意味着所有元素的下标都要重新计算,这一步称为再散列(rehash)。
扩容:m → m'
for each 元素 e in 旧表:
把 e 重新插入到新表中(重新计算 index)
扩容倍数的常见选择:
| 倍数 | 采用者 | 特点 |
|---|---|---|
| 2 倍 | Java HashMap、多数实现 | 容量保持 2 的幂,可用一位判断完成拆分(见第 3 小节) |
| 1.5 倍 | 部分动态表实现 | 空间增长更平缓,但失去 2 的幂的位运算优势 |
| 按需(扩到刚好容纳) | 批量导入路径 | 一次到位,避免多次搬迁 |
扩容的代价由两部分构成:
- 时间代价:一次扩容要遍历旧表全部 n 个元素并重新插入,单次为 O(n)。若容量从 m₀ 逐次翻倍增长到 n,扩容次数为 log₂(n/m₀),每次搬运量随容量增长,累计工作量约为 2n。因此单次插入是均摊 O(1),而不是严格 O(1)。
- 空间代价(内存峰值):扩容瞬间,旧表与新表同时存在。若新容量是旧容量的 2 倍,这段时间内该结构的桶数组占用达到旧表的 3 倍(旧表 m + 新表 2m)。对存量几十万到几百万条目的映射,这个峰值足以让堆进入紧张状态,触发 Full GC 甚至 OOM。
摊还分析的结论可以用"势能"来理解:把扩容时的一次性大额开销,按元素均摊到此前每一次插入上。每次插入多付一点"存储成本"(多占的槽位),在扩容那一刻一次性偿还。总代价被摊平后,插入的均摊复杂度是 O(1)。
这是"容量预分配"最基本的理由:它不是省下几次复制,而是削掉扩容瞬间的内存峰值。按预期元素数 n 计算初始容量时,
HashMap需要的容量是n / 负载因子,再向上取整到 2 的幂。
3.3 缩容策略
删除导致元素数明显下降时,是否需要缩容是另一个取舍:
- 不缩容:实现简单,避免抖动。删除后表长期偏大,空间被浪费。多数语言运行时的默认行为是不自动缩容。
- 缩容:节省内存,但若元素数在阈值附近反复波动,会不断触发"缩容→插入→扩容",即抖动(thrashing)。因此缩容阈值必须明显低于扩容阈值(例如元素数降到容量的 1/8 才缩到一半)。
缩容只有在内存是明确瓶颈、且元素数变化趋势单向时才值得引入。
4. 渐进式 rehash
4.1 一次性扩容的问题
前面的扩容模型是"一次性搬完"。对单线程、延迟不敏感的容器这没有问题,但对单线程处理请求、且表可能很大的系统就是致命缺陷。
以 Redis 为例,命令执行在主线程串行完成。若一个哈希键内有百万级字段,一次扩容就要在主线程内完成百万次重新插入,期间所有其他请求排队等待。表现为一段可观测的服务停顿(毫秒到秒级),且这段时间与表的大小成正比。
一次性扩容的另一个问题是内存:搬完之前旧表不能释放,新旧两份数据同时驻留。
4.2 桶分批迁移
渐进式 rehash(incremental rehash)把"一次搬完"改成"每次搬一点"。核心是同时维护两张表和一个游标:
ht[0] 旧表,正在被迁出
ht[1] 新表,容量为 ht[0] 的两倍
rehashidx 迁移游标,指向 ht[0] 中下一个待迁移的桶下标;-1 表示未在迁移
迁移由每一次访问顺带完成,而不依赖单独的搬运线程:
dictAdd / dictFind / dictDelete 的公共入口:
如果正在 rehash(rehashidx != -1):
执行 _dictRehashStep(),迁移 1 个桶
_dictRehashStep:
迁移 ht[0] 中从 rehashidx 开始的 1 个非空桶:
把该桶整条链拆到 ht[1] 中(按 hash & ht[1].sizemask 计算新下标)
rehashidx++
如果 ht[0] 的所有桶都已迁移:
释放 ht[0],把 ht[1] 提升为 ht[0],重置 rehashidx = -1
除请求期间的逐步推进外,定时任务(Redis 的 serverCron)也会在空闲时以时间片方式主动迁移一批桶,避免在长期无请求的键上迁移停滞。
4.3 迁移期间的读写路由
迁移期间两张表都可能是有效数据的存放处,因此每一次操作都要考虑"元素可能在旧表也可能在新表":
| 操作 | 路由规则 | 原因 |
|---|---|---|
| 查找 | 先查 ht[0],未命中且正在 rehash 时再查 ht[1] | 元素可能尚未迁出(在旧表),也可能已迁出(在新表) |
| 删除 | 两张表都要尝试删除 | 与查找同理,不能只删一边 |
| 插入 | 一律写入 ht[1] | 保证 ht[0] 中的元素只减不增,迁移单调收敛 |
"新增键一律写入新表"是渐进式 rehash 能收敛的关键约束。若新元素继续写入旧表,旧表的元素数不会下降,迁移可能永远追不上新写入。
4.4 迁移期间的内存占用
渐进式 rehash 用时间上的平摊换取了单次低延迟,但并没有减少总的内存占用。相反,由于迁移期可能很长,两张表同时存在的时间也被拉长:
- 正常情况下,桶数组占用在迁移期间是旧表加新表,约为扩容后容量的 1.5 倍;
- 若迁移期间业务写入集中在旧表对应的键上(在 Redis 中表现为持续访问同一批哈希键),迁移会持续推进但内存峰值窗口更长;
- 因此内存规划必须按"新旧两份桶数组同时存在"来估算,而不能只按扩容后的容量估算。
Redis 还引入了"有子进程时不扩容"的约束:当执行 AOF 重写或生成 RDB 时,若允许扩容,写时复制(copy-on-write)会让内存占用放大到最坏 2 倍。这里的判断依据正是"扩容期间内存峰值"这一成本。Redis 的数据结构、编码转换与字典相关行为见 Redis 核心与数据结构 第 2.2 节。
5. 键的相等语义
散列表的定位只解决"桶在哪里",桶内的去重与命中判定仍要依赖键的相等语义。
5.1 hashCode 与 equals 的契约
以 Java 为例,Object 定义了两个必须成对遵守的方法:
public boolean equals(Object obj) // 默认实现是 this == obj
public int hashCode() // 默认实现通常由对象地址推导
契约只有一条强制方向:
equals 相等 ⇒ hashCode 必须相等
hashCode 相等 ⇏ equals 相等(允许冲突)
两个方向的违反后果不对称:
| 情形 | 后果 |
|---|---|
equals 相等但 hashCode 不同 | 两个"逻辑上相同"的键落到不同桶,get 取不到、remove 删不掉、去重失效 |
hashCode 相等但 equals 不同 | 落在同一桶,属于可接受的冲突,只是平均链长变长 |
hashCode 恒返回常量 | 所有元素挤入一个桶,散列表退化为链表 |
这套契约不限于 Java。Python 的 __hash__ 与 __eq__、C# 的 GetHashCode 与 Equals、Go 中可比较类型的相等规则,本质上都是同一个约束:散列决定桶,相等决定桶内命中。两者的分工不能混淆。
5.2 可变对象作键的风险
若键对象在放入容器后被修改,且修改涉及参与散列计算的字段,就会出现"失联":
List<String> key = new ArrayList<>(List.of("a"));
Map<List<String>, String> map = new HashMap<>();
map.put(key, "value"); // 按下标 j 入桶
key.add("b"); // 修改了参与 hashCode 的字段
map.get(key); // null:新哈希算出的下标已不是 j
map.remove(key); // 也删不掉,元素残留在旧桶
元素既取不出也删不掉,只能等到整体清空或重建。因此作键的对象应满足不可变,或至少在作键期间不修改参与散列的状态。
天然满足这一要求的候选:String、包装类(Integer、Long 等)、枚举、record、java.time 系列。需要特别注意的例外是数组:数组的 equals 与 hashCode 继承自 Object,是身份语义,两个内容相同的数组互不相等,用数组作键的结果是每个数组都是独立键。
5.3 自定义键的常见错误
| 错误 | 症状 | 修正 |
|---|---|---|
只重写 equals,不重写 hashCode | 相同逻辑键产生多条记录,get 返回 null | 两个方法必须同时重写,字段集合保持一致 |
hashCode 使用了参与 equals 之外的字段 | 逻辑相等的键散列值不同 | 参与散列与相等的字段集合必须一致 |
equals 不对称或不可传递 | 去重结果依赖比较顺序,偶发不一致 | 按值比较全部业务字段,使用 Objects.equals |
| 键对象可变 | 元素取不出、删不掉 | 冻结参与散列的字段,或改用不可变类型 |
Java 中键契约与实现要点的完整讨论、String 与包装类的散列实现、以及正确实现的双字段写法,见 Java 集合框架实现原理 第 3.6、3.7 与第 8 节。
6. 哈希攻击
6.1 攻击方式
散列表的平均 O(1) 依赖"键的散列值不可预测且分布均匀"。当键来自外部输入且散列函数固定时,这个前提可以被主动破坏。
攻击的基本模型是:攻击者先离线找出大量**散列值相同(或落入同一桶)**的键,再把这些键作为参数提交给服务端。服务端把这些键插入同一个散列表,全部元素挤入少数桶,散列退化为链表:
正常情况:n 个键分布到 m 个桶,单次查找 O(1 + n/m)
攻击情况:n 个恶意键落入 1 个桶,单次查找 O(n),构造 n 个键的总代价 O(n²)
后果是单次请求的 CPU 时间随参数个数平方增长。一个体量不大的请求(例如几 KB 的表单、JSON 对象、HTTP 头部)就能让 CPU 满载,进而影响全部并发请求。这类攻击被称为哈希碰撞攻击(HashDoS),2011 年前后在多个语言运行时中集中暴露。
散列表中可能被触发的入口包括:解析来自外部的 JSON / 表单 / HTTP 头部时的键映射、按用户输入构造的查询缓存键、把外部标识直接作为键的统计结构。
6.2 防护手段
防护的核心是让攻击者无法预测散列值,以及让即使冲突发生也退化的程度有限。
| 手段 | 做法 | 效果与代价 |
|---|---|---|
| 随机种子 | 进程启动时取随机数作为散列函数的种子(SipHash 是典型实现) | 攻击者无法离线构造同桶键;代价是散列值不可跨进程复现,不能持久化 |
| 树化兜底 | 桶内元素达到阈值后转为红黑树(Java HashMap 的做法) | 最坏查找从 O(m) 降到 O(log m);代价是节点内存上升与树化/退化的维护成本 |
| 容量下限 | 树化前先扩容,把冲突的根因(表太短)先解决 | 避免为短表付出树结构的维护成本 |
| 限制请求规模 | 限制 JSON 深度与字段数、表单参数个数、头部总长度 | 把单次请求可构造的冲突元素数压到安全范围,是最外层的兜底 |
| 限流与超时 | 对同类接口做速率限制,对处理耗时设上限 | 降低攻击的放大效应,但不能消除单次请求内的平方复杂度 |
这三层的关系是:随机种子从源头让冲突不可构造,树化把已发生的冲突的代价封顶,限制请求规模把最坏情况的输入规模压小。缺少任意一层,另外两层的压力都会变大。只做长度限制而不做随机种子仍可能被少量构造键拖慢;只做随机种子而不限制请求规模,则在散列函数被攻破或存在实现缺陷时缺少兜底。
7. 一致性哈希与分片
7.1 普通取模在节点变化时的全量迁移问题
当数据量或吞吐超过单机上限时,散列的目标从"桶数组的下标"变成"某个节点的编号":
普通取模分片: node = hash(key) mod N // N 为节点数
这套规则在 N 不变时表现完美:分布均匀,定位 O(1)。问题出在 N 变化时。
假设 N 从 3 变为 4,某个键原本映射到 hash(key) mod 3 = 2,现在要落到 hash(key) mod 4。这个新值可能是 0、1、2、3 中的任何一个,且与旧值没有关系。统计结果是:约 (N−1)/N 的键都要换节点——N 从 3 变为 4 时约 75% 的键需要迁移,从 9 变为 10 时约 90%。缓存场景下这意味着绝大部分缓存同时失效,后续流量全部压向数据库。
迁移范围取决于算法,这一对比在分库分表的算法选型中是首要依据,见 分片与全局唯一 ID 第 2.3 节。
7.2 哈希环与虚拟节点
一致性哈希(consistent hashing)把"取模"的对象从节点数换成固定的环形空间:
1. 把散列值空间组织成一个环,通常取 [0, 2³²)
2. 每个节点用其标识(IP 或名字)散列到环上的一个位置
3. 每个键用同样方式散列到环上的一个位置
4. 键归属于从它所在位置顺时针方向的第一个节点
由此得到的性质是:增加或删除一个节点,只影响它在环上的相邻区间。节点从 N 个增加到 N+1 个时,只有约 1/(N+1) 的键需要迁移,其余键的归属不变。
但仅靠物理节点会产生两个问题:
- 数据倾斜。节点的散列位置是随机的,N 较小时环上的区间长度很不均匀,可能出现某个节点承担远超平均的数据量。
- 节点数很少时更严重。N = 2 时两个节点可能把环切成 90% 与 10% 两段。
解决办法是虚拟节点(virtual node):每个物理节点在环上对应多个虚拟节点(例如每个物理节点生成 100 至 1000 个),键先映射到虚拟节点,再归属到对应的物理节点。
node = 环上顺时针第一个 ≥ hash(key) 的位置对应的虚拟节点
physical_node = virtual_node.owner
虚拟节点数量越多,各区间的长度越接近,倾斜越小;代价是环的元数据变大,且节点增减时需要变动的虚拟节点更多。实践中虚拟节点数取 100 至 300 通常已足够平滑。
副本是另一个正交的维度:同一份数据在环上的多个后继节点各存一份,用于容错与读扩展。副本数与虚拟节点数共同决定"一次节点故障影响的数据比例"。
7.3 应用场景
| 场景 | 用法 | 关注点 |
|---|---|---|
| 分布式缓存客户端分片 | 客户端用一致性哈希把键路由到某个缓存节点 | 节点扩缩容时的命中率下降幅度;虚拟节点数 |
| 缓存中间件的集群分片 | Redis Cluster 使用哈希槽:16384 个固定槽,键归属为 CRC16(key) mod 16384 | 槽是迁移单位;扩缩容只搬部分槽,等价于"固定逻辑分片 + 映射",见下 |
| 分库分表 | 一致性哈希或预分片加映射决定数据落在哪个库表 | 分片键的选择、跨片查询代价 |
| 负载均衡 | 按请求标识的散列把同一会话导向同一后端 | 后端扩缩容时的会话漂移 |
| 有状态服务的请求粘滞 | 同上,用于本地缓存亲和 | 节点故障时的重路由策略 |
Redis Cluster 的哈希槽方案值得单独说明:它并不使用一致性哈希环,而是预分片加映射的思路——先把散列值空间固定切分为 16384 个槽,键先映射到槽,槽再分配给节点。节点变化时只需迁移槽,而不是重算键到节点的映射。这与前面提到的"固定逻辑分片数、物理实例数可变"是同一思想。
键名中的哈希标签({} 之间的内容参与槽计算)则用于让多个键落在同一槽以便参与多键操作,代价是标签基数低时会造成负载倾斜。槽与哈希标签的机制、重定向与迁移流程,见 Redis 高可用与集群 第 2.3 节;分片键选择、分片算法的对照表与数据倾斜的排查,见 分片与全局唯一 ID 第 2.2 至 2.3 节。
一致性哈希与哈希槽解决的是同一类问题的两个层次:一致性哈希在算法层把节点变化的影响限制在相邻区间;哈希槽在架构层用固定分片数把映射关系与物理节点解耦,使扩容变成"迁移槽"这一可控操作。
三、实现
1. 结构定义与基本操作
1.1 链地址法的结构
public class ChainedHashTable<K, V> {
private static class Node<K, V> {
final int hash; // 缓存散列值,桶内比较时先比 hash 再比 equals
final K key;
V value;
Node<K, V> next;
Node(int hash, K key, V value, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
}
private Node<K, V>[] table;
private int size;
private int threshold; // 触发扩容的元素数 = 容量 × 负载因子
private static final float LOAD_FACTOR = 0.75f;
// 扰动:把高位异或到低位,弥补"容量取 2 的幂"时高位被丢弃的问题
static int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
// 容量为 2 的幂时用位与代替取模
static int indexFor(int hash, int capacity) {
return hash & (capacity - 1);
}
}
两个字段的职责需要区分清楚:size 是逻辑元素数,threshold 是扩容阈值。桶数组的槽位数(table.length)与 size 是独立概念,前者决定冲突率,后者决定内存占用。
1.2 插入与查找
public V put(K key, V value) {
if (table == null) {
table = resize(); // 首次插入时再分配,避免空表占内存
}
int h = hash(key);
int idx = indexFor(h, table.length);
// 桶内查找:先比 hash 快速排除,再用 == 与 equals 判断键相等
for (Node<K, V> p = table[idx]; p != null; p = p.next) {
if (p.hash == h && (p.key == key || (key != null && key.equals(p.key)))) {
V old = p.value;
p.value = value; // 键已存在:只替换值,元素数不变
return old;
}
}
table[idx] = new Node<>(h, key, value, table[idx]); // 头插,单线程下 O(1)
if (++size > threshold) {
resize();
}
return null;
}
public V get(Object key) {
if (table == null) {
return null;
}
int h = hash(key);
for (Node<K, V> p = table[indexFor(h, table.length)]; p != null; p = p.next) {
if (p.hash == h && (p.key == key || (key != null && key.equals(p.key)))) {
return p.value;
}
}
return null;
}
查找路径上有两处优化值得注意:
- 先比较
hash再比较equals。hash是 int 比较,equals可能涉及多字段逐一对比。先用 int 比较排除绝大多数不匹配的节点,能显著减少equals调用次数。 - 先比较引用再调用
equals(p.key == key ||)。同一个对象的引用比较比方法调用便宜,且能避免equals自身处理自反性的开销。
1.3 删除
public V remove(Object key) {
if (table == null) {
return null;
}
int h = hash(key);
int idx = indexFor(h, table.length);
Node<K, V> prev = null;
for (Node<K, V> p = table[idx]; p != null; prev = p, p = p.next) {
if (p.hash == h && (p.key == key || (key != null && key.equals(p.key)))) {
if (prev == null) {
table[idx] = p.next; // 删除的是头节点
} else {
prev.next = p.next; // 删除的是中间或尾节点
}
size--;
return p.value;
}
}
return null;
}
链地址法的删除只需断链,没有墓碑问题。开放寻址法的删除则必须保留探测链的连续性:
_TOMBSTONE = object()
class OpenAddressingMap:
"""线性探测实现;容量取 2 的幂,负载因子上限 0.5。"""
def __init__(self, capacity=16, load_factor=0.5):
self._keys = [None] * capacity
self._values = [None] * capacity
self._size = 0
self._load_factor = load_factor
def _insert_raw(self, key, value):
cap = len(self._keys)
idx = hash(key) % cap
first_tombstone = -1
while True:
k = self._keys[idx]
if k is None:
# 真正空槽:优先复用之前遇到的第一个墓碑,减少墓碑累积
target = first_tombstone if first_tombstone != -1 else idx
self._keys[target] = key
self._values[target] = value
self._size += 1
return
if k is _TOMBSTONE:
if first_tombstone == -1:
first_tombstone = idx
elif k == key:
self._values[idx] = value # 键已存在,替换值
return
idx = (idx + 1) % cap # 线性探测:步长为 1
def put(self, key, value):
if (self._size + 1) / len(self._keys) > self._load_factor:
self._resize(len(self._keys) * 2)
self._insert_raw(key, value)
def get(self, key, default=None):
cap = len(self._keys)
idx = hash(key) % cap
for _ in range(cap):
k = self._keys[idx]
if k is None: # 空槽终止查找
return default
if k is not _TOMBSTONE and k == key:
return self._values[idx]
idx = (idx + 1) % cap # 墓碑不能终止查找,必须继续探测
return default
def remove(self, key):
cap = len(self._keys)
idx = hash(key) % cap
for _ in range(cap):
k = self._keys[idx]
if k is None:
return None
if k is not _TOMBSTONE and k == key:
value = self._values[idx]
self._keys[idx] = _TOMBSTONE # 写入墓碑,保持探测链连续
self._values[idx] = None
self._size -= 1
return value
idx = (idx + 1) % cap
return None
def _resize(self, new_capacity):
old_keys, old_values = self._keys, self._values
self._keys = [None] * new_capacity
self._values = [None] * new_capacity
self._size = 0
for key, value in zip(old_keys, old_values):
if key is not None and key is not _TOMBSTONE:
self._insert_raw(key, value) # 重插有效元素,墓碑被自然清除
这段实现里删除与查找的差异是最容易写错的地方:get 遇到墓碑必须继续探测,只有遇到真正的空槽才能判定不存在;remove 必须写墓碑而不是写空槽,否则会把探测链切断。
1.4 迭代与顺序性
散列表的遍历通常按桶顺序扫描,桶内再沿链或按探测顺序访问。由此得出三点关于顺序的结论:
- 散列表不承诺任何元素顺序。它实现的是映射语义,不是有序映射。
- 遍历顺序不是稳定的契约。即使某次实现的输出看起来有规律(例如恰好按插入顺序),也不构成接口保证。
- 遍历顺序会随以下因素变化:表容量(扩容会改变下标)、散列函数实现(不同语言版本可能调整)、插入与删除历史(墓碑位置与桶内链序)。同一份数据在不同进程、不同版本、不同扩容历史下遍历顺序都可能不同。
这条的性质与"依赖 HashMap 迭代顺序"完全一致:本地测试稳定、上线后顺序变化,是典型的表现。需要稳定顺序时应改用保持插入顺序或按序维护的结构(对应到 Java 是 LinkedHashMap 与 TreeMap,见 Java 集合框架实现原理 第 4 与第 5 节)。
2. 扩容实现要点
2.1 触发条件
触发条件必须写成一个可判定的表达式,而不是"觉得需要扩容时":
if (size + 1 > capacity × load_factor) → 扩容
需要注意两点:
- 先判断再插入还是先插入再判断。若先插入后判断,
size会短暂超过阈值但不会漏判;若先判断后插入,要按size + 1判断,否则插入后可能正好越界。两种写法等价,但必须统一。 - 树化与扩容的优先级。当桶内冲突严重而表容量很小时,扩容比树化更划算(元素被摊开,冲突自然减少)。Java 的
treeifyBin在容量小于MIN_TREEIFY_CAPACITY时执行扩容而非树化,正是这个判断。
2.2 再散列的写法
再散列有两种实现路径,复杂度相同,效率差别很大。
路径一:逐个重新计算下标。通用、适用于任意容量变化:
for j in [0, oldCapacity):
for each 节点 e in 旧表[j]:
新表[indexFor(e.hash, newCapacity)].push(e)
路径二:2 的幂容量下按位拆分。容量翻倍时,newCapacity − 1 相比 oldCapacity − 1 只多出一个高位 1:
旧容量 oldCap = 16,oldCap - 1 = 0000 1111
新容量 newCap = 32,newCap - 1 = 0001 1111
↑ 多出的这一位决定去向
e.hash & oldCap == 0 → 新下标 = 旧下标 j
e.hash & oldCap != 0 → 新下标 = 旧下标 + oldCap
因此只需一次位判断,就能把旧桶内的整条链拆成两条子链,且不必重新计算 hashCode():
Node<K, V> loHead = null, loTail = null; // 留在原下标 j
Node<K, V> hiHead = null, hiTail = null; // 迁到 j + oldCap
for (Node<K, V> e = oldTab[j]; e != null; e = e.next) {
if ((e.hash & oldCap) == 0) {
if (loTail == null) loHead = e; else loTail.next = e;
loTail = e;
} else {
if (hiTail == null) hiHead = e; else hiTail.next = e;
hiTail = e;
}
}
if (loTail != null) { loTail.next = null; newTab[j] = loHead; }
if (hiTail != null) { hiTail.next = null; newTab[j + oldCap] = hiHead; }
这是"容量取 2 的幂"在扩容路径上的直接回报:把 O(n) 次散列计算与 O(n) 次插入,降为 O(n) 次位判断与 O(n) 次指针重接。
2.3 迁移过程中的并发与一致性
扩容是散列表最容易出问题的地方,因为它涉及"读旧表 + 写新表 + 改引用"三个步骤,而引用替换不是原子的(在非并发实现中甚至没有同步)。
| 问题 | 成因 | 处理方式 |
|---|---|---|
| 并发扩容形成环形链表 | 头插法在并发搬运同一条链时可能让节点指向自身,后续 get 陷入死循环 | 改用尾插法保持相对顺序,消除成环条件 |
| 并发写入丢数据 | 两个线程同时写同一空桶,后写覆盖先写 | 非并发实现不承诺线程安全,需外部加锁 |
扩容期间读到 null | 新表已发布但部分桶尚未搬迁 | 先迁移后发布,或使用并发实现 |
扩容期间 size 计数错误 | 计数更新与结构调整非原子 | 使用原子计数或分桶锁 |
需要强调:消除死循环不等于线程安全。JDK 8 把 HashMap 的扩容从 JDK 7 的头插改为尾插,消除了环形链表这一最恶性的后果,但并发 put 仍会丢数据、size 计数仍可能错误、扩容期间仍可能读到 null。完整对比见 Java 集合框架实现原理 第 3.5 节。
并发实现的做法与之不同。ConcurrentHashMap 在扩容时允许多个线程协作搬运:每个线程领取一段桶区间(stride)进行迁移,迁移完成的桶用转发节点(ForwardingNode)标记,其他线程遇到转发节点时先协助迁移再访问。这样把一次扩容的暂停时间按线程数摊分,同时保证读操作在扩容期间仍能正确路由。这也是"渐进式 rehash 的单机版本"——把一次大停顿拆成多个小停顿。
2.4 缩容策略
若引入缩容,需要遵守两条约束:
- 缩容阈值必须明显低于扩容阈值。若两者接近(例如容量 c 时
size > 0.75c扩容、size < 0.7c缩容),元素数在阈值附近波动会反复扩容缩容,每次都要全量再散列。 - 缩容必须整表重建。桶数组无法原地缩小,缩容只能重新分配一个更小的数组并重插全部元素,代价与扩容相同。
常见取值是缩到"元素数低于容量的 1/8 时容量减半"。多数语言的内置实现默认不缩容,把内存回收交给业务侧显式重建。
3. 复杂度与实测
3.1 复杂度
| 操作 | 平均(期望) | 最坏 | 说明 |
|---|---|---|---|
| 查找 | O(1) | O(n) | 最坏发生在全部键同桶;树化实现下最坏为 O(log n) |
| 插入 | 均摊 O(1) | O(n) | 均摊中的常数来自扩容摊还;最坏包含一次 O(n) 扩容 |
| 删除 | O(1) | O(n) | 开放寻址法还需考虑墓碑累积带来的探测变长 |
| 遍历 | O(n + m) | O(n + m) | 需扫描全部桶,含空桶;m 为容量而非元素数 |
三点必须写清楚:
- 表中的 O(1) 是平均值,前提是散列均匀且负载因子上界合理。这不是"任意情况下都快"。
- 遍历复杂度中的
m提醒了空桶的成本:负载因子越低,扫描空桶的开销占比越高。元素稀疏时遍历可能比按元素数预期慢很多。 - 开放寻址法的最坏情况比链地址法差。链地址法可以用树化把最坏降到 O(log n),开放寻址法的探测链长度无法用树结构压缩。
3.2 哈希质量与冲突率的测量
评价一个散列函数或一次运行时的散列质量,可直接统计桶长分布:
def bucket_stats(keys, capacity):
buckets = [0] * capacity
for key in keys:
buckets[hash(key) % capacity] += 1
used = [c for c in buckets if c > 0]
return {
"capacity": capacity,
"keys": len(keys),
"load_factor": len(keys) / capacity,
"empty_ratio": (capacity - len(used)) / capacity, # 空桶比例
"avg_len": sum(buckets) / capacity, # 平均桶长
"max_len": max(buckets), # 最长桶
"avg_len_used": sum(used) / len(used) if used else 0, # 非空桶平均长
}
判读方式:
| 指标 | 健康值 | 异常含义 |
|---|---|---|
| 空桶比例 | 接近 e^(−α)(α = 0.75 时约 0.47) | 显著偏离说明散列分布不均 |
| 最长桶 | 远小于元素数,且在负载因子 0.75 下出现长桶的概率极低 | 出现长桶指向散列函数的规律性缺陷或恶意键 |
| 非空桶平均长 | 接近 α | 远高于 α 说明局部聚集 |
| 桶长方差 | 小 | 方差大意味着延迟存在长尾,平均值会掩盖问题 |
还可以做卡方检验:把观测到的桶长分布与理论均匀分布对比,判断偏差是否显著。若能获得多个候选散列函数的统计,该检验可以量化选择。
对开放寻址法,更直接的指标是平均探测次数:在给定的 α 下,成功与失败查找的探测次数应落在前面给出的理论公式附近。若实测值明显高于公式值,说明散列分布不均或墓碑积累过多。
3.3 在不同数据规模与键类型下的实测
散列性能对键类型与哈希质量高度敏感。同样的操作,Integer 键与随机字符串键、与低位规律明显的键,耗时可能相差数倍。因此实测必须覆盖:
| 维度 | 取值建议 | 观察点 |
|---|---|---|
| 数据规模 | 10³、10⁴、10⁵、10⁶、10⁷ | 单次操作的耗时应基本平坦;明显上升说明扩容摩擦或缓存失效 |
| 键类型 | int、定长字符串、UUID、长文本、自定义对象 | 装箱成本、hashCode 成本、比较成本 |
| 散列质量 | 正常键、低位规律键、故意同桶的键 | 验证最坏情况的退化幅度与兜底机制是否生效 |
| 负载因子 | 0.5、0.75、0.9 | 验证冲突率随负载因子的上升幅度 |
| 容量预分配 | 预设容量 vs 不预设 | 验证扩容次数与内存峰值 |
测量本身有大量陷阱。JIT 的即时优化、死代码消除、常量折叠会让"看起来在测"的代码实际什么都没执行;手工计时的精度、GC 抖动、预热不足都会污染结果。微基准必须使用 JMH 这类专门框架,它通过多轮预热、测量模式选择、黑洞消费返回值等机制消除上述干扰。JMH 的使用方式、常见误用与结果判读,见 JMH 微基准测试。
下面是一个针对键类型的对比基准骨架:
@State(Scope.Benchmark)
public class HashLookupBenchmark {
@Param({"1000", "100000", "1000000"})
public int size;
private int[] intKeys;
private String[] stringKeys;
private Map<Integer, Integer> intMap;
private Map<String, Integer> stringMap;
@Setup(Level.Trial)
public void setup() {
intMap = new HashMap<>(size * 4 / 3 + 1); // 按负载因子反推容量,消除扩容干扰
stringMap = new HashMap<>(size * 4 / 3 + 1);
intKeys = new int[size];
stringKeys = new String[size];
for (int i = 0; i < size; i++) {
intKeys[i] = i;
stringKeys[i] = "key-" + i;
intMap.put(i, i);
stringMap.put(stringKeys[i], i);
}
}
@Benchmark
public Integer lookupInt(Blackhole bh, ThreadLocalRandom random) {
return intMap.get(intKeys[random.nextInt(size)]); // 返回值交给 Blackhole 消费
}
@Benchmark
public Integer lookupString(Blackhole bh, ThreadLocalRandom random) {
return stringMap.get(stringKeys[random.nextInt(size)]);
}
}
判读这类结果时,需要区分三种成本:散列计算成本(字符串逐字符累积远高于 int 直接返回)、相等比较成本、内存访问成本(桶数组与键值对象在堆上的分布导致缓存命中率差异)。只有把这三项分开估算,才能解释为何"同为 O(1)"的两种键实际操作耗时可能相差数倍。
4. 工程应用
散列表是使用最广的数据结构之一,下述场景几乎都是它的直接应用。
4.1 语言内置字典与映射
各语言的字典、映射、集合类型基本都是散列表:
| 语言 | 类型 | 冲突解决 | 备注 |
|---|---|---|---|
| Java | HashMap / HashSet | 链地址法 + 红黑树 | 容量取 2 的幂,负载因子 0.75 |
| Python | dict / set | 开放寻址法 | 散列带随机种子,抗碰撞攻击 |
| Go | map | 桶内数组 + 溢出桶 | 每个桶容纳 8 个键值对 |
| C++ | unordered_map / unordered_set | 链地址法 | 桶数通常取质数 |
| Redis | 字典(hash 结构的基础编码之一) | 链地址法 + 渐进式 rehash | 见 4.1 与 4.3 |
Java 中 HashMap、HashSet、LinkedHashMap、LinkedHashSet、ConcurrentHashMap 的组织关系与实现差异,见 Java 集合框架实现原理 第 3 至第 5 节。
4.2 缓存键设计与哈希槽
缓存的核心是"键 → 值"的映射,键的设计直接决定命中率与分布:
- 键必须覆盖全部影响值的输入。键若缺少某个维度,不同输入会命中同一份缓存,返回错误结果。
- 键的可读性。由多字段拼成的键应保留字段名(如
user:1001:profile),便于排查与按前缀清理。 - 键的基数。基数过低会造成键热点(所有请求争抢同一份缓存),基数过高会让缓存命中率下降且内存占用上升。
- 键的散列分布。若键以高相似度前缀为主(如带时间戳的键、带自增 ID 的键),散列函数对相似前缀的区分能力决定分片是否均匀。
在分片缓存中,键还需要携带路由信息。当多个键必须落在同一分片以参与原子操作时,可通过哈希标签把一个片段固定进哈希计算。哈希标签的机制、代价(标签基数低会导致倾斜)与设计原则见 Redis 高可用与集群 第 2.3.4 节。
4.3 去重与计数
- 去重:
HashSet的语义就是"元素唯一",判断元素是否出现过是 O(1)。大规模去重时,集合本身的内存会成为瓶颈——每个元素都要存一份,此时需要评估是否可以用近似结构(如布隆过滤器)换取内存。 - 计数:
HashMap<Key, Integer>是最直接的词频统计与维度计数方式。热点路径上可用ConcurrentHashMap.merge或computeIfAbsent保证复合操作的原子性,避免"先判断再写入"的竞态。 - 基数估算:只需知道"有多少个不同的值"、不需要枚举具体值时,基数估算结构(如 Redis 的 HyperLogLog)可以用固定内存近似给出结果,代价是存在误差且无法判断单个元素是否存在。Redis 各类结构在去重、计数与基数估算上的分工见 Redis 核心与数据结构 第 2.2.2 与 2.2.4 节。
4.4 分布式缓存分片
单机缓存受单机内存容量限制,超过后必须分片。分片算法决定了扩缩容时的数据迁移量:
| 算法 | 分布均匀性 | 扩缩容搬迁量 | 说明 |
|---|---|---|---|
| 普通取模 | 均匀 | 接近全量 | 实现最简单,节点数变化时代价最高 |
| 一致性哈希 | 均匀(虚拟节点调优后) | 约 1/n | 需要维护环与虚拟节点 |
| 哈希槽(固定逻辑分片) | 均匀 | 只搬迁被调整映射的槽 | 把分片数与物理节点解耦 |
选择依据是扩容搬迁范围:取模分片在节点数变化时接近全量搬迁,一致性哈希与哈希槽只搬迁受影响部分。这一对比与分库分表算法选型中的结论一致,见 分片与全局唯一 ID 第 2.3 节。
4.5 数据库哈希索引与哈希连接
散列表在数据库内部也有直接应用:
- 哈希索引。把索引键散列后直接定位记录,等值查询为 O(1),但不支持范围查询与排序,因为散列破坏了顺序。因此哈希索引通常只用于纯等值场景(如内存数据库或部分存储引擎的辅助索引)。支持范围与排序的 B+ 树索引与哈希索引的定位差异,见 MySQL 索引与执行计划。
- 哈希连接。把小表按连接键构建成内存哈希表,再扫描大表逐行探测,把嵌套循环的 O(n×m) 降为 O(n + m)。这是数据库执行器中最基础的连接算法之一。它依赖一个完整假设:小表能装进内存。
5. 常见问题与排查
| 现象 | 可能原因 | 验证方式 | 处理 |
|---|---|---|---|
| 单次查找耗时随元素数明显上升 | 散列分布不均,存在长桶 | 打印桶长分布,检查最长桶与空桶比例 | 更换散列函数或增加扰动,检查键的低位规律 |
| 写入大量同前缀键后性能骤降 | 键的散列值集中,或散列函数高位未参与下标计算 | 统计最长桶长 | 引入随机种子或加强扰动;服务端限制单请求键数量 |
get 返回 null 但键"明明插入过" | 键对象被修改,导致散列值变化,换了桶 | 打印插入前后键的散列值做对比 | 改用不可变键;冻结参与散列的字段 |
| 去重失效,出现逻辑重复元素 | equals 与 hashCode 未同时重写或字段集合不一致 | 断言两个疑似重复元素的 equals 与散列值 | 同时重写两个方法,字段集合保持一致 |
| 扩容时出现延迟毛刺 | 一次性扩容,单次停顿与表大小成正比 | 观察延迟曲线与扩容日志的时间相关性 | 容量预分配;采用渐进式 rehash 或分片化 |
| 扩容时内存占用骤增甚至 OOM | 新旧桶数组同时存在,峰值达到旧表容量的数倍 | 观察 GC 日志与堆占用曲线 | 预设容量;按峰值而非稳态估算内存 |
| 上线后遍历顺序变化导致逻辑失败 | 把遍历顺序当成了稳定契约 | 检查是否存在依赖顺序的逻辑或断言 | 改用保持顺序的结构;测试不断言顺序 |
| 删除后查找越来越慢(开放寻址法) | 墓碑累积,可用空槽减少,探测链变长 | 统计墓碑占比与平均探测次数 | 墓碑占比超阈值时执行一次 rehash 重建 |
| 分片后节点负载不均 | 分片键基数不足、取值分布集中,或虚拟节点数太少 | 对比各节点的键数量与资源使用率 | 提高分片键基数、对热点取值二次散列、增加虚拟节点 |
| 节点扩缩容后缓存命中率断崖下降 | 使用普通取模分片,键归属几乎全变 | 观察扩容前后的缓存命中率曲线 | 改用一致性哈希或哈希槽方案 |
排查的通用顺序是:先确认是"散列分布问题"还是"键语义问题",再决定方向。分布问题的证据是桶长统计异常(长桶、空桶比例偏离),键语义问题的证据是散列值在插入与查找之间发生了变化。两者表现相似(都是"查找变慢或找不到"),但处理方式完全不同。
6. 选型与检查清单
6.1 何时用散列表,何时不用
| 需求 | 推荐 | 理由 |
|---|---|---|
| 等值查找、插入、删除,无需顺序 | 散列表 | 平均 O(1),没有更快的通用选择 |
| 需要按键排序输出或范围查询 | 有序结构(红黑树、跳表、B+ 树) | 散列破坏了顺序,无法支持区间与相邻查询 |
| 需要稳定的遍历顺序 | 保持插入顺序的映射 / 有序映射 | 散列表不承诺顺序 |
| 判断元素"是否存在"且能接受极小误判 | 布隆过滤器 | 用固定内存换取存在性判断,代价是有假阳性且不能删除元素 |
| 只需基数估算 | 基数估算结构(如 HyperLogLog) | 用固定内存近似计数,不保存原始元素 |
| 需要按优先级取出元素 | 堆 | 散列没有优先级语义 |
| 数据量很小(几十条以内) | 顺序查找或有序数组 | 散列的计算与内存开销可能超过线性查找的收益 |
需要区分"需要精确成员判断"与"需要近似成员判断":布隆过滤器与基数估算结构都是以可控的误差换取数量级更低的内存,一旦业务需要精确结果或需要删除元素,就必须回到散列表或有序结构。适用边界与误判率的量化方式,需要在具体实现中按元素数量与可接受误差评估。
6.2 容量与负载因子的设定
| 检查项 | 做法 |
|---|---|
| 元素数可预估 | 按 元素数 / 负载因子 计算容量并向上取整(容量为 2 的幂时向上取到 2 的幂) |
| 元素数不可预估 | 给出量级上界作为初始容量;或先批量收集,再一次性构建 |
| 内存敏感 | 提高负载因子,接受冲突率上升;或改用开放寻址的实现以省去指针开销 |
| 延迟敏感 | 降低负载因子,压低最长桶与探测次数,换取更稳的 P99 |
| 键来自不可信输入 | 使用带随机种子的散列;限制单请求的键数量;确认实现有退化兜底 |
| 存在并发写入 | 使用并发实现或外部加锁,注意复合操作需要原子方法 |
| 长生命周期缓存 | 不要使用无上限的裸映射,改用带容量上限与淘汰策略的缓存组件 |
6.3 上线前检查清单
- 键是否不可变,且参与散列与相等的字段集合一致。
- 容量是否预分配,是否按扩容峰值而非稳态估算过内存。
- 散列分布是否验证过,在真实键样本上统计过空桶比例与最长桶。
- 遍历顺序是否被依赖,代码与测试中是否出现依赖顺序的断言或逻辑。
- 是否评估过最坏情况,键分布异常或被人为构造时的退化幅度与兜底机制。
- 缓存键是否覆盖全部输入维度,是否存在不同输入映射到同一键的路径。
- 分片方案是否考虑过扩缩容,节点变化时的数据迁移量与命中率下降幅度。
四、总结
散列表用一个函数把关键字映射为存储位置,把查找从"逐次比较"变成"一次计算"。这个转换的代价是一个数学事实:键域大于桶数时冲突不可避免。散列表的所有设计取舍,都是围绕这个矛盾展开的。
原理层面的核心事实可以归为几条主线:
- 散列函数解决"冲突多不多"。确定性是底线,均匀性是目标,计算成本是约束,抗碰撞构造是安全要求。除留余数法依赖模数的性质(质数优于含小质因子的合数),乘法散列法对模数不敏感,字符串散列统一走多项式滚动哈希(BKDR、DJB2、FNV-1a、Java 的 31 进制)。容量取 2 的幂可以用位与替代取模,但要求散列值低位均匀,因此常配合扰动函数;取质数则对低位规律更鲁棒。
- 冲突解决解决"冲突了怎么办"。链地址法把冲突元素放到桶外,负载因子可以大于 1,删除只需断链,代价是节点指针开销与较差的缓存局部性;开放寻址法把元素留在桶数组内,缓存友好、无指针开销,但负载因子必须低于 1,且删除必须使用墓碑以维持探测链的连续性。线性探测有一次聚集,平方探测有二次聚集,双重散列最接近理想分布。Java 的"链表加红黑树"是链地址法对最坏情况的兜底。
- 负载因子与扩容是空间与时间的调节旋钮。负载因子越大,冲突越多、空间越省;越小则相反。扩容的代价有两层:时间是 O(n) 的全量再散列,摊还后单次插入仍是 O(1);空间是扩容瞬间新旧两份桶数组同时存在,峰值可达旧表的数倍。后者是"容量预分配"最重要、也最常被忽略的理由。
- 渐进式 rehash 用时间摊平停顿。维护新旧两张表与一个迁移游标,把一次性搬运拆成每次访问顺带的少量迁移;查找要先旧后新,删除要两表都试,插入一律写入新表以保证旧表单调收敛。它降低的是单次停顿,不降低总内存占用,迁移期间的内存峰值反而被拉长。
- 键的相等语义决定命中与否。散列决定桶,相等决定桶内命中,两者的字段集合必须一致。契约只有一条强制方向:
equals相等则散列值必须相等。违反的后果是元素取不出、删不掉、去重失效。可变对象作键若修改了参与散列的字段,元素会永久失联。 - 哈希攻击是把平均情况变成最坏情况。当键来自外部且散列函数固定时,攻击者可以离线构造大量同桶键,使单次请求的开销随参数个数平方增长。防护分三层:随机种子从源头让冲突不可构造,树化把已发生的冲突代价封顶到 O(log n),限制请求规模把最坏输入压小。
- 一致性哈希与哈希槽解决的是分布问题。普通取模在节点数变化时约 (N−1)/N 的键要迁移;一致性哈希把键与节点都映射到环上,只影响相邻区间;虚拟节点解决小规模下的倾斜;哈希槽把散列空间固定切分,使扩容变成"迁移槽"这一可控操作。三者的共同目标是让"节点变化"的影响局部化。
工程层面的结论同样收敛:
- 容量预分配是性价比最高的优化。它同时削掉扩容的时间开销与瞬时内存峰值,且实现成本为零。按
元素数 / 负载因子反推容量,是使用散列表前应养成的习惯。 - 散列表的复杂度承诺是有条件的。表中的 O(1) 是平均期望值,前提是散列均匀、负载因子合理、键不可变且来自可信来源。把最坏情况纳入评估,是把它用对的前提。
- 顺序是额外的结构,不要从散列表里索取。需要稳定顺序、范围查询或相邻查询时,应选择有序结构,而不是依赖当前实现的遍历顺序。
- 排查先分类。桶长分布异常指向散列质量问题,散列值在插入前后变化指向键语义问题。两者表现相似但修法不同,先分类再动手能省下大量试错。
散列表是"用空间换时间"这一原则最纯粹的体现:它把查找的时间成本转移为一次散列计算和一部分被浪费的空间,并在冲突这一无法消除的约束下,通过负载因子、扩容与冲突解决策略,把浪费控制在可预期的范围内。