HashMap 在 JDK 1.8 相比 1.7 有哪些优化，为什么改变插入方式？

核心回答

JDK 8 的 HashMap 相比 JDK 7，主要优化了冲突桶结构、扩容迁移和哈希扰动。以下对比以 OpenJDK 7u80 与 8u412 的实现为例：

1. 长冲突链可以转成红黑树。 JDK 7 主要使用数组加链表；JDK 8 在满足条件时树化，减少大量冲突下长链扫描的代价。表容量较小时会优先扩容，并非一发生碰撞就建树。
2. 扩容按新增的一位拆分。 容量翻倍后，节点留在原桶，或移动到“原桶下标加旧容量”的位置，可以依据节点已保存的 hash 直接拆成两个目标组，简化重新定位。
3. 链表插入与迁移不再依靠头插反转。 JDK 8 普通链表追加新键时使用尾插，扩容也保持拆分后各组的相对顺序，避开了 JDK 7 头插迁移反转链表所关联的经典环链竞争路径。
4. 哈希扰动更简洁。 JDK 8 用原始 hashCode 与其高 16 位异或，使高位参与桶定位，配合树化等机制处理碰撞。

这些改变改善了冲突和迁移处理，没有把 HashMap 改成线程安全容器，也没有增加遍历顺序保证。

头插与尾插要分清两处操作

第一处是普通 put：JDK 7 新增冲突节点时可直接放到桶首；JDK 8 在检查链表是否已有相等键的过程中，未找到则追加到尾部。已有键仍是更新其值，并不是每次 put 都追加新节点；树桶也走自己的插入逻辑。

第二处是扩容迁移，也是历史并发环链的关键。JDK 7 遍历旧链，把当前节点头插到新桶，会改变 next 指向并反转同一目标桶内的顺序。多个线程无同步地交错迁移同一批节点，可能利用已被另一个线程改动的链接形成环。

JDK 8 对普通链表维护低位组和高位组的头尾指针，按旧链顺序追加到相应组，再分别接到新表，避免这种反转过程。不过“尾插”不是同步手段：两个线程同时插入仍可能覆盖桶入口、丢失计数或产生其他不一致。不能将“换尾插”解释成所有并发问题已经解决。

扩容为什么只看一位

桶容量是 2 的幂，定位使用“内部 hash 与容量减一按位与”。例如容量从 16 变为 32，掩码从 15 变为 31，只多考虑值为 16 的那一位：

• 该位为 0，节点仍在原下标；
• 该位为 1，节点移到原下标加 16。

例如内部 hash 为 3 和 19，旧表中都在下标 3；扩容后分别在 3 和 19。这里使用的是节点保存的内部 hash，不是说重新调用每个键的 hashCode。

JDK 7 迁移会逐节点按新容量计算目标下标，部分路径还可能因替代哈希机制变化重新计算 hash；不能笼统说 JDK 7 每次扩容都重新调用所有键的 hashCode。JDK 8 的优化在于直接按这个新增位把旧桶拆成两组，扩容仍需遍历和处理旧节点，并非 O(1)。

树化为什么不能只背一个阈值

树节点比普通链表节点更复杂、占用更多空间，所以只在冲突足够多且表容量合适时使用；表太小，扩容可能已经能把碰撞节点分开。树化改善的是冲突桶的处理，良好的 hashCode 和正确的 equals 仍然重要，不能承诺任意键、任意操作都获得同一种复杂度。

“保持拆分后各组的相对顺序”也不等于保持整张 Map 的遍历顺序。HashMap 的迭代顺序始终没有契约保证，需要顺序时应选择满足相应顺序语义的容器。

参考资料