深度剖析HashMap扩容resize()方法
☁️调用resize有两种情况
- 初始化table（第一次调用put方法）
- 在table大小超过threshold之后进行扩容
下面直接上源码！
/**
* table表
*/
transient Node<K,V>[] table;
/**
* 加载因子
*/
int threshold;
/**
* 最大容量
*/
static final int MAXIMUM_CAPACITY = 1 << 30;
/**
* 默认初始容量
*/
static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;
/**
* 默认加载因子
*/
static final float DEFAULT_LOAD_FACTOR = 0.75f;
/**
* Initializes or doubles table size. If null, allocates in
* accord with initial capacity target held in field threshold.
* Otherwise, because we are using power-of-two expansion, the
* elements from each bin must either stay at same index, or move
* with a power of two offset in the new table.
*
*初始化或增加表大小。如果为null，则根据字段阈值中保持的初始容量目
*标分配*。 *否则，因为我们使用的是2的幂，所以每个bin中的*元素必须
*保持相同的索引，或者在新表中以2的偏移量移动*
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
//旧扩容临界值
int oldThr = threshold;
int newCap, newThr = 0;
//原table中已经有值
if (oldCap > 0) {
//如果已经超过最大容量值，不再扩容，返回table。
if (oldCap >= MAXIMUM_CAPACITY) {
//将扩容临界值赋值成Integer最大值，容量是旧表长度oldTab.length
threshold = Integer.MAX_VALUE;
return oldTab;
}
//注意：这里是扩容两倍，原因：newCap = oldCap << 1 ，特殊情况，当0 < 容量 < 16,容量大小每次左移一位
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//新临界值 = 旧临界值 的 两倍
newThr = oldThr << 1; // double threshold
}
// 在构造函数中我们要知道，构造函数会做两件事：赋值threshold 和loadFactor
// 如果没有指定initialCapacity, 则不会给threshold赋值, 该值被初始化为 0
// 如果指定了initialCapacity, threshold值被初始化成大于initialCapacity的最小的2的次幂
// 这里是指, 如果构造时指定了initialCapacity, 则用threshold作为table的实际大小
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
//如果构造时没有指定initialCapacity，则使用默认值
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
//计算指定了initialCapacity情况下的新的threshold
//以下两种情况会进入：
//当初始化时指定了容量的初始值 或 旧容量的大小为 oldCap < 16
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//从以上操作我们知道, 初始化HashMap时,
//如果构造函数没有指定initialCapacity, 则table大小为16
//如果构造函数指定了initialCapacity, 则table大小为threshold, 即大于指定initialCapacity的最小的2的整数次幂
// 从下面开始, 初始化table或者扩容, 实际上都是通过新建一个table来完成的
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 下面这段就是把原来table里面的值全部搬到新的table里面
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 这里注意, table中存放的只是Node的引用, 这里将oldTab[j]=null只是清除旧表的引用
//, 但是真正的node节点还在, 只是现在由e指向它
oldTab[j] = null;
// 如果该存储桶里面只有一个bin, 就直接将它放到新表的目标位置
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 { // preserve order
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;
}
}
}
}
}
return newTab;
}
✅这段是假如链表上有数据的
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️⃣第一段
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
上面这段定义了四个Node的引用, 从变量命名上,我们初步猜测, 这里定义了两个链表, 我们把它称为
lo链表和hi链表，loHead和loTail分别指向lo链表的头结点和尾结点，hiHead和hiTail以此类推
2️⃣第二段
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);
从上面的框架上来看, 就是在按顺序遍历该存储桶位置上的链表中的节点.
实质就是：我们首先准备了两个链表lo和hi，然后我们顺序遍历该存储桶上的链表的每个节点，如果（e.hash & oldCap）== 0, 我们就将节点放入lo链表，否则，放入hi链表
3️⃣第三段
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
如果lo链表非空, 我们就把整个lo链表放到新table的
j位置上
如果hi链表非空, 我们就把整个hi链表放到新table的j+oldCap位置上
❗综上我们知道, 这段代码的意义就是将原来的链表拆分成两个链表, 并将这两个链表分别放到新的table的j位置和j+oldCap上， j位置上就是原链表在原table中的位置，拆分标准就是
(e.hash & oldCap)
⁉️关于（e.hash & oldCap）== 0和 j 与j + oldCap
理解这个首先要明确三点：
oldCap一定是2的整数次幂, 这里假设是2^m
newCap是oldCap的两倍, 则会是2^(m+1)
hash对数组大小取模(n - 1) & hash, 其实就是取hash的低m位
⚡例如：
我们假设oldCap = 16，即 2^4
✏️16 - 1 = 15, 二进制标识为0000 0000 0000 0000 0000 0000 0000 1111可见除了低4位，其余位置都是0（简洁起见，高位后面就不写了），则（16-1）& hash 自然就是取hash值得低4位，这个就是Node存在旧表中的位置，我们假设 abcd
以此类推, 当我们将oldCap扩大两倍后, 新的index的位置就变成了 （32 -1）& hash，其实就是取hash值的低5位，那么对于同一个Node，低5位的值无外乎下面两种情况：
0abcd1abcd
✏️可以得知Node的位置有可能在以下两种情况，其中，0abcd与原来的index值一致，而 1abcd = 0abcd + 10000 = 0abcd + oldCap
而新旧index是否一致就体现在hash值的第4位(我们把最低为称作第0位), 怎么拿到这一位的值呢, 只要:
hash & 0000 0000 0000 0000 0000 0000 0001 0000
上式就等于
hash & oldCap
故得出结论
如果（e.hash & oldCap）== 0 则该节点在新表的下标位置与旧表一致都为
j
如果（e.hash & oldCap）！= 0 则该节点在新表的下标位置j + oldCap
根据这个条件，我们将原来位置的链表拆分成两个链表，然后一次性将整个链表放到新的table对应的位置上
总结
- resize发生在table初始化, 或者
table中的节点数超过threshold值的时候,threshold的值一般为负载因子乘以容量大小. - 如果table的大小 >= MAXIMUM_CAPACITY ,则会返回原table ，否则每次扩容都会新建一个
table, 新建的table的大小为原大小的2倍. - 扩容时,会将原table中的节点re-hash到
新的table中, 但节点在新旧table中的位置存在一定联系: 要么下标相同, 要么相差一个oldCap(原table的大小).
本文地址：https://blog.csdn.net/qq_42164368/article/details/110917477
上一篇： 前端面试题收集整合
下一篇： c++数据结构----直接插入排序