文章概述：
大家好，之前我们讲解了map的哈希冲突，相信各位已经迫不及待来学习咱们的map中篇了，我们中篇讲解的就是map的扩容知识，接下来我们就正式进入到学习中来，相信大家读完这篇文章后，一定能收获相关的知识。
一、扩容的概述
啥是扩容，现象是什么
当 map中的元素超过了阈值，也就map中的规定的容量 ，此时就需要进行扩容，你想呀，如果map的数组都装满了，那么来了元素之后，不就只能都冲突了吗，所以我们在map满足了一定容量后，就得扩容啦~~那么怎么扩容呢~，并且扩容的条件是什么呢？
二、map1.7何时扩容
我们先来看看1.7的构造方法
public HashMap() {
this.loadFactor = DEFAULT_LOAD_FACTOR;
threshold = (int)(DEFAULT_INITIAL_CAPACITY * DEFAULT_LOAD_FACTOR);
table = new Entry[DEFAULT_INITIAL_CAPACITY];
init();
}
解释说明
DEFAULTINITIALCAPACITY= 16 默认的数组长度
DEFAULTLOADFACTOR = 0.75f 默认的负载因子
threshold：阈值的临界值
我们再来找找它扩容条件
if (size++ >= threshold)
resize(2 * table.length);
也就是说，在默认情况下：当map中的容量个数大于等于阈值时，也就是我们之前计算出来的 数组长度0.75就会扩容，比如初始情况下，扩容的条件就是16 * 0.75=12
注意：当我们向map中存放了一个元素，比如map.put(key,value)，只要这个元素存入到了map中，我们就认为容量加1
三、 map1.7如何扩容
其实map1.7的做法非常的简单，它会遍历当前这个数组，拿到数组中的每一个entry，然后再遍历entry上的每一个节点，然后把每一个节点重新计算其在新数组上的位置。
我们为了能更好的理解扩容，先来定两个假设，假设map的计算索引的方法是 用key % table.size() ，再假设map的数组长度是2,于是当我插入key 分别是 3,7,5 这三个数据时，它们计算出来的索引都是1号索引
具体计算方式:3 % 2= 1 ; 7 % 2= 1 ; 5% 2 = 1;如下图：
源码如下：并标明基本的含义
// 参数说明：扩容后的map对象，长度为原来两倍
void transfer(Entry[] newTable) {
// 原始map对象，未扩容前的
Entry[] src = table;
// 拿到新扩容后的长度
int newCapacity = newTable.length;
// 遍历数组
for (int j = 0; j < src.length; j++) {
//拿到每一个entry
Entrye = src[j]; //标记0
if (e != null) { //标记1
//断开和原来map之间的关系
src[j] = null; //标记2
do {
// 具体分析见后文
Entrynext = e.next; //标记3
int i = indexFor(e.hash, newCapacity); //标记4
e.next = newTable[i];//标记5
newTable[i] = e; //标记6
e = next; //标记7
} while (e != null); //标记8
}
}
}
以下内容建议大家拿着源码对照着看哦
key为3 的节点转移情况说明：
在标记0 处，Entry e = src[1] = 0x01 ，此时满足标记1的情况，同时在标记2 处，src[1]=null ，key=3的entry节点与原map断开关系，此时再标记3 处Entrynext = e.next 取出来具体的值 就变成了Entry next = 0x02，
而重新去计算索引值的标记4 ，按照咱们的约定，我们算出来是3 % 4= 3; 接着再标记5处，newTable[3] 的值也就是一个null （注意：new出来的对象数组值都为null）将null赋值给e.next ，此时key=3 的entry 和key=7 的entry 断开连接，同时将0x01 赋值给了newTable[3] ，最后用next的值也就是0x02 赋值给e，综上，第一次遍历完成后，整体效果会变成下图
key=7时的处理情况说明
在标记8 处，e!=null，所以do，while循环继续 , 在标记3处：Entrynext = 0x04，在标记处4 ，算出来key=7时的索引应为 7 % 4= 3 ;在标记5处 e.next = newTable[i]; 相当于 e.next= 0x01，此时key=7的next 值会变为0x01，会指向key=3的节点，同时断开和key=5的关系， 在标记6处，newTable[i] = e; 会将0x02的的值赋值给newTable[3]，此时map指向key=7的节点，再把next=0x04的值赋值给e 综上
key=5时的处理情况说明
在标记8 处，e!=null，所以do，while循环继续 ，在标记3处：Entrynext = null，在标记处4 ，算出来key=5时的索引应为 5 % 4= 1 ;在标记5处，e.next = newTable[1]; e.next = null,在标记6处，newTable[i] = e;
则newTable[1] = 0x04，所以数组指向key=5，标记7处， 将e =null，此时不再满足 do while 循环条件退出，综上
最后，总结一下map1.7的扩容：就是遍历当前这个数组，拿到数组中的每一个entry，然后再遍历entry上的每一个节点，然后把每一个节点重新计算其在新数组上的位置，这句话其实在咱们如何扩容标题就已经告诉大家了哟~大家也只需要这么去回答面试官就好啦~
四、map1.8如何扩容
注意：oldCap是原来数组的长度
源码如下，并附上简单说明
for (int j = 0; j < oldCap; ++j) {
Nodee;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null)
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode)e).split(this, newTab, j, oldCap);
else { // preserve order
NodeloHead = null, loTail = null;
NodehiHead = null, hiTail = null;
Nodenext;
do {
next = e.next;
// 通过源码我们发现 它会去判断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);
// 根据是否0 ，来判断是否移动
if (loTail != null) {
// 如果是0 ，不移动
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null)
//如果是0 ，移动，并且移动为原来的oldCap这么大
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
分析流程
变量说明：oldCap ：就是原来的数组长度
1.8 的扩容做法，是遍历数组上的链表数据， 并不是每个人都重新算一遍 只是去拿着这个当前遍历到这个值去 & oldCap 算出来是 0 或者是 算出来不是0 -> 去挪动元素 如果是 0 ， 不挪动，就放在原来位置 如果非 0 ， 就挪动， 挪动的位数是原来位置 + oldCap
情况一、当与oldCap计算出来结果是0时
同学，此刻你有没有发现，最终的这个索引值到底有没有变化，其实原数组长度最高位对上去的那一位是否是个0 呢？如果你还不明白，那么我们接着往后看
小总结
是的，是看的没扩容之前的oldCap的最高位，如果我计算出来这个值是0 ，那么扩容没扩容实际上没有区别，如果你算出来的值不是0 ，那么就需要移动，需要移动多少呢，对，就是oldCap最高位的二进制
情况二、当与oldCap计算出来结果不是0时
为了让同学们更好的理解，我们再来模拟一个不是0 的情况 ,同学们注意看哦，我把hashCode 的从后向前数的5位从0 ，改成了1
小总结
你会发现，如果oldCap对上去的那一位是1的话，那么此时新容量的计算是要移动的，并且移动的位数就是用原来的长度+ 用新算法算出来的那个值 也就是10 + 16 = 26 确定它的位置
五、 总结
好了，哥们门，如果以后面试官问你，map的扩容是怎么一回事，怎么答，你应该知道了吧，希望大家通过学习能有所收获
京公网安备 11010802041100号