/**
* 这个方法是基于当前桶中所有元素的数量进行计算的使用阈值为threshold.它不同于链表转化到tree时的链表长度(可以理解为树的高度)阈值TREEIFY_THRESHOLD
*/
final Node<K,V>[] resize() {
//----------------------------------- 新容量与阈值计算 -----------------------------------
// 缓存桶引用
Node<K,V>[] oldTab = table;
// 缓存老的桶的长度,桶为null时,使用0
// 注意,这里用的是oldTab.length,而不是size
int oldCap = (oldTab == null) ? 0 : oldTab.length;
// 缓存阈值
int oldThr = threshold;
// 新桶容量与阈值
int newCap, newThr = 0;
// 老容量大于.这一般代表这个桶已经经过了resize的数次处理
if (oldCap > 0) {
// 老容量大于MAXIMUM_CAPACITY = 1 << 30 = 1073741824
// 容量计算方式为n<<1,当oldCap >= MAXIMUM_CAPACITY时,再次执行位移.其可能的最大值就是Integer.MAX_VALUE
if (oldCap >= MAXIMUM_CAPACITY) {
// 设置阈值为Integer.MAX_VALUE
threshold = Integer.MAX_VALUE;
// 直接return.放弃全部后续处理
return oldTab;
}
// 使用oldCap << 1初始化newCap
// 当oldCap小于MAXIMUM_CAPACITY并且oldCap大于DEFAULT_INITIAL_CAPACITY(16)时
// 此时newCap可能已经大于MAXIMUM_CAPACITY并且newThr=0或者newCap很小(小于16>>2)并且newThr=0
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
//设置newThr为oldThr << 1(这里没有做正确性校验,待查)
newThr = oldThr << 1; // double threshold
}
// 判断老阈值是否大于0
// 走到这说明oldCap==0,并且使用了包含initialCapacity参数的构造器构造了这个map,且没有被添加过元素
else if (oldThr > 0) // initial capacity was placed in threshold
// 使用将新容量复制为老阈值(newCap此时为0)
// 注意: 在使用了包含initialCapacity参数的构造方法时,其threshold已经被计算为2的n次幂
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 默认方法,当使用无参构造方法时,会出现oldThr与oldCap都等于0的情况
// 使用默认初始化容量赋值到newCap
newCap = DEFAULT_INITIAL_CAPACITY;
// 使用默认初始化容量与加载因子相乘赋值到newThr
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 统一处理newThr
if (newThr == 0) {
// 新容量与加载因子相乘
float ft = (float)newCap * loadFactor;
// 当newCap与ft均小于MAXIMUM_CAPACITY时,newThr=ft.否则newThr=Integer.MAX_VALUE
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//----------------------------------- 元素重排 -----------------------------------
// 更新threshold
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
// 更新桶对象(此时是空的)
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 判断老桶是否为空
if (oldTab != null) {
// 老桶不为空.进行遍历
for (int j = 0; j < oldCap; ++j) {
// 桶元素
Node<K,V> e;
// 进行桶元素获取
// 判断桶元素是否存在(因为使用(n-1)&hash的方式进行计算,所以经常会出现这种情况)
if ((e = oldTab[j]) != null) {
// 删除引用
oldTab[j] = null;
// 判断桶元素是否有下一个元素
if (e.next == null)
// 没有下一个元需.使用相同的算法计算在新桶中的下标并赋值
newTab[e.hash & (newCap - 1)] = e;
// 桶元素存在next,判断是否为TreeNode
else if (e instanceof TreeNode)
// 进行委派执行
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
// 对于链表结构,拆分到高位与低位两组
// loHead与loTail非别代表低位头与低位尾
Node<K,V> loHead = null, loTail = null;
// hiHead与hiTail非别代表高位头与高位尾
Node<K,V> hiHead = null, hiTail = null;
// next
Node<K,V> next;
// 已经存在遍历目标,直接使用do while
do {
// 拿到e的next.
next = e.next;
// 判断e的hash是否是高位
// 判断原理如下.
// 首先oldCap恒定为2的n次幂,二进制表达为1000...
// 下标计算方程为(n-1)&hash
// 带入n后,为...111&hash
// 当n=111时,hash为1101,结果为101
// 当n=1111时,hash为1101,结果为1101.表示为高位(注意hash的高位)
// 当n=1111时,hash为0101,结果为101.表示为低位(注意hash的高位)
// 这样就,可以直接求出新的下标.但是,这种方式需要对所有的元素进行重新计算,非常低效
// 所以jdk使用了一个特别的方法.就是直接比较最高位,当一个hash与数组长度(也就是n的n次幂)时,如1101&1000
// 当结果等于0时,代表这个hash是低位hash,其他就是高位hash
if ((e.hash & oldCap) == 0) {
// 低位
// 判断低位尾部是否存在
if (loTail == null)
// 不存在,代表头部也没有,进行初始化
loHead = e;
else
// 存在,追加到尾部的next
loTail.next = e;
// 更新尾部
loTail = e;
}
else {
// 高位
if (hiTail == null)
// 不存在,代表头部也没有,进行初始化
hiHead = e;
else
// 存在,追加到尾部的next
hiTail.next = e;
// 更新尾部
hiTail = e;
}
} while ((e = next) != null);
// 进行收尾处理
// 判断低位是否为空
if (loTail != null) {
// 不为空
// 清除末尾元素的next.当loTail是链表倒数第二个元素且倒数第一个元素是高位元素时,需要清空loTail的next对高位元素的引用
loTail.next = null;
// 低位使用原下标进行保存
newTab[j] = loHead;
}
if (hiTail != null) {
// 不为空
// 清除末尾元素的next.理由同上但判断方式相反
hiTail.next = null;
// 低位使用原下标+原容量进行保存
newTab[j + oldCap] = hiHead;
}
}
}
}
}
// 返回newTab
return newTab;
}