扩容机制

一、扩容触发条件

1. 初始化扩容：第一次调用put()方法时，调用resize()初始化数组，默认容量为16，扩容阈值为16 × 0.75 = 12
2. 元素数量触发：当元素数量size > threshold（数组容量×加载因子0.75）时，触发扩容
3. 树化触发：当链表长度≥8且数组长度≥64时，触发树化，若数组长度<64则优先扩容

---

二、扩容核心流程

1. 计算新容量：
   • 若oldCap > 0，则newCap = oldCap × 2（容量翻倍，保持2的幂）
   • 若oldCap = 0（首次初始化），则设置默认容量16，扩容阈值12
2. 创建新数组：初始化容量为newCap的空数组newTab
3. 数据迁移：遍历旧数组，将元素迁移到新数组中
4. 更新引用：将table指向新数组，更新threshold为新的扩容阈值

---

三、数据迁移逻辑

1. 普通节点（无冲突）

• 直接通过e.hash & (newCap - 1)计算新数组下标，放入对应位置

2. 链表节点

• 遍历链表，通过(e.hash & oldCap)判断元素在新数组中的位置：
  • 若结果为0：元素留在原下标位置（newTab[j]）
  • 若结果非0：元素迁移到newTab[j + oldCap]位置
• 拆分后的链表分别挂载到新数组的对应位置，无需重新计算哈希值

3. 红黑树节点

• 并非直接传递树的地址，而是需要对红黑树进行拆分：
  1. 遍历红黑树节点，根据(e.hash & oldCap)将节点分为两部分
  2. 分别挂载到新数组的j和j + oldCap位置
  3. 若拆分后树的节点数≤6，则红黑树退化为链表；若仍≥8，则保留红黑树结构
• 红黑树的拆分逻辑与链表类似，只是在拆分后额外判断是否退化，保证性能最优

---

四、面试高频问题解析

1. 问：HashMap的扩容机制是什么？答： 当元素数量超过数组容量×0.75时触发扩容，容量翻倍并创建新数组。遍历旧数组，普通节点直接按新容量计算下标迁移；链表节点根据hash & oldCap分为原位置和原位置+oldCap两部分；红黑树节点也按此规则拆分，节点数≤6时退化为链表。

2. 问：扩容时为什么要把链表拆成两部分？答： 因为扩容后数组容量翻倍，(e.hash & (newCap - 1))的结果只会是j或j + oldCap两种情况，无需重新计算哈希值，提升迁移效率。同时拆分链表避免了节点移动的性能开销。

3. 问：红黑树在扩容时是怎么处理的？直接传地址还是拆分？答： 不是直接传递树的地址，而是需要遍历红黑树节点，按(e.hash & oldCap)将节点分为两部分，分别挂载到新数组的对应位置。拆分后若节点数≤6，红黑树会退化为链表，减少维护开销。

4. 问：为什么HashMap的扩容是容量翻倍？答： 为了保证数组容量始终是2的幂，使(n - 1) & hash能均匀分布元素下标，减少哈希冲突。同时翻倍扩容可以使hash & oldCap的结果只有0或非0两种情况，简化数据迁移逻辑。