“当两个不同的 Key 撞在了一起”这句话背后的“事故”现场就是 HashMap 的哈希碰撞。做 Java 开发这么多年HashMap 我几乎天天在用但真正让我把它的脾气摸清楚的恰恰是线上那一场因为“撞 Key”引发的性能抖动。今天这篇文章不讲废话直接拆开 HashMap 的肚子看看它内部到底是怎么处理“撞车”的以及作为一个普通开发者遇到“撞车”、甚至因此掉进坑里时该怎么急救、怎么预防。不论你是正在准备面试还是工作中碰巧踩到了 HashMap 的坑这篇应该都能帮上忙。1. 事故现场Key 是怎么“撞车”的1.1 从“停车找车位”说起HashMap 的基本存取逻辑很多人学 HashMap 的时候喜欢把它的结构比喻成“数组加链表”。这个比喻没错但我觉得更贴切的场景是“一个大型停车场配合一套找车位系统”。想象一下你开着一辆车对应一个 Key-Value 条目进停车场门口的系统会告诉你“去 3 号区 7 号位”。你到了 3 号区发现 7 号位已经停了另一辆完全不同的车这就是“撞车”。在 HashMap 的世界里那个决定你去哪个区哪个位的系统就是哈希函数一块块停车区就是一个个“桶”bucket术语上叫 bin。但这套找车位系统有个非常核心的设计思路它希望你把车停到哪个位置仅取决于你的车牌号Key本身而不是车辆进场时的顺序。所以 HashMap 会先对 Key 调用hashCode()得到一个 32 位的整数然后再做一次扰动处理和一次按位与运算最终得到一个数组下标。这个下标决定了这个 Key-Value 条目会被放进哪个桶里。这里的重点在于数组下标是有限的比如初始容量是 16下标范围就是 0 到 15而 Key 的hashCode()范围是天文数字。所以从数学上就注定了必然存在两个完全不相同的 Key它们经过计算后得到相同的数组下标。这并不是 BUG而是有限资源下无法避免的数学事实。用专业一点的话说这就是哈希碰撞。1.2 哈希碰撞的本质为什么不同的 Key 会落到同一个桶聊到这里可能有人会问既然hashCode()不同那下标会不会不同答案是不一定。HashMap 拿到的“车位号”并不是直接用原始hashCode()而是要经过两步处理。第一步HashMap 会对hashCode()做一个高 16 位和低 16 位的异或运算这一步叫“扰动函数”。它的作用是把高位信息也混入低位这样即使你的 Key 的 hashCode 分布在高位变化、低位不变最终映射到数组下标时也能更均匀。第二步再把扰动后的哈希值跟数组长度减 1length - 1做按位与运算。因为数组长度是 2 的幂次方比如 16length - 1的二进制就是低位全是 1高位全是 0所以按位与的结果就相当于“只保留低位”。这一步相当于停车场系统只看了你车牌号的最后几位来分配车位。看得出来了吧如果两个 Key 的哈希值经过扰动后低的那几位恰好相同那么不管它们高 32 位、或者其他什么特征有多大的差异最终都会被分配到同一个桶里。这就是“撞车”的底层原因之一。也有一种更“人工制造”的撞车你自定义了一个对象作为 Key但是这个对象的hashCode()写得极其草率比如直接返回一个常量或者返回的哈希值高度集中在某个小范围。这就会导致所有 Key 都涌进同一两个桶里HashMap 直接退化成链表查询效率从 O(1) 掉到 O(n)。这种情况我见过不少典型的“人祸”。2. 底层原理HashMap 是怎么处理“撞车”的2.1 JDK 8 之前单靠链表硬扛最开始 Java 的 HashMap 使用了“数组 链表”的方式发生碰撞的元素就串成一个链表挂在同一个桶上。你要查找其中一个元素就得沿着链表一个个比过去直到找到 equals 为真的那个节点。在元素少的时候链表查找还凑合。但一旦某个桶的链表特别长比如几千个元素全挂在同一个桶上查找效率就会惨不忍睹。JDK 8 之前之所以在极端场景下容易成为性能瓶颈原因就在这里。我记得早年的时候有些攻击者甚至专门构造大量会发生碰撞的 Key去制造“哈希洪水”把 HashMap 的查询复杂度人为拉高到 O(n^2)从而拖垮整个应用。这个思路本质上就是利用 HashMap 链表过长的弱点。2.2 JDK 8 的升级链表不是唯一的解法红黑树来了JDK 8 之后HashMap 的“事故处理机制”升级了。现在它在单个桶中引入了一个阈值判断当一个桶中的元素个数达到 8 个时并且整个数组容量达到 64链表就会转换成红黑树TreeBin。红黑树的查找复杂度是 O(log n)比起链表的 O(n) 要好得多。反过来当红黑树的元素个数下降到 6 个时它又会变回链表避免树结构在数据少时的开销。为什么阈值是 8这里有个很经典的统计学依据在随机哈希码的情况下单个桶内元素个数符合泊松分布到达 8 个元素的概率已经低于千万分之一。换句话说在正常使用场景下链表转红黑树几乎不会发生。但这也恰恰说明一旦你发现自己的 HashMap 里真的出现了红黑树节点那大概率说明你的 Key 的哈希分布出了问题或者你碰到了恶意构造的碰撞场景。这里我多说一句树的节点是普通链表节点的两倍大小内存开销更高。所以 JDK 源码里搞的“8 转树、6 转回链表”这个设计其实是在内存和查询性能之间做的一个平衡。它不是想让大家依赖红黑树去解决哈希碰撞而是作为一道“最后防线”防止极端情况把系统打垮。2.3 扩容机制反应不过来就会连环事故还有一类“事故”不是 Key 故意撞车而是 HashMap 容量不够导致的“被动拥挤”。当 HashMap 中的元素数量超过容量 × 负载因子时它就会触发扩容。默认负载因子是 0.75比如初始容量 16元素到了 12 个就会扩容到原来的两倍也就是 32。扩容的过程不是简单地“把数组变宽”而是要重新计算所有已有元素的桶位置。因为数组长度变了length - 1变了按位与的结果也可能变。所以扩容意味着每一个元素都要拿出来重新做一遍定位、插入。扩容期间如果你还在并发地读写这个 HashMap那就会遇到更头疼的问题JDK 7 的 HashMap 在并发扩容时链表反向插入还可能导致循环链表下一次 get 某个不存在的 Key 时就会无限循环CPU 直接飙到 100%。虽然 JDK 8 在插入方式上做了调整不再那么容易形成循环链表但并发下的线程安全问题依旧存在——线程之间相互覆盖、丢失数据都可能发生。所以如果你的同事跟你说“HashMap 是危险的”他说的不是 HashMap 本身而是我们不规范的使用方式。3. 急救指南写代码时如何降低 HashMap “事故率”3.1 正确重写 hashCode 和 equals这是一切的起点多数 HashMap 的“事故”源头都是因为 Key 的hashCode()和equals()不一致引起的。HashMap 的规则很简单先用hash找到桶再用equals判断同一个桶里有没有相等的 Key。如果你的hashCode()说两个对象不相等返回了不同值但业务上这两个对象其实是同一个 Key那就很可能出现你存进去一个值却取不到的情况。这不是危言耸听我见过有人直接用 StringBuilder 做 Key结果每次new StringBuilder(abc)都存不进去因为新建的两个 StringBuilder 对象的 hashCode 是不同的。也有人重写了equals()却忘记重写hashCode()导致两个内容一样的对象“equals 相等但 hashCode 不同”HashMap 在查找时根本不会把这两个对象放到同一个桶里。规范做法是如果自定义类要用来当 Key必须同时重写hashCode()和equals()并且保证“equals 相等的两个对象hashCode 一定相等”。至于字段选择尽量使用业务上唯一且不可变的字段。最省事的办法是让 IDE 帮你生成或者在 Java 7 直接用java.util.Objects.hash()。我不提倡手写散列逻辑因为很容易写出低质量的哈希函数。3.2 合理设置初始容量和负载因子很多人直接new HashMap()一把梭这在数据量小的时候没有感觉但数据量一大就会频繁扩容扩容期间的 CPU 消耗和内存复制非常可观。如果事先知道大约要存放多少条数据就应该指定初始容量。有一个很实用的计算方式期望存储的元素个数除以负载因子得到一个容量值再向上取到 2 的幂。例如我预计放 1000 条数据1000 / 0.75 ≈ 1333.3向上取 2 的幂那就是 2048。直接new HashMap(2048)就能在很大程度上避免中途扩容。负载因子这个参数日常开发我基本不动它。0.75 是空间和时间的最佳折中。如果你特别吃内存可以把负载因子调大一些比如 1.0但这样冲突概率会提高查询会变慢反过来如果你极度追求查询速度把负载因子调小到 0.5 或 0.6意味着数组更早扩容占用内存更多。没有完美参数只有适合你场景的参数。3.3 自定义 Key 类的实战要点我强烈建议能用基本类型包装类如 Integer、Long、String当 Key 就用它们不要动不动造自定义类。如果必须用自定义类那就把它们设计成不可变的。所有字段用final修饰并且不要在存进 HashMap 之后修改 Key 的字段值。为什么强调这一点因为一旦 Key 存进 HashMap 之后其 hashCode 依赖的字段变了那么它原本所在的桶位置就不会再匹配新的 hashCode。下次你想 get 这个 KeyHashMap 会按新的 hashCode 去找桶自然找不到。轻则一次查询失败重则你把这个“变异”的 Key 再放进去同一份逻辑数据在 Map 里出现两份后续处理数据时直接乱套。我自己吃过这个亏以前写过一个报表系统把含有“统计日期”字段的对象当 Key中途改了对象里的日期结果在 Map 里查不到数据排查了半天才发现是 Key 被改动了。那之后我给自己定了一条规矩放进 Map 的 Key不可变是底线。3.4 特别注意不要用可变对象做 Key除非你能克制住刚才提到的不可变原则我再展开聊一点。Java 世界里String 和 Integer 是不可变的天生安全但像java.util.Date虽然很多人当作 Key 用它却是可变的。你存进去之后如果后续调用了setTime()或者修改它的内部时间那你之前存的位置和之后查的位置就对不上了。如果真的遇到“必须用一个会变化的时间点做 Key”的需求我的方案是不要直接拿 Date 当 Key而是把它格式化成固定字符串比如2024-12-01或者使用 LocalDate 这种不可变类型。这不算什么高深技巧只是从源头上避免自己犯低级错误。4. 实战排查从“运行缓慢”到“定位撞车”4.1 典型案发现场明明数据量不大为什么 100% CPU有一次线上服务报警某个接口的 TP99 从 20ms 涨到了 2000msCPU 居高不下。我第一反应是看 GC 日志、看线程栈。后来定位到某个热点方法里有一段map.get(key)频繁调用而且这个 map 的初始容量只有 16但是里面装了将近 10 万条数据。因为 hash 分布极差大量 Key 挤在少数几个桶上链表极长每次 get 都退化成接近线性扫描。这是相对好排查的因为线程栈里能看到频繁调用 HashMap.get 的栈帧。麻烦的是那种 Key 本身 hashCode 很均匀但因为扩容导致的性能抖动。那种问题光看栈不一定看得出来需要结合火焰图、GC 日志、堆内存快照一起看。4.2 排查工具看透 HashMap 的“内脏”坦白说Java 默认没提供太方便的 HashMap 可视化工具但我们有办法。一个很直接的手段是用 JOLJava Object Layout或者 MATMemory Analyzer Tool去分析堆转储看看 HashMap 里的 table 数组中每个桶挂了多少节点。如果某些桶的节点数量远大于其他桶基本可以断定哈希函数分布有问题或者 Key 设计有问题。如果你想在运行期实时查看那就只能在代码里打日志或者写一个临时方法遍历 HashMap 的 table把每个桶里的元素个数打印出来。我自己写过一个小工具方法接收一个 HashMap输出总共多少个桶、最大链长是多少、多少个桶超过 5 个元素。输出结果一出来问题在哪里几乎一目了然。另外JDK 里还有一个冷门但好用的思路如果你的 Key 是 String 类型String 的哈希算法是多项式散列分布一般不会太差。真正容易出问题的是把多个字段拼接成字符串再当 Key比如userId _ date _ type。看似没问题但如果你拼接顺序设计得不好很容易在特定业务数据下产生哈希碰撞。这一点我建议在设计 Key 时多做一步“小样本数据分布检查”。4.3 快速诊查清单我把平时排查 HashMap 问题的步骤整理成一个速查清单你可以直接照着做先定位到可疑代码确认是 HashMap.get 还是 put 慢。打印 map.size() 和 table.length看元素数量和容量是否严重不平衡。如果 size 很大先看初始容量是否给得太小导致 Ljava 扩容过度。用 MAT 分析堆转储看哪些桶的链表过长。检查自定义 Key 类是否重写了恰当的 hashCode 和 equals。检查 Key 是否在存放后被修改过字段。确认代码是否存在多线程同时读写同一个 HashMap 的情况。这套流程执行下来大部分“事故”都能快速定位不至于一头扎进业务代码里瞎猜。5. 从 HashMap 到其他 Map什么时候该换方案5.1 撞车严重时的直接“急救”换一个 Map 实现如果业务并发不高只是单线程场景但哈希碰撞特别严重除了优化 hashCode还有一个简单立竿见影的方案换用TreeMap。TreeMap 基于红黑树实现Key 的顺序性和查找效率是 O(log n)。它的前提是 Key 必须可比较实现 Comparable或者传入 Comparator。虽然 O(log n) 不如 HashMap 理想情况下的 O(1)但要比“链表退化成 O(n)”的 HashMap 强太多。另外如果你知道 Key 是有限范围内的整数比如 0 到 1000那你根本不需要 HashMap直接用数组或者 EnumMap 就能解决问题。EnumMap 的底层是数组按键的枚举序号直接索引性能和内存都远胜 HashMap。如果你的 Key 是枚举类型请一定优先考虑 EnumMap。5.2 并发现场ConcurrentHashMap 才是你的选择很多线程安全的“事故”源于程序员直接在多个线程里操作同一个 HashMap还指望它不出问题。这在 JDK 7 里可能导致死循环在 JDK 8 里虽然不容易死循环但数据丢失和脏读不可避免。如果必须并发读写我只有一个建议使用ConcurrentHashMap。它采用了 CAS synchronized 锁机制在 JDK 8 里对单个桶的访问做细粒度加锁并发性能很优秀。注意即使使用 ConcurrentHashMap也要避免在遍历的同时修改结构否则会抛ConcurrentModificationException或者得不到一致的遍历结果。关于 ConcurrentHashMap 的遍历一致性源码注释里讲得很清楚它的迭代器是弱一致的。也就是说你在遍历过程中别的线程对 Map 的修改不一定立刻可见。如果你需要强一致的快照那就在遍历前手动加锁或者干脆把 Map 拷贝出来再遍历。5.3 哈希冲突攻击一个容易被忽视的隐患平时写业务代码很少有人会把“哈希冲突攻击”放在心上。但当你面对的是对外暴露的 HTTP 接口且接口参数会被解析成 Key-Value 结构时如果有人精心构造大量发生碰撞的 Key比如伪造表单字段名就可能让 HashMap 的某几个桶出现超长链表进而拖垮 CPU。JDK 8 的红黑树在一定程度上缓解了这类攻击的破坏力但不能从根本上免除计算压力。有安全洁癖的话建议在网关层统一限制请求体的字段数量或者对特别敏感的入口使用基于树结构的 Map比如 TreeMap来存储解析结果从根本上让刻意构造的哈希碰撞失效。6. 面试高频点为什么 HashMap 的容量总是 2 的幂次6.1 从位运算说起为什么不是 17 也不是 18如果你仔细看源码会发现 HashMap 的容量总是要求是 2 的幂次方。即使你构造时传了 17HashMap 也会通过一系列右移和或运算帮你向上取整到 32。这是因为它的取模操作不是真的取模而是hash (length - 1)。为什么用位运算因为位运算比%模运算快得多。而hash (length - 1)要想等价于hash % length前提恰恰是 length 是 2 的幂次方。举个例子容量为 16 时length - 1 15二进制 1111hash 对它做按位与等价于只保留 hash 的低 4 位范围是 0 到 15正好对应 16 个桶。如果容量不是 2 的幂次比如 17那length - 1是 16二进制 10000按位与的结果就只有两种可能0 或 16。这会导致大量 Key 集中在少数桶里撞车概率爆炸式增长。这就是为什么 HashMap 宁可多做几次位运算调整容量也不愿意用一个“看似正常”的任意数字。6.2 扩容后元素为什么可能落在“原位置”或“原位置 旧容量”这也是面试官爱问的细节。扩容翻倍之后元素新位置有两种可能要么还在原来的下标要么在“原下标 旧容量”。我用一个实例说明旧容量是 16某个元素的哈希值是 7那么它所在的桶是7 15 7。扩容后容量是 3232 - 1 31二进制 111117 31还是 7。所以它在原位置。如果哈希值是 2323 15 7在旧容量为 16 时它在 7 号桶。扩容后23 31 23结果是 7 16也就是“原位置 旧容量”。这个现象背后的数学本质就是扩容后多出来一位二进制位参与按位与运算这一位是 0 还是 1直接决定了元素是留在原地还是搬到“原位 旧容量”那边。JDK 8 的扩容代码里就专门检查了这一位省去了重新计算每个元素哈希值的开销只通过位运算就能把旧数组里的链表拆分成“低位链”和“高位链”再分别放到新数组的对应位置。这个方法不仅快而且能保持链表内元素的相对顺序避免 JDK 7 里扩容时“头插法”导致的链表反转和循环引用问题。这里没必要死记结论你只需要理解扩容不是无脑重建而是基于二进制特性的一次高效重定位。7. 性能对比链长多少时 HashMap 会“感知到痛”7.1 一张表看懂不同链长下的查询成本我整理了一张不同场景下的对比表你可以直观感受一下场景数据结构平均查询复杂度极端情况复杂度适用场景理想 HashMap数组O(1)O(1)绝大多数业务场景冲突严重的 HashMap数组 超长链表O(n)O(n)不推荐需要优化冲突严重的 HashMapJDK8数组 红黑树O(log n)O(log n)抵抗极端碰撞TreeMap红黑树O(log n)O(log n)需要 Key 有序ConcurrentHashMap数组 链表 CAS/synchronizedO(1) 平均O(log n) 极端并发环境平时我们总说“HashMap 是 O(1)”这句话成立的前提是哈希分布足够均匀。当碰撞多起来实际复杂度会逐渐向 O(log n) 甚至 O(n) 漂移。所以我在性能调优时不只看平均耗时还会专门观察有没有哪个桶的链长异常偏大。一个友好的参考标准在容量 1024、数据 500 条的情况下最大链长超过 10就值得警惕。7.2 定位“热点桶”的小脚本如果你想快速检查现有 HashMap 的健康状况可以用下面这个思路写个临时工具。它直接反射拿到 HashMap 内部的 table 数组统计每个桶的元素数量。import java.lang.reflect.Field; import java.util.HashMap; public class HashMapInspector { public static void inspect(HashMap?, ? map, String name) throws Exception { Field tableField HashMap.class.getDeclaredField(table); tableField.setAccessible(true); Object[] table (Object[]) tableField.get(map); if (table null) { System.out.println(name is empty); return; } int maxBinSize 0; int overEight 0; int sum 0; for (Object node : table) { if (node null) continue; int size binSize(node); sum size; maxBinSize Math.max(maxBinSize, size); if (size 8) overEight; } System.out.printf(%s: table.length%d, size%d, maxBinSize%d, binsWithMoreThan8%d%n, name, table.length, map.size(), maxBinSize, overEight); } private static int binSize(Object node) throws Exception { int count 0; // 这里需要区分普通链表节点和 TreeNodeTreeNode 是链表节点的子类 // 可以通过 next 字段遍历如果是 TreeNodebin 里实际是 TreeNode 链。 // 用递归或者 while(next ! null) 都可以我这里只做示意。 Object cur node; Field nextField getNextField(cur); while (cur ! null) { count; cur nextField.get(cur); } return count; } private static Field getNextField(Object node) throws Exception { // 注意TreeNode 类继承了 Node字段 next 定义在 Node 中 Class? clazz node.getClass(); while (clazz ! null) { try { Field f clazz.getDeclaredField(next); f.setAccessible(true); return f; } catch (NoSuchFieldException e) { clazz clazz.getSuperclass(); } } throw new NoSuchFieldException(next); } }写这段代码不是为了让你生产环境去跑而是为了让你在本地调试、分析“事故现场”时有个趁手工具。我在定位线上问题时通常会先在压测环境复现再用这个工具看一眼最大链长和分布基本就能判断撞车到底是个别现象还是系统性问题。8. 常见问题速查表症状可能原因急救方案get 返回 null但数据明明 put 过Key 的 equals/hashCode 不一致或 Key 可变被修改重写 hashCode/equalsKey 设计为不可变某个接口性能突然劣化哈希碰撞严重链长过大检查 Key 分布、调整初始容量、换 TreeMap并发环境下数据丢失多个线程同时操作同一个 HashMap换成 ConcurrentHashMap多个 Key 对应同一桶hashCode 分布差优化哈希函数使用 Objects.hash遍历时抛 ConcurrentModificationException遍历中修改了 Map 结构使用迭代器的 remove或另案处理JDK 7 升级 JDK 8 后 HashMap 行为变慢可能是树化/退化逻辑异常确认 JDK 版本检查 Key 的 hashCode 分布排查 HashMap 相关的问题最忌讳的是瞎改代码。我的经验是先找到“现场证据”比如堆转储、日志或你写完的那个检查工具的输出再对症下药。很多看起来玄乎的问题只要把桶的分布打出来真相立马浮出水面。说到最后分享一点个人心得。HashMap 源码我前前后后读过好几遍每次以为自己懂了过一阵子碰到新问题又发现理解不够深。但有一次我真正把“两个不同 Key 可以落在同一个桶”这件事用极端压力测试的方式跑了一遍之后我对哈希冲突的感受就完全不一样了——不再把它当成课本上的概念而是当成了一个只要设计 Key 稍有不慎就会付出的真实代价。那次之后我写任何 Map 相关代码都会问自己一句这个 Key 的哈希质量靠得住吗这个 Key 会变吗并发环境下安全吗这三个问题问完HashMap 的“事故”大概率就不会找上你。