都 2026 年了，你真的搞清楚 HashMap 在 JDK 1.7 和 1.8 之间到底变了什么吗？

㊗️本期内容已收录至专栏《Java核心实操(进阶版)》，持续完善知识体系与项目实战，建议先订阅收藏，后续查阅更方便～ ㊙️本期难度指数：⭐⭐⭐ 🉐福利： 一次订阅后，专栏内的所有文章可永久免费看，持续更新中，保底1000+(篇)硬核实战内容。

前言：从一次线上事故说起

那是某年某月，一个凌晨三点的生产环境。

我盯着监控大屏，CPU 飙到 100%，某个服务线程全卡死，日志里一堆 java.lang.OutOfMemoryError，看得我头皮发麻。排查到最后，定位到的罪魁祸首是——几个线程同时往一个 HashMap 里写数据，触发了扩容，然后形成了死循环。

对，你没看错。HashMap 在多线程扩容的时候，会形成链表死循环，然后 CPU 就永远转圈圈了，永不停止，堪称死亡螺旋。

那是 JDK 1.7 的年代。

后来升到 JDK 1.8，这个问题消失了，但并不是说 HashMap 就线程安全了——它只是换了一种方式"坑"你。

所以这篇文章就是我在踩完这些坑、翻完 OpenJDK 源码之后，用我自己的话，把 JDK 1.7 和 JDK 1.8 的 HashMap 到底有哪些区别、为什么要改、改了之后有什么影响，全都讲清楚。

适合人群：

• 刚接触 Java 集合框架、听说过 HashMap 但没深入研究的同学
• 面试前临时抱佛脚想搞清楚这道经典题的同学
• 像我一样在生产环境踩过坑、想彻底搞明白底层原因的同学

全文会从数据结构、哈希算法、插入方式、扩容机制、线程安全问题五个维度展开，每个维度都会有代码和图解辅助。准备好了，咱们开始。

一、先搞清楚 HashMap 的基本骨架

在聊 1.7 和 1.8 的区别之前，先把 HashMap 的基本设计逻辑梳理一遍，不然后面讲变化的时候容易摸不着头脑。

1.1 HashMap 是个什么东西？

说人话就是：一个允许你用任意类型的键来存取值的容器，底层通过哈希表实现快速的存取操作，平均时间复杂度是 O(1)。

用生活化的比喻来说，你可以把 HashMap 想象成一个超大型的快递柜：

• 每个格子有一个编号（数组下标）
• 你寄快递的时候，系统根据你的手机号（键）算出一个格子编号（哈希值），然后把快递放进去
• 取的时候一样，输入手机号，算出格子编号，直接开柜

但问题来了：不同的手机号可能算出同一个格子编号——这就是哈希冲突（Hash Collision）。

解决哈希冲突的方式，HashMap 用的是链地址法（Separate Chaining）——同一个格子里放不下了，就在格子后面挂一条链表，新来的往链表上加。

这是 HashMap 的基础逻辑，在 JDK 1.7 和 1.8 中都一样，区别在于：当链表越来越长的时候，该怎么处理？

二、JDK 1.7 的实现：数组 + 链表

2.1 数据结构

JDK 1.7 的 HashMap，底层是一个 Entry<K, V>[] 数组，每个 Entry 是链表的节点，包含 key、value、hash、next 四个字段。

#mermaid-svg-w23QN7Q19v1N7fZk{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-w23QN7Q19v1N7fZk .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-w23QN7Q19v1N7fZk .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-w23QN7Q19v1N7fZk .error-icon{fill:#552222;}#mermaid-svg-w23QN7Q19v1N7fZk .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-w23QN7Q19v1N7fZk .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-w23QN7Q19v1N7fZk .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-w23QN7Q19v1N7fZk .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-w23QN7Q19v1N7fZk .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-w23QN7Q19v1N7fZk .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-w23QN7Q19v1N7fZk .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-w23QN7Q19v1N7fZk .marker{fill:#333333;stroke:#333333;}#mermaid-svg-w23QN7Q19v1N7fZk .marker.cross{stroke:#333333;}#mermaid-svg-w23QN7Q19v1N7fZk svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-w23QN7Q19v1N7fZk p{margin:0;}#mermaid-svg-w23QN7Q19v1N7fZk .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-w23QN7Q19v1N7fZk .cluster-label text{fill:#333;}#mermaid-svg-w23QN7Q19v1N7fZk .cluster-label span{color:#333;}#mermaid-svg-w23QN7Q19v1N7fZk .cluster-label span p{background-color:transparent;}#mermaid-svg-w23QN7Q19v1N7fZk .label text,#mermaid-svg-w23QN7Q19v1N7fZk span{fill:#333;color:#333;}#mermaid-svg-w23QN7Q19v1N7fZk .node rect,#mermaid-svg-w23QN7Q19v1N7fZk .node circle,#mermaid-svg-w23QN7Q19v1N7fZk .node ellipse,#mermaid-svg-w23QN7Q19v1N7fZk .node polygon,#mermaid-svg-w23QN7Q19v1N7fZk .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-w23QN7Q19v1N7fZk .rough-node .label text,#mermaid-svg-w23QN7Q19v1N7fZk .node .label text,#mermaid-svg-w23QN7Q19v1N7fZk .image-shape .label,#mermaid-svg-w23QN7Q19v1N7fZk .icon-shape .label{text-anchor:middle;}#mermaid-svg-w23QN7Q19v1N7fZk .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-w23QN7Q19v1N7fZk .rough-node .label,#mermaid-svg-w23QN7Q19v1N7fZk .node .label,#mermaid-svg-w23QN7Q19v1N7fZk .image-shape .label,#mermaid-svg-w23QN7Q19v1N7fZk .icon-shape .label{text-align:center;}#mermaid-svg-w23QN7Q19v1N7fZk .node.clickable{cursor:pointer;}#mermaid-svg-w23QN7Q19v1N7fZk .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-w23QN7Q19v1N7fZk .arrowheadPath{fill:#333333;}#mermaid-svg-w23QN7Q19v1N7fZk .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-w23QN7Q19v1N7fZk .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-w23QN7Q19v1N7fZk .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-w23QN7Q19v1N7fZk .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-w23QN7Q19v1N7fZk .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-w23QN7Q19v1N7fZk .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-w23QN7Q19v1N7fZk .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-w23QN7Q19v1N7fZk .cluster text{fill:#333;}#mermaid-svg-w23QN7Q19v1N7fZk .cluster span{color:#333;}#mermaid-svg-w23QN7Q19v1N7fZk div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-w23QN7Q19v1N7fZk .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-w23QN7Q19v1N7fZk rect.text{fill:none;stroke-width:0;}#mermaid-svg-w23QN7Q19v1N7fZk .icon-shape,#mermaid-svg-w23QN7Q19v1N7fZk .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-w23QN7Q19v1N7fZk .icon-shape p,#mermaid-svg-w23QN7Q19v1N7fZk .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-w23QN7Q19v1N7fZk .icon-shape .label rect,#mermaid-svg-w23QN7Q19v1N7fZk .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-w23QN7Q19v1N7fZk .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-w23QN7Q19v1N7fZk .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-w23QN7Q19v1N7fZk :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

HashMap内部数组 table[]

table[0]: null

table[1]: Entry{k1,v1}

table[2]: Entry{k2,v2} -> Entry{k3,v3} -> Entry{k4,v4}

table[3]: null

table[4]: Entry{k5,v5} -> Entry{k6,v6}

…

这张图就是 JDK 1.7 HashMap 的真实状态：大部分位置是 null，有些位置只挂了一个节点，有些位置因为哈希冲突，挂了一条长长的链表。

2.2 哈希算法：对扰动函数的执念

JDK 1.7 对 key 的 hashCode 做了四次扰动，目的是让哈希分布更均匀，减少冲突：

// JDK 1.7 的 hash 方法
static int hash(int h) {
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}

// 然后通过这个方法计算数组下标
static int indexFor(int h, int length) {
return h & (length – 1); // 等价于 h % length，但位运算更快
}

说实话，第一次看到这段代码的时候我是懵的。这几个右移和异或操作，粗看像是乱写的，其实背后是有数学依据的——通过多次移位和异或，把高位的信息"混入"低位，这样在 & (length – 1) 的时候，高位信息也能参与到下标计算中，减少碰撞概率。

2.3 插入方式：头插法

JDK 1.7 往链表里插入新节点，用的是头插法——每次都把新节点放到链表的头部，原有的节点往后挪。

为什么用头插法？当年的设计者觉得：新插入的数据被访问的概率更高（局部性原理），放在头部可以更快被找到。

这个逻辑听起来没问题，但问题藏在扩容的时候……等我们讲到多线程问题那节再展开。

// JDK 1.7 的 addEntry 和 createEntry（简化版）
void addEntry(int hash, K key, V value, int bucketIndex) {
if ((size >= threshold) && (null != table[bucketIndex])) {
resize(2 * table.length); // 扩容
// …重新计算 hash 和 bucketIndex
}
createEntry(hash, key, value, bucketIndex);
}

void createEntry(int hash, K key, V value, int bucketIndex) {
Entry<K,V> e = table[bucketIndex];
// 头插法：新节点的 next 指向原来的头节点
table[bucketIndex] = new Entry<>(hash, key, value, e);
size++;
}

2.4 扩容机制

JDK 1.7 扩容的触发条件：当 size >= threshold（threshold = capacity × loadFactor，默认 16 × 0.75 = 12）且当前 bucket 非空时，触发扩容，容量翻倍。

扩容时，每一个元素都要重新计算哈希值和新数组下标，然后再把元素重新插入新数组。这个过程叫 rehash。

// JDK 1.7 的 transfer 方法（扩容核心逻辑，简化版）
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next;
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity);
// 头插法！新数组里也是头插
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}

注意那个头插法——单线程下没问题，多线程下这就是灾难的起源。后面重点讲。

三、JDK 1.8 的进化：数组 + 链表 + 红黑树

3.1 最大的变化：引入红黑树

JDK 1.8 对 HashMap 做了重大重构，最显眼的变化是：当链表长度超过 8，且数组长度达到 64 时，链表会转换成红黑树。

为什么要引入红黑树？

链表查找的时间复杂度是 O(n)，如果哈希冲突严重，链表越来越长，性能就越来越差。红黑树的查找复杂度是 O(log n)，在链表比较长的场景下，性能提升非常明显。

但是红黑树的维护成本也比链表高，节点数少的时候，用链表反而更轻量。所以 JDK 1.8 选了一个阈值：8。这个值的选取基于泊松分布的计算——在默认负载因子（0.75）的情况下，一个 bucket 里链表长度超过 8 的概率约为 0.00000006，也就是说正常情况下很少会触发树化，只有在哈希函数特别差或者恶意攻击的情况下才会出现。

#mermaid-svg-sPSczN3gMryh8YA2{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-sPSczN3gMryh8YA2 .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-sPSczN3gMryh8YA2 .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-sPSczN3gMryh8YA2 .error-icon{fill:#552222;}#mermaid-svg-sPSczN3gMryh8YA2 .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-sPSczN3gMryh8YA2 .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-sPSczN3gMryh8YA2 .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-sPSczN3gMryh8YA2 .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-sPSczN3gMryh8YA2 .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-sPSczN3gMryh8YA2 .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-sPSczN3gMryh8YA2 .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-sPSczN3gMryh8YA2 .marker{fill:#333333;stroke:#333333;}#mermaid-svg-sPSczN3gMryh8YA2 .marker.cross{stroke:#333333;}#mermaid-svg-sPSczN3gMryh8YA2 svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-sPSczN3gMryh8YA2 p{margin:0;}#mermaid-svg-sPSczN3gMryh8YA2 .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-sPSczN3gMryh8YA2 .cluster-label text{fill:#333;}#mermaid-svg-sPSczN3gMryh8YA2 .cluster-label span{color:#333;}#mermaid-svg-sPSczN3gMryh8YA2 .cluster-label span p{background-color:transparent;}#mermaid-svg-sPSczN3gMryh8YA2 .label text,#mermaid-svg-sPSczN3gMryh8YA2 span{fill:#333;color:#333;}#mermaid-svg-sPSczN3gMryh8YA2 .node rect,#mermaid-svg-sPSczN3gMryh8YA2 .node circle,#mermaid-svg-sPSczN3gMryh8YA2 .node ellipse,#mermaid-svg-sPSczN3gMryh8YA2 .node polygon,#mermaid-svg-sPSczN3gMryh8YA2 .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-sPSczN3gMryh8YA2 .rough-node .label text,#mermaid-svg-sPSczN3gMryh8YA2 .node .label text,#mermaid-svg-sPSczN3gMryh8YA2 .image-shape .label,#mermaid-svg-sPSczN3gMryh8YA2 .icon-shape .label{text-anchor:middle;}#mermaid-svg-sPSczN3gMryh8YA2 .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-sPSczN3gMryh8YA2 .rough-node .label,#mermaid-svg-sPSczN3gMryh8YA2 .node .label,#mermaid-svg-sPSczN3gMryh8YA2 .image-shape .label,#mermaid-svg-sPSczN3gMryh8YA2 .icon-shape .label{text-align:center;}#mermaid-svg-sPSczN3gMryh8YA2 .node.clickable{cursor:pointer;}#mermaid-svg-sPSczN3gMryh8YA2 .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-sPSczN3gMryh8YA2 .arrowheadPath{fill:#333333;}#mermaid-svg-sPSczN3gMryh8YA2 .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-sPSczN3gMryh8YA2 .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-sPSczN3gMryh8YA2 .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-sPSczN3gMryh8YA2 .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-sPSczN3gMryh8YA2 .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-sPSczN3gMryh8YA2 .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-sPSczN3gMryh8YA2 .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-sPSczN3gMryh8YA2 .cluster text{fill:#333;}#mermaid-svg-sPSczN3gMryh8YA2 .cluster span{color:#333;}#mermaid-svg-sPSczN3gMryh8YA2 div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-sPSczN3gMryh8YA2 .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-sPSczN3gMryh8YA2 rect.text{fill:none;stroke-width:0;}#mermaid-svg-sPSczN3gMryh8YA2 .icon-shape,#mermaid-svg-sPSczN3gMryh8YA2 .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-sPSczN3gMryh8YA2 .icon-shape p,#mermaid-svg-sPSczN3gMryh8YA2 .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-sPSczN3gMryh8YA2 .icon-shape .label rect,#mermaid-svg-sPSczN3gMryh8YA2 .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-sPSczN3gMryh8YA2 .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-sPSczN3gMryh8YA2 .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-sPSczN3gMryh8YA2 :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

是

否

是

否

是

否

是

否

put(key, value)

计算哈希值确定bucket位置

bucket是否为空?

直接插入节点

当前节点是红黑树节点?

按红黑树方式插入

遍历链表

找到相同key?

更新value

链表尾部插入

链表长度 >= 8且数组长度 >= 64?

链表转红黑树 treeifyBin()

保持链表结构

size++，检查是否需要扩容

3.2 数据结构变化

节点类型从 Entry 变成了 Node（正常情况）和 TreeNode（树化之后）：

// JDK 1.8 的 Node 类
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
// …
}

// JDK 1.8 的 TreeNode 类（继承自 LinkedHashMap.Entry，再继承自 Node）
static final class TreeNode<K,V> extends LinkedHashMap.Entry<K,V> {
TreeNode<K,V> parent; // 父节点
TreeNode<K,V> left; // 左子节点
TreeNode<K,V> right; // 右子节点
TreeNode<K,V> prev; // 用于删除时维护链表
boolean red; // 颜色标志
// …
}

3.3 哈希算法简化

JDK 1.8 把原来的四次扰动简化成了一次扰动：

// JDK 1.8 的 hash 方法
static final int hash(Object key) {
int h;
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

只做了一次右移 16 位再异或。为什么够用了？因为 JDK 1.8 引入了红黑树，即使冲突稍多一点，也能保证查询性能，不需要像 1.7 那样用复杂的扰动来极力减少冲突。

另外，null 键会被映射到下标 0，这一点两个版本都一样。

3.4 插入方式：尾插法

这是 JDK 1.8 一个非常关键的改变：链表的插入方式从头插法改成了尾插法。

新节点不再插到链表头部，而是插到链表尾部。这个改变看似微小，却直接解决了多线程扩容时死循环的问题（虽然并没有让 HashMap 变成线程安全的，但至少不会死循环了）。

// JDK 1.8 的 putVal 方法（链表插入部分，简化版）
for (int binCount = 0; ; ++binCount) {
if ((e = p.next) == null) {
// 尾插法！
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD – 1) // TREEIFY_THRESHOLD = 8
treeifyBin(tab, hash); // 转红黑树
break;
}
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
break;
p = e;
}

3.5 扩容优化：高低位拆分

JDK 1.8 扩容时有一个非常精妙的优化，不再需要像 1.7 那样每个元素都重新计算哈希值。

逻辑是这样的：数组容量始终是 2 的幂次（设原容量为 n），扩容后变成 2n。元素在新数组中的位置，要么还在原来的下标 i，要么在 i + n。判断的依据是元素的哈希值的第 log2(n) + 1 位（也就是新增的那一位掩码位）是 0 还是 1。

// JDK 1.8 扩容的核心判断逻辑（简化版）
// e.hash & oldCap 如果为 0，新下标 = 原下标
// e.hash & oldCap 如果为 1，新下标 = 原下标 + oldCap
do {
next = e.next;
if ((e.hash & oldCap) == 0) {
// 放到低位链表（lo 链表），位置不变
if (loTail == null) loHead = e;
else loTail.next = e;
loTail = e;
} else {
// 放到高位链表（hi 链表），位置 = 原位置 + 原容量
if (hiTail == null) hiHead = e;
else hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);

这个优化有两个好处：

#mermaid-svg-oXzLtgA7fWqqC0WO{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-oXzLtgA7fWqqC0WO .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-oXzLtgA7fWqqC0WO .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-oXzLtgA7fWqqC0WO .error-icon{fill:#552222;}#mermaid-svg-oXzLtgA7fWqqC0WO .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-oXzLtgA7fWqqC0WO .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-oXzLtgA7fWqqC0WO .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-oXzLtgA7fWqqC0WO .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-oXzLtgA7fWqqC0WO .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-oXzLtgA7fWqqC0WO .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-oXzLtgA7fWqqC0WO .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-oXzLtgA7fWqqC0WO .marker{fill:#333333;stroke:#333333;}#mermaid-svg-oXzLtgA7fWqqC0WO .marker.cross{stroke:#333333;}#mermaid-svg-oXzLtgA7fWqqC0WO svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-oXzLtgA7fWqqC0WO p{margin:0;}#mermaid-svg-oXzLtgA7fWqqC0WO .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-oXzLtgA7fWqqC0WO .cluster-label text{fill:#333;}#mermaid-svg-oXzLtgA7fWqqC0WO .cluster-label span{color:#333;}#mermaid-svg-oXzLtgA7fWqqC0WO .cluster-label span p{background-color:transparent;}#mermaid-svg-oXzLtgA7fWqqC0WO .label text,#mermaid-svg-oXzLtgA7fWqqC0WO span{fill:#333;color:#333;}#mermaid-svg-oXzLtgA7fWqqC0WO .node rect,#mermaid-svg-oXzLtgA7fWqqC0WO .node circle,#mermaid-svg-oXzLtgA7fWqqC0WO .node ellipse,#mermaid-svg-oXzLtgA7fWqqC0WO .node polygon,#mermaid-svg-oXzLtgA7fWqqC0WO .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-oXzLtgA7fWqqC0WO .rough-node .label text,#mermaid-svg-oXzLtgA7fWqqC0WO .node .label text,#mermaid-svg-oXzLtgA7fWqqC0WO .image-shape .label,#mermaid-svg-oXzLtgA7fWqqC0WO .icon-shape .label{text-anchor:middle;}#mermaid-svg-oXzLtgA7fWqqC0WO .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-oXzLtgA7fWqqC0WO .rough-node .label,#mermaid-svg-oXzLtgA7fWqqC0WO .node .label,#mermaid-svg-oXzLtgA7fWqqC0WO .image-shape .label,#mermaid-svg-oXzLtgA7fWqqC0WO .icon-shape .label{text-align:center;}#mermaid-svg-oXzLtgA7fWqqC0WO .node.clickable{cursor:pointer;}#mermaid-svg-oXzLtgA7fWqqC0WO .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-oXzLtgA7fWqqC0WO .arrowheadPath{fill:#333333;}#mermaid-svg-oXzLtgA7fWqqC0WO .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-oXzLtgA7fWqqC0WO .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-oXzLtgA7fWqqC0WO .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-oXzLtgA7fWqqC0WO .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-oXzLtgA7fWqqC0WO .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-oXzLtgA7fWqqC0WO .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-oXzLtgA7fWqqC0WO .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-oXzLtgA7fWqqC0WO .cluster text{fill:#333;}#mermaid-svg-oXzLtgA7fWqqC0WO .cluster span{color:#333;}#mermaid-svg-oXzLtgA7fWqqC0WO div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-oXzLtgA7fWqqC0WO .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-oXzLtgA7fWqqC0WO rect.text{fill:none;stroke-width:0;}#mermaid-svg-oXzLtgA7fWqqC0WO .icon-shape,#mermaid-svg-oXzLtgA7fWqqC0WO .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-oXzLtgA7fWqqC0WO .icon-shape p,#mermaid-svg-oXzLtgA7fWqqC0WO .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-oXzLtgA7fWqqC0WO .icon-shape .label rect,#mermaid-svg-oXzLtgA7fWqqC0WO .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-oXzLtgA7fWqqC0WO .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-oXzLtgA7fWqqC0WO .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-oXzLtgA7fWqqC0WO :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

扩容后 capacity=16

扩容前 capacity=8

hash & 8 == 0

hash & 8 != 0

hash & 8 != 0

index 0

hash:01001 key:A

hash:10001 key:B

hash:11001 key:C

index 0 (bit=0)

key:A hash:01001

index 8 (bit=1)

key:B hash:10001

key:C hash:11001

四、核心区别汇总对比

到这里，核心的变化已经全部讲完了，来个表格对比一下，方便记忆：

五、最容易被忽视的坑：线程安全问题

这部分是整篇文章最重要的实战内容。我在前言里提到的那次线上事故，就出在这里。

5.1 JDK 1.7 的死循环问题

先用图来理解 JDK 1.7 扩容时为什么会死循环。

假设当前链表是 A -> B -> null，两个线程同时触发扩容：

共享内存

线程2

线程1

共享内存

线程2

线程1

#mermaid-svg-nGUteG2ROhgjZ83E{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-nGUteG2ROhgjZ83E .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-nGUteG2ROhgjZ83E .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-nGUteG2ROhgjZ83E .error-icon{fill:#552222;}#mermaid-svg-nGUteG2ROhgjZ83E .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-nGUteG2ROhgjZ83E .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-nGUteG2ROhgjZ83E .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-nGUteG2ROhgjZ83E .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-nGUteG2ROhgjZ83E .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-nGUteG2ROhgjZ83E .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-nGUteG2ROhgjZ83E .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-nGUteG2ROhgjZ83E .marker{fill:#333333;stroke:#333333;}#mermaid-svg-nGUteG2ROhgjZ83E .marker.cross{stroke:#333333;}#mermaid-svg-nGUteG2ROhgjZ83E svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-nGUteG2ROhgjZ83E p{margin:0;}#mermaid-svg-nGUteG2ROhgjZ83E .actor{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-nGUteG2ROhgjZ83E text.actor>tspan{fill:black;stroke:none;}#mermaid-svg-nGUteG2ROhgjZ83E .actor-line{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);}#mermaid-svg-nGUteG2ROhgjZ83E .innerArc{stroke-width:1.5;stroke-dasharray:none;}#mermaid-svg-nGUteG2ROhgjZ83E .messageLine0{stroke-width:1.5;stroke-dasharray:none;stroke:#333;}#mermaid-svg-nGUteG2ROhgjZ83E .messageLine1{stroke-width:1.5;stroke-dasharray:2,2;stroke:#333;}#mermaid-svg-nGUteG2ROhgjZ83E #arrowhead path{fill:#333;stroke:#333;}#mermaid-svg-nGUteG2ROhgjZ83E .sequenceNumber{fill:white;}#mermaid-svg-nGUteG2ROhgjZ83E #sequencenumber{fill:#333;}#mermaid-svg-nGUteG2ROhgjZ83E #crosshead path{fill:#333;stroke:#333;}#mermaid-svg-nGUteG2ROhgjZ83E .messageText{fill:#333;stroke:none;}#mermaid-svg-nGUteG2ROhgjZ83E .labelBox{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-nGUteG2ROhgjZ83E .labelText,#mermaid-svg-nGUteG2ROhgjZ83E .labelText>tspan{fill:black;stroke:none;}#mermaid-svg-nGUteG2ROhgjZ83E .loopText,#mermaid-svg-nGUteG2ROhgjZ83E .loopText>tspan{fill:black;stroke:none;}#mermaid-svg-nGUteG2ROhgjZ83E .loopLine{stroke-width:2px;stroke-dasharray:2,2;stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);}#mermaid-svg-nGUteG2ROhgjZ83E .note{stroke:#aaaa33;fill:#fff5ad;}#mermaid-svg-nGUteG2ROhgjZ83E .noteText,#mermaid-svg-nGUteG2ROhgjZ83E .noteText>tspan{fill:black;stroke:none;}#mermaid-svg-nGUteG2ROhgjZ83E .activation0{fill:#f4f4f4;stroke:#666;}#mermaid-svg-nGUteG2ROhgjZ83E .activation1{fill:#f4f4f4;stroke:#666;}#mermaid-svg-nGUteG2ROhgjZ83E .activation2{fill:#f4f4f4;stroke:#666;}#mermaid-svg-nGUteG2ROhgjZ83E .actorPopupMenu{position:absolute;}#mermaid-svg-nGUteG2ROhgjZ83E .actorPopupMenuPanel{position:absolute;fill:#ECECFF;box-shadow:0px 8px 16px 0px rgba(0,0,0,0.2);filter:drop-shadow(3px 5px 2px rgb(0 0 0 / 0.4));}#mermaid-svg-nGUteG2ROhgjZ83E .actor-man line{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;}#mermaid-svg-nGUteG2ROhgjZ83E .actor-man circle,#mermaid-svg-nGUteG2ROhgjZ83E line{stroke:hsl(259.6261682243, 59.7765363128%, 87.9019607843%);fill:#ECECFF;stroke-width:2px;}#mermaid-svg-nGUteG2ROhgjZ83E :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

原链表: A ->> B ->> null

扩容后(头插法): B ->> A ->> null

⚠️ 形成环: A ->> B ->> A ->> B…

读取 e=A, next=B

线程1被挂起(时间片用完)

完成整个扩容过程

恢复执行

头插A到新table: A ->> null

next=B, 继续处理B

B.next = A (因为扩容后B.next指向A)

头插B: B ->> A ->> null

next = A (B.next在扩容前是A)

处理A: A.next已指向B

核心原因：头插法在扩容时会反转链表顺序，两个线程并发执行时，会形成一个指针环，导致后续的 get 操作陷入无限循环，CPU 100%。

5.2 JDK 1.8 的改进与残留问题

JDK 1.8 改成尾插法之后，扩容时不再反转链表，所以不会再出现死循环。但是——

HashMap 在 JDK 1.8 中仍然不是线程安全的！多线程并发 put 时，可能会出现数据丢失：

// 这是一个反面教材！千万不要在多线程环境下这样用！
HashMap<String, Integer> map = new HashMap<>();

// 线程1和线程2同时执行 put，且两个 key 映射到同一个 bucket
// 当两个线程同时判断 (p.next == null) 为 true
// 都执行 p.next = newNode(…)
// 其中一个线程的写入会被覆盖，数据直接丢失！

另外，JDK 1.8 的扩容过程中，多线程可能导致 table 引用和 size 不一致，最终也会出现各种稀奇古怪的问题，比如 get 返回 null（明明已经 put 过了）。

5.3 正确的多线程方案

老实说，工作这么多年，我见过太多把 HashMap 用在多线程场景的代码了。这里给出几个正确姿势：

方案一：使用 ConcurrentHashMap（推荐）

import java.util.concurrent.ConcurrentHashMap;

// 直接替换，API 基本一致
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap<>();

// JDK 1.7: 分段锁（Segment）
// JDK 1.8: CAS + synchronized，锁的粒度更细（只锁链表/树的头节点）
map.put("user_count", 100);
Integer count = map.get("user_count");

// 原子操作：不存在才插入
map.putIfAbsent("session_id", 1);

// 原子操作：计算并更新
map.compute("visit_count", (key, oldVal) -> oldVal == null ? 1 : oldVal + 1);

方案二：Collections.synchronizedMap（不推荐，性能差）

Map<String, String> syncMap = Collections.synchronizedMap(new HashMap<>());
// 所有操作都加了 synchronized，并发性能很差
// 而且遍历的时候还需要手动加锁，否则依然不安全
synchronized (syncMap) {
for (Map.Entry<String, String> entry : syncMap.entrySet()) {
// 遍历逻辑
}
}

方案三：Hashtable（别用了，太老了）

// Hashtable 的所有方法都加了 synchronized
// 性能比 Collections.synchronizedMap 还差
// 而且继承了很多历史遗留问题，现代项目别用这个了
Hashtable<String, String> table = new Hashtable<>();

结论：多线程场景，老老实实用 ConcurrentHashMap。

六、红黑树的那些细节

红黑树这块很多文章一笔带过，但如果面试被问到"为什么用红黑树而不用 AVL 树"，不提前想清楚可能会答错。

6.1 红黑树 vs AVL 树

AVL 树是严格平衡的二叉搜索树，左右子树高度差不超过 1，查找效率极高，但维护平衡的代价也大——每次插入删除都可能触发大量旋转操作。

红黑树是"近似平衡"的，不要求严格平衡，插入和删除时旋转次数更少（最多 3 次旋转）。对于 HashMap 这种读写都频繁的场景，红黑树的综合性能更优。

#mermaid-svg-vIoAJVH08MpGtjho{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;fill:#333;}@keyframes edge-animation-frame{from{stroke-dashoffset:0;}}@keyframes dash{to{stroke-dashoffset:0;}}#mermaid-svg-vIoAJVH08MpGtjho .edge-animation-slow{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 50s linear infinite;stroke-linecap:round;}#mermaid-svg-vIoAJVH08MpGtjho .edge-animation-fast{stroke-dasharray:9,5!important;stroke-dashoffset:900;animation:dash 20s linear infinite;stroke-linecap:round;}#mermaid-svg-vIoAJVH08MpGtjho .error-icon{fill:#552222;}#mermaid-svg-vIoAJVH08MpGtjho .error-text{fill:#552222;stroke:#552222;}#mermaid-svg-vIoAJVH08MpGtjho .edge-thickness-normal{stroke-width:1px;}#mermaid-svg-vIoAJVH08MpGtjho .edge-thickness-thick{stroke-width:3.5px;}#mermaid-svg-vIoAJVH08MpGtjho .edge-pattern-solid{stroke-dasharray:0;}#mermaid-svg-vIoAJVH08MpGtjho .edge-thickness-invisible{stroke-width:0;fill:none;}#mermaid-svg-vIoAJVH08MpGtjho .edge-pattern-dashed{stroke-dasharray:3;}#mermaid-svg-vIoAJVH08MpGtjho .edge-pattern-dotted{stroke-dasharray:2;}#mermaid-svg-vIoAJVH08MpGtjho .marker{fill:#333333;stroke:#333333;}#mermaid-svg-vIoAJVH08MpGtjho .marker.cross{stroke:#333333;}#mermaid-svg-vIoAJVH08MpGtjho svg{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:16px;}#mermaid-svg-vIoAJVH08MpGtjho p{margin:0;}#mermaid-svg-vIoAJVH08MpGtjho .label{font-family:\”trebuchet ms\”,verdana,arial,sans-serif;color:#333;}#mermaid-svg-vIoAJVH08MpGtjho .cluster-label text{fill:#333;}#mermaid-svg-vIoAJVH08MpGtjho .cluster-label span{color:#333;}#mermaid-svg-vIoAJVH08MpGtjho .cluster-label span p{background-color:transparent;}#mermaid-svg-vIoAJVH08MpGtjho .label text,#mermaid-svg-vIoAJVH08MpGtjho span{fill:#333;color:#333;}#mermaid-svg-vIoAJVH08MpGtjho .node rect,#mermaid-svg-vIoAJVH08MpGtjho .node circle,#mermaid-svg-vIoAJVH08MpGtjho .node ellipse,#mermaid-svg-vIoAJVH08MpGtjho .node polygon,#mermaid-svg-vIoAJVH08MpGtjho .node path{fill:#ECECFF;stroke:#9370DB;stroke-width:1px;}#mermaid-svg-vIoAJVH08MpGtjho .rough-node .label text,#mermaid-svg-vIoAJVH08MpGtjho .node .label text,#mermaid-svg-vIoAJVH08MpGtjho .image-shape .label,#mermaid-svg-vIoAJVH08MpGtjho .icon-shape .label{text-anchor:middle;}#mermaid-svg-vIoAJVH08MpGtjho .node .katex path{fill:#000;stroke:#000;stroke-width:1px;}#mermaid-svg-vIoAJVH08MpGtjho .rough-node .label,#mermaid-svg-vIoAJVH08MpGtjho .node .label,#mermaid-svg-vIoAJVH08MpGtjho .image-shape .label,#mermaid-svg-vIoAJVH08MpGtjho .icon-shape .label{text-align:center;}#mermaid-svg-vIoAJVH08MpGtjho .node.clickable{cursor:pointer;}#mermaid-svg-vIoAJVH08MpGtjho .root .anchor path{fill:#333333!important;stroke-width:0;stroke:#333333;}#mermaid-svg-vIoAJVH08MpGtjho .arrowheadPath{fill:#333333;}#mermaid-svg-vIoAJVH08MpGtjho .edgePath .path{stroke:#333333;stroke-width:2.0px;}#mermaid-svg-vIoAJVH08MpGtjho .flowchart-link{stroke:#333333;fill:none;}#mermaid-svg-vIoAJVH08MpGtjho .edgeLabel{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-vIoAJVH08MpGtjho .edgeLabel p{background-color:rgba(232,232,232, 0.8);}#mermaid-svg-vIoAJVH08MpGtjho .edgeLabel rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-vIoAJVH08MpGtjho .labelBkg{background-color:rgba(232, 232, 232, 0.5);}#mermaid-svg-vIoAJVH08MpGtjho .cluster rect{fill:#ffffde;stroke:#aaaa33;stroke-width:1px;}#mermaid-svg-vIoAJVH08MpGtjho .cluster text{fill:#333;}#mermaid-svg-vIoAJVH08MpGtjho .cluster span{color:#333;}#mermaid-svg-vIoAJVH08MpGtjho div.mermaidTooltip{position:absolute;text-align:center;max-width:200px;padding:2px;font-family:\”trebuchet ms\”,verdana,arial,sans-serif;font-size:12px;background:hsl(80, 100%, 96.2745098039%);border:1px solid #aaaa33;border-radius:2px;pointer-events:none;z-index:100;}#mermaid-svg-vIoAJVH08MpGtjho .flowchartTitleText{text-anchor:middle;font-size:18px;fill:#333;}#mermaid-svg-vIoAJVH08MpGtjho rect.text{fill:none;stroke-width:0;}#mermaid-svg-vIoAJVH08MpGtjho .icon-shape,#mermaid-svg-vIoAJVH08MpGtjho .image-shape{background-color:rgba(232,232,232, 0.8);text-align:center;}#mermaid-svg-vIoAJVH08MpGtjho .icon-shape p,#mermaid-svg-vIoAJVH08MpGtjho .image-shape p{background-color:rgba(232,232,232, 0.8);padding:2px;}#mermaid-svg-vIoAJVH08MpGtjho .icon-shape .label rect,#mermaid-svg-vIoAJVH08MpGtjho .image-shape .label rect{opacity:0.5;background-color:rgba(232,232,232, 0.8);fill:rgba(232,232,232, 0.8);}#mermaid-svg-vIoAJVH08MpGtjho .label-icon{display:inline-block;height:1em;overflow:visible;vertical-align:-0.125em;}#mermaid-svg-vIoAJVH08MpGtjho .node .label-icon path{fill:currentColor;stroke:revert;stroke-width:revert;}#mermaid-svg-vIoAJVH08MpGtjho :root{–mermaid-font-family:\”trebuchet ms\”,verdana,arial,sans-serif;}

红黑树示例 (HashMap内的 bucket)

黑节点: 7

红节点: 3

黑节点: 11

黑节点: 1

黑节点: 5

红节点: 9

红节点: 13

6.2 树化与反树化阈值为什么是 8 和 6？

• 树化阈值 8：泊松分布计算的结果，正常情况下链表长度超过 8 的概率极低（约 6×10⁻⁸），只有哈希函数很差或者数据刻意构造的时候才会发生。
• 反树化阈值 6：并不是 7，而是 6，为了防止频繁在链表和红黑树之间来回转换——如果树化和反树化的阈值一样，比如都是 8，那么删除一个元素变成 7 就退化成链表，再插入一个变成 8 又树化，这就是性能抖动，很蠢。设置一个差值（8 – 6 = 2）来做缓冲，是很合理的设计。

// JDK 1.8 中相关的常量定义
static final int TREEIFY_THRESHOLD = 8; // 树化阈值
static final int UNTREEIFY_THRESHOLD = 6; // 反树化阈值
static final int MIN_TREEIFY_CAPACITY = 64; // 最小树化数组容量

注意 MIN_TREEIFY_CAPACITY = 64 这个常量——如果数组长度还不到 64，即使链表长度超过 8，也不会树化，而是选择扩容。这是因为当数组长度比较小的时候，扩容可以更有效地减少哈希冲突，没必要急着树化。

七、从实战角度：如何用好 HashMap？

光知道原理还不够，工程上怎么用才是关键。

7.1 初始化容量的设置

这个细节很多人忽略，但可能对性能有影响。

如果你已经知道 HashMap 里大概会放多少元素，应该在初始化的时候就指定容量，避免频繁扩容：

// 反面教材：不指定初始容量
Map<String, Object> userInfo = new HashMap<>();
// 随着数据增加，会触发多次扩容（每次扩容都要 rehash，性能开销大）

// 正确做法：预估好数量，除以负载因子，向上取整到 2 的幂
// 比如预计存 100 个元素：100 / 0.75 = 134，所以初始化 256（2^8）
Map<String, Object> userInfoOptimized = new HashMap<>(256);

// 或者用 Guava 提供的工具方法，它帮你算好了
// Maps.newHashMapWithExpectedSize(100)
// 等价于 new HashMap<>(147)，内部按 expectedSize / 0.75 + 1 计算

7.2 Key 的设计原则

HashMap 的 key 需要正确实现 hashCode() 和 equals() 方法，这几乎是个老生常谈的点，但踩坑的人依然不少：

// 反面教材：用可变对象作为 key
public class MutableKey {
private String name;
// 省略 hashCode 和 equals，都基于 name
}

Map<MutableKey, String> map = new HashMap<>();
MutableKey key = new MutableKey("Alice");
map.put(key, "工程师");

key.setName("Bob"); // 修改了 key 的属性！
// 此时 key 的 hashCode 变了，但它在 map 里存的位置没变
// get 操作用新的 hashCode 找，找到错误的 bucket，返回 null
String value = map.get(key); // null！！！
System.out.println(value); // 数据"丢失"了，其实还在，只是找不到了

最佳实践：用不可变对象作为 key，比如 String、Integer 等包装类，或者你自己定义的 final 类。

// 正确做法：用不可变的 String 作为 key
Map<String, UserInfo> userMap = new HashMap<>();
userMap.put("user_001", new UserInfo("Alice", 28));
// String 是不可变的，hashCode 不会变，安全

7.3 一个完整的电商场景示例

结合一个真实场景来展示 HashMap 的合理用法——一个简单的商品库存管理模块：

import java.util.HashMap;
import java.util.Map;
import java.util.concurrent.ConcurrentHashMap;

/**
* 商品库存管理服务
* 单机版用 HashMap，分布式场景需要换成 Redis
*/
public class InventoryService {

// 单线程操作用 HashMap（比如批量导入场景）
private final HashMap<String, Integer> localCache;

// 多线程操作用 ConcurrentHashMap（比如并发下单场景）
private final ConcurrentHashMap<String, Integer> stockMap;

public InventoryService(int expectedProductCount) {
// 预估商品数量，计算合理的初始容量，避免扩容开销
// expectedProductCount / 0.75 + 1，取最近的 2 的幂
int initialCapacity = tableSizeFor((int)(expectedProductCount / 0.75f + 1.0f));

this.localCache = new HashMap<>(initialCapacity);
this.stockMap = new ConcurrentHashMap<>(initialCapacity);
}

/**
* 批量初始化库存（单线程批量导入，用普通 HashMap 处理后转入）
*/
public void batchInitStock(Map<String, Integer> stockData) {
// 在单线程的批量处理逻辑里用 HashMap 临时存储，性能更好
HashMap<String, Integer> tempMap = new HashMap<>(stockData.size() * 2);

for (Map.Entry<String, Integer> entry : stockData.entrySet()) {
String skuId = entry.getKey();
Integer stock = entry.getValue();

// 简单的数据校验
if (skuId == null || skuId.isBlank() || stock == null || stock < 0) {
System.err.printf("非法库存数据，跳过：skuId=%s, stock=%s%n", skuId, stock);
continue;
}

tempMap.put(skuId, stock);
}

// 批量转入线程安全的 ConcurrentHashMap
stockMap.putAll(tempMap);
System.out.printf("成功初始化 %d 个 SKU 的库存数据%n", tempMap.size());
}

/**
* 扣减库存（多线程安全版）
* 使用 ConcurrentHashMap 的原子操作
*/
public boolean deductStock(String skuId, int quantity) {
if (skuId == null || quantity <= 0) {
throw new IllegalArgumentException("参数非法：skuId=" + skuId + ", quantity=" + quantity);
}

// compute 方法是原子操作，避免并发扣减出现超卖
final int[] result = {–1}; // 用数组绕过 lambda 的 effectively final 限制

stockMap.compute(skuId, (key, currentStock) -> {
if (currentStock == null) {
result[0] = –1; // 商品不存在
return null;
}
if (currentStock < quantity) {
result[0] = 0; // 库存不足
return currentStock; // 不变
}
result[0] = 1; // 扣减成功
return currentStock – quantity;
});

if (result[0] == 1) {
System.out.printf("库存扣减成功：skuId=%s, 扣减数量=%d%n", skuId, quantity);
return true;
} else if (result[0] == 0) {
System.out.printf("库存不足：skuId=%s%n", skuId);
return false;
} else {
System.out.printf("商品不存在：skuId=%s%n", skuId);
return false;
}
}

/**
* 查询库存
*/
public int getStock(String skuId) {
return stockMap.getOrDefault(skuId, 0);
}

/**
* 批量查询库存（返回一个快照，用 HashMap 存结果）
*/
public Map<String, Integer> batchGetStock(Iterable<String> skuIds) {
Map<String, Integer> result = new HashMap<>();
for (String skuId : skuIds) {
result.put(skuId, getStock(skuId));
}
return result;
}

// 计算最近的 2 的幂（参考 HashMap 内部实现）
private static 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 >= (1 << 30)) ? (1 << 30) : n + 1;
}
}

// 使用示例
public class Main {
public static void main(String[] args) {
InventoryService service = new InventoryService(1000);

// 批量初始化
Map<String, Integer> initData = new HashMap<>();
initData.put("SKU_APPLE_001", 500);
initData.put("SKU_MILK_002", 1000);
initData.put("SKU_BREAD_003", 300);
service.batchInitStock(initData);

// 查询库存
System.out.println("苹果库存: " + service.getStock("SKU_APPLE_001")); // 500

// 扣减库存
boolean success = service.deductStock("SKU_APPLE_001", 50);
System.out.println("扣减结果: " + success); // true
System.out.println("扣减后库存: " + service.getStock("SKU_APPLE_001")); // 450

// 尝试超卖
boolean oversell = service.deductStock("SKU_BREAD_003", 400);
System.out.println("超卖扣减结果: " + oversell); // false
}
}

代码里有几个设计值得说一下：

八、面试高频问题与我的理解

既然讲到这里了，顺带把 HashMap 相关的高频面试题也梳理一下，算是帮大家把学到的知识做个应用：

Q1：HashMap 的初始容量是多少？负载因子是多少？为什么默认这些值？

初始容量 16，负载因子 0.75。容量必须是 2 的幂，方便用位运算代替取模（h & (n-1) vs h % n）。负载因子 0.75 是空间和时间的平衡值：太大了冲突多，太小了浪费空间，官方文档提到这是基于泊松分布选出的一个经验值。

Q2：HashMap 的 key 可以是 null 吗？

可以，而且只能有一个 null key，会被映射到数组下标 0。Hashtable 不允许 null key。

Q3：为什么 HashMap 不是线程安全的？

JDK 1.7：并发扩容时头插法导致链表成环，get 操作无限循环，CPU 100%。 JDK 1.8：尾插法解决了死循环，但并发 put 时仍然可能丢失数据（两个线程同时判断链表尾节点为 null，后写的覆盖前写的）。

Q4：HashMap 和 LinkedHashMap、TreeMap 的区别？

• HashMap：无序，查找 O(1)，不保证迭代顺序
• LinkedHashMap：维护插入顺序或访问顺序（双向链表），可用来实现 LRU 缓存
• TreeMap：按 key 的自然顺序或 Comparator 排序，基于红黑树，查找 O(log n)

Q5：JDK 1.8 的红黑树化，什么时候触发？

两个条件同时满足：① 链表长度 ≥ 8；② 数组长度 ≥ 64。如果数组长度 < 64 但链表长度 ≥ 8，会优先选择扩容而不是树化。

九、总结与思考

回过头来看，JDK 1.8 对 HashMap 的改进，本质上是在解决一个问题：如何在保证查找性能的前提下，应对极端的哈希冲突场景？

JDK 1.7 的方案是：更好的哈希算法（四次扰动），让冲突尽量少发生。

JDK 1.8 的方案是：一方面简化哈希算法（减少计算开销），另一方面引入红黑树做兜底（就算冲突发生了，查找也能维持 O(log n) 而不是退化到 O(n)）。

同时，把头插法改成尾插法，消除了并发扩容时的死循环风险，让 HashMap 的行为在多线程场景下更可预期（虽然还是不安全，但至少不会把服务搞死）。

工程上，记住几个原则：

最后说一句：这些原理不是为了背面试题而存在的。真正搞懂了，你才能在生产环境出问题的凌晨三点，不是茫然地看着崩掉的服务，而是有条不紊地定位问题，三分钟给出解决方案。

那种感觉，真的不一样。

🌟 文末

哈喽，各位小伙伴们，你们好呀，我是喵手。运营社区：C站/掘金/腾讯云/阿里云/华为云/51CTO；欢迎大家常来逛逛

好啦～以上就是本期 《Java核心实操(进阶版)》的全部内容啦！如果你在实践过程中遇到任何疑问，欢迎在评论区留言交流，我看到都会尽量回复～咱们下期见！

小伙伴们在批阅的过程中，如果觉得文章不错，欢迎点赞、收藏、关注哦～ 三连就是对我写作道路上最好的鼓励与支持！ ❤️🔥

📌 专栏持续更新中｜建议收藏 + 订阅

专栏 👉 《Java核心实操(进阶版)》，我会按照“入门 → 进阶 → 工程化 → 项目落地”的路线持续更新，争取让每一篇都做到：

✅ 讲得清楚（原理）｜✅ 跑得起来（代码）｜✅ 用得上（场景）｜✅ 扛得住（工程化）

📣 想系统提升的小伙伴：强烈建议先订阅专栏，再按目录顺序学习，效率会高很多～

⭐️ 若喜欢我，就请关注我叭～（更新不迷路） ⭐️ 若对你有用，就请点赞支持一下叭～（给我一点点动力） ⭐️ 若有疑问，就请评论留言告诉我叭～（我会补坑 & 更新迭代）