HashMap的扩容算法
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 1.旧表的容量不为0，即旧表不为空
if (oldCap > 0) {
// 1.1 判断旧表的容量是否超过最大容量值：如果超过则将阈值设置为Integer.MAX_VALUE，并返回旧表,
// 此时oldCap * 2比Integer.MAX_VALUE大，因此无法进行重新分布，只是单纯的将阈值扩容到最大
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 1.2 将新表容量赋值为oldCap * 2,如果newCap<最大容量且oldCap>=16,则将新阈值设置为旧阈值的两倍
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 2.如果旧表的容量为0, 旧表的阈值大于0, 是因为初始容量被放入阈值，则将新表的容量设置为旧表的阈值
else if (oldThr > 0)
newCap = oldThr;
else {
// 3.旧表的容量为0, 旧表的阈值为0，这种情况是没有传初始容量的new方法创建的空表，将阈值和容量设置为默认值
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 4.如果新表的阈值为空, 则通过新的容量*负载因子获得阈值
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
// 5.将当前阈值设置为刚计算出来的新的阈值，定义新表，容量为刚计算出来的新容量，将table设置为新定义的表。
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 6.如果旧表不为空，则需遍历旧表所有节点，将节点赋值给新表
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
// 如果索引值为j的旧表头节点不为空，则e指向该头结点
if ((e = oldTab[j]) != null) {
oldTab[j] = null; // 将旧表的节点设置为空, 以便垃圾收集器回收空间
// 7.如果e.next为空, 则说明旧表的该位置只有1个节点。
// 计算该节点在新表中的索引位置, 然后将该节点放在该位置
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
// 8.如果是红黑树节点，则进行红黑树的重hash分布(跟链表的hash分布基本相同)
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
// 9.如果是普通的链表节点，则进行普通的重hash分布
else {
// 存储“原索引位置”的节点
Node<K,V> loHead = null, loTail = null;
// 存储“原索引位置+oldCap”的节点
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
// 9.1 如果e的hash值与旧表的容量进行与运算为0,则扩容后的索引位置跟旧表的索引位置一样
if ((e.hash & oldCap) == 0) {
if (loTail == null) // 如果loTail为空, 代表该节点为第一个节点
loHead = e; // 则将loHead赋值为第一个节点
else
loTail.next = e; // 否则将节点添加在loTail后面
loTail = e; // 并将loTail赋值为新增的节点
}
// 9.2 如果e的hash值与旧表的容量进行与运算为1,则扩容后的索引位置为:旧表的索引位置＋oldCap
else {
if (hiTail == null) // 如果hiTail为空, 代表该节点为第一个节点
hiHead = e; // 则将hiHead赋值为第一个节点
else
hiTail.next = e; // 否则将节点添加在hiTail后面
hiTail = e; // 并将hiTail赋值为新增的节点
}
} while ((e = next) != null);
// 10.如果loTail不为空（说明旧表的数据有分布到新表上“原索引位置”的节点），则将最后一个节点
// 的next设为空，并将新表上索引位置为“原索引位置”的节点设置为对应的头节点
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
// 11.如果hiTail不为空（说明旧表的数据有分布到新表上“原索引+oldCap位置”的节点），则将最后
// 一个节点的next设为空，并将新表上索引位置为“原索引+oldCap”的节点设置为对应的头节点
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// 12.返回新表
return newTab;
}
扩容过程中索引值的计算
中同一索引的所有节点进行重hash计算，得到的索引位置分布在：原索引位置和原索引位置 + 旧表容量？
这里使用旧表其容量为16向新表其容量为32扩容过程中，展示节点A和节点B的索引的重新计算过程：
根据table表索引计算公式index = (n - 1) & hash计算旧表中节点在新表中的索引值。
旧表中节点A和节点B所在的索引位置：
扩容后节点A和节点B所在新表中的索引位置：
参考：https://blog.csdn.net/v123411739/article/details/78996181