JDK8 HashMap源码拆解：散列、红黑树与扩容机制一次讲透-北京尧图网络

1. 先看清HashMap的底层结构数组、链表、红黑树是怎么拼在一起的HashMap大概是Java容器里被面试官问得最多、被线上故障坑得最惨的一个类。我最早认真读它的源码正因为某个跨平台系统的压测频繁出现CPU100%抓完线程栈发现所有线程都卡在HashMap的get方法上。那会儿才意识到只背“键值对数组加链表”这种结论远远不够。这篇文章基于JDK8的HashMap源码把它的底层结构、hash散列、put/get流程、resize扩容以及几个最容易踩的生产环境问题一次性讲透。1.1 核心字段table、size、threshold、loadFactor分别是什么打开HashMap的源码第一眼看到的是这一组静态常量static final int DEFAULT_INITIAL_CAPACITY 1 4; // 16 static final int MAXIMUM_CAPACITY 1 30; static final float DEFAULT_LOAD_FACTOR 0.75f; static final int TREEIFY_THRESHOLD 8; static final int UNTREEIFY_THRESHOLD 6; static final int MIN_TREEIFY_CAPACITY 64;真正存数据的地方是transient NodeK,V[] table这是一个Node节点数组。Node节点内部有四个字段hash、key、value、next。next指向同一个桶里的下一个节点所以数组的每一个位置都是一个链表头当链表太长时又会整体转换成红黑树。table数组的长度默认是16但不是在new HashMap()时立刻创建的。源码里table的初始化是懒加载第一次put的时候才通过resize()把数组建出来。这么做的原因很简单很多Map创建之后根本不会放数据没必要为每个实例都提前分配一块连续内存。loadFactor默认0.75threshold capacity * loadFactor。threshold不是容量上限而是触发扩容的“水位线”。比如说容量是16threshold就是12当size一旦超过12下一次put就会触发扩容到32。0.75这个值本质上是在时间和空间之间取的平衡太小浪费内存太大容易让冲突变多链表和红黑树更早出现读写性能下降。1.2 JDK8为什么要引入红黑树阈值8和6又是怎么定的在JDK7及以前HashMap的每一个桶都只有链表。如果很多key的hash撞到同一个桶get就变成遍历一个很长的链表最坏情况O(n)。对在线服务来说一个接口里如果频繁get这种退化的链表遍历足以让CPU使用率直接拉满。JDK8的改进是当单个桶里的节点数达到TREEIFY_THRESHOLD8并且table数组长度不小于MIN_TREEIFY_CAPACITY64这个桶就从链表转换成红黑树。树化后查找复杂度从O(n)降为O(log n)。红黑树的优点不只是平衡更重要的是插入和删除不需要像AVL树那样频繁调整整体更适合HashMap这种频繁读写的数据结构。这里有两个细节容易被忽略。第一不是链表长度一到8就立刻树化数组长度小于64时resize()会优先把数组扩大一倍让数据分散开而不是马上转树。第二扩容拆分红黑树时如果某个桶里的节点数量降到UNTREEIFY_THRESHOLD6以下会从树退回到链表。8和6之间留了2的缓冲避免节点数量在边界附近震荡时反复树化和退化这个设计很像操作系统里“高水位”“低水位”的思路。2. hash散列与桶下标计算真正决定性能的不是put而是位运算很多人以为HashMap算桶下标用的是key.hashCode() % size其实不对。JDK8里面两步走先扰动哈希码再用位运算取模。2.1 高16位异或低16位到底防的是什么先看hash方法static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }key为null时hash为0所以HashMap允许一个null键。不为null时把key的hashCode赋值给h再把h右移16位和原来的h做异或。这一步叫扰动函数。为什么不直接用hashCode因为table数组长度默认是16计算下标用的掩码(n-1)只有低4位是1数组长度再大参与下标计算的通常也只是低位。而hashCode是一个32位整数如果对象本身的hashCode分布不好低位很容易出现大量重复高位的信息就白白浪费了。把高16位异或到低16位相当于让高位也参与后续的取模从而让散列结果更均匀。这一步代价极小但对碰撞率的影响非常明显。2.2 为什么长度必须是2的幂以及tableSizeFor做了什么桶下标计算是tab[i (n - 1) hash]这里用的是按位与等效于hash % n但前提是n必须是2的幂。所以HashMap的容量永远要求是2的幂。你new HashMap(19)的时候它不会真的用19当初始容量而是通过tableSizeFor方法把它变成大于等于19的最小的2的幂也就是32。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; }这段代码把cap减1后从最高位的1开始通过连续右移和或运算把后面所有低位全部填成1最后加1得到2的幂。用(n-1) hash而不是取模主要有两个原因一是在绝大多数CPU上位运算比取模指令快二是当n是2的幂时相当于只取hash的低log2(n)位作为下标这为后面扩容时“无需rehash”的分流方案打下了基础。这一点在讲resize时再展开。3. put流程逐行走一遍从懒初始化到链表树化的完整分支判断put的入口是put(K key, V value)真正干活的putVal方法。理解putVal基本就理解了大半个HashMap。3.1 new HashMap()为什么没有立刻分配数组确认一下懒加载的代码路径final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) { NodeK,V[] tab; NodeK,V p; int n, i; 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 { // 桶里已经有节点进入冲突处理分支 } modCount; if (size threshold) resize(); afterNodeInsertion(evict); return null; }第一次put时table为null直接进入resize()去创建默认容量16的数组。这一步也解释了为什么很多人new HashMap()后看内存占用几乎没区别真正的数据容器是在首次写入时才建出来的。3.2 putVal的冲突处理覆盖、追加、树化分别走哪条路桶下标i算出来后如果该位置为null直接创建一个新节点放进去这是最理想情况。有冲突时先判断第一个节点p是否和当前key相同if (p.hash hash ((k p.key) key || (key ! null key.equals(k)))) e p;这里先比hash再比引用最后才用equals。因为hash相等的两个key不一定相等但hash不等的一定不相等先比hash可以快速过滤掉绝大多数无关节点。如果p是TreeNode说明这个桶已经树化改走putTreeVal。否则遍历链表在链表尾追加新节点同时用binCount统计当前节点数。遍历过程中如果找到相同key就跳出循环准备替换value。真正替换value的代码是这样的if (e ! null) { V oldValue e.value; if (!onlyIfAbsent || oldValue null) e.value value; afterNodeAccess(e); return oldValue; }这意味着put发现有相同key时不会新建节点而是复用旧节点、覆盖value。很多人忽略的“Map里面放null值”也是在这里体现的只有当onlyIfAbsent为true且旧值不为null时才不覆盖。链表追加完成之后还有这一段if (binCount TREEIFY_THRESHOLD - 1) treeifyBin(tab, hash);binCount从0开始计数binCount到了7就说明链表里有8个节点于是尝试树化。但treeifyBin内部会先检查tab.length是否小于MIN_TREEIFY_CAPACITY如果小于64就会先扩容而非转树。这是HashMap里“先扩大桶数量再尝试转红黑树”的优先级体现。3.3 树化阈值8和最小容量64为什么缺一不可假设哈希函数设计得非常糟糕大量key都映射到同一个桶链表会越来越长查询退化成线性扫描。这时如果数组容量还很小正确做法是扩大数组让数据往更多桶里分散而不是为这一个桶建一棵树。所以64这个下限保证了树化之前底层容器已经有一定规模。反过来如果桶内节点达到8但数组容量已经很大说明这一小片区域碰撞极端严重这时候转红黑树才有意义。红黑树本身每个节点TreeNode比普通Node多维护parent、left、right、prev四个引用内存开销明显更大。所以HashMap只在“冲突极端严重”的条件下才树化普通场景下用链表就已经很便宜了。4. resize扩容过程拆解为什么JDK8不需要重新计算每个桶的下标扩容是HashMap源码里最容易被讲错的一段。JDK7的扩容需要把每个节点重新计算hash、重新放入新数组JDK8把这件事变成了“要么原地不动要么整体挪动oldCap的距离”。4.1 新容量和新阈值怎么算resize的开头是一系列容量和阈值计算if (oldCap 0) { if (oldCap MAXIMUM_CAPACITY) { threshold Integer.MAX_VALUE; return oldTab; } else if ((newCap oldCap 1) MAXIMUM_CAPACITY oldCap DEFAULT_INITIAL_CAPACITY) newThr oldThr 1; }正常情况下新容量是旧容量的两倍新阈值也是旧阈值的两倍。当oldCap到了130这个上限后HashMap不再扩容而是把threshold抬高到Integer.MAX_VALUE意思是“能塞多少塞多少别想再扩了”。容量翻倍而不是扩大10%是为了保证长度继续保持2的幂这一步是后面位运算分流的基础。4.2 (e.hash oldCap) 0 的分流逻辑扩容时遍历每一个桶如果桶里只有一个节点直接重新计算下标放到新数组。如果桶里是链表就把链表拆成两条if ((e.hash oldCap) 0) { // 留在原索引 loTail.next e; } else { // 挪到原索引 oldCap hiTail.next e; }为什么用e.hash oldCap就能判断因为扩容时新掩码比旧掩码多了一个高位。比如容量从16变成32下标掩码从1111变成11111多了第5位。如果一个节点的hash在第5位上是0那么它在32长度下的下标与16长度时完全一样如果第5位是1新下标就是旧下标加16。oldCap恰好就是那个新增位的权重所以e.hash oldCap为0则不动为1则加oldCap。这个方案比JDK7的“逐节点rehash”聪明得多不需要重算hash不需要再次取模本质上只是把一个桶里的链表按新增的某一位拆成高低两半。这也是HashMap从“每次resize都要全量重算”到“扩容成本大幅降低”的key优化。4.3 并发下resize的经典问题JDK8到底还死不死循环JDK7的死亡循环是头插法在并发扩容时造成链表成环之后get一个不存在的key就可能无限循环。JDK8改成了尾插法并且使用高低位拆分从代码结构上确实不会再因为扩容形成环形链表所以“JDK8修复了并发死循环”这个说法在字面上成立。但千万别理解成JDK8的HashMap并发安全了。两个线程同时put各自读到同一个table引用各自扩容最后后完成的人直接把前一个人扩容后的数组覆盖掉丢数据是必然的。size计数也不是原子的多线程put后size可能偏小导致永远不会触发扩容。所以结论仍然是并发场景下老老实实用ConcurrentHashMap用HashMap做并发缓存结果往往不是报错而是数据悄悄丢失这种问题最难排查。5. get/containsKey的查找路径与hashCode、equals的三大契约坑5.1 getNode怎么用最短路径找到目标节点get方法的实际逻辑集中在getNodefinal NodeK,V getNode(int hash, Object key) { NodeK,V[] tab; NodeK,V first, e; int n; K k; if ((tab table) ! null (n tab.length) 0 (first tab[(n - 1) hash]) ! null) { if (first.hash hash ((k first.key) key || (key ! null key.equals(k)))) return first; if ((e first.next) ! null) { if (first instanceof TreeNode) return ((TreeNodeK,V)first).getTreeNode(hash, key); do { if (e.hash hash ((k e.key) key || (key ! null key.equals(k)))) return e; } while ((e e.next) ! null); } } return null; }查找顺序很清楚先看table是否为空再看桶里第一个节点接着区分当前桶是红黑树还是链表然后沿着对应结构找。整个查找过程里最短路径是“数组不为空且第一个节点就是目标”最坏情况是在红黑树里走O(log n)。containsKey与get的差别只在于有没有返回value查找逻辑完全一样。这里有个实用技巧get前不需要自己判空containsKey直接get返回null就可以认为不存在。但要注意如果业务允许value为null那么get返回null并不能区分“key不存在”和“value是null”。如果业务上把null当合法值最好用containsKey做明确判断或者干脆约定Map里不放null。5.2 hashCode重写了equals不重写或者反过来会发生什么HashMap判断两个key是否相同用的是(p.hash hash) ((k p.key) key || (key ! null key.equals(k)))。这个条件同时依赖hashCode和equals。如果类只重写equals不重写hashCode两个内容相同的对象在用equals比较时相等但它们的hashCode很可能继承自Object的地址值完全不相同于是被分到不同桶get时到不了那个桶结果就是“明明存过却取不出来”。反方向也一样只重写hashCode不重写equals两个对象即使hashCode相同也在同一个桶里但equals不相等最终还是会判断为不同key。所以实际开发中有一条铁律重写equals必须同步重写hashCode。如果用的是IDE自动生成通常没问题但如果你手写了equals而忽略了hashCode线上偶发的“查不到数据”十有八九就是这个原因。5.3 可变对象作key放进Map之后就别再改字段HashMap的桶下标在put时就已经根据当时的hashCode算好了。如果某个对象作为key放进Map之后它的hashCode相关的字段被修改再去get时算出来的下标已经和之前不一样自然找不到。即使仍能落到同一个桶equals也可能因为字段变化而返回false。更隐蔽的情况是对同一个对象修改前后分别调get前一次能取到后一次取不到排障时很容易误以为是并发问题。解决办法很简单放进HashMap的key要么用String、Integer这种不可变类型要么保证对象不可变如果必须用自定义对象至少别在put之后修改参与hashCode计算的字段。6. 线上HashMap问题排查清单从CPU飙高到查不到数据的常见原因看完源码再看实际业务里的问题大多都能从上面这些机制里找到答案。6.1 症状一线程卡在get上CPU飙高如果线程栈显示大量线程卡在HashMap.get/put多半是扩容或者链表遍历出了问题。先确认这个Map是否被多个线程共享如果是直接换ConcurrentHashMap然后压测验证。如果单线程下也慢重点查key的hashCode分布比如某个对象重写了hashCode但实现里把所有内容都一样地返回同一个固定值那所有key都会挤在一个桶里形成超长链表用测试工具统计各桶深度能立刻看出问题。6.2 症状二put进去之后get不到按顺序排查key类有没有重写hashCode和equals两个方法是否一致key对象在put之后有没有被修改有没有多个线程同时操作导致数据被覆盖。还有一个容易被忽略的细节如果自定义key的hashCode依赖随机字段比如UUID每次new对象hashCode不同那同一逻辑对象每次get时算出的桶都不一样也会产生“找不到”的假象。6.3 从源码反推参数调优已知未来大概要放expectedSize个元素初始容量可以直接设置成expectedSize / 0.75f 1。比如预估1000个元素1000 / 0.75 1约等于1334HashMap会通过tableSizeFor自动调整到2048。这么做的目的是减少扩容次数。无参构造默认16容量当数据量超过threshold时连续扩容每次扩容都要复制和重排所有节点浪费很明显。如果某个Map的key多但value更新频繁可以设置较低的负载因子比如0.6来降低冲突率。代价是内存占用变高table数组里会有更多空桶。相反如果内存紧张且能接受偶尔的链表扫描可以用0.8甚至0.9。注意loadFactor必须在构造时传入HashMap没有提供运行时修改loadFactor的公开方法。6.4 最后几点个人体会读HashMap源码最值得学的不是“八股答案”而是那套“用空间换时间、用位运算替代取模、用阈值做结构切换”的思路。后来我排查过的很多非HashMap性能问题最终都会回到“数据分布是否均匀”这个根本问题上。我的习惯是每个项目都写一个小的Map诊断工具打印出总节点数、最大桶深度、空桶比例。实测下来只要最大桶深度超过5就该检查key的hashCode了如果超过20基本上可以认定是人为的设计缺陷。这个工具的统计逻辑可以直接从源码里抄遍历table数组对每个非null桶走一遍链表或树统计深度分布。如果你刚接触源码建议从putVal和resize这两段入手先把主干逻辑画成普通的文字分支导读再补HashMap的并发问题。把这几个核心流程吃透之后再去看getNode、removeNode、replaceAll这些方法会发现它们都在讲同一套规则。源码读通的那一刻很多以前只能靠背的结论都会开始变得理所当然。

JDK8 HashMap源码拆解：散列、红黑树与扩容机制一次讲透

相关推荐

ARM64中断处理全链路解析：从GIC硬件触发到Linux驱动回调

AI日报系统设计：分层流水线架构与本地化实践

16进制文件头识别指南：从魔数表到Python实战脚本

更多资讯

SAP Fiori Elements实战：从CDS注解到RAP应用开发全解析

实训5指纹设置全解析：从传感器原理到实操与安全

语音特征提取全流程：从原始波形到MFCC特征向量

Java线程start()方法原理与线程生命周期解析

Spring Cloud Gateway GatewayFilter 源码解析与责任链机制

粒子群算法优化LQR的二级倒立摆控制设计与避坑实践

今日更新

Cephadm实战指南：Linux系统工程师的生产级Ceph集群部署与排障

不想再被 Token 额度卡脖子？把免费 API 接入 WorkBuddy 的完整教程

ITK中SpatialObject几何体系解析：坐标系、变换与管道集成

本周精选

交通拥堵预测毕设：基于Python+LSTM的车辆流量预测系统全流程解析

MATLAB/Simulink搭建10机39节点电力系统暂态稳定仿真实战

无人机航拍三维重建全流程：从SfM到网格生成的避坑指南

本月热门

我发现了一个新思路：用 Remotion + Claude Code 像写代码一样自动化生成短视频

Windows下 Codex 中 Chrome 和 Computer Use 插件不可用问题排查及解决参考方式：TaoToken 统一 Key 配置与验证

2026 大模型集体涨价：用 Python 做企业 Token 成本测算与选型避坑（附配置）

读完文章，想聊聊您的网站？