JDK 8 的HashMap扩容源代码分析
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; // 获取原来的数组 table
int oldCap = (oldTab == null) ? 0 : oldTab.length; // 获取数组长度 oldCap
int oldThr = threshold; // 获取阈值 oldThr
int 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 threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = 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]; // 创建新数组 newTab
table = newTab; // 将新数组 newTab 赋值给成员变量 table
if (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; // 将该元素作为低位链表的头结点
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; // 将低位链表的尾结点指向 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：计算新容量和新阈值
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，新阈值 = 旧阈值 * 2
else 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;-
规则：
-
默认扩容为原容量的 2 倍（
newCap = oldCap << 1）。 -
新阈值 = 新容量 × 负载因子（如
0.75）。 -
若旧容量已达最大值（
MAXIMUM_CAPACITY），则不再扩容。
-
步骤 2：创建新数组
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; // 更新哈希表的数组引用-
创建一个新数组
newTab，容量为newCap，并将其赋值给哈希表的table字段。
步骤 3：迁移旧数据到新数组
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;
}
}
}
}
}关键点：
-
单个节点：直接计算新位置
e.hash & (newCap - 1)。 -
红黑树节点：调用
split方法将树拆分为两个链表，再判断是否需要退化为链表。 -
链表节点：
-
通过
注：扩容为原来的一倍以后，链表索引只可能是低位链表（原索引位置）或者高位链表（原索引 + 旧容量位置）。(e.hash & oldCap)判断节点属于 低位链表（原索引位置）还是 高位链表（原索引 + 旧容量位置）。 -
低位链表：哈希值的最高位是
0，新索引与原索引相同。 -
高位链表：哈希值的最高位是
1，新索引 = 原索引 + 旧容量。 -
尾插法：保持链表的原有顺序（避免多线程下的死循环问题）。
-
3. 设计思想
-
均匀分布：通过扩容减少哈希冲突，保证查询效率为 O(1)。
-
高效迁移：
-
利用位运算
(e.hash & oldCap)快速判断新位置，避免重新计算哈希值。 -
拆分链表为高低位两部分，直接分配到新数组的对应位置。
-
-
兼容性：
-
处理单节点、链表、红黑树三种情况。
-
在链表迁移时使用尾插法，避免多线程环境下的链表死循环问题。
-
4. 举例说明
假设旧容量为 8，某个桶的链表为 A → B → C，哈希值分别为：
-
A.hash & 8 = 0→ 低位链表 -
B.hash & 8 = 8→ 高位链表 -
C.hash & 8 = 0→ 低位链表
迁移后：
-
低位链表
A → C放入新数组的索引j（原位置）。 -
高位链表
B放入新数组的索引j + 8（旧容量 + 原位置）。