外观
04 - Hash 表为什么快:从用户缓存到冲突处理
前置阅读:01 - 时间复杂度如何决定系统上限、03 - 数组与链表的真实取舍。
后续阅读:26 - Bloom Filter 与概率判断、28 - 一致性哈希与缓存扩缩容。并发复合操作见ConcurrentHashMap 与并发容器。
摘要
按用户 ID 查询缓存时,Hash 表(哈希表)可以先计算存储位置,避免逐个扫描所有用户。本文先解释键值对、桶和冲突,再说明平均常数时间查找的前提,以及扩容、键设计和并发操作的边界。冲突与扩容主要影响成本,错误的键设计还可能导致查询失败。
1. 场景:按用户 ID 查询为什么不需要遍历
假设缓存中保存用户 ID 与用户信息的对应关系。用户 ID 是 Key(键),用户信息是 Value(值),两者组成一个条目。如果把条目放在普通数组中,并且不知道 ID 对应哪个下标,查询就要逐个比较 ID。
Hash 表也使用数组,但数组中的每个位置是一个桶,用来保存分配到该位置的条目。Hash Function(哈希函数)先把键转换成整数哈希值,再根据桶数组的长度计算合法下标。查询时重复同样的计算,就能直接找到候选桶,而不必扫描整个数组。
text
key -> hash -> spread/mix -> bucket index -> equals comparison这里的 spread/mix 指混合哈希值的位,让更多位参与桶位置计算;它是实现中的处理步骤,不是所有 Hash 表都必须采用的步骤。bucket index 是桶下标,最后的 equals comparison 是比较键是否相等。
桶只是候选范围:不同键可能有相同的哈希值,不同哈希值也可能映射到同一桶。因此,在 Java 的键比较语义下,仍需用 equals() 确认目标键。插入时也一样:先定位桶,再检查是否已有相等键;有则更新值,没有才增加条目。
2. 冲突不可避免
当可能的键多于桶时,就无法保证每个键独占一个桶。不同键落入同一桶,称为冲突。常见处理方式:
- 链地址法:把同桶条目连接成链表,查询沿链逐个比较;部分实现会在特定条件下改用树结构。
- 开放寻址法:条目保存在数组槽位中,冲突时按约定规则继续寻找其他槽位;查询也必须沿相同规则查找。
对链地址法,若有 n 个条目、m 个桶,分布均匀时每桶平均约有 n/m 个条目。只有在这个比值受到控制,且计算哈希值与比较键的成本也可视为常数时,查找才具有平均 O(1) 成本。若大量条目集中在同一条链上,查询就可能需要扫描很长的链。
Java HashMap 采用数组加链表/树的结构,树化阈值和最小容量属于 JDK 版本实现细节,使用时应固定版本核对。
3. equals() 与 hashCode() 契约
契约是键对象必须遵守的约定:如果 a.equals(b) 为 true,那么 a.hashCode() 与 b.hashCode() 必须相同。反过来不成立,因为哈希值相同仍可能只是冲突。查询先按哈希定位,再比较相等性;若两个相等对象产生不同哈希值,就可能被分配到不同桶,桶内比较也无法补救。
例如,把租户 ID 与用户 ID 一起作为键,避免不同租户的同号用户被当成同一个用户:
java
record UserKey(long tenantId, long userId) {}Java record 是按组件描述数据的记录类,会根据组件生成一致的 equals() 和 hashCode()。这里两个组件都是基本类型 long,适合表示不可变值键;若组件是可变对象,不能仅凭使用 record 就认为键的相等性和哈希值不会变化。此片段需要支持 record 的 Java 环境。
下面是示意片段,省略了 equals() 和 hashCode() 的实现,用来说明依赖可变字段的风险:
java
class MutableKey {
String code;
// equals/hashCode 依赖 code
}放入 Map 后若修改 code,且修改导致哈希值或相等性变化,条目不会自动迁移或重新建立键关系。后续查询按修改后的状态查找,就可能无法匹配原条目。需要保持稳定的是参与 equals() 和 hashCode() 的状态;不可变值键更容易满足这一要求。
4. 扩容为什么昂贵
装载因子是条目数与桶数的比值,即 n/m。桶数不变而条目增多时,这个比值上升;在相同哈希分布下,每桶的候选通常也会增多。扩容通过增加桶数降低这个比值,但需要分配更大的数组,并按新容量重新分布条目。
单次扩容可能处理全部 n 个条目,因此会带来延迟和分配峰值。若容量按倍数增长,且哈希分布与键操作成本满足前述条件,连续插入的总成本可以分摊到每次操作上,通常得到均摊 O(1)。均摊描述一串操作的平均成本,不保证每次插入都很快。
已知数据量时,合理设置初始容量可以减少扩容;过度预留则会浪费桶数组空间。容量规划不能只把预计元素数原样传给构造器:构造参数不一定就是最终桶数,装载因子决定允许的拥挤程度,扩容阈值则是触发扩容的条目数界限。容量计算需结合目标 JDK 的实现策略验证;若依赖精确阈值,应核对对应实现,不能直接套用网上的公式。
5. Hash 冲突也是安全边界
平均 O(1) 依赖 Hash 值分布足够均匀。外部输入若能构造大量碰撞,查找和写入可能退化,并放大 CPU 消耗。JDK 的树化策略只能缓解满足特定条件的桶,不等于所有 Hash 结构都能抵御碰撞攻击。
工程上应检查:
- Key 是否来自不可信输入;
- Hash Function 是否只使用了少量字段或低位;
- 单桶链长、请求耗时或 CPU 是否随特定 Key 集合异常增长;
- 跨进程协议是否错误依赖
Object.hashCode()的具体结果; - 是否应使用经过验证的稳定 Hash、带随机种子的实现或输入限额。
这些方案解决的问题不同:稳定哈希用于让参与方按约定得到一致结果,随机种子用于改变映射以增加预先构造碰撞的难度,输入限额用于约束资源消耗。稳定并不自动意味着抗碰撞攻击,应按具体威胁和实现选择。
6. 最小应用:统计频率
用单词作键、出现次数作值。下面是局部方法片段,需放入类中;假设 words 数组及其元素非 null,计数不超出 Integer 范围。merge 在键尚无计数时写入 1,已有计数时用 Integer::sum 将旧值与 1 相加。
java
import java.util.HashMap;
import java.util.Map;
static Map<String, Integer> frequency(String[] words) {
Map<String, Integer> counts = new HashMap<>();
for (String word : words) {
counts.merge(word, 1, Integer::sum);
}
return counts;
}设 n 是单词数、k 是不同单词数量。在哈希分布良好,并把单词哈希与比较的成本视为常数的模型下,每个单词进行一次更新,平均时间为 O(n),额外空间为 O(k)。若还分析单词长度,就需要计入字符串哈希与相等比较的成本,不能只按单词个数估算。
7. 完整可运行示例:链地址法 Hash 表
下面的类对应文件名 SimpleHashMapDemo.java,包含 main 入口。table 保存各桶的链表入口,Entry 是包含键、值及后继引用 next 的条目,size 记录条目总数。
java
import java.util.Objects;
/**
* 可运行示例:Hash 表为什么快:从用户缓存到冲突处理。
* 重点观察核心状态如何更新,以及边界输入如何处理。
*/
public class SimpleHashMapDemo {
static class SimpleHashMap<K, V> {
static class Entry<K, V> {
final K key;
V value;
Entry<K, V> next;
Entry(K key, V value, Entry<K, V> next) {
this.key = key;
this.value = value;
this.next = next;
}
}
private Entry<K, V>[] table;
private int size;
@SuppressWarnings("unchecked")
SimpleHashMap(int capacity) {
table = (Entry<K, V>[]) new Entry[Math.max(2, capacity)];
}
V put(K key, V value) {
// 插入后若预计超过装载因子阈值,先扩容以降低冲突概率。
if ((size + 1.0) / table.length > 0.75) resize();
// Hash 负责定位桶,桶内仍要通过 equals 确认真正的 Key。
int index = index(key, table.length);
for (Entry<K, V> e = table[index]; e != null; e = e.next) {
if (Objects.equals(e.key, key)) {
V old = e.value;
e.value = value;
return old;
}
}
// 使用头插法把新条目链接到冲突链表。
table[index] = new Entry<>(key, value, table[index]);
size++;
return null;
}
V get(K key) {
int index = index(key, table.length);
for (Entry<K, V> e = table[index]; e != null; e = e.next) {
if (Objects.equals(e.key, key)) return e.value;
}
return null;
}
private int index(K key, int length) {
int hash = key == null ? 0 : key.hashCode();
// 混合高低位,避免桶下标只受低位 Hash 质量影响。
hash ^= hash >>> 16;
return Math.floorMod(hash, length);
}
@SuppressWarnings("unchecked")
private void resize() {
Entry<K, V>[] old = table;
table = (Entry<K, V>[]) new Entry[old.length * 2];
size = 0;
// 桶数量变化后下标也会变化,所有条目必须重新散列。
for (Entry<K, V> bucket : old) {
for (Entry<K, V> e = bucket; e != null; e = e.next) put(e.key, e.value);
}
}
}
// 运行入口:使用一组包含典型边界的数据验证主要算法。
public static void main(String[] args) {
SimpleHashMap<String, Integer> counts = new SimpleHashMap<>(2);
counts.put("spring", 1);
counts.put("algorithm", 2);
counts.put("spring", 3);
System.out.println(counts.get("spring"));
System.out.println(counts.get("missing"));
}
}示例展示冲突链和倍增扩容,未实现删除、迭代器与并发控制,也未专门处理极大容量下的整数溢出或内存分配失败,生产应使用标准容器。它允许 null 键和值,因此 get() 返回 null 无法区分“键不存在”与“该键的值为 null”。
注意 put() 在查找旧键之前,先按 size + 1 检查阈值,所以覆盖已有键也可能触发一次不必要的扩容;这是当前示例的实际行为。index() 混合高低位后用 Math.floorMod 得到非负下标,这种混合不能保证任意键都分布均匀,也不能把它当成完整的 JDK HashMap 实现。
手工推演与正确性
假设桶数组至少有 3 个桶,A、B 的桶下标都为 2。先插入 A,再插入 B,头插法会形成 B -> A。查询 A 时先定位桶 2,比较 B 不相等后,再比较 A;不会扫描其他桶。桶下标相同不要求原始哈希值相同,最终仍以键的相等性确定条目。
扩容后桶数量变化,部分条目的下标会改变,所以不能只把旧桶入口复制到新数组的同一位置。示例先把 size 清零,再遍历旧链并重新执行 put(),以新的容量计算位置、创建条目并恢复计数;旧链仍用于遍历,不会被新链覆盖。
按代码推演,main 先写入 spring=1 和 algorithm=2,再把 spring 更新为 3;不存在的 missing 返回 null。预期输出如下。
text
3
null建议测试:覆盖写入、null Key、不同 Key 冲突、多次扩容,以及相等对象必须产生相同 Hash Code 的契约。
8. 并发与复合操作边界
线程安全的单次操作,不代表多个操作组合起来也具有原子性。原子性在这里指其他线程不能插入到“检查并决定写入”的中间,破坏这次决定。下面是局部伪代码,map、key 和 load() 由业务提供;即使换成并发 Map,两个线程也可能都先看到键不存在,再各自执行加载和写入:
java
if (!map.containsKey(key)) {
map.put(key, load(key));
}并发场景应根据语义使用 putIfAbsent、computeIfAbsent 或显式协调,并核对具体容器的保证。putIfAbsent 可以协调写入,但若值已在调用前通过 load() 算出,加载仍可能重复。使用 computeIfAbsent 时,还要确认映射函数(根据键计算值的函数)的阻塞、递归调用和异常行为,不能把所有 Map 实现的保证视为相同。
Hash 表解决定位问题,不自动解决加载去重、一致性或缓存击穿。缓存击穿指热点键失效或缺失时,大量请求同时回源加载,给后端带来压力;它需要结合缓存和加载流程处理。
9. 排障证据
下面是排查方向,不是仅凭症状就能确定的原因。应结合操作耗时、CPU 调用栈、分配记录和 GC(垃圾回收)事件确认:
- CPU 升高但元素数不大:检查 Hash 分布、碰撞和昂贵的
equals()。 - 延迟周期性尖峰:检查是否与扩容、对象分配和 GC 同时发生。
- 放入后查不到:检查 Key 是否可变,以及
equals/hashCode是否一致。 - 并发重复加载:检查是否把复合操作拆成了多个非原子步骤。
- 内存高于预期:同时计算桶数组、Entry、Key、Value 和对象对齐成本;对象对齐指运行时按规定边界分配对象,可能产生额外填充空间。
10. 容易踩的坑
使用前可按四类边界复查,避免遗漏:
- 键语义:是否一致实现
equals()与hashCode(),参与二者的状态在入表后是否保持稳定。 - 性能条件:是否误把平均
O(1)当作最坏情况保证,或只使用少量字段、低位导致条目聚集。 - 并发访问:是否在并发写入时使用普通
HashMap,或把需要原子执行的流程拆成多步。 - 协议边界:是否把 Java 进程内的哈希结果当作跨语言、跨版本的稳定协议,而没有明确算法与编码约定。
11. 工程应用
Hash 表适合以“键是否相等”为核心的缓存、去重、频率统计和内存索引。它按哈希分桶,没有按键大小排列,因此不能像有序结构那样直接定位一个范围并顺序遍历。
需要维护插入顺序或访问顺序时,可考虑 LinkedHashMap 并明确配置;需要按键排序或范围查询时,可考虑有序树结构。并发访问则应根据单次操作和复合操作的语义选择 ConcurrentHashMap 等方案,不能只凭容器名称判断整个业务流程是否安全。
12. 总结
Hash 表的平均高效来自均匀分桶,正确性则依赖稳定且一致的 Key 语义。
- Hash 只缩小候选范围,Key 相等仍由
equals()决定。 - 冲突和扩容是 Hash 表设计不可回避的成本。
- 保持键的哈希值与相等性稳定,才能避免“放得进去、找不回来”;不可变值键更容易做到这一点。
下一篇:栈与队列的解题模型。概率集合见Bloom Filter 与概率判断,稳定分片见一致性哈希与缓存扩缩容。