HashMap 这个类写过几年业务代码的人基本天天在用但真被问到 Java 1.8 对它做了哪些优化很多人的第一反应还是那句背了无数遍的结论加了红黑树。这话对但太省事甚至在不少场景下会把人带偏——因为真正让 1.8 的 HashMap 在大 key 量、高碰撞场景下表现更稳的不是红黑树这一个点而是哈希扰动、扩容拆分、插入顺序、树化边界这一整套组合拳红黑树只是其中最显眼的一环。我前后迭代过几个订单归集、日志聚合类的小服务key 动辄百万级早期用 1.7 那套思路调优吃过的亏不少扩容时链表的顺序被打乱、并发下偶尔出现诡异的高 CPU、初始容量给小了导致反复扩容。换了 1.8 之后这些问题大部分自然消失了但如果不懂它改了什么出问题时依旧只能靠猜。这篇文章就把 HashMap 在 Java 1.8 中的优化点逐条拆开讲清楚改了什么、为什么这么改、源码里长什么样、参数是怎么算出来的、线上遇到问题怎么排查。手上有一定 Java 基础、能看懂基本泛型和位运算的读者都能顺着往下读写业务为主、平时不太翻 JDK 源码的同学也能拿到能直接抄的参数和排查表。1. 先把结论摆上台面1.8 动了哪几刀1.1 从「数组加链表」变成「数组加链表加红黑树」1.7 的 HashMap 底层是数组加单向链表每个桶里挂着一条 Entry 链。这个结构在散列均匀时非常快平均 O(1)但它的命门在散列不均匀一旦某些 key 的 hash 落到同一个桶里链表越挂越长查询就退化成线性扫描。攻击者很容易利用这一点故意构造一批 hash 冲突的 key把某个桶的链表撑到几千上万一次 get 就变成 O(n)CPU 直接被打满。1.8 的做法是在链表长度到达阈值之后把这个桶里的链表原地转换成红黑树。红黑树是一种近似平衡的二叉查找树查找、插入、删除都是 O(log n)。链表长度 1000 的时候最坏要比较 1000 次转成树之后最多比较十几次差距是数量级的。不过要注意这里不是「整张表都变成树」而是单个桶自己变。HashMap 的整体结构依旧是数组数组的每个槽位要么是一个普通 Node要么是一棵 TreeNode 树的根要么是空。理解这一点很关键后面讲扩容为什么能只看一位 hash 的时候就靠它。1.2 五个改动点的全景对照把 1.7 和 1.8 放在一起看改动远不止加红黑树。我整理了一张对照表日常排查问题时对着看会快很多维度JDK 1.7JDK 1.8数据结构数组 单向链表数组 链表 红黑树哈希扰动四次移位异或h^(h20)^(h12) 再异或两次一次h ^ (h 16)链表插入方式头插法尾插法扩容时机插入前判断且目标桶非空才扩容插入后判断size threshold扩容后节点位置重新计算hash (newCap-1)用(hash oldCap)判断原位置或原位置oldCap扩容后链表顺序相对顺序反转保持原顺序节点类型EntryNode / TreeNode树化阈值无链表长度 ≥ 8 且容量 ≥ 64表格里最容易被忽略的其实是「扩容后节点位置」和「链表插入方式」这两行。红黑树解决的问题是极端碰撞而这两行解决的是普通场景下的性能和稳定性影响面反而更大。1.3 为什么这些改动值得单独拿出来讲很多资料把 1.8 的优化讲成一次性能升级这个说法太笼统。更准确地说1.8 的三次改动分别对应三个不同的目标第一类是降低碰撞概率靠扰动函数解决。让高位也参与下标运算避免一堆 key 挤在低位相同的槽里。第二类是处理碰撞的极端情况靠红黑树解决。碰撞无法完全避免但只要冲突集中在一个桶里就把比较次数从线性压到对数。第三类是降低扩容的代价和风险靠高低位拆分和尾插法解决。扩容是 HashMap 里最重的动作1.7 在扩容时会重新计算每个节点的下标1.8 用一次位与就搞定了1.7 的头插法在并发下会形成环形链表1.8 的尾插法至少不会自环。我个人的判断是如果你只记一个结论记住「1.8 的优化是围绕碰撞和扩容两条线展开的」比记住「加了红黑树」有用得多。2. 哈希扰动函数一行代码背后的碰撞账2.1 1.7 的四次移位异或为什么被砍先看 1.7 是怎么算 hash 的final int hash(Object k) { int h hashSeed; if (0 ! h k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^ k.hashCode(); h ^ (h 20) ^ (h 12); return h ^ (h 7) ^ (h 4); }这套算法做了四次移位、四次异或目的是把高位的差异「搅」到低位去因为数组下标只取低位。理论上扰动越充分碰撞越少。但实际测下来四次扰动带来的收益已经非常有限反而每次 put 和 get 都要多做几次位运算属于典型的性价比不高。更要紧的是里面有hashSeed和针对 String 的特殊分支这两个东西增加了代码复杂度也让行为在不同环境下不一致——早期有同学就是因为 hashSeed 的开关不同导致两次压测结果对不上排查了大半天。1.8 直接砍成一行static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }顺便把 null key 的处理也收进来了null 的 hash 固定为 0所以 null key 永远落在table[0]那个桶里。2.2h ^ (h 16)到底做了什么理解这一行得先知道数组下标的算法是(n - 1) hashn 是数组长度。假设 table 长度是 16n - 1就是 15二进制0000 0000 0000 0000 0000 0000 0000 1111。这一与运算只保留 hash 的最低 4 位高 28 位全被丢弃了。问题来了如果一批 key 的 hashCode 只有高几位不一样、低几位一样这在内置类里很常见比如某些对象按属性拼 hash 时低位规律性很强那么它们算出来的下标会完全一样全挤在一个桶里此时高位的差异根本没被利用上。h 16就是把 32 位 int 的高 16 位无符号右移到低 16 位再和原值异或。这样原 hash 的高 16 位信息就被「折叠」进了低 16 位。因为 HashMap 的容量上限是 2^30实际用到的下标位最多 30 位折叠一次足够覆盖。举一个具体例子。假设某个 key 的 hashCode 是0x12340000十进制 305397760原值二进制高 16 位是0001 0010 0011 0100低 16 位全是 0。h 16得到0x00001234。异或结果0x12340000 ^ 0x00001234 0x12341234。现在低 16 位不再是 0 (n-1)的时候就能算出分散的下标了。而在 1.7 里如果这个 hashCode 恰好被四次扰动「搅」得不好低位依旧可能很集中。2.3 为什么数组长度必须是 2 的幂扰动函数能生效的前提是数组长度必须是 2 的幂。原因有两个其一当 n 是 2 的幂时n - 1的二进制是「低位全 1」的形式(n - 1) hash恰好等于hash % n但位与比取模快得多而且没有负数问题。如果 n 不是 2 的幂(n-1)中间会出现 0 位那些位置永远算不出下标数组就有一半槽位是浪费的。其二扩容时才能用「只看一位」的技巧下一节细讲。所以 1.8 在构造方法里就把容量强行拉到 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; }这段代码的套路是把最高位的 1 不断向右「涂抹」最终得到「从最高位到最低位全是 1」的数再 1 就变成比 cap 大的最小 2 的幂。先做cap - 1是为了处理 cap 本身就是 2 的幂的情况否则会多翻一倍。验证一下cap 17 → n 1610000→ 涂抹后变1111131→ 1 32。cap 16 → n 1501111→ 涂抹还是 15 → 1 16。正确。2.4 自己动手验证扰动效果光看代码没感觉可以写个小程序实测。思路是构造一批低位相同、高位不同的 key看它们在 1.8 的 hash 之后下标分布如何public class HashSpread { static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); } public static void main(String[] args) { int cap 16; int[] buckets new int[cap]; for (int i 0; i 1000; i) { long id ((long) i) 16; // 高位变化低位固定 String key order- id; buckets[hash(key) (cap - 1)]; } for (int i 0; i cap; i) { System.out.println(bucket i - buckets[i]); } } }跑完之后你会看到 16 个桶的分布相对均匀。如果把hash()换成直接返回key.hashCode()再跑一次分布就会明显塌到几个桶里。这个对比很直观也是我在团队内部分享时最常用的一张图这里就不画图了自己打印数字看更真实。注意扰动函数解决的是「低位信息不足」的问题它治不了 hashCode 本身写得烂。如果业务对象的 hashCode 永远返回 1那再怎么扰动也全在一个桶里只能靠红黑树兜底。3. 红黑树登场树化的触发条件与边界3.1 链表长度 8 这个数字是怎么来的很多人以为 8 是拍脑袋定的其实源码注释里给了推导。注释大意是在理想的随机 hash 下桶中节点数量服从参数约为 0.5 的泊松分布各长度出现的概率分别是链表长度出现概率00.6065306610.3032653320.0759854530.0126368040.0015795250.0001579560.0000131670.0000009480.00000006长度到 8 的概率大约是千万分之六。也就是说在 hash 分布正常的情况下链表长到 8 几乎不会发生一旦真的发生了大概率说明 hash 函数分布很差或者被人为构造了冲突这时候转成红黑树去兜底是划算的。这个数字背后其实是一个成本和收益的权衡TreeNode 对象比普通 Node 大约多占一倍内存多了 parent、left、right、prev 四个引用和 red 标志如果阈值定得太低比如 3 或 4那么正常业务里就会频繁树化内存和 CPU 都白花定得太高比如 16那碰撞严重时还是得先扫 16 次链表收益又不够。3.2 树化的完整条件是「长度够」加「容量够」这里有个特别容易记错的点不是链表一到 8 就立刻树化。真正的判断在treeifyBin里final void treeifyBin(NodeK,V[] tab, int hash) { int n, index; NodeK,V e; if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY) resize(); else if ((e tab[index (n - 1) hash]) ! null) { // 遍历链表把 Node 换成 TreeNode再调用 treeify 建树 } }MIN_TREEIFY_CAPACITY的值是 64。也就是说如果 table 长度还不到 64即使某个桶的链表已经有 8 个节点HashMap 也不会树化而是选择先扩容。为什么要这样设计因为容量小的时候碰撞往往不是因为 hash 烂而是因为桶太少了。长度 16 的表最多只有 16 个位置稍多一点元素必然挤。这种情况下扩容比树化更划算扩容能把元素摊开从根源上减少碰撞而且小表就树化树节点额外占的内存相对总容量来说比例太大不经济。所以实际触发树化的条件是桶内链表长度 8并且table.length 64。这一点在面试和实际调优里都是高频误区我在代码评审里纠正过不止一次。3.3 退化阈值为什么是 6 而不是 8树化阈值是 8退化untreeify阈值是 6中间留了 7 这个缓冲带。如果两者都设成 8那么链表长度在 7 和 8 之间反复抖动时就会不停地树化、退化、再树化每次树化和退化都要重建结构开销很大。留出一格的空隙是为了避免这种「临界抖动」。退化发生在两个地方。一是扩容时对树的拆分TreeNode.split里会统计拆出来的 lo 和 hi 两条链长度只要 UNTREEIFY_THRESHOLD6就调用untreeify退回普通链表。二是删除节点时removeTreeNode里判断树太小也会退化。这个设计思路在工程里很常见任何有状态切换的地方都别用同一个阈值来回切加个滞回区间能省掉大量无谓抖动。类似的还有垃圾回收里的各种水位线。3.4 TreeNode 到底多花了多少内存TreeNode 的继承链是TreeNode extends LinkedHashMap.EntryK,V extends HashMap.NodeK,V也就是说它除了保留 Node 的hash、key、value、next还额外带了parent、left、right、prev和red标志。在 64 位 JVM 开启指针压缩的情况下一个普通 Node 大约 32 字节一个 TreeNode 大约 56 字节接近两倍。这就是源码注释里那句「TreeNodes are about twice the size of regular nodes」的由来。所以别指望着把TREEIFY_THRESHOLD改小来提升性能。改小到 4意味着稍微碰一下就是两倍内存而且树化过程本身要遍历链表、建树、平衡成本不低。JDK 定的 8 是经过大量实测的平衡点业务代码里没特殊理由不要动。3.5 用调试手段观察真实的树化过程想亲眼看树化发生最直接的办法是断点调试treeifyBin然后构造一批必然碰撞的 key。最简单的是重写 hashCode 返回固定值static class BadKey { final int id; BadKey(int id) { this.id id; } Override public int hashCode() { return 1; } Override public boolean equals(Object o) { return o instanceof BadKey ((BadKey) o).id id; } }然后往一个初始容量 64 的 HashMap 里塞 10 个 BadKey断点停在treeifyBin就能看到n 64走的是 else 分支链表被换成 TreeNode。如果初始容量给 16同样的代码会走resize()表先扩到 32再扩到 64然后才可能树化。提示调试resize()时把断点条件设成oldCap 16能过滤掉前面几次无关的小扩容省不少时间。4. 扩容机制重写resize 里的两处关键优化4.1 头插法改尾插法把环形链表堵死了1.7 在扩容迁移节点时用的是头插法遍历旧链表每读一个节点就插到新链表的头部。这样迁移完成后链表顺序会整体反转。单线程下顺序反转没什么影响但并发下就出事了。两个线程同时触发扩容各自持有一份旧链表引用交错执行头插很容易让两个节点互相指向对方形成环形链表。之后任何一次 get 落到这个桶就会在环里无限循环CPU 直接飙到 100%而且线程 dump 出来只是卡在HashMap.getEntry看不出明显原因。1.8 改成尾插法迁移时保持原有顺序。虽然 HashMap 依然不是线程安全的并发 put 依然可能丢数据、覆盖值但至少不会自环成死循环。这个改动在工程上的价值其实比红黑树更直接——它把一个「会拖垮整个进程」的故障模式降级成了「数据可能不对」。4.2 高低位拆分一次位与代替重新取模这是 1.8 扩容里最精妙的一处。1.7 在迁移时对每个节点都重新算一遍indexFor(hash, newCapacity)也就是重新做一次取模。1.8 完全不重算只判断一位if ((e.hash oldCap) 0) { // 留在原位置 j } else { // 移动到 j oldCap }推导过程其实很朴素。旧容量 oldCap 是 2 的幂oldCap - 1的二进制是低位全 1比如 16 的时候是01111。新容量是 32newCap - 1是11111。两者相比多出来的就是 oldCap 那一位16 对应的10000。所以扩容后下标相比扩容前只可能多一个 oldCap 的值。而这一位到底是不是 1直接看hash oldCap就行结果为 0 说明这位是 0下标不变结果非 0 说明这位是 1下标变成j oldCap。举个例子。假设 oldCap 16某个 key 的 hash 是 20二进制10100。旧下标 20 15 4。扩容到 32 后新下标 20 31 20。而20 16 16非 0所以新下标 4 16 20正好对上。再看 hash 400100旧下标 44 16 0新下标还是 4也对。这个技巧省掉的是每个节点的取模运算看起来每次只省几个指令但扩容时可能有几十万个节点要迁移累积起来差别不小。更关键的是它把「迁移」变成了「拆成两条链」一条留在原位一条挂到j oldCap两条链内部顺序都不变实现干净利落。NodeK,V loHead null, loTail null; NodeK,V hiHead null, hiTail null; NodeK,V next; do { next e.next; if ((e.hash oldCap) 0) { if (loTail null) loHead e; else loTail.next e; loTail e; } else { if (hiTail null) hiHead e; else hiTail.next e; hiTail e; } } while ((e next) ! null); if (loTail ! null) { loTail.next null; newTab[j] loHead; } if (hiTail ! null) { hiTail.next null; newTab[j oldCap] hiHead; }注意最后那两行把tail.next置为 null这一步不能少。否则新链表的尾节点可能还指着旧链表里的某个节点在新表里就形成了一条多余的尾巴轻则数据结构错乱重则又出现环。4.3 扩容时机从「先扩后插」变成「先插后扩」1.7 的 put 逻辑大致是先判断size threshold 目标桶不为空满足就扩容然后再插入。注意那个「目标桶不为空」的条件——如果这次要插入的位置是空的1.7 认为不扩容也能放下就先不扩。1.8 改成了插入完成之后判断modCount; if (size threshold) resize();也就是先插进去再看总数是否超过阈值。这个改动看起来小实际影响挺大第一行为更可预测。1.7 那种「桶空就不扩容」的策略会让扩容时机依赖于具体的 hash 分布很难在压测里复现。1.8 只看元素总数size threshold就一定扩逻辑线性。第二减少了无效扩容。1.7 在某些场景下会因为桶的占用情况提前扩容扩完之后发现其实还用不上1.8 是真正装不下了才扩。第三注意是而不是。threshold 默认是capacity * 0.75容量 16 时 threshold 是 12意味着第 13 个元素插入后才会扩容此时 size 变成 13 12。4.4 初始容量怎么给才不浪费扩容是重操作最好的策略是压根不让它发生。这就涉及初始容量的估算。负载因子 0.75 是时间与空间的折中太低会浪费数组空间0.5 的话一半槽位空着太高会让碰撞变多0.9 以上链表容易变长。0.75 是 JDK 团队实测的选择配合泊松分布刚好让链表长度超过 8 的概率低到可忽略。估算公式是预期元素数量 / 0.75 1然后 HashMap 内部会通过tableSizeFor向上取到 2 的幂。具体算一下。要放 100 个元素100 / 0.75 133.33加 1 得 134。tableSizeFor(134)134 的二进制是10000110比它大的最小 2 的幂是 256。所以初始容量传 134最终 table 长度是 256threshold 192。有人会问那直接传 256 不是更省事可以但如果你在多个地方都这么「向上取整到 2 的幂」累积起来浪费会不小。传 134 让 JDK 自己算语义更清楚。另一个坑是构造函数里并不是真的分配了数组。new HashMap(134)只是把threshold设成了tableSizeFor(134) 256真正的数组要等第一次 put 时才在resize()里创建。所以构造一个空 HashMap 的开销很小可以放心地提前建。5. put 和 get 全流程拆解新逻辑是怎么串起来的5.1 putVal 的七个分支1.8 的 put 主逻辑全在putVal里。第一次读可能觉得分支很多但按顺序理一遍其实很清楚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 { NodeK,V e; K k; 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; } } if (e ! null) { V oldValue e.value; if (!onlyIfAbsent || oldValue null) e.value value; afterNodeAccess(e); return oldValue; } } modCount; if (size threshold) resize(); afterNodeInsertion(evict); return null; }按顺序拆第一步table 为空或长度为 0先resize()初始化。这就是惰性初始化构造函数没分配数组第一次 put 才建。第二步算下标(n - 1) hash如果该位置是 null直接newNode放进去。这是最理想的情况一次就完事。第三步位置不为空比较头节点的 hash 和 key。相等就直接覆盖值返回旧值。第四步头节点是 TreeNode走红黑树的putTreeVal。第五步头节点是普通 Node说明是链表从头往后扫。扫到尾节点就把新节点挂上去同时判断binCount 7TREEIFY_THRESHOLD - 1因为计数从 0 开始头节点不算达到就调treeifyBin。第六步扫的过程中找到相同 key就跳出循环准备覆盖值。第七步全新的 key插入后size超过 threshold 就扩容。有个细节值得注意链表遍历里先判断e p.next null再决定是插入还是继续比较这个写法比先比较再判断 next 少一次循环变量维护是典型的性能微调。另外putTreeVal里如果树中已经存在该 key会返回对应节点外层统一处理覆盖逻辑返回值语义保持一致。5.2 get 的查找路径短得多get 的逻辑相对简单getNode里依次做判断 table 非空且对应桶非空 → 比较头节点 → 头节点是 TreeNode 就走树的查找 → 否则顺着链表往后找。final 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; }比较 key 的顺序是在前、equals在后这个顺序是有意的。同一个对象引用比较是零成本的能挡掉大量实际场景比如枚举、常量池字符串、缓存对象只有引用不同才走equals。还有一个常被忽略的保护first.hash hash。先比 hash 再比 key能过滤掉绝大多数不匹配的节点。因为 hash 是 int 比较非常便宜。5.3 从 1.7 到 1.8流程差异的核心就三处把两版流程对齐看变化集中在三处插入位置头插换尾插、扩容判断位置前移后移、以及插入后是否要做树化检查。其余骨架基本一致。这三处的组合效果是单线程下行为更可预测并发下最坏情况从「死循环」降为「数据不一致」碰撞极端时从「线性扫描」降为「对数查找」。这也解释了为什么 1.8 之后很多老系统升级 JDK 会感觉「突然变稳了」很多时候稳的不是业务代码而是底层容器。注意不要因为 1.8 修了环形链表问题就以为 HashMap 可以并发用。并发 put 依然会丢数据、会读到中间态、size 会算错。真要在多线程环境共享用ConcurrentHashMap它的分段思路和 CAS 才是为并发设计的。6. 常见问题与排查实录6.1 问题速查表日常排查 HashMap 相关问题我整理了一张表遇到现象先对一遍能省掉不少翻源码的时间现象可能原因排查方向处理方式单次 get 明显变慢桶内链表过长或树化失败dump 出 map 的 table统计每个桶长度检查 key 的 hashCode 分布必要时改 hash 算法内存占用远超预期初始容量给小反复扩容或大量树节点看 table.length 与 size 的比值按size/0.751预设容量CPU 长时间打满并发场景下的结构破坏或碰撞攻击线程栈看是否卡在 map 相关方法换并发容器限制入参 key 数量put 之后取不到值key 是可变对象hashCode 被改了检查 key 是否在入 map 后被修改key 用不可变对象或存副本遍历时抛并发修改异常遍历过程中做了结构性修改看 fail-fast 的 modCount 检查用迭代器的 remove或先收集再处理扩容后顺序变了1.7 头插法的正常行为确认 JDK 版本需要顺序就换 LinkedHashMap表格里最值得展开的是「key 是可变对象」这一条现实中踩的人特别多。6.2 可变 key 引起的隐形事故假设你用某个业务对象当 key放进 HashMap 之后业务逻辑又修改了这个对象的某个参与 hashCode 计算的字段。结果就是这个 entry 还躺在原来的桶里但用这个对象去 get 时算出来的 hash 变了找的是另一个桶自然取不到值。表现出来就是「明明 put 进去了就是 get 不出来」。更麻烦的是这个 entry 变成了「孤儿」它还在 table 里占着内存遍历能遍历到但按 key 查不到也没法用 remove 删掉remove 也是按 hash 找的。时间一长内存缓慢上涨还查不出明显泄漏点。排查这类问题的思路是先确认 key 对象在入 map 之后有没有被 setter 改过如果不好确认可以写个工具方法把 map 里的所有 key 重新算一遍 hash对比节点里存的 hash 值不一致的就是被改过的。static K, V int countStaleKeys(HashMapK, V map) throws Exception { java.lang.reflect.Field tableField HashMap.class.getDeclaredField(table); tableField.setAccessible(true); Object[] table (Object[]) tableField.get(map); int count 0; for (Object bucket : table) { Object node bucket; while (node ! null) { java.lang.reflect.Field hashField node.getClass().getSuperclass().getDeclaredField(hash); hashField.setAccessible(true); int storedHash hashField.getInt(node); java.lang.reflect.Field keyField node.getClass().getSuperclass().getDeclaredField(key); keyField.setAccessible(true); Object key keyField.get(node); if (key ! null key.hashCode() ! storedHash) count; java.lang.reflect.Field nextField node.getClass().getSuperclass().getDeclaredField(next); nextField.setAccessible(true); node nextField.get(node); } } return count; }这段代码只建议在排查阶段临时用不要放进生产代码。反射访问内部字段在 JDK 9 之后模块化限制更多得加--add-opens而且性能很差。稳妥的做法很朴素key 一律用不可变对象String、Integer、枚举、或者自己写的 final 字段类。真要用业务对象就在入 map 前把它转成一个不可变的值对象。6.3 几处容易踩的坑第一个坑初始容量传了「元素个数」结果还是扩了一次。很多人new HashMap(100)以为能装 100 个不扩容实际 threshold 是 128 * 0.75 96第 97 个元素就会扩。要装 100 个不扩得传 134 以上。第二个坑遍历中直接 remove。for-each 遍历时调map.remove(k)会抛ConcurrentModificationException因为 modCount 变了但迭代器的期望值没更新。正确做法是用Iterator.remove()或者干脆先new ArrayList(map.keySet())拷一份再遍历删。第三个坑以为containsKey是免费的。它的内部走的就是getNode遇到长链表或树也要走一遍查找。如果只是想判断再取值直接 get 判断 null 更省一次查找前提是确认不会存 null value。第四个坑用hashCode()直接当下标。有同学为了「优化」自己写一个简化版 map直接table[Math.abs(key.hashCode()) % len]忘了负数取模和扩容的问题。这种轮子能不造就不造标准库已经把边角情况都处理好了。第五个坑serialVersionUID 和反序列化。HashMap 实现了 Serializable但它的内部结构在反序列化时是重建的。如果序列化时的容量和反序列化后的不一致会出现「元素数没变但表结构变了」的情况。跨版本传输时注意验证。6.4 一个关于树的实测观察最后分享一个实测细节很多人以为树化之后性能就一定更好其实在节点数刚好在 8 到 10 之间时树和链表的性能差距很小甚至因为树节点创建和平衡的开销树可能略慢。我做过一组粗略对比在固定 64 容量的表里让一个桶分别挂 8、9、10、16、32 个节点用相同 key 反复 get 一百万次统计耗时。8 个节点时链表和树的差距在误差范围内到 16 个节点时树开始明显领先到 32 个节点时差距接近三倍。这也就解释了为什么阈值不能定得太低——在低节点数区间树化是纯亏本买卖。提示如果你的业务里某个 map 长期只有一个桶在撑先别急着怀疑红黑树不够快。看看是不是 key 的 hashCode 只用了少数几个值或者干脆被上游截断了。分布问题比结构问题更常见。我个人在实际项目里的体会是HashMap 的 1.8 优化确实把很多「脏活」在底层消化掉了但代价是你更容易忽略它依然不是并发安全这个事实。真正需要关注的仍然是三件事——key 的 hashCode 是否分散、初始容量是否一次给够、多线程场景是否该换容器。这三件事做到位红黑树大概率一辈子都不会在你的 map 里长出来。
HashMap 这个类写过几年业务代码的人基本天天在用但真被问到 Java 1.8 对它做了哪些优化很多人的第一反应还是那句背了无数遍的结论加了红黑树。这话对但太省事甚至在不少场景下会把人带偏——因为真正让 1.8 的 HashMap 在大 key 量、高碰撞场景下表现更稳的不是红黑树这一个点而是哈希扰动、扩容拆分、插入顺序、树化边界这一整套组合拳红黑树只是其中最显眼的一环。我前后迭代过几个订单归集、日志聚合类的小服务key 动辄百万级早期用 1.7 那套思路调优吃过的亏不少扩容时链表的顺序被打乱、并发下偶尔出现诡异的高 CPU、初始容量给小了导致反复扩容。换了 1.8 之后这些问题大部分自然消失了但如果不懂它改了什么出问题时依旧只能靠猜。这篇文章就把 HashMap 在 Java 1.8 中的优化点逐条拆开讲清楚改了什么、为什么这么改、源码里长什么样、参数是怎么算出来的、线上遇到问题怎么排查。手上有一定 Java 基础、能看懂基本泛型和位运算的读者都能顺着往下读写业务为主、平时不太翻 JDK 源码的同学也能拿到能直接抄的参数和排查表。1. 先把结论摆上台面1.8 动了哪几刀1.1 从「数组加链表」变成「数组加链表加红黑树」1.7 的 HashMap 底层是数组加单向链表每个桶里挂着一条 Entry 链。这个结构在散列均匀时非常快平均 O(1)但它的命门在散列不均匀一旦某些 key 的 hash 落到同一个桶里链表越挂越长查询就退化成线性扫描。攻击者很容易利用这一点故意构造一批 hash 冲突的 key把某个桶的链表撑到几千上万一次 get 就变成 O(n)CPU 直接被打满。1.8 的做法是在链表长度到达阈值之后把这个桶里的链表原地转换成红黑树。红黑树是一种近似平衡的二叉查找树查找、插入、删除都是 O(log n)。链表长度 1000 的时候最坏要比较 1000 次转成树之后最多比较十几次差距是数量级的。不过要注意这里不是「整张表都变成树」而是单个桶自己变。HashMap 的整体结构依旧是数组数组的每个槽位要么是一个普通 Node要么是一棵 TreeNode 树的根要么是空。理解这一点很关键后面讲扩容为什么能只看一位 hash 的时候就靠它。1.2 五个改动点的全景对照把 1.7 和 1.8 放在一起看改动远不止加红黑树。我整理了一张对照表日常排查问题时对着看会快很多维度JDK 1.7JDK 1.8数据结构数组 单向链表数组 链表 红黑树哈希扰动四次移位异或h^(h20)^(h12) 再异或两次一次h ^ (h 16)链表插入方式头插法尾插法扩容时机插入前判断且目标桶非空才扩容插入后判断size threshold扩容后节点位置重新计算hash (newCap-1)用(hash oldCap)判断原位置或原位置oldCap扩容后链表顺序相对顺序反转保持原顺序节点类型EntryNode / TreeNode树化阈值无链表长度 ≥ 8 且容量 ≥ 64表格里最容易被忽略的其实是「扩容后节点位置」和「链表插入方式」这两行。红黑树解决的问题是极端碰撞而这两行解决的是普通场景下的性能和稳定性影响面反而更大。1.3 为什么这些改动值得单独拿出来讲很多资料把 1.8 的优化讲成一次性能升级这个说法太笼统。更准确地说1.8 的三次改动分别对应三个不同的目标第一类是降低碰撞概率靠扰动函数解决。让高位也参与下标运算避免一堆 key 挤在低位相同的槽里。第二类是处理碰撞的极端情况靠红黑树解决。碰撞无法完全避免但只要冲突集中在一个桶里就把比较次数从线性压到对数。第三类是降低扩容的代价和风险靠高低位拆分和尾插法解决。扩容是 HashMap 里最重的动作1.7 在扩容时会重新计算每个节点的下标1.8 用一次位与就搞定了1.7 的头插法在并发下会形成环形链表1.8 的尾插法至少不会自环。我个人的判断是如果你只记一个结论记住「1.8 的优化是围绕碰撞和扩容两条线展开的」比记住「加了红黑树」有用得多。2. 哈希扰动函数一行代码背后的碰撞账2.1 1.7 的四次移位异或为什么被砍先看 1.7 是怎么算 hash 的final int hash(Object k) { int h hashSeed; if (0 ! h k instanceof String) { return sun.misc.Hashing.stringHash32((String) k); } h ^ k.hashCode(); h ^ (h 20) ^ (h 12); return h ^ (h 7) ^ (h 4); }这套算法做了四次移位、四次异或目的是把高位的差异「搅」到低位去因为数组下标只取低位。理论上扰动越充分碰撞越少。但实际测下来四次扰动带来的收益已经非常有限反而每次 put 和 get 都要多做几次位运算属于典型的性价比不高。更要紧的是里面有hashSeed和针对 String 的特殊分支这两个东西增加了代码复杂度也让行为在不同环境下不一致——早期有同学就是因为 hashSeed 的开关不同导致两次压测结果对不上排查了大半天。1.8 直接砍成一行static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); }顺便把 null key 的处理也收进来了null 的 hash 固定为 0所以 null key 永远落在table[0]那个桶里。2.2h ^ (h 16)到底做了什么理解这一行得先知道数组下标的算法是(n - 1) hashn 是数组长度。假设 table 长度是 16n - 1就是 15二进制0000 0000 0000 0000 0000 0000 0000 1111。这一与运算只保留 hash 的最低 4 位高 28 位全被丢弃了。问题来了如果一批 key 的 hashCode 只有高几位不一样、低几位一样这在内置类里很常见比如某些对象按属性拼 hash 时低位规律性很强那么它们算出来的下标会完全一样全挤在一个桶里此时高位的差异根本没被利用上。h 16就是把 32 位 int 的高 16 位无符号右移到低 16 位再和原值异或。这样原 hash 的高 16 位信息就被「折叠」进了低 16 位。因为 HashMap 的容量上限是 2^30实际用到的下标位最多 30 位折叠一次足够覆盖。举一个具体例子。假设某个 key 的 hashCode 是0x12340000十进制 305397760原值二进制高 16 位是0001 0010 0011 0100低 16 位全是 0。h 16得到0x00001234。异或结果0x12340000 ^ 0x00001234 0x12341234。现在低 16 位不再是 0 (n-1)的时候就能算出分散的下标了。而在 1.7 里如果这个 hashCode 恰好被四次扰动「搅」得不好低位依旧可能很集中。2.3 为什么数组长度必须是 2 的幂扰动函数能生效的前提是数组长度必须是 2 的幂。原因有两个其一当 n 是 2 的幂时n - 1的二进制是「低位全 1」的形式(n - 1) hash恰好等于hash % n但位与比取模快得多而且没有负数问题。如果 n 不是 2 的幂(n-1)中间会出现 0 位那些位置永远算不出下标数组就有一半槽位是浪费的。其二扩容时才能用「只看一位」的技巧下一节细讲。所以 1.8 在构造方法里就把容量强行拉到 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; }这段代码的套路是把最高位的 1 不断向右「涂抹」最终得到「从最高位到最低位全是 1」的数再 1 就变成比 cap 大的最小 2 的幂。先做cap - 1是为了处理 cap 本身就是 2 的幂的情况否则会多翻一倍。验证一下cap 17 → n 1610000→ 涂抹后变1111131→ 1 32。cap 16 → n 1501111→ 涂抹还是 15 → 1 16。正确。2.4 自己动手验证扰动效果光看代码没感觉可以写个小程序实测。思路是构造一批低位相同、高位不同的 key看它们在 1.8 的 hash 之后下标分布如何public class HashSpread { static final int hash(Object key) { int h; return (key null) ? 0 : (h key.hashCode()) ^ (h 16); } public static void main(String[] args) { int cap 16; int[] buckets new int[cap]; for (int i 0; i 1000; i) { long id ((long) i) 16; // 高位变化低位固定 String key order- id; buckets[hash(key) (cap - 1)]; } for (int i 0; i cap; i) { System.out.println(bucket i - buckets[i]); } } }跑完之后你会看到 16 个桶的分布相对均匀。如果把hash()换成直接返回key.hashCode()再跑一次分布就会明显塌到几个桶里。这个对比很直观也是我在团队内部分享时最常用的一张图这里就不画图了自己打印数字看更真实。注意扰动函数解决的是「低位信息不足」的问题它治不了 hashCode 本身写得烂。如果业务对象的 hashCode 永远返回 1那再怎么扰动也全在一个桶里只能靠红黑树兜底。3. 红黑树登场树化的触发条件与边界3.1 链表长度 8 这个数字是怎么来的很多人以为 8 是拍脑袋定的其实源码注释里给了推导。注释大意是在理想的随机 hash 下桶中节点数量服从参数约为 0.5 的泊松分布各长度出现的概率分别是链表长度出现概率00.6065306610.3032653320.0759854530.0126368040.0015795250.0001579560.0000131670.0000009480.00000006长度到 8 的概率大约是千万分之六。也就是说在 hash 分布正常的情况下链表长到 8 几乎不会发生一旦真的发生了大概率说明 hash 函数分布很差或者被人为构造了冲突这时候转成红黑树去兜底是划算的。这个数字背后其实是一个成本和收益的权衡TreeNode 对象比普通 Node 大约多占一倍内存多了 parent、left、right、prev 四个引用和 red 标志如果阈值定得太低比如 3 或 4那么正常业务里就会频繁树化内存和 CPU 都白花定得太高比如 16那碰撞严重时还是得先扫 16 次链表收益又不够。3.2 树化的完整条件是「长度够」加「容量够」这里有个特别容易记错的点不是链表一到 8 就立刻树化。真正的判断在treeifyBin里final void treeifyBin(NodeK,V[] tab, int hash) { int n, index; NodeK,V e; if (tab null || (n tab.length) MIN_TREEIFY_CAPACITY) resize(); else if ((e tab[index (n - 1) hash]) ! null) { // 遍历链表把 Node 换成 TreeNode再调用 treeify 建树 } }MIN_TREEIFY_CAPACITY的值是 64。也就是说如果 table 长度还不到 64即使某个桶的链表已经有 8 个节点HashMap 也不会树化而是选择先扩容。为什么要这样设计因为容量小的时候碰撞往往不是因为 hash 烂而是因为桶太少了。长度 16 的表最多只有 16 个位置稍多一点元素必然挤。这种情况下扩容比树化更划算扩容能把元素摊开从根源上减少碰撞而且小表就树化树节点额外占的内存相对总容量来说比例太大不经济。所以实际触发树化的条件是桶内链表长度 8并且table.length 64。这一点在面试和实际调优里都是高频误区我在代码评审里纠正过不止一次。3.3 退化阈值为什么是 6 而不是 8树化阈值是 8退化untreeify阈值是 6中间留了 7 这个缓冲带。如果两者都设成 8那么链表长度在 7 和 8 之间反复抖动时就会不停地树化、退化、再树化每次树化和退化都要重建结构开销很大。留出一格的空隙是为了避免这种「临界抖动」。退化发生在两个地方。一是扩容时对树的拆分TreeNode.split里会统计拆出来的 lo 和 hi 两条链长度只要 UNTREEIFY_THRESHOLD6就调用untreeify退回普通链表。二是删除节点时removeTreeNode里判断树太小也会退化。这个设计思路在工程里很常见任何有状态切换的地方都别用同一个阈值来回切加个滞回区间能省掉大量无谓抖动。类似的还有垃圾回收里的各种水位线。3.4 TreeNode 到底多花了多少内存TreeNode 的继承链是TreeNode extends LinkedHashMap.EntryK,V extends HashMap.NodeK,V也就是说它除了保留 Node 的hash、key、value、next还额外带了parent、left、right、prev和red标志。在 64 位 JVM 开启指针压缩的情况下一个普通 Node 大约 32 字节一个 TreeNode 大约 56 字节接近两倍。这就是源码注释里那句「TreeNodes are about twice the size of regular nodes」的由来。所以别指望着把TREEIFY_THRESHOLD改小来提升性能。改小到 4意味着稍微碰一下就是两倍内存而且树化过程本身要遍历链表、建树、平衡成本不低。JDK 定的 8 是经过大量实测的平衡点业务代码里没特殊理由不要动。3.5 用调试手段观察真实的树化过程想亲眼看树化发生最直接的办法是断点调试treeifyBin然后构造一批必然碰撞的 key。最简单的是重写 hashCode 返回固定值static class BadKey { final int id; BadKey(int id) { this.id id; } Override public int hashCode() { return 1; } Override public boolean equals(Object o) { return o instanceof BadKey ((BadKey) o).id id; } }然后往一个初始容量 64 的 HashMap 里塞 10 个 BadKey断点停在treeifyBin就能看到n 64走的是 else 分支链表被换成 TreeNode。如果初始容量给 16同样的代码会走resize()表先扩到 32再扩到 64然后才可能树化。提示调试resize()时把断点条件设成oldCap 16能过滤掉前面几次无关的小扩容省不少时间。4. 扩容机制重写resize 里的两处关键优化4.1 头插法改尾插法把环形链表堵死了1.7 在扩容迁移节点时用的是头插法遍历旧链表每读一个节点就插到新链表的头部。这样迁移完成后链表顺序会整体反转。单线程下顺序反转没什么影响但并发下就出事了。两个线程同时触发扩容各自持有一份旧链表引用交错执行头插很容易让两个节点互相指向对方形成环形链表。之后任何一次 get 落到这个桶就会在环里无限循环CPU 直接飙到 100%而且线程 dump 出来只是卡在HashMap.getEntry看不出明显原因。1.8 改成尾插法迁移时保持原有顺序。虽然 HashMap 依然不是线程安全的并发 put 依然可能丢数据、覆盖值但至少不会自环成死循环。这个改动在工程上的价值其实比红黑树更直接——它把一个「会拖垮整个进程」的故障模式降级成了「数据可能不对」。4.2 高低位拆分一次位与代替重新取模这是 1.8 扩容里最精妙的一处。1.7 在迁移时对每个节点都重新算一遍indexFor(hash, newCapacity)也就是重新做一次取模。1.8 完全不重算只判断一位if ((e.hash oldCap) 0) { // 留在原位置 j } else { // 移动到 j oldCap }推导过程其实很朴素。旧容量 oldCap 是 2 的幂oldCap - 1的二进制是低位全 1比如 16 的时候是01111。新容量是 32newCap - 1是11111。两者相比多出来的就是 oldCap 那一位16 对应的10000。所以扩容后下标相比扩容前只可能多一个 oldCap 的值。而这一位到底是不是 1直接看hash oldCap就行结果为 0 说明这位是 0下标不变结果非 0 说明这位是 1下标变成j oldCap。举个例子。假设 oldCap 16某个 key 的 hash 是 20二进制10100。旧下标 20 15 4。扩容到 32 后新下标 20 31 20。而20 16 16非 0所以新下标 4 16 20正好对上。再看 hash 400100旧下标 44 16 0新下标还是 4也对。这个技巧省掉的是每个节点的取模运算看起来每次只省几个指令但扩容时可能有几十万个节点要迁移累积起来差别不小。更关键的是它把「迁移」变成了「拆成两条链」一条留在原位一条挂到j oldCap两条链内部顺序都不变实现干净利落。NodeK,V loHead null, loTail null; NodeK,V hiHead null, hiTail null; NodeK,V next; do { next e.next; if ((e.hash oldCap) 0) { if (loTail null) loHead e; else loTail.next e; loTail e; } else { if (hiTail null) hiHead e; else hiTail.next e; hiTail e; } } while ((e next) ! null); if (loTail ! null) { loTail.next null; newTab[j] loHead; } if (hiTail ! null) { hiTail.next null; newTab[j oldCap] hiHead; }注意最后那两行把tail.next置为 null这一步不能少。否则新链表的尾节点可能还指着旧链表里的某个节点在新表里就形成了一条多余的尾巴轻则数据结构错乱重则又出现环。4.3 扩容时机从「先扩后插」变成「先插后扩」1.7 的 put 逻辑大致是先判断size threshold 目标桶不为空满足就扩容然后再插入。注意那个「目标桶不为空」的条件——如果这次要插入的位置是空的1.7 认为不扩容也能放下就先不扩。1.8 改成了插入完成之后判断modCount; if (size threshold) resize();也就是先插进去再看总数是否超过阈值。这个改动看起来小实际影响挺大第一行为更可预测。1.7 那种「桶空就不扩容」的策略会让扩容时机依赖于具体的 hash 分布很难在压测里复现。1.8 只看元素总数size threshold就一定扩逻辑线性。第二减少了无效扩容。1.7 在某些场景下会因为桶的占用情况提前扩容扩完之后发现其实还用不上1.8 是真正装不下了才扩。第三注意是而不是。threshold 默认是capacity * 0.75容量 16 时 threshold 是 12意味着第 13 个元素插入后才会扩容此时 size 变成 13 12。4.4 初始容量怎么给才不浪费扩容是重操作最好的策略是压根不让它发生。这就涉及初始容量的估算。负载因子 0.75 是时间与空间的折中太低会浪费数组空间0.5 的话一半槽位空着太高会让碰撞变多0.9 以上链表容易变长。0.75 是 JDK 团队实测的选择配合泊松分布刚好让链表长度超过 8 的概率低到可忽略。估算公式是预期元素数量 / 0.75 1然后 HashMap 内部会通过tableSizeFor向上取到 2 的幂。具体算一下。要放 100 个元素100 / 0.75 133.33加 1 得 134。tableSizeFor(134)134 的二进制是10000110比它大的最小 2 的幂是 256。所以初始容量传 134最终 table 长度是 256threshold 192。有人会问那直接传 256 不是更省事可以但如果你在多个地方都这么「向上取整到 2 的幂」累积起来浪费会不小。传 134 让 JDK 自己算语义更清楚。另一个坑是构造函数里并不是真的分配了数组。new HashMap(134)只是把threshold设成了tableSizeFor(134) 256真正的数组要等第一次 put 时才在resize()里创建。所以构造一个空 HashMap 的开销很小可以放心地提前建。5. put 和 get 全流程拆解新逻辑是怎么串起来的5.1 putVal 的七个分支1.8 的 put 主逻辑全在putVal里。第一次读可能觉得分支很多但按顺序理一遍其实很清楚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 { NodeK,V e; K k; 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; } } if (e ! null) { V oldValue e.value; if (!onlyIfAbsent || oldValue null) e.value value; afterNodeAccess(e); return oldValue; } } modCount; if (size threshold) resize(); afterNodeInsertion(evict); return null; }按顺序拆第一步table 为空或长度为 0先resize()初始化。这就是惰性初始化构造函数没分配数组第一次 put 才建。第二步算下标(n - 1) hash如果该位置是 null直接newNode放进去。这是最理想的情况一次就完事。第三步位置不为空比较头节点的 hash 和 key。相等就直接覆盖值返回旧值。第四步头节点是 TreeNode走红黑树的putTreeVal。第五步头节点是普通 Node说明是链表从头往后扫。扫到尾节点就把新节点挂上去同时判断binCount 7TREEIFY_THRESHOLD - 1因为计数从 0 开始头节点不算达到就调treeifyBin。第六步扫的过程中找到相同 key就跳出循环准备覆盖值。第七步全新的 key插入后size超过 threshold 就扩容。有个细节值得注意链表遍历里先判断e p.next null再决定是插入还是继续比较这个写法比先比较再判断 next 少一次循环变量维护是典型的性能微调。另外putTreeVal里如果树中已经存在该 key会返回对应节点外层统一处理覆盖逻辑返回值语义保持一致。5.2 get 的查找路径短得多get 的逻辑相对简单getNode里依次做判断 table 非空且对应桶非空 → 比较头节点 → 头节点是 TreeNode 就走树的查找 → 否则顺着链表往后找。final 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; }比较 key 的顺序是在前、equals在后这个顺序是有意的。同一个对象引用比较是零成本的能挡掉大量实际场景比如枚举、常量池字符串、缓存对象只有引用不同才走equals。还有一个常被忽略的保护first.hash hash。先比 hash 再比 key能过滤掉绝大多数不匹配的节点。因为 hash 是 int 比较非常便宜。5.3 从 1.7 到 1.8流程差异的核心就三处把两版流程对齐看变化集中在三处插入位置头插换尾插、扩容判断位置前移后移、以及插入后是否要做树化检查。其余骨架基本一致。这三处的组合效果是单线程下行为更可预测并发下最坏情况从「死循环」降为「数据不一致」碰撞极端时从「线性扫描」降为「对数查找」。这也解释了为什么 1.8 之后很多老系统升级 JDK 会感觉「突然变稳了」很多时候稳的不是业务代码而是底层容器。注意不要因为 1.8 修了环形链表问题就以为 HashMap 可以并发用。并发 put 依然会丢数据、会读到中间态、size 会算错。真要在多线程环境共享用ConcurrentHashMap它的分段思路和 CAS 才是为并发设计的。6. 常见问题与排查实录6.1 问题速查表日常排查 HashMap 相关问题我整理了一张表遇到现象先对一遍能省掉不少翻源码的时间现象可能原因排查方向处理方式单次 get 明显变慢桶内链表过长或树化失败dump 出 map 的 table统计每个桶长度检查 key 的 hashCode 分布必要时改 hash 算法内存占用远超预期初始容量给小反复扩容或大量树节点看 table.length 与 size 的比值按size/0.751预设容量CPU 长时间打满并发场景下的结构破坏或碰撞攻击线程栈看是否卡在 map 相关方法换并发容器限制入参 key 数量put 之后取不到值key 是可变对象hashCode 被改了检查 key 是否在入 map 后被修改key 用不可变对象或存副本遍历时抛并发修改异常遍历过程中做了结构性修改看 fail-fast 的 modCount 检查用迭代器的 remove或先收集再处理扩容后顺序变了1.7 头插法的正常行为确认 JDK 版本需要顺序就换 LinkedHashMap表格里最值得展开的是「key 是可变对象」这一条现实中踩的人特别多。6.2 可变 key 引起的隐形事故假设你用某个业务对象当 key放进 HashMap 之后业务逻辑又修改了这个对象的某个参与 hashCode 计算的字段。结果就是这个 entry 还躺在原来的桶里但用这个对象去 get 时算出来的 hash 变了找的是另一个桶自然取不到值。表现出来就是「明明 put 进去了就是 get 不出来」。更麻烦的是这个 entry 变成了「孤儿」它还在 table 里占着内存遍历能遍历到但按 key 查不到也没法用 remove 删掉remove 也是按 hash 找的。时间一长内存缓慢上涨还查不出明显泄漏点。排查这类问题的思路是先确认 key 对象在入 map 之后有没有被 setter 改过如果不好确认可以写个工具方法把 map 里的所有 key 重新算一遍 hash对比节点里存的 hash 值不一致的就是被改过的。static K, V int countStaleKeys(HashMapK, V map) throws Exception { java.lang.reflect.Field tableField HashMap.class.getDeclaredField(table); tableField.setAccessible(true); Object[] table (Object[]) tableField.get(map); int count 0; for (Object bucket : table) { Object node bucket; while (node ! null) { java.lang.reflect.Field hashField node.getClass().getSuperclass().getDeclaredField(hash); hashField.setAccessible(true); int storedHash hashField.getInt(node); java.lang.reflect.Field keyField node.getClass().getSuperclass().getDeclaredField(key); keyField.setAccessible(true); Object key keyField.get(node); if (key ! null key.hashCode() ! storedHash) count; java.lang.reflect.Field nextField node.getClass().getSuperclass().getDeclaredField(next); nextField.setAccessible(true); node nextField.get(node); } } return count; }这段代码只建议在排查阶段临时用不要放进生产代码。反射访问内部字段在 JDK 9 之后模块化限制更多得加--add-opens而且性能很差。稳妥的做法很朴素key 一律用不可变对象String、Integer、枚举、或者自己写的 final 字段类。真要用业务对象就在入 map 前把它转成一个不可变的值对象。6.3 几处容易踩的坑第一个坑初始容量传了「元素个数」结果还是扩了一次。很多人new HashMap(100)以为能装 100 个不扩容实际 threshold 是 128 * 0.75 96第 97 个元素就会扩。要装 100 个不扩得传 134 以上。第二个坑遍历中直接 remove。for-each 遍历时调map.remove(k)会抛ConcurrentModificationException因为 modCount 变了但迭代器的期望值没更新。正确做法是用Iterator.remove()或者干脆先new ArrayList(map.keySet())拷一份再遍历删。第三个坑以为containsKey是免费的。它的内部走的就是getNode遇到长链表或树也要走一遍查找。如果只是想判断再取值直接 get 判断 null 更省一次查找前提是确认不会存 null value。第四个坑用hashCode()直接当下标。有同学为了「优化」自己写一个简化版 map直接table[Math.abs(key.hashCode()) % len]忘了负数取模和扩容的问题。这种轮子能不造就不造标准库已经把边角情况都处理好了。第五个坑serialVersionUID 和反序列化。HashMap 实现了 Serializable但它的内部结构在反序列化时是重建的。如果序列化时的容量和反序列化后的不一致会出现「元素数没变但表结构变了」的情况。跨版本传输时注意验证。6.4 一个关于树的实测观察最后分享一个实测细节很多人以为树化之后性能就一定更好其实在节点数刚好在 8 到 10 之间时树和链表的性能差距很小甚至因为树节点创建和平衡的开销树可能略慢。我做过一组粗略对比在固定 64 容量的表里让一个桶分别挂 8、9、10、16、32 个节点用相同 key 反复 get 一百万次统计耗时。8 个节点时链表和树的差距在误差范围内到 16 个节点时树开始明显领先到 32 个节点时差距接近三倍。这也就解释了为什么阈值不能定得太低——在低节点数区间树化是纯亏本买卖。提示如果你的业务里某个 map 长期只有一个桶在撑先别急着怀疑红黑树不够快。看看是不是 key 的 hashCode 只用了少数几个值或者干脆被上游截断了。分布问题比结构问题更常见。我个人在实际项目里的体会是HashMap 的 1.8 优化确实把很多「脏活」在底层消化掉了但代价是你更容易忽略它依然不是并发安全这个事实。真正需要关注的仍然是三件事——key 的 hashCode 是否分散、初始容量是否一次给够、多线程场景是否该换容器。这三件事做到位红黑树大概率一辈子都不会在你的 map 里长出来。
为null：异常信息丢失的六类场景与排查工具)
