/**
* 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.
*
* @return the table
*/
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;//threshold 扩容阈值 : 元素长度大于 > threshold 时扩容
int newCap, newThr = 0;
if (oldCap > 0) { //已初始化
//oldCap最大为MAXIMUM_CAPACITY(2^30)
if (oldCap >= MAXIMUM_CAPACITY) {
/**
* oldCap最大为MAXIMUM_CAPACITY(2^30),
*
* 当容量为MAX_VALUE(2^31-1)时,转换成二进制 0111 1111 1111 1111 1111 1111 1111 1110
* hash xxxx xxxx xxxx xxxx xxxx xxxx xxxx xxx0
* (第一位符号位 32位都为1的话就成负数了)
* 从上面可看出最低位无论hash是任何值时,都为0,也就是下标只有2^30种可能,有2^30-1个下标没有被使用
* 所以当容量为MAX_VALUE(2^31-1)时会造成一半的空间浪费,效率等同于MAXIMUM_CAPACITY(2^30)
*/
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
/**
* 为什么需要判断oldCap >= DEFAULT_INITIAL_CAPACITY呢？
* 应该是容量较小时 capacity * loadFactor造成的误差比较大,
* 例如初始化容量为2 threshold则为1,如果每次扩容threshold都翻倍,
* 那负载因子是0.5了。
* 为什么只小于16呢？
* 我猜测是在每次扩容都计算threshold和用位运算翻倍之间做权衡
*/
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // 带的参初始化
newCap = oldThr;
else { // 不带的参初始化
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 重新算threshold
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
//扩容
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;
//旧值赋值给e
if ((e = oldTab[j]) != null) {
oldTab[j] = null;//置空旧位置
if (e.next == null)//如果next空, 将e放到新数组对应的位置
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 {//把头移过去不就行了,为什么要一个个遍历???????
//答:容量变化后,和之前hash值相与的结果可能会有变化
next = e.next;
//原索引值:[ oldCap - 1 & hash]
//新索引值:[2 * oldCap - 1 & hash]
//举个例子: hash: 37(0010 0101)
// oldCap: 64(0100 0000)
// newCap:128(1000 0000)
//原索引: 0010 0101 新索引: 0010 0101
// & 0011 1111 & 0111 1111
// = 0010 0101 = 0010 0101
//索引值未改变.
//
//索引值是否改变只与hash & 扩容后长度的最高位(oldCap) 是否为1有关
//结果为1时,需要移动位置(j -> j + oldCap),结果为0时,位置不变
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;//尾部next置空
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;//尾部next置空
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
