先说说我为什么想写这个话题。前阵子帮朋友排查一个线上服务接口平时几毫秒就能返回压测到一定量级后突然变成几百毫秒CPU 直接飙红。查来查去问题根源竟然是一个 HashMap 的 Key 设计不规范大量对象落进同一个桶位链表被拉得老长O(1) 的查询活生生退化成了 O(n)。这让我意识到很多人对 HashMap 的理解停留在“会用”层面一旦牵扯到底层哈希碰撞、扩容、树化这些机制就容易两眼一抹黑。所以这篇东西我想从一次“事故”入手把 Key 碰撞的成因、源码逻辑、定位手段和规避方案都摊开讲清楚。不管你是准备面试、期末复习还是真的在线上遇到过类似劣化问题看完应该都能建立起一套完整的排查思路。1. 事故现场还原当 Key“撞车”之后发生了什么1.1 先搞明白HashMap 凭什么敢说 O(1)要理解碰撞得先建立“桶位”的概念。你可以把 HashMap 想象成一栋公寓楼每层有若干净的房间房间里可以挂一个链表链表上每个节点存一份键值对。put 一个 Key 时HashMap 会先用 Key 的 hashCode 算出一个整数再用这个整数找到对应的房间号也就是数组下标。如果房间是空的直接入住如果房间里已经有人了就在链表的末尾追加一个节点。这个“找房间”的过程理想情况下只做一次散列运算和一次数组取值所以时间复杂度是 O(1)。但问题在于房间数量是有限的而 Key 的可能取值是无限的。就像一个只有 16 个格子的储物柜要存 100 个包裹不可避免会出现两个不同的 Key 被算到了同一个格子里的情况这就是哈希碰撞或者叫哈希冲突。碰撞发生那一刻HashMap 的性能就开始走下坡路了因为后续的查找不再是一步到位而是要在链表里逐个比较。这里有个容易混淆的点hashCode相同一定会碰撞但hashCode不同也可能碰撞。HashMap 并不是直接用hashCode当数组下标而是先把hashCode做一次扰动运算再用数组长度减一去做与运算。这个过程中不同hashCode的低位如果恰好相同就会落到同一个桶位。也就是说碰撞的本质是两个 Key 最终被映射到了同一个桶而不是两个 Key 本身一定有什么相同之处。1.2 两个 Key 撞在一起的几种方式我习惯把碰撞分成三类方便排查时对症下药。第一类是“同 hashCode 碰撞”也是最常见的事故来源。比如你自己定义了一个类作为 Key只重写了equals没有重写hashCode那么每个新对象都会继承Object.hashCode()底层是对象内存地址转换来的一个整数。业务上“相等”的对象在这个方法眼里完全不相等哈希值自然千奇百怪。但如果反过来你重写了hashCode却写得极其敷衍比如直接return 1那所有 Key 都会进同一个桶HashMap 就彻底退化成一条链表。第二类是“异 hashCode 碰撞”。整体哈希值不同但经过扰动和与运算之后低位相同最终落点相同。比如数组长度是 16 时下标计算只看哈希值的低 4 位也就是说凡是以 16 为倍数的哈希值都会挤到下标为 0 的桶里。这种碰撞在数据量小时不明显数据量大了就会引发局部热点。第三类是“扩容后的重新分布”。扩容时桶数翻倍一些本来不在同一个桶的元素可能被重新分配到不同桶反过来一些本来在不同桶的元素也可能因为新的寻址逻辑而跑到同一个桶里。这不算严格意义上的“事故”但如果你在扩容过程中去读 HashMap就会发现数据一直处于“搬家”状态这也是并发操作会出问题的关键背景。2. HashMap 底层实现原理拆解数组、链表与红黑树的配合2.1 桶位寻址hash() 与 (n - 1) hash 的默契配合大家背过八股文都知道 HashMap 的数组长度默认 16负载因子默认 0.75扩容时翻倍。但很多人没细想过一个问题为什么数组容量必须是 2 的幂答案藏在寻址公式里。// 这是 JDK 1.8 中的 hash 扰动方法 static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }第一步把key.hashCode()拿到的 32 位整数高 16 位与低 16 位做异或。为什么要这么干因为数组长度只有 2 的幂时n - 1的二进制表示是“一连串 1”比如 16 减 1 等于 15二进制是 1111。这时候(n - 1) hash实际上只取了哈希值的低 4 位高 28 位全被丢弃了。如果原始 hashCode 的高位分布很好、低位分布很差就会出现大量 Key 只用到低 4 位的情况碰撞率直线上升。让高半区和低半区异或相当于把高位信息“混入”低位哪怕数组很小也能让最终的下标分布更均匀。第二步(n - 1) hash本质上就是hash % n但因为 n 是 2 的幂位运算比取模快得多。2 的幂这个约束保证了n - 1的低位全是 1高位全是 0与运算不会产生“空洞”。如果你非要让 HashMap 的容量不是 2 的幂它内部会调用tableSizeFor算法强行把容量调整成最接近且大于等于传入值的一个 2 的幂。比如你传 17实际容量是 32传 100实际容量是 128。2.2 链表变红黑树树化阈值 8 与退化阈值 6 背后的逻辑JDK 1.8 之前HashMap 的每个桶位只有链表结构数据量大而碰撞严重时链表可以变得非常长。JDK 1.8 引入了红黑树当链表长度超过阈值后链表会被转换成红黑树把单次查找从 O(n) 降到 O(log n)。源码里有几个关键常量static final int TREEIFY_THRESHOLD 8; static final int UNTREEIFY_THRESHOLD 6; static final int MIN_TREEIFY_CAPACITY 64;树化条件有两个链表长度大于等于 8并且数组长度大于等于 64。注意这是“并且”的关系。如果数组长度才 16哪怕某个桶的链表已经有 10 个节点HashMap 也不会立即树化而是先触发扩容把桶分散开。这个设计的意图很明确当容量还小时优先通过扩容解决碰撞因为扩容的成本比树化重建低只有容量到位了、链表依然很长时才判断这是“恶意碰撞”或者哈希分布严重不均用红黑树兜底。为什么树化阈值选 8 而不是 6 或 10源码注释里给过一组泊松分布的概率数据在负载因子 0.75、哈希函数随机性良好的情况下同一个桶位链表长度达到 8 的概率约为千万分之六。换句话说正常业务数据几乎不可能让链表长度触到 8真触到了要么是你 Key 类的 hashCode 写得有问题要么是有人恶意构造数据搞攻击。红黑树本身比链表复杂节点占内存更大维护成本也高所以只在“异常情况”下使用平时还是以链表为主。退化阈值选 6是为了留一个缓冲区间。如果树化阈值是 8、退化阈值也是 8那元素在 8 附近增减时链表和树反复互相转换性能抖动会非常明显。中间隔了两档给系统留出回旋余地这是非常典型的空间换稳定性的思路。2.3 resize 扩容机制为什么扩容后元素要么不动、要么平移旧容量扩容是 HashMap 里最容易被低估的一个环节。旧数组容量 16新数组容量 32很多人的第一反应是“重新计算所有元素的哈希值和下标”。实际上 HashMap 根本没有重新调用hash()而是利用了一个很巧妙的事实。之前说过下标计算是(n - 1) hash。容量从 16 变成 32掩码从 1111 变成 11111相当于参与位运算的位数从低 4 位变成低 5 位。每个元素的新下标要么不变要么等于“旧下标 旧容量”。举个例子一个元素的 hash 是 5旧容量 16 时5 15 5新容量 32 时5 31 5位置不变。另一个元素的 hash 是 21旧容量 16 时21 15 5新容量 32 时21 31 2121 恰好等于 5 16。所以扩容时只需要看 hash 值新增的那一位是 0 还是 1是 0留在原位是 1平移到“原位 旧容量”的位置。源码里的(e.hash oldCap)就是干这件事的。这个优化在 JDK 1.8 中配合尾插法彻底解决了 JDK 1.7 时代扩容时链表倒置导致的死循环问题。JDK 1.7 用的是头插法扩容时链表会反转并发操作下可能出现两个节点互相引用的环get 的时候 CPU 直接跑满。所以说 HashMap 线程不安全不是一句空话背后是真实的历史事故。3. 实战复现手写一个“恶意”Key 类亲眼看看碰撞现场3.1 让所有 Key 都进同一个桶的“事故代码”纸上谈兵没用我建议你亲手跑一下下面的代码感受一下碰撞的杀伤力。定义一个类hashCode恒定返回一个固定值让所有对象都挤到同一个桶。import java.util.HashMap; import java.util.Map; public class CollisionDanger { static class BadKey { private final int id; private final String name; BadKey(int id, String name) { this.id id; this.name name; } Override public int hashCode() { return 1; // 故意制造碰撞所有 Key 共享同一个哈希值 } Override public boolean equals(Object obj) { if (this obj) { return true; } if (!(obj instanceof BadKey)) { return false; } BadKey other (BadKey) obj; return id other.id name.equals(other.name); } } public static void main(String[] args) { MapBadKey, Integer map new HashMap(); int testSize 100000; long start System.nanoTime(); for (int i 0; i testSize; i) { map.put(new BadKey(i, user- i), i); } long putCost System.nanoTime() - start; start System.nanoTime(); int hit 0; for (int i 0; i testSize; i) { hit map.getOrDefault(new BadKey(i, user- i), -1); } long getCost System.nanoTime() - start; System.out.println(put cost : putCost / 1_000_000.0 ms); System.out.println(get cost : getCost / 1_000_000.0 ms); System.out.println(hit sum : hit); } }跑完你会发现插入 10 万条数据耗时非常夸张查询 10 万次更是慢到让人不能接受。作为对比如果你把hashCode改成id哪怕不重写equals性能也会好上几个数量级。这个对比能直观告诉你哈希值分布均匀是 HashMap 高性能的前提分布不均匀HashMap 就是一个长了尾巴的链表。这里还要强调一个实际工程项目里很容易踩的变体有些团队的实体类确实重写了hashCode但是直接用了业务对象本身做 Key并且业务对象内部还有List、Map之类的可变字段。一旦对象在放入 Map 之后被修改hashCode变了再用原来的引用去 get就永远找不到那个节点了。这类问题比单纯碰撞更隐蔽排查起来也更费劲。3.2 put 的完整执行流程源码级解读手动复现现场之后我们把 put 的源码流程走一遍。这一步不需要你背代码但理解它能帮你解决很多“为什么这个 HashMap 表现反直觉”的问题。final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { NodeK,V[] tab; NodeK,V p; int n, i; // 如果桶数组还没初始化先触发 resize if ((tab table) null || (n tab.length) 0) { n (tab resize()).length; } // 定位桶位如果桶位为空直接放一个新节点 if ((p tab[i (n - 1) hash]) null) { tab[i] newNode(hash, key, value, null); } else { // 桶位不为空说明发生了碰撞 NodeK,V e; K k; // 如果第一个节点的 hash 和 key 当前值相同直接覆盖 if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) { e p; } else if (p instanceof TreeNode) { // 已经树化走红黑树的插入逻辑 e ((TreeNodeK,V)p).putTreeVal(this, tab, hash, key, value); } else { // 还是链表遍历找尾巴 for (int binCount 0; ; binCount) { if ((e p.next) null) { p.next newNode(hash, key, value, null); // 链表长度达到树化阈值尝试树化 if (binCount TREEIFY_THRESHOLD - 1) { treeifyBin(tab, hash); } break; } if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) { break; } p e; } } // 找到相同 Key替换旧值 if (e ! null) { V oldValue e.value; e.value value; return oldValue; } } // 插入完成后判断是否需要扩容 if (size threshold) { resize(); } return null; }整段逻辑可以浓缩成一句话算哈希找桶桶空直接放桶不空看是不是同一个 Key是就覆盖不是就顺着链表找找不到就追加追加完看要不要树化最后 size 超了阈值就扩容。里面有三处边界情况值得记住。第一两个 Key 是否“相等”判断条件是p.hash hash且key.equals(k)。也就是说即便equals返回 true如果hashCode不相等HashMap 也认为它们不是同一个 Key会放进不同桶。反过来hashCode相等但equals不相等就会被放在同一个桶里靠链表串起来。这就解释了为什么重写equals必须重写hashCode两者不协同HashMap 的语义就崩了。第二树化的入口是treeifyBin它内部会再检查一次数组长度是否达到 64。数组长度不够时它不会真的树化而是调用resize()扩容。看到这个逻辑你就能理解为什么说“链表到 8 就转红黑树”这句话严格来说是不准确的——至少要数组长度 64 且链表长度 8两者同时满足才转。第三插入完成后才size所以遍历时如果手动调了map.size()看到的是插入前的旧值。当然正常代码不会依赖这个细节但面试里如果被问到“HashMap 的 size 是实时更新的吗”这个点是得分关键。3.3 负载因子、初始容量从默认参数看作者的设计取舍HashMap 有两个默认参数是绕不开的初始容量 16负载因子 0.75。很多初学者不理解为什么负载因子不是 1.0也不是 0.5偏偏取了个 0.75。先说结论。负载因子越高空间利用率越高但碰撞概率和扩容后的“拥挤度”也会增加查询成本上升负载因子越低桶越空冲突少查询快但内存浪费明显。0.75 是 JDK 作者在大量实验基础上取的一个折中值既没有让空间太浪费也没有让冲突太频繁。如果你是做服务端开发的有一个经验值得记住如果提前知道要往 Map 里塞 N 个元素初始化容量别直接写 N也别写N / 0.75这种不整不零的数建议写(int) (N / 0.75f) 1。为什么因为 HashMap 的扩容阈值是capacity * loadFactor容量 16、负载因子 0.75 时阈值是 12也就是说插到第 13 个元素就会触发扩容触发一次 16 - 32 的数组复制和重映射。如果你一开始就知道要放 1000 个元素却只new HashMap(1000)那么实际容量会被调整到 1024阈值是 768插到第 769 个元素时又要扩容一次。提前按N / 0.75算好容量就能省掉这次扩容的代价。不过也有反例。有些场景下内存比 CPU 更紧张或者数据量特别大有人会刻意把负载因子调高到 1.0 甚至更高。这是可以接受的但你要记得查询耗时和碰撞概率会同步上升排查问题时别忽略这个自定义参数的影响。4. 碰撞后的急救方案与排查思路4.1 线上出现性能劣化怎么判断是 HashMap 碰撞引起回到文章开头说的那个线上事故。接口慢下来之后第一反应通常是看日志、看数据库慢查询、看下游依赖很少有人会第一时间怀疑到 JVM 内存里的一个 Map。这里分享一套排查步骤帮你快速定位到“哈希碰撞”这个源头。第一步看 CPU 火焰图。如果 HashMap 是元凶火焰图上通常能看到java.util.HashMap.getNode或者putVal占了很高的比例。注意getNode是链表遍历的核心方法正常数据量下它不该有存在感一旦它出现在热点里基本可以断定碰撞严重。第二步看 GC 日志和堆转储。长时间运行的 HashMap 如果链表很长节点对象会占用大量堆内存。用jmap导出堆转储然后用 MAT 或者 VisualVM 分析重点看java.util.HashMap$Node对象的数量和分布。如果某个桶下挂了上千个节点一眼就能发现。第三步写一段临时的诊断代码。比如用反射拿到 HashMap 内部的table数组遍历每个桶统计链表长度。这个过程比较 Hack但排查时很管用。import java.lang.reflect.Field; import java.util.HashMap; import java.util.Map; public class HashMapInspect { public static void main(String[] args) throws Exception { MapString, String map new HashMap(); for (int i 0; i 10000; i) { map.put(key- i, value- i); } Field tableField HashMap.class.getDeclaredField(table); tableField.setAccessible(true); Object[] table (Object[]) tableField.get(map); int maxChain 0; for (Object node : table) { if (node null) { continue; } int len 0; Object cur node; while (cur ! null) { len; Field nextField cur.getClass().getDeclaredField(next); nextField.setAccessible(true); cur nextField.get(cur); } if (len maxChain) { maxChain len; } } System.out.println(capacity table.length , maxChain maxChain); } }这个工具类可以临时加到工程里也可以直接在测试环境用。它能告诉你当前 Map 的容量、最大链表长度和超过阈值的桶数量比靠猜靠谱得多。第四步也是最关键的一步回过来检查 Key 类的hashCode和equals实现。很多事故的根因都是团队成员把某个实体类当 Key 用而这个实体类的hashCode恰好返回了一个常量或者只依赖某个极少变化的字段甚至直接用了Object默认实现。找到问题类把它的哈希逻辑改成分布均匀的写法问题通常就解决了。4.2 Key 类设计规范equals 与 hashCode 的正确打开方式这里说几个可以直接抄作业的规则。规则一如果你不确定 Key 类的hashCode该怎么写优先用java.util.Objects.hash()组合多个不可变字段。比如return Objects.hash(id, type, region);JDK 底层用的是 31 作为乘数分布已经足够均匀。31 这个质数的好处是乘法可以被 JVM 优化成移位和减法31 * x等价于(x 5) - x算得快。规则二equals里参与比较的字段必须与hashCode里参与计算的字段保持一致。如果equals用了五个字段hashCode只用了一个字段就会出现“equals 相等的对象 hashCode 不等”的情况HashMap 会认为它们不是同一个 Key可能造成数据重复和查询不到。规则三Key 对象最好是不可变的。HashMap 存的是引用不是拷贝。如果 Key 的字段在放入 Map 之后被修改hashCode就会变化但桶位不会跟着变原本的键值对就“丢”在了旧桶里。String、Integer 这些类本身就是不可变的天然适合当 Key。规则四如果确实要用自定义对象做 Key并且业务字段比较多可以考虑只把id作为 hashCode 和 equals 的依据。虽然极端情况下不同对象可能 id 相同而其他字段不同但通常业务上 id 就能唯一标识一条记录了。这个设计的核心是“删繁就简”让哈希值集中反映业务唯一性。4.3 从根上规避冲突容量预估与哈希分布优化如果已经确认碰撞存在但业务上没法立刻改 Key 类的实现有几条临时方案可以过渡。第一提高初始容量。扩容之前的数据搬迁本身也是一次性能重排如果你能预估数据量把容量直接调大让 Map 在生命周期内完全不需要扩容很多问题会自然缓解。第二给自定义 Key 的hashCode增加随机扰动。比如引入一个与业务无关的种子字段或者用ThreadLocalRandom.current().nextInt()参与计算。注意这样做的代价是同一个 Key 在不同 JVM 进程里的哈希值不同只要你不依赖跨进程一致性是可以接受的。第三改用专门处理冲突的数据结构。TreeMap会在 Key 上做自然排序或自定义排序查找复杂度稳定在 O(log n)不依赖哈希分布。ConcurrentSkipListMap也是类似思路而且支持并发。如果碰撞的根因是 Key 本身能取的合法值有限、天然容易冲突这类结构会更合适。第四如果是恶意攻击导致的哈希碰撞即有人故意构造大量hashCode相同的 Key 打垮服务可以考虑在应用层对 Key 做一次合法性校验或者干脆换用Redis之类的分布式缓存承接这部分访问把压力从 JVM 内转移出去。5. 高频问题的排查实录与避坑指南5.1 迭代时修改 Map 为什么会抛 ConcurrentModificationException这是 HashMap 面试里最经典的八股题之一但在实际工程里它也会冒出来比如有人在for-each遍历 Map 的同时在循环体里调用了put或remove。HashMap 内部维护了一个modCount字段每次结构性修改都会自增。迭代器创建时会记住当时的modCount每次next()都会检查当前modCount是否和预期值相等不等就抛异常。这个机制叫 fail-fast目的是尽早暴露并发修改问题而不是把数据搞坏。正确做法是如果需要遍历过程中删除元素用迭代器的remove()方法它会同步更新预期modCount如果需要批量删除可以先把要删的 Key 收集到一个 List 里遍历结束后统一调用removeAll或循环remove。还有一种常见场景是更新现有 Key 的 value这不属于结构性修改不会触发异常。5.2 线程安全场景下的替代方案再强调一遍HashMap 不是线程安全的。JDK 1.7 下并发扩容可能产生环形链表get 操作会死循环JDK 1.8 下虽然解决了死循环问题但仍然存在并发 put 时数据覆盖、size 统计不准的问题。有并发需求时别指望靠外部加锁来和 HashMap 配合直接用ConcurrentHashMap更省心。ConcurrentHashMap的底层在 JDK 1.8 后放弃了 JDK 1.7 的分段锁改成了 CAS synchronized 的方式对数组某个桶位进行写入时先尝试用 CAS 把节点放进空桶如果桶位已经有节点就对这个桶的链表头节点加锁锁粒度更细并发冲突更少。它把读操作设计成无锁get永远不需要加锁所以读多写少场景下的吞吐量非常可观。如果你只是需要一个线程安全的简单 Map 做缓存Collections.synchronizedMap(map)也能凑合但它把所有操作都变成全表锁并发一高就劣化。工程上还是优先ConcurrentHashMap。5.3 null key 的特殊待遇与常见误解HashMap 允许存一个 null Key底层会把 null 的哈希值当成 0所以 null Key 一定会被放到table[0]这个桶位。这个设计方便了某些习惯用 null 表达“无”的业务场景但有两个隐患。第一table[0]可能同时挂着其他正常 Key 的节点。当数组长度是 16 时所有哈希值低位为 0 的 Key 也会落在 0 号桶与 null Key 共享同一条链表。如果你业务里有大量哈希尾数为 0 的 Key又塞了一个 null Key0 号桶的链表长度会被双重叠加。第二ConcurrentHashMap不允许 null Key 和 null Value因为并发场景下无法区分“不存在”和“值为 null”。如果你的代码从HashMap迁到ConcurrentHashMap别忘了一并处理 null 值的兼容。5.4 几个面试经典问题的答题角度到了复习阶段下面几个问题基本是必考项我给出可以直接套用的答题框架。问题一为什么 HashMap 容量必须是 2 的幂不传 2 的幂会怎样核心答三点位运算替代取模速度快(n - 1) hash能保证下标均匀覆盖整个数组区间传入非 2 的幂时tableSizeFor会向上取最近的 2 的幂。问题二为什么链表长度到 8 才转红黑树先说概率负载因子 0.75 时链表长度达到 8 的概率约千万分之六正常数据几乎不会触发。再说性能红黑树节点占用内存比链表节点大维护成本高只在碰撞异常时才使用。顺带补充退化阈值 6 是为了防止阈值附近频繁震荡。问题三重写equals为什么要重写hashCode直接抛出两个反例只重写equals两个相等的对象hashCode不同HashMap 会放进不同桶语义崩塌只重写hashCode两个hashCode相等的对象equals不等会挂同一条链表影响性能。正确写法是两者保持字段一致。问题四HashMap 的 key 是可变的会有什么后果记住一句话放入 Map 之后再修改 Key会让hashCode变化但桶位不变后续根据新哈希值找不到旧节点数据相当于永久丢失。最后分享几个我自己的实操建议写了这么多其实最想对各位说的是排查 HashMap 问题不要一开始就钻源码先把“Key 类的 hashCode 和 equals 是否规范”这条基线检查掉。我接过好几个类似的线上事故答案最后都指向同一个地方——某个实体类作为 Key 时hashCode写得太随意数据量一上来就暴露了。这其实是个很好的提醒技术方案再漂亮也敌不过底层数据结构的“地基”没打牢。平时写代码时多加一句Objects.hash(...)可能就省掉一次凌晨三点的排查。另外一个容易被忽略的习惯是多线程环境里别图省事直接用 HashMap哪怕当前看起来并发量不大也要为后续流量预留空间否则迟早要还债。