今天我们来看HashMap的扩容机制,这个用文字不好讲，我尽量说清楚,我们只要讲的逻辑在resize,我们可以把这个方法分为两部分
resize方法
这个方法主要有两部逻辑,第一部分就是在扩容的时候设置新数组的大小(newCap)和新数组的阀值(newThr),第二部分就是老数组的数据到新数组的迁移,我们先看第一部分
代码语言：javascript复制final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table; //当前所有元素所在的数组，称为老的元素数组
int oldCap = (oldTab == null) ? 0 : oldTab.length; //老的元素数组长度
int oldThr = threshold; // 老的扩容阀值设置
int newCap, newThr = 0; // 新数组的容量，新数组的扩容阀值都初始化为0
if (oldCap > 0) { // 如果老数组长度大于0，说明已经存在元素
// 情况1
if (oldCap >= MAXIMUM_CAPACITY) { // 如果数组元素个数大于等于限定的最大容量（2的30次方）
// 扩容阀值设置为int最大值（2的31次方 -1 ），因为oldCap再乘2就溢出了。
threshold = Integer.MAX_VALUE;
return oldTab; // 返回老的元素数组
}
/*
* 如果数组元素个数在正常范围内，那么新的数组容量为老的数组容量的2倍（左移1位相当于乘以2）
* 如果扩容之后的新容量小于最大容量 并且 老的数组容量大于等于默认初始化容量（16），那么新数组的扩容阀值设置为老阀值的2倍。（老的数组容量大于16意味着：要么构造函数指定了一个大于16的初始化容量值，要么已经经历过了至少一次扩容）
*/
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 情况2
// 运行到这个else if 说明老数组没有任何元素
// 如果老数组的扩容阀值大于0，那么设置新数组的容量为该阀值
// 这一步也就意味着构造该map的时候，指定了初始化容量。
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
// 能运行到这里的话，说明是调用无参构造函数创建的该map，并且第一次添加元素
newCap = DEFAULT_INITIAL_CAPACITY; // 设置新数组容量 为 16
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); // 设置新数组扩容阀值为 16*0.75 = 12。0.75为负载因子（当元素个数达到容量了4分之3，那么扩容）
}
// 如果扩容阀值为0 （情况2）
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr; // 设置map的扩容阀值为 新的阀值
第二部分先省略....
return newTab; // 返回新数组
}
上面代码又分为两种情况
第一种情况，就是上图的标记情况1，老数组长度大于0，说明已经存在值了,如果老数组的容量大于最大容量，就直接返回老的数组,如果正常范围内,直接扩容新数组为原来的2倍,且阀值为老数组的2倍
第二种情况，就是上图的标记情况2，走到情况2，说明老数组没有任何元素,注意这里如果新数组指定了初始化容量，则设置新数组的容量为老数组的阀值，且新数组的阀值为下面逻辑，否则设置默认值
接下来我们看看老数组数据迁移的过程
代码语言：javascript复制 final Node<K,V>[] resize() {
//省略部分代码......
// 创建新的数组（对于第一次添加元素，那么这个数组就是第一个数组；对于存在oldTab的时候，那么这个数组就是要需要扩容到的新数组）
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab; // 将该map的table属性指向到该新数组
if (oldTab != null) { // 如果老数组不为空，说明是扩容操作，那么涉及到元素的转移操作
for (int j = 0; j < oldCap; j) { // 遍历老数组
Node<K,V> e;
if ((e = oldTab[j]) != null) { // 如果当前位置元素不为空，那么需要转移该元素到新数组
oldTab[j] = null; // 释放掉老数组对于要转移走的元素的引用（主要为了使得数组可被回收）
if (e.next == null) // 如果元素没有有下一个节点，说明该元素不存在hash冲突
// PS3
// 把元素存储到新的数组中，存储到数组的哪个位置需要根据hash值和数组长度来进行取模
// 【hash值 % 数组长度】 = 【 hash值 & （数组长度-1）】
// 这种与运算求模的方式要求 数组长度必须是2的N次方，但是可以通过构造函数随意指定初始化容量呀，如果指定了17,15这种，岂不是出问题了就？没关系，最终会通过tableSizeFor方法将用户指定的转化为大于其并且最相近的2的N次方。15 -> 16、17-> 32
newTab[e.hash & (newCap - 1)] = e;
// 如果该元素有下一个节点，那么说明该位置上存在一个链表了（hash相同的多个元素以链表的方式存储到了老数组的这个位置上了）
// 例如：数组长度为16，那么hash值为1（1=1）的和hash值为17（17=1）的两个元素都是会存储在数组的第2个位置上（对应数组下标为1），当数组扩容为32（12=1）时，hash值为1的还应该存储在新数组的第二个位置上，但是hash值为17（172=17）的就应该存储在新数组的第18个位置上了。
// 所以，数组扩容后，所有元素都需要重新计算在新数组中的位置。
else if (e instanceof TreeNode) // 如果该节点为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; // 按命名来翻译的话，应该叫高位首尾节点
// 以上的低位指的是新数组的 0 到 oldCap-1 、高位指定的是oldCap 到 newCap - 1
Node<K,V> next;
// 遍历链表
do {
next = e.next;
// 这部分简单来说就是把新数组分为了高位和低位，
//比如新数组长度32,[0,15]是低位,[16,31]是高位
//最终目的就是把老数组上的链表，尽可能分散到新数组上不同位置
if ((e.hash & oldCap) == 0) {
// PS4
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; // 例：hash为 17 在老数组放置在0下标，在新数组放置在16下标； hash为 18 在老数组放置在1下标，在新数组放置在17下标；
}
}
}
}
}
return newTab; // 返回新数组
}
这部分代码要比较难懂的就是如何把老数组的数据均匀分布到新数组上的不同位置首先看下面代码是重点
代码语言：javascript复制(e.hash & oldCap) == 0假设老数组长度为16，新数组长度32，15和31都在老数组下表为15的位置
看到上图使用e.hash&oldCap与运算，如果得到的是0,则放到和老数组同样的位置即15在新数组的下标是15，如果不是，就会放到老数组下表 老数组长度即31在新数组的下标是31,下节看看面试对于HashMap还有那些问题
