Java 1.8 HashMap优化：哈希扰动、扩容与红黑树全解析

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 放在一起看，改动远不止加红黑树。我整理了一张对照表，日常排查问题时对着看会快很多：

表格里最容易被忽略的其实是「扩容后节点位置」和「链表插入方式」这两行。红黑树解决的问题是极端碰撞，而这两行解决的是普通场景下的性能和稳定性，影响面反而更大。

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) & hash，n 是数组长度。假设 table 长度是 16，n - 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 = 16（10000）→ 涂抹后变11111（31）→ +1 = 32。cap = 16 → n = 15（01111）→ 涂抹还是 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 的泊松分布，各长度出现的概率分别是：

长度到 8 的概率大约是千万分之六。也就是说，在 hash 分布正常的情况下，链表长到 8 几乎不会发生；一旦真的发生了，大概率说明 hash 函数分布很差或者被人为构造了冲突，这时候转成红黑树去兜底是划算的。

这个数字背后其实是一个成本和收益的权衡：TreeNode 对象比普通 Node 大约多占一倍内存（多了 parent、left、right、prev 四个引用和 red 标志），如果阈值定得太低，比如 3 或 4，那么正常业务里就会频繁树化，内存和 CPU 都白花；定得太高，比如 16，那碰撞严重时还是得先扫 16 次链表，收益又不够。

3.2 树化的完整条件是「长度够」加「容量够」

这里有个特别容易记错的点：不是链表一到 8 就立刻树化。真正的判断在treeifyBin里：

final void treeifyBin(Node<K,V>[] tab, int hash) { int n, index; Node<K,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_THRESHOLD（6）就调用untreeify退回普通链表。二是删除节点时，removeTreeNode里判断树太小也会退化。

这个设计思路在工程里很常见：任何有状态切换的地方，都别用同一个阈值来回切，加个滞回区间能省掉大量无谓抖动。类似的还有垃圾回收里的各种水位线。

3.4 TreeNode 到底多花了多少内存

TreeNode 的继承链是TreeNode extends LinkedHashMap.Entry<K,V> extends HashMap.Node<K,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。新容量是 32，newCap - 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 = 4（00100），旧下标 4，4 & 16 = 0，新下标还是 4，也对。

这个技巧省掉的是每个节点的取模运算，看起来每次只省几个指令，但扩容时可能有几十万个节点要迁移，累积起来差别不小。更关键的是，它把「迁移」变成了「拆成两条链」：一条留在原位，一条挂到j + oldCap，两条链内部顺序都不变，实现干净利落。

Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null; Node<K,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 长度是 256，threshold = 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) { Node<K,V>[] tab; Node<K,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 { Node<K,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 = ((TreeNode<K,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 >= 7（TREEIFY_THRESHOLD - 1，因为计数从 0 开始，头节点不算），达到就调treeifyBin。

第六步，扫的过程中找到相同 key，就跳出循环准备覆盖值。

第七步，全新的 key，插入后++size，超过 threshold 就扩容。

有个细节值得注意：链表遍历里先判断e = p.next == null再决定是插入还是继续比较，这个写法比先比较再判断 next 少一次循环变量维护，是典型的性能微调。另外putTreeVal里如果树中已经存在该 key，会返回对应节点，外层统一处理覆盖逻辑，返回值语义保持一致。

5.2 get 的查找路径短得多

get 的逻辑相对简单，getNode里依次做：判断 table 非空且对应桶非空 → 比较头节点 → 头节点是 TreeNode 就走树的查找 → 否则顺着链表往后找。

final Node<K,V> getNode(int hash, Object key) { Node<K,V>[] tab; Node<K,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 ((TreeNode<K,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 相关问题，我整理了一张表，遇到现象先对一遍，能省掉不少翻源码的时间：

表格里最值得展开的是「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(HashMap<K, 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 里长出来。