解剖HashMap的put ＜五＞ JDK1.8

在 HashMap 的put流程中，第五步是 “判断是否需要扩容（resize）”—— 这是维持 HashMap 性能的关键一步。当元素数量过多时，哈希冲突会加剧，查询 / 插入效率会下降，而扩容通过增加数组容量、重新分布元素来缓解冲突，保证 HashMap 的高效性。

---

这一步是最后一步，以下完整代码

final V putVal(int hash, K key, V value, boolean onlyIfAbsent, boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;// 1. 初始化或扩容检查if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;// 2. 计算桶索引if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null); // 直接插入else {Node<K,V> e; K k;// 3. 检查第一个节点if (p.hash == hash && ((k = p.key) == key || (key != null && key.equals(k))))e = p; // 记录节点// 4. 检查是否是树节点else if (p instanceof TreeNode)e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);else {// 5. 链表遍历（尾插法）for (int binCount = 0; ; ++binCount) {if ((e = p.next) == null) {p.next = newNode(hash, key, value, null); // 尾插// 6. 树化检查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;}}// 7. 值覆盖if (e != null) {V oldValue = e.value;if (!onlyIfAbsent || oldValue == null)e.value = value;return oldValue;}}// 8. 扩容检查++modCount;if (++size > threshold)resize();return null;
}

一、第五步的触发时机  链接：什么是负载因子

第五步发生在第四步 “插入 / 更新元素” 之后，具体触发条件是：
插入新元素后，当前元素总数量size > 阈值（threshold）。

• size：HashMap 中实际存储的键值对数量（每次插入新元素后size++）。
• threshold：扩容阈值，计算公式为 threshold = 数组容量（n） × 负载因子（loadFactor）。
  • 数组容量n：初始为 16，每次扩容后翻倍（始终是 2 的幂）。
  • 负载因子loadFactor：默认 0.75（可在构造函数中自定义），是 “容量利用率” 的临界值。

二、为什么需要扩容？

负载因子的默认值 0.75 是时间与空间的平衡选择：

• 若负载因子太小（如 0.5）：阈值低，扩容频繁，数组利用率低（浪费空间），但冲突少（效率高）。
• 若负载因子太大（如 1.0）：阈值高，扩容少，空间利用率高，但冲突多（链表 / 红黑树变长，效率低）。

当size超过阈值时，说明数组已接近 “饱和”，冲突概率大幅上升，此时必须通过扩容 “减负”，重新分布元素。

三、扩容（resize()）的核心步骤（JDK 1.8）

扩容是 HashMap 中最复杂的操作之一，核心是 “创建新数组 + 迁移旧元素”，具体步骤如下：

步骤 1：计算新容量和新阈值

• 新容量：如果旧容量oldCap不为 0，则新容量newCap = oldCap × 2（翻倍，仍保持 2 的幂）；如果是首次初始化（旧容量为 0），则新容量为初始容量 16。
• 新阈值：
  • 若旧阈值oldThr不为 0，则新阈值newThr = oldThr × 2（翻倍）；
  • 若首次初始化，则新阈值newThr = 16 × 0.75 = 12。

步骤 2：创建新数组

根据新容量newCap，创建一个长度为newCap的新数组（newTab）。

步骤 3：迁移旧元素到新数组

将旧数组（oldTab）中的所有元素重新计算索引，放入新数组（newTab）中。这是扩容的核心，也是最耗时的步骤。

迁移逻辑根据旧桶的结构（空、链表、红黑树）不同而不同：

子情况 1：旧桶为空（oldTab[i] == null）

无需处理，直接跳过。

子情况 2：旧桶是单个节点（无冲突）

旧桶中只有一个节点，直接计算其在新数组中的索引，放入新桶：

// 伪代码：单个节点迁移
Node<K,V> e = oldTab[i];
// 计算新索引（利用JDK 1.8优化：无需重新计算哈希值）
int newIndex = e.hash & (newCap - 1);
newTab[newIndex] = e;

子情况 3：旧桶是链表（多个节点）

链表中的节点需要重新分布到新数组中。JDK 1.8 有一个精妙优化：
由于新容量是旧容量的 2 倍（newCap = oldCap × 2），节点的新索引只有两种可能：

• 与旧索引相同（oldIndex）；
• 旧索引 + 旧容量（oldIndex + oldCap）。

原因：新容量newCap = oldCap × 2，因此newCap - 1 = (oldCap - 1) | oldCap（二进制多了一个高位 1）。节点哈希值的该高位如果是 0，新索引 = 旧索引；如果是 1，新索引 = 旧索引 + 旧容量。

基于此，迁移时可将链表拆分为两个子链表，分别放入两个新索引位置，无需逐个计算索引：

// 伪代码：链表拆分迁移
Node<K,V> loHead = null, loTail = null; // 新索引=旧索引的子链表
Node<K,V> hiHead = null, hiTail = null; // 新索引=旧索引+oldCap的子链表
Node<K,V> e;
do {e = p.next;// 判断哈希值的高位（旧容量对应的bit）是否为0if ((p.hash & oldCap) == 0) { // 高位为0 → 新索引=旧索引if (loTail == null) loHead = p;else loTail.next = p;loTail = p;} else {// 高位为1 → 新索引=旧索引+oldCapif (hiTail == null) hiHead = p;else hiTail.next = p;hiTail = p;}
} while ((p = e) != null);// 将两个子链表放入新数组
if (loTail != null) {loTail.next = null;newTab[oldIndex] = loHead;
}
if (hiTail != null) {hiTail.next = null;newTab[oldIndex + oldCap] = hiHead;
}

子情况 4：旧桶是红黑树

红黑树的迁移逻辑与链表类似，但更复杂：

• 先将红黑树拆分为两个子树（对应新索引的两种可能）；
• 若子树的节点数≤6，则退化为链表（避免树结构的维护成本）；
• 否则，将子树转为新的红黑树，放入新数组的对应索引。

步骤 4：更新 HashMap 的内部状态

• 将新数组newTab赋值给 HashMap 的table属性（替代旧数组）；
• 更新容量n为新容量newCap；
• 更新阈值threshold为新阈值newThr。

四、举例说明扩容过程

假设初始状态：

• 容量n=16，阈值threshold=12（16×0.75），size=12。

插入第 13 个元素后：

• size=13 > 12 → 触发扩容。
• 新容量newCap=32，新阈值newThr=24（32×0.75）。
• 创建长度 32 的新数组，迁移旧 16 个桶中的元素：
  • 旧桶中链表的节点，根据哈希值的第 4 位（因为 16 是 2⁴，对应 bit 位）是否为 0，分别放入旧索引或旧索引 + 16 的新位置。

五、第五步的核心目标

1. 缓解哈希冲突：通过增加数组容量，让元素重新分布到更多的桶中，减少单个桶中的元素数量（缩短链表 / 红黑树）。
2. 维持高效性能：保证后续的查询、插入操作仍能保持接近 O (1) 的时间复杂度。
3. 平衡空间与时间：通过负载因子控制扩容时机，避免过度占用空间或效率下降。

归纳

第五步（扩容）是 HashMap 的 “自我优化” 机制：当元素数量超过阈值时，通过翻倍容量、重新分布元素来减少冲突，确保 HashMap 在数据量增长时仍能保持高效的存取性能。这一步虽然耗时（涉及元素迁移），但为后续操作的高效性奠定了基础。