java">final Node<K,V>[] resize() {Node<K,V>[] oldTab = table; // 获取原来的数组 tableint oldCap = (oldTab == null) ? 0 : oldTab.length; // 获取数组长度 oldCapint oldThr = threshold; // 获取阈值 oldThrint newCap, newThr = 0;if (oldCap > 0) { // 如果原来的数组 table 不为空if (oldCap >= MAXIMUM_CAPACITY) { // 超过最大值就不再扩充了，就只好随你碰撞去吧threshold = Integer.MAX_VALUE;return oldTab;}else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && // 没超过最大值，就扩充为原来的2倍oldCap >= DEFAULT_INITIAL_CAPACITY)newThr = oldThr << 1; // double threshold}else if (oldThr > 0) // initial capacity was placed in thresholdnewCap = oldThr;else { // zero initial threshold signifies using defaultsnewCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);}// 计算新的 resize 上限if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?(int)ft : Integer.MAX_VALUE);}threshold = newThr; // 将新阈值赋值给成员变量 threshold@SuppressWarnings({"rawtypes","unchecked"})Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; // 创建新数组 newTabtable = newTab; // 将新数组 newTab 赋值给成员变量 tableif (oldTab != null) { // 如果旧数组 oldTab 不为空for (int j = 0; j < oldCap; ++j) { // 遍历旧数组的每个元素Node<K,V> e;if ((e = oldTab[j]) != null) { // 如果该元素不为空oldTab[j] = null; // 将旧数组中该位置的元素置为 null，以便垃圾回收if (e.next == null) // 如果该元素没有冲突newTab[e.hash & (newCap - 1)] = e; // 直接将该元素放入新数组else if (e instanceof TreeNode) // 如果该元素是树节点((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 将该树节点分裂成两个链表else { // 如果该元素是链表Node<K,V> loHead = null, loTail = null; // 低位链表的头结点和尾结点Node<K,V> hiHead = null, hiTail = null; // 高位链表的头结点和尾结点Node<K,V> next;do { // 遍历该链表next = e.next;if ((e.hash & oldCap) == 0) { // 如果该元素在低位链表中if (loTail == null) // 如果低位链表还没有结点loHead = e; // 将该元素作为低位链表的头结点elseloTail.next = e; // 如果低位链表已经有结点，将该元素加入低位链表的尾部loTail = e; // 更新低位链表的尾结点}else { // 如果该元素在高位链表中if (hiTail == null) // 如果高位链表还没有结点hiHead = e; // 将该元素作为高位链表的头结点elsehiTail.next = e; // 如果高位链表已经有结点，将该元素加入高位链表的尾部hiTail = e; // 更新高位链表的尾结点}} while ((e = next) != null); //if (loTail != null) { // 如果低位链表不为空loTail.next = null; // 将低位链表的尾结点指向 null，以便垃圾回收newTab[j] = loHead; // 将低位链表作为新数组对应位置的元素}if (hiTail != null) { // 如果高位链表不为空hiTail.next = null; // 将高位链表的尾结点指向 null，以便垃圾回收newTab[j + oldCap] = hiHead; // 将高位链表作为新数组对应位置的元素}}}}}return newTab; // 返回新数组
}

这段代码是 Java 中 HashMap 的 扩容（resize） 方法，用于在哈希表容量不足时扩大数组长度，并重新分布所有元素。以下是逐步分析：

---

1. 核心目标

• 扩容：当哈希表中的元素数量超过阈值（threshold = capacity * loadFactor）时，扩容数组以减少哈希冲突，保证查询效率。

• 重分布：将旧数组中的元素重新分配到新数组中，确保哈希表的均匀分布。

---

2. 代码分步解析

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

java">Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;if (oldCap > 0) {// 旧容量已达最大值，无法扩容if (oldCap >= MAXIMUM_CAPACITY) {threshold = Integer.MAX_VALUE;return oldTab;}// 新容量 = 旧容量 * 2，新阈值 = 旧阈值 * 2else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {newThr = oldThr << 1;}
} else if (oldThr > 0) { // 初始化时手动指定了容量（通过阈值）newCap = oldThr;
} else { // 默认初始化newCap = DEFAULT_INITIAL_CAPACITY;newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}// 计算新阈值（如果未在之前的逻辑中设置）
if (newThr == 0) {float ft = (float)newCap * loadFactor;newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE);
}
threshold = newThr;

• 规则：

  1. 默认扩容为原容量的 2 倍（newCap = oldCap << 1）。

  2. 新阈值 = 新容量 × 负载因子（如 0.75）。

  3. 若旧容量已达最大值（MAXIMUM_CAPACITY），则不再扩容。

---

步骤 2：创建新数组

java">Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; // 更新哈希表的数组引用

• 创建一个新数组 newTab，容量为 newCap，并将其赋值给哈希表的 table 字段。

---

步骤 3：迁移旧数据到新数组

java">
if (oldTab != null) {for (int j = 0; j < oldCap; ++j) { // 遍历旧数组的每个位置（桶）Node<K,V> e;if ((e = oldTab[j]) != null) { // 如果当前位置有元素oldTab[j] = null; // 清空旧位置，帮助垃圾回收// 情况 1：单个节点（无冲突）if (e.next == null) {newTab[e.hash & (newCap - 1)] = e; // 直接计算新位置}// 情况 2：红黑树节点else if (e instanceof TreeNode) {((TreeNode<K,V>)e).split(this, newTab, j, oldCap); // 分裂树}// 情况 3：链表节点else { // 定义低位链表和高位链表的头尾指针Node<K,V> loHead = null, loTail = null;Node<K,V> hiHead = null, hiTail = null;Node<K,V> next;do { // 遍历链表next = e.next;// 判断节点属于低位链表还是高位链表if ((e.hash & oldCap) == 0) {// 将节点添加到低位链表尾部if (loTail == null) loHead = e;else loTail.next = e;loTail = e;} else {// 将节点添加到高位链表尾部if (hiTail == null) hiHead = e;else hiTail.next = e;hiTail = e;}} while ((e = next) != null);// 将低位链表放入新数组的原索引位置if (loTail != null) {loTail.next = null;newTab[j] = loHead;}// 将高位链表放入新数组的 [原索引 + 旧容量] 位置if (hiTail != null) {hiTail.next = null;newTab[j + oldCap] = hiHead;}}}}
}

关键点：

1. 单个节点：直接计算新位置 e.hash & (newCap - 1)。

2. 红黑树节点：调用 split 方法将树拆分为两个链表，再判断是否需要退化为链表。

3. 链表节点：

   • 通过 (e.hash & oldCap) 判断节点属于 低位链表（原索引位置）还是 高位链表（原索引 + 旧容量位置）。

     注：扩容为原来的一倍以后，链表索引只可能是低位链表（原索引位置）或者高位链表（原索引 + 旧容量位置）。

   • 低位链表：哈希值的最高位是 0，新索引与原索引相同。

   • 高位链表：哈希值的最高位是 1，新索引 = 原索引 + 旧容量。

   • 尾插法：保持链表的原有顺序（避免多线程下的死循环问题）。

---

3. 设计思想

1. 均匀分布：通过扩容减少哈希冲突，保证查询效率为 O(1)。

2. 高效迁移：

   • 利用位运算 (e.hash & oldCap) 快速判断新位置，避免重新计算哈希值。

   • 拆分链表为高低位两部分，直接分配到新数组的对应位置。

3. 兼容性：

   • 处理单节点、链表、红黑树三种情况。

   • 在链表迁移时使用尾插法，避免多线程环境下的链表死循环问题。

---

4. 举例说明

假设旧容量为 8，某个桶的链表为 A → B → C，哈希值分别为：

• A.hash & 8 = 0 → 低位链表

• B.hash & 8 = 8 → 高位链表

• C.hash & 8 = 0 → 低位链表

迁移后：

• 低位链表 A → C 放入新数组的索引 j（原位置）。

• 高位链表 B 放入新数组的索引 j + 8（旧容量 + 原位置）。