HashMap18之后结构的优化有哪些

首次来源：京东 2021 一面整理

另见：vipkid 2021 一面

原题

HashMap1.8之后结构的优化有哪些

完整讲解（权威版）

最后更新：2026-10-30 · 基于第 1 次作答

L1 · 30 秒速记

结论：HashMap 1.8 四大优化——数组+链表+红黑树、头插改尾插、扰动函数、扩容省重算。 关键词：红黑树化 · 尾插 · 扰动 ^ · 扩容判高位 边界：树化条件是链表长度>8 且数组长度≥64；仍非线程安全，并发用 ConcurrentHashMap。

L2 · 核心讲解

核心考点定位：面试官要"优化点 + 为什么这么优化"，重点是树化阈值、尾插防死链、扰动函数细节；需区分"性能优化"与"并发安全"两个不同命题。

机制链（≥3 环）：

1. 树化 → 链表查询 O(N)，超阈值转红黑树 O(log N)，缓解 hash 冲突严重时的退化。
2. 尾插 → 1.7 头插在并发扩容时会形成环（死链），1.8 改尾插避免链表断链成环。
3. 扰动 → h ^ (h >>> 16) 让高 16 位参与低 16 位，减少冲突，且比多次位运算开销低。
4. 扩容 → 1.8 不重算 hash，用 (e.hash & oldCap) 判断元素留在原位或移到 原位置+oldCap。
5. 阈值设计 → 树化阈值 8 来自泊松分布，负载因子 0.75 平衡时间与空间，扩容 2 倍保持 2 的幂。
6. 并发对照 → HashMap 所有优化都不解决并发，1.8 的 ConcurrentHashMap 才用 CAS + 锁头节点保证线程安全。

证据锚点：

• 树化阈值：链表长度 > 8（默认 TREEIFY_THRESHOLD=8）且数组 ≥ 64（MIN_TREEIFY_CAPACITY）才转红黑树。
• 扰动函数：h ^ (h >>> 16)，异或，不是按位与——注意别混淆。
• 扩容判定：(e.hash & oldCap) == 0 原位，否则 原位置 + oldCap。
• 初始容量：默认 16，负载因子 0.75，扩容 2 倍。
• 8 的由来：泊松分布，链表长度达 8 概率极低（约 0.00000006），可视为冲突已严重。
• UNTREEIFY_THRESHOLD：树退化回链表的阈值 6。
• TREEIFY_THRESHOLD：转树阈值 8；MIN_TREEIFY_CAPACITY：最小数组容量 64。
• hash & (n-1)：定位桶下标，容量必须 2 的幂才能用位运算代替取模。
• 扩容：容量翻倍后重新分布，只移动 oldCap 位为 1 的桶。
• 泊松分布：哈希桶中节点数服从泊松分布，长度 8 概率约 0.00000006，树化阈值由此确定。
• 2 的幂：初始容量 16 且每次扩容 ×2，保证 hash & (n-1) 等价取模且位置只差 oldCap。
• ConcurrentHashMap：1.8 用 CAS + synchronized 锁头节点，替代 1.7 的 Segment 分段锁。

对比与权衡：

版本	结构	插入	扰动	扩容
1.7	数组+链表	头插（并发会环）	多次位运算	全量重算 hash
1.8	数组+链表+红黑树	尾插	h^(h>>>16)	只判高位，部分移动

常见误区：

1. 错误：扰动是"按位与" → 正确：h ^ (h >>> 16) 是异或 → 为什么：异或让高低位混合，与运算做不到。
2. 错误：链表>8 就树化 → 正确：需同时数组≥64，否则先扩容 → 为什么：数组小先扩容摊薄冲突更优。
3. 错误：1.8 是线程安全 → 正确：仍非线程安全，并发用 ConcurrentHashMap → 为什么：树化/扩容都可能竞态。
4. 错误：扩容必须重算所有 hash → 正确：只判断 (hash & oldCap) 移动部分元素 → 为什么：容量 2 的幂，位置只差 oldCap。
5. 错误：初始容量随便设 → 正确：默认 16，负载因子 0.75 → 为什么：0.75 平衡冲突与空间，避免频繁扩容。
6. 错误：红黑树能解决并发问题 → 正确：树化只是优化查询复杂度，不解决并发 → 为什么：并发安全需 ConcurrentHashMap 的 CAS + 锁分段。
7. 错误：扰动函数可有可无 → 正确：扰动让高 16 位参与，分布更均匀 → 为什么：key 哈希高位差异大时，不扰动会集中碰撞。

适用边界：HashMap 树化会因扩容/删除退化回链表（UNTREEIFY_THRESHOLD=6）；高并发下仍必须 ConcurrentHashMap 而非 HashMap；扩容是性能拐点，若已知元素数量应预估容量避免多次扩容；单线程读多写少可考虑只读副本，避免并发写冲突。

延伸追问（≥3）

1. 为什么树化阈值是 8？

• 要点：泊松分布下链表长度 8 概率约 0.00000006，可视为冲突严重，再长该树化。
• 追问落点：负载因子 0.75 与 8 的推导关系。

1. 1.7 头插为什么并发扩容会死链？

• 要点：头插在并发扩容迁移时，两个线程对同一链表头插导致节点互相指向成环，get 死循环。
• 追问落点：尾插为什么能避免。

1. 扩容为什么不用重算 hash？

• 要点：容量 2 的幂，hash & (n-1) 决定位置；扩容后只需看 hash 的第 oldCap 位，(hash & oldCap)==0 原位否则 +oldCap。
• 追问落点：为什么容量必须 2 的幂。

面试者参考回答（400–700 字）

【结论】 面试官您好，HashMap 1.8 的核心优化有四块——数据结构、插入方式、哈希扰动、扩容策略。

【三点】 第一，数据结构从"数组 + 链表"升级为"数组 + 链表 + 红黑树"：当链表长度超过 8 且数组长度达到 64 时，链表转红黑树，把查询从 O(N) 降到 O(log N)，缓解极端 hash 冲突下的性能退化；这个 8 不是拍脑袋，而是泊松分布下链表长度到 8 的概率约 0.00000006，说明冲突已经很严重。第二，插入从头插改成尾插：1.7 的头插在并发扩容迁移时，两个线程对同一链表头插会让节点互相指向形成环，get 时死循环；尾插按原顺序追加，不会成环，虽然并发下仍非线程安全。第三，哈希扰动从多次位运算简化为 h ^ (h >>> 16)——把高 16 位与低 16 位异或，让高位信息参与定位，减少冲突，开销更低；扩容也不再全量重算 hash，因为容量是 2 的幂，用 (hash & oldCap) == 0 判断元素留在原位还是移到"原位置 + oldCap"，只处理部分元素。

【边界】 当然，这些优化没有让 HashMap 变成线程安全——并发环境下树化、扩容都可能竞态，必须用 ConcurrentHashMap；而且树化不是永久，元素减少到阈值 6 以下会退化回链表。另外 HashMap 不能保证顺序，如果面试官要有序，得用 LinkedHashMap 或 TreeMap。

面试记录 2026-10-30（第 1 次）

题目：HashMap18之后结构的优化有哪些

难度：high

标签：real-interview, db/redis/advanced, company/京东, company/vipkid

评分：⭐⭐⭐☆☆（3/5）

我的回答

JDK 1.8 的核心变动在 HashMap 上，其实是底层算法的变动。底层数据结构吧，它把原来的数组加链表改成了数组加链表加红黑树，会涉及一个经过升级后转化从链表转红黑树的过程。当数组长度超过一定限制，应该是 64，然后链表长度超过了 8 的时候，就需要把这个链表转化为红黑树，提高数据的遍历。另外就是头插法改尾插法。原本头插法在高并发下，或者说在并发下会有一个核心问题，就是它会涉及断跟重新创建链接的过程。如果出现环，会导致整个链接死掉，可能导致核心的链路都断掉的问题。伪差法后，虽然还是不能在并发编程下使用，但是它可以保证不会出现那种核心的问题，死环的问题。还有就是哈希算法的优化。哈希算法它的扰动算法从原本的多次位移转变成把高 16 位的内容与低 16 位内容做按位与,达到高低位内容都能使用到,减少计算开销,提高扰动能力;扩容的优化,原本是每个位置都进行 hash 重算,现在扩容只计算涉及变动的部分,不会全量重算。

点评

优点：四大优化主线正确——树化（阈值 8/64）、头插改尾插（防死链）、扰动优化、扩容不重算只算变动部分；尾插防环的判断准确。

不足：概念错误——扰动算法说成"按位与"，实际是异或 ^（h ^ (h >>> 16)）；未讲 8 的泊松分布由来；树化条件表述"数组超 64 且链表超 8"顺序欠精确。

补充：扰动是异或不是与；树化需链表>8 且数组≥64；8 来自泊松分布，概率约 0.00000006。

完整讲解见上方「完整讲解（权威版）」