1. 哈希表不是魔法它到底解决了什么问题先用一个最朴素的问题开场为什么我们需要哈希表数组大家都熟按下标访问元素的时间复杂度是 O(1)这已经是计算机里最快的随机访问方式了。但数组有个要命的前提——下标必须是整数而且你还得知道这个下标是多少。如果我想查一个叫张三的人的电话号码数组根本不认识张三这四个字它只认识 0、1、2、3……这种整数下标。那你怎么办只能遍历整个数组一个一个比O(n) 就出来了。链表也是类似的困境想找一个元素只能从头结点开始挨个走平均 O(n)。树结构能优化到 O(logn)比如平衡二叉树、B树这已经是很大的进步了但还不是最快的。哈希表的思路完全不一样既然数组访问快那我就想办法把任意一个 key映射成一个数组下标。你给我一个字符串、一个对象、一个数字我都通过一个函数算出一个整数然后把这个整数当成数组下标直接把数据存进数组的这个位置。查的时候也一样拿着 key 再算一遍下标直接去数组那个位置拿。整个过程跟数组一样是 O(1)但又不要求 key 必须是整数。这个把任意 key 算成数组下标的函数就是哈希函数。一句话总结哈希表 数组 哈希函数。数组负责 O(1) 的存取速度哈希函数负责把五花八门的 key 转换成数组能认的整数下标。你可能已经发现了这里面藏着一个巨大的隐患如果两个不同的 key 算出来的下标一样怎么办比如 keyA 算出来是 7keyB 算出来也是 7但数组下标 7 这个位置已经被 keyA 占了。这就是哈希冲突。哈希表的所有设计难点说白了都是围绕两件事怎么让哈希函数尽量少产生冲突以及真产生了冲突怎么办。后面几节我会分别拆开讲。在往下走之前先明确哈希表支持的三个核心操作方便后面讨论put(key, value)把 key 映射成下标存进去。get(key)把 key 映射成下标取出来。remove(key)把 key 映射成下标删掉。这三个操作在理想情况下都是 O(1)。注意我说的是理想情况实际工程里有很多因素会让这个 O(1) 退化如果你只记住了哈希表查得快而忽略了它的退化条件后面线上出问题的时候你连排查方向都没有。2. 哈希函数散列质量的生死线哈希函数决定了整个哈希表的命运。一个优秀的哈希函数应该满足三个要求。2.1 一致性同一个 key 永远算出同一个值这个没什么好说的如果同一个 key 第一次算出来是 3第二次算出来是 8那整个哈希表直接崩了。它的真正含义是两个相等的 key必须产生相同的哈希值。这在 Java 里对应着hashCode()和equals()的约定后面我会专门讲这个坑。2.2 高效性计算不能太慢哈希函数本身是有 CPU 成本的。如果算一次哈希要执行几百条复杂指令那就算查表是 O(1)整体性能也可能不如一棵简单的二叉树。工程上常说空间换时间哈希函数其实是用计算换时间。2.3 均匀性不同的 key 尽量分散到不同的下标这是最核心的一条。如果哈希函数把所有 key 都算成同一个下标那哈希表就退化成了一条链表get 操作又变回 O(n) 了。Java 里String的hashCode()是个非常经典的教学案例它用的是这个公式hash s[0]*31^(n-1) s[1]*31^(n-2) ... s[n-1]这里每个字符都参与计算而且位置越靠前的字符权重越大。为什么乘 31两个原因31 是奇素数乘法运算时不容易产生信息丢失同时 JVM 会对31 * i做优化等价于(i 5) - i一次位移一次减法非常快。你可以去看看 Java 源码里的String.hashCode()实现就是按这个公式来的。不过hashCode()算完并不代表能直接用Java 的 HashMap 内部还做了一次扰动处理源码里叫hash()static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }看到那行h ^ (h 16)了吗它的意思是把 int 的高 16 位和低 16 位做异或让高位的特征也混入低位。为什么要这么做因为 HashMap 计算数组下标时用的是(n - 1) hash这里的 n 是数组长度。如果长度只有 16也就是 n-1 的二进制约束了只看低 4 位那 hashCode 的高位信息就全被丢掉了。两个对象的 hashCode 高位不同但低位恰好相同在这张表里就会被算到同一个下标。扰动函数让高位信息也参与低位的运算就是为了在容量还很小的时候让 key 也能散得更均匀。这里的经验是别指望每个人的 hashCode 都写得好HashMap 在入口处帮你兜了一道底。你去看 ConcurrentHashMap 也有类似的处理这个思想跟上位运算在哈希表领域特别常见。反过来看什么样的 hashCode 是灾难级的// 反例1所有对象返回相同哈希值 Override public int hashCode() { return 1; } // 反例2直接用唯一ID取模ID分布不均时冲突严重 Override public int hashCode() { return id % 10; } // 反例3组合字段时用加法可能会导致(A,B)和(B,A)撞车 Override public int hashCode() { return name.hashCode() age; // 顺序敏感度差 }业务对象正确做法是选择各个字段的哈希值然后用质数加权组合。Java 自带Objects.hash(...)就是这么干的Override public int hashCode() { return Objects.hash(name, age, email); }底层会把每个字段的哈希值和一个初始种子数比如 31做迭代乘法累加。质数的好处是即使不同字段的哈希值恰好线性相关组合后也不容易产生倍数关系的冲突。3. 哈希冲突的四种解法以及它们的取舍差异不管你哈希函数写得多漂亮只要 key 的空间大于哈希表的容量冲突就不可避免抽屉原理鸽巢原理。所以真正区分哈希表工程质量的是它怎么处理冲突。主流方案有四类3.1 链地址法拉链法这是最常见、也最直接的思路数组的每个位置不放单个元素而是放一条链表。冲突了没问题直接往链表尾部挂。Java 的 HashMap、ConcurrentHashMap 都是这个方案。链地址法有几个天然的优势实现简单增删改查逻辑很直白。删除容易链表上摘一个节点就行不需要做墓碑之类的标记。对负载因子容忍度高链表稍微长一点问题不大极端情况下还能转红黑树救场。扩容迁移方便重新计算下标后节点按高低位拆成两条链不用反复插入。它的缺点也很明显链表节点的内存不连续CPU 缓存命中率低而且每个节点都有额外的指针存储开销。3.2 开放寻址法数组的每个位置只能放一个元素。冲突了别慌往后找一个空位放进去。查找的时候就顺着往下找直到找到目标或者遇到空位说明没这个 key。找空位的方式有三种线性探测冲突了就往后挪一个位置(hash1) % n。实现最简单但容易产生聚集问题——冲突的 key 扎堆排队导致后续的插入和查找都要跨越很长一段距离。二次探测往后挪的步长是 1²、2²、3²……(hash i²) % n。步长逐渐加大可以一定程度上缓解聚集但要小心别跳出了还没找到空位。双重散列准备第二个哈希函数冲突时用第二个函数算出步长(hash i * hash2(key)) % n。效果最好但也最讲究哈希函数质量。开放寻址有个特别容易踩的坑删除操作不能直接置空。如果直接把一个位置置为 null那后面本来排在它后面的元素在查找时会因为遇到 null 而被误判为不存在。所以工程实现里需要用一个墓碑标记删除位置查询时遇到墓碑继续往后走插入时可以覆盖墓碑。这比链地址法麻烦得多。开放寻址对负载因子也特别敏感内存使用率接近 0.7 时冲突会急剧恶化所以一般会把负载因子压到 0.5 左右空间浪费比较大。但它的好处是数据全在连续数组里缓存命中率极高在内存受控、数据量可预测的底层场景里反而更常用。3.3 再哈希法准备一组哈希函数第一个冲突了换第二个第二个再冲突换第三个……直到找到空位。这个方案在通用哈希表里基本绝迹了因为它需要维护多个哈希函数的状态而且查找时的路径没法预判实际工程价值有限。但它在一致性哈希、分布式负载均衡这类场景里思想还有延续——本质上是通过多次哈希来选择目标只是目的从存数据变成了选节点。3.4 建立公共溢出区额外开辟一块溢出区所有冲突的 key 统一放进去。适合冲突极少但必须兜底的场景比如某些数据库索引结构。实现上虽然简单但溢出区一旦变大性能就崩了。四种方式怎么选看场景没有绝对最优方案实现成本删除缓存友好度负载因子容忍度典型应用链地址法低容易较低高可到 0.75Java HashMap、Redis线性探测低需墓碑高低约 0.5ThreadLocalMap二次探测中需墓碑中低早期哈希表教材实现双重散列高需墓碑中中性能敏感型哈希表再哈希/溢出区高复杂低低特定专用结构4. Java HashMap 的工程化细节红黑树、扩容与那场死循环事故如果你只把哈希表当纯理论看那到这里基本已经够了。但既然热搜词里出现了java哈希表输出说明大量实际问题是出在 Java 的 HashMap 实现上的。这一节我按 JDK 8确切说是 JDK 8u20 之后的实现来讲顺便聊聊 JDK 7 那个让无数人 CPU 跑满的历史事故。4.1 JDK 7 到 JDK 8 的结构升级JDK 7 及以前的 HashMap 是数组 单向链表的结构新增元素时采用头插法——新节点插到链表头部。JDK 8 改为数组 单向链表 红黑树插入时用尾插法——新节点挂到链表尾部。为什么改尾插后面讲死循环的时候你就明白了。4.2 链表什么时候升级成红黑树JDK 8 的源码里有三个关键常量static final int TREEIFY_THRESHOLD 8; // 链表长度达到8尝试转树 static final int UNTREEIFY_THRESHOLD 6; // 红黑树节点数降到6退化为链表 static final int MIN_TREEIFY_CAPACITY 64; // 转树前数组容量必须达到64转树的条件是链表长度超过 8且数组容量至少 64。这两个条件缺一不可如果容量还没到 64就算链表很长HashMap 也会选择先扩容而不是转树。为什么阈值偏偏是 8因为这个数字来自泊松分布。在随机哈希即各桶概率均匀且负载因子为 0.75 的情况下单个桶内链表长度达到 8 的概率大约是千万分之六约等于几乎不可能发生。也就是说正常情况下链表长度不会超过 8转红黑树本来就是给哈希函数写得极烂的场景兜底的。红黑树节点的内存占用大概是普通链表节点的两倍所以树化其实是用空间换极端情况下的时间。树退化阈值取 6 而不是 7 是为了防止元素在阈值附近反复增删时链表和树来回切换产生抖动。退一步如果取 7那链表长度在 7 和 8 之间震荡五次结构就切换五次一次转换的代价可不小。4.3 为什么容量必须是 2 的 n 次幂HashMap 有两个和容量相关的细节值得单独说。第一tableSizeFor方法保证初始容量向上取整到 2 的幂次static final int tableSizeFor(int cap) { int n cap - 1; n | n 1; n | n 2; n | n 4; n | n 8; n | n 16; return (n 0) ? 1 : (n MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n 1; }你传入 17它给你 32传入 100给你 128。这套右移或的位运算巧妙地把最高位以下的位全部填成 1再加 1 进位得到最近的 2 的幂。第二为什么非要 2 的幂因为这样计算下标可以省掉取模运算直接用位运算index (n - 1) hash这个式子等价于hash % n前提就是 n 是 2 的幂。位运算比取模快得多而哈希表几乎每个操作都要算下标这个优化省下的 CPU 很可观。4.4 扩容机制为什么是 2 倍扩容当元素个数超过容量 * 负载因子时HashMap 触发扩容容量直接翻倍。负载因子默认 0.75也就是默认容量的 16 个桶存到 12 个元素就会扩容到 32。扩容不只是把数组换大那么简单所有已存在元素的桶下标都要重新计算——因为(n - 1) hash里的 n 变了同一个 hash 算出的低位掩码长度变了下标大概率也会变。但 JDK 8 的扩容有个巧妙的优化。由于容量从 oldCap 变成 2 * oldCapnewCap - 1 相比 oldCap - 1 多了一个最高位为 1 的二进制位。某个节点在新数组的下标要么是原来的下标要么是原下标 oldCap。判断依据就是(hash oldCap) 0结果为 0说明新增的这一位正好是 0下标不变。结果不为 0说明新增的这一位是 1下标需要偏移 oldCap。所以 JDK 8 的 rehash 不是逐个重算而是把每个桶里的链表按hash oldCap拆成 lo 和 hi 两条链分别挂到新数组的原下标和新下标位置。4.5 JDK 7 的死循环事故这个历史问题值得每个用 HashMap 的人知道。JDK 7 的扩容采用头插法遍历旧链表把节点一个个摘下来插入到新数组桶的头部。多线程并发扩容时两个线程同时操作同一个桶的链表就可能让链表节点形成环也就是 A - B - A。之后任何线程在这个桶上执行 get就会在环形链表里死循环CPU 直接爆到 100%。这个事故在当年是让无数团队吃过亏的经典案例。JDK 8 改尾插法避免了新链表逆序导致的环但这只是降低了死循环的概率并没有让 HashMap 变得线程安全。并发下依然会出现数据覆盖、丢失等问题正确做法是使用 ConcurrentHashMap 或Collections.synchronizedMap。关于并发替代方案的对比后面会专门讲。5. 为什么 HashMap 遍历输出的顺序总是不稳定现在回到热搜词里的java哈希表输出。这个搜索词的高频出现说明大量开发者在实际敲代码时遇到了同一个困惑往 HashMap 里 put 的顺序明明是 A、B、C为什么遍历输出的时候顺序完全对不上这个现象的原因正是上面讲过的所有机制叠加的结果。5.1 桶下标与插入顺序没有必然关系元素存到哪个桶取决于hash(key)和当前容量。HashMap 的默认容量是 16那么keyA 的 hash 是 65(16-1) 65 1存桶 1。keyB 的 hash 是 33(16-1) 33 1也在桶 1。keyC 的 hash 是 130(16-1) 130 2存桶 2。插入顺序是 A、B、C但桶的顺序是 1、1、2。遍历时从桶 0 开始逐个走出来的顺序就是 A、B、C 或者 B、A、C取决于链表内部顺序这自然跟插入顺序对不上。等扩容到 32 之后这些 key 的下标又全变了输出顺序又一次大变。所以 HashMap 的输出顺序从来就是不确定的它依赖 key 的 hashCode、当前容量、负载因子、冲突链路长的共同作用。你要是在代码里依赖这个顺序做业务那基本等于埋雷哪天线上环境换了 JDK 版本或者 key 结构调整了输出顺序一变程序可能就出 bug 了。5.2 需要保序时用什么如果确实需要按某种确定的顺序遍历别硬掰 HashMap换数据结构更省心LinkedHashMap内部额外维护一条双向链表记录插入顺序或访问顺序。遍历时按这条链走输出顺序就是插入顺序。它的构造方法里有个accessOrder参数设为 true 可以按最近访问排序这是实现 LRU 缓存的利器像 MyBatis、Spring 的一些缓存模块底层都用了这个特性。TreeMap按 key 的自然顺序或自定义 Comparator 排序遍历输出天然有序代价是操作复杂度从 O(1) 变成 O(logn)。5.3 多线程下的输出异常与安全替换HashMap 在并发环境下不只是顺序问题数据完整性都可能出问题。我帮你把几个常见方案的特性列个表方案线程安全机制读性能写性能适用场景HashMap无最高最高单线程或确定无并发竞争Hashtable全方法加 synchronized 锁低低基本不用了Collections.synchronizedMap包装整个 Map 加锁中中遗留项目兼容ConcurrentHashMapCAS synchronized 锁桶/分段锁高高并发读多写多的首选ConcurrentHashMap 的性能接近 HashMap并发安全系数高得多。它把整个 Map 分成很多桶不同线程操作不同桶时可以并行只有操作同一个桶时才需要等待锁粒度远小于 Hashtable。如果并发场景里你对数据还有强一致性的要求比如先判断再写入这种复合操作那 ConcurrentHashMap 提供的computeIfAbsent、merge这类原子方法也足够用了。6. 真实业务里的哈希表排障从我踩过的坑说起前面讲完了原理和实现最后这部分是我实际项目里遇到过的哈希表相关故障每一个都是线上真实发生的。光知道理论容易眼高手低遇到实际问题能定位才是真本事。6.1 坑一hashCode 返回常量接口从秒回变成超时有次排查一个接口的耗时陡增从平均 50ms 涨到 4 秒多用火焰图一看热点全在哈希表的查找上。定位到最后发现是团队里一个模型类重写了hashCode()但实现是Override public int hashCode() { // 当时为了暂时通过编译随便写的 return 1; }结果这个类被当成 key 塞进了 HashMap所有 key 全落在同一个桶里链表长度到了几千每次 get 都是 O(n)。更糟的是JDK 8 下这个链表还可能转成红黑树虽然不至于死循环但性能一样崩。这个排查经验告诉你如果线上某接口突然变慢而且特征和数据量没涨多少但耗时线性暴涨吻合先检查 key 的 hashCode 实现。6.2 坑二用可变对象做 keyget 返回 null还有一次业务方反馈数据存进去了但查不出来。看代码put 的时候明明输出有值get 的时候却是 null。原因是他们用了某个自定义对象做 key这个对象里有几个字段是可变的。第一次 put 的时候对象的 hashCode 是 A之后业务逻辑改了对象里的某个字段再 get 的时候hashCode 变成了 B。HashMap 拿 B 去算下标自然去错了桶桶里空空如也。这个问题在原理上讲就是哈希函数的一致性被破坏了。对象存进 HashMap 之后所有参与 hashCode 计算的字段都不能再被修改。最稳妥的做法是用不可变对象做 key比如 String、Integer或者自己定义一个所有字段 final 的类。如果非要用可变对象那就在存进去之前先对字段做防御性拷贝。6.3 坑三重写 equals 却没重写 hashCode很多新手会犯这个错。重写了equals()判断两个对象逻辑相等但没动hashCode()两个对象 equals 返回 truehashCode 却不相等。HashMap 判断 key 是否相等时是先比 hashCode 再比 equals 的equals 相同而 hashCode 不同的话这两个 key 在 HashMap 眼里就是两个完全不同的 key会出现重复存放、查不到数据等一系列诡异问题。反之也一样hashCode 相同不意味着 equals 一定相同哈希冲突本来就允许但 equals 相同必须保证 hashCode 相同。这条约定是哈希表工作的前提。6.4 坑四遍历时删除元素抛 ConcurrentModificationException这个其实不算哈希表专有的问题只要是使用 fail-fast 迭代器的集合都有。但 HashMap 使用频率高踩的人也多// 错误示范遍历中直接删除抛 ConcurrentModificationException for (String key : map.keySet()) { if (key.startsWith(temp)) { map.remove(key); } }正确打开方式有两种// 方式一使用迭代器的 remove 方法 IteratorString it map.keySet().iterator(); while (it.hasNext()) { String key it.next(); if (key.startsWith(temp)) { it.remove(); } } // 方式二JDK 8 的 removeIf map.keySet().removeIf(key - key.startsWith(temp));6.5 预分配初始容量这是性能优化里最简单有效的一条。HashMap 扩容是个相对昂贵的操作涉及新建数组和把所有元素重新分布而且每次扩容都是翻倍。如果事先知道大概要存多少条数据直接指定初始容量// 已知要存 600 条数据负载因子 0.75直接用 1024 的容量 MapString, User userMap new HashMap(1024);计算方式是预计元素数 / 0.75 1向上取整到 2 的幂。600 / 0.75 800向上取 1024。这样能省掉扩容次数在大数据量场景下效果立竿见影。还有个跟这个相关的小技巧如果你在做数据统计、去重并且数据量在百万级以上考虑用 Guava 的HashMultiset或者直接上LongAdder按哈希分桶避免单个 HashMap 的压力过于集中。6.6 怎么验证自己的哈希分布是否均匀最后分享一个排查用的小工具思路。假设你想确认某个类的 hashCode 分布是否合理可以写一个临时方法模拟 HashMap 的散列过程统计各个桶的长度分布public static void checkHashDistribution(ListYourKey keys, int capacity) { int[] bucketSize new int[capacity]; for (YourKey key : keys) { int index (capacity - 1) key.hashCode(); bucketSize[index]; } MapInteger, Long distribution Arrays.stream(bucketSize) .boxed() .collect(Collectors.groupingBy(i - i, Collectors.counting())); System.out.println(桶长度分布 distribution); }如果发现大量桶长度为 0而某几个桶特别长说明 hashCode 分布不均匀需要重新设计。正常随机哈希下桶长度应该接近泊松分布大多数桶是 0 或 1极少有超过 5 的。7. 写在最后哈希表性能问题的一般排查思路综合前面这些内容如果线上真的遇到哈希表相关的性能或正确性问题我一般按这个顺序排查先确认数据量级。如果元素数量和初始容量严重不匹配扩容会非常频繁先考虑预分配容量。再看 key 的哈希实现。用上面那个分布统计工具跑一遍看看桶长度是否均匀。如果集中在少数几个桶问题基本就定位到了。确认 key 是否会中途改变哈希值。可变对象做 key 是数据查不到的常见元凶。确认是否有并发操作。多线程同时 put 到同一个 HashMap表现是数据丢失、无限循环JDK 7 时代这种情况直接换 ConcurrentHashMap。如果怀疑链表退化和树化切换频繁可以打印一下 bucket 的深度分布进一步确认负载因子设置是否合理。哈希表这个数据结构原理上不过十行代码就能说清楚但真正用好它需要对散列函数、冲突策略、扩容机制和并发特性都有整体认识。希望这篇文章能帮你在遇到哈希表问题的时候不只是搜一下报错然后复制粘贴而是真正能判断问题出在哪个环节。