扩容原理
HashMap的扩容方法resize()高达70行代码，可谓是相当多了，很多初次接触的同学面对这么多代码可能会直接劝退，但如果静下心来梳理的话，其实也就两部分：
- 确定扩容后的新容量和下次扩容的阈值，并根据新容量创建一个新数组。
- 将原数组中的数据放在新数组中
现在我们根据梳理出来的两部分，看一下完整的源码：
final Node<K,V>[] resize() {
// 确定扩容后的新容量和下次扩容的阈值
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else {
// zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
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;
}
下面我们以梳理出来的两部分内容，来看一下其中的细节
1、确认新的容量和阈值
我们把这一部分源码再次贴出来具体分析一下其中的细节
// 确定扩容后的新容量和下次扩容的阈值
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else {
// zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
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];
首先，获取原数组的容量
oldCap，即原数组的长度。由于HashMap对底层结构采用延迟初始化的策略，就是说实例化HashMap对象时，其实并没有立即对底层结构实例化，底层数组依然为空，因此当我们首次像该HashMap对象中put数据时，才会通过扩容来创建底层数组的实例。而当底层数组为空时，就认为数组长度为0即可。
int oldCap = (oldTab == null) ? 0 : oldTab.length;获取原阈值，即
threshold我们在聊构造方法时，如果我们指定了数组的初始容量，HashMap使用
tableSizeFor()方法重新确定容量时，将确定的容量赋值给阈值threshold了，如下所示：public HashMap(int initialCapacity, float loadFactor) { // ...... this.threshold = tableSizeFor(initialCapacity); }因此，阈值
threshold可能表示其本省的含义此时为0，也可能暂时表示底层数组长度。确定新数组的长度
newCap和下次扩容时的阈值thresholdif (oldCap > 0) { if (oldCap >= MAXIMUM_CAPACITY) { threshold = Integer.MAX_VALUE; return oldTab; } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) newThr = oldThr << 1; // double threshold } else if (oldThr > 0) // initial capacity was placed in threshold newCap = oldThr; else { // zero initial threshold signifies using defaults newCap = DEFAULT_INITIAL_CAPACITY; newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY); } if (newThr == 0) { float ft = (float)newCap * loadFactor; newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ? (int)ft : Integer.MAX_VALUE); } threshold = newThr; Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];如果原数组容量大于0，说明原数组已经初始化了，相应的阈值也已经设置过了。
此时只需要将原数组容量 2作为新数组容量，原阈值 2作为新阈值。
如果原数组容量为0，说明原数组还没有初始化，这种情况针对的是两个参数的构造方法。
这时如果原阈值大于0，说明该原阈值目前只是暂时表示数组长度，就回到了上面的问题了，只需要将该原阈值作为新数组容量就可以了。然后再根据 数组容量 * 加载因子
loadFactor的值 作为 新的阈值即可。如果原数组容量为0，原阈值也为0，这种情况针对的是无参构造方法。
这是只需要将新数组容量设置为默认的初始容量，新阈值设置为默认的初始容量与加载因子的乘积即可。
2、将原数组中的数据放在新数组中
同样，我们也把这一部分源码再次贴出来具体分析一下其中的细节，看起来很复杂吧，别慌。
其中判断节点位于原数组和新数组中的下标是否变化，下一节会详细介绍
Node<K,V>[] oldTab = table;
table = newTab;
if (oldTab != null) {
// 遍历原数组
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 获取原数组中下标为j的节点e
// 并将原数组中下标为j的节点设置为空
oldTab[j] = null;
if (e.next == null)
// 如果节点e没有后置节点，即表示该位置不存在链表或红黑树
// 通过节点e的hash值与新数组的容量计算出节点e在新数组中的下标
// 并将e放在该下标处
// 以下代码处理该位置仅有一个节点的情况
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
// 节点e为TreeNode对象，即表示该位置存在以节点e为根的红黑树
// 以下代码处理红黑树情况
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else {
// preserve order
// 节点e既有后置节点，又不是TreeNode对象，即表示该位置存在以节点e为头节点的链表
// 以下代码处理链表情况
// loHead表示从原数组移动至新数组的过程中下标不变的链表的头节点
// loTail表示从原数组移动至新数组的过程中下标不变的链表的尾节点
// 简单点说，以loHead为头节点的链表在原数组与新数组的下标相同，loTail是该链表的尾节点
Node<K,V> loHead = null, loTail = null;
// hiHead表示从原数组移动至新数组的过程中下标变化的链表的头节点
// hiTail表示从原数组移动至新数组的过程中下标变化的链表的尾节点
// 简单点说，以hiHead为头节点的链表在原数组与新数组的下标不同，hiTail是该链表的尾节点
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
// 遍历以节点e为头节点的链表
next = e.next;
// 如果下标不变，则为true
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;
}
}
}
}
}
3、扩容时对红黑树的处理
上面代码中直接处理单节点和链表这两种情况，而当遇到红黑树时调用split()方法单独处理，该方法由HashMap内部类TreeNode提供。
注意：虽然当前处理的是红黑树，但是别忘了TreeNode中依然存在一个next属性，也就是说，当我们以left和right遍历时，它是红黑树；当我们以next遍历时，它是链表。这对下面的方法实现很重要。
下面我们看一下此方法如何实现
// map - hashMap对象
// tab - hashMap对象中的新数组
// index - 红黑树根节点位于hashMap对象中原数组的下标
// bit - hashMap对象中原数组的长度
final void split(HashMap<K,V> map, Node<K,V>[] tab, int index, int bit) {
// 红黑树的根节点
TreeNode<K,V> b = this;
// 下面四个对象的含义与上面遇到的相同
TreeNode<K,V> loHead = null, loTail = null;
TreeNode<K,V> hiHead = null, hiTail = null;
// lc和hc都表示当前红黑树中节点数量，它两个的区别与上面四个对象的区别一样
int lc = 0, hc = 0;
// 通过next，将红黑树以链表的形式遍历，并记录红黑树中的节点数量
// 遍历结果，获得以loHead为头结点、以loTail为尾节点的链表，或以hiHead为头结点、以hiTail为尾结点的链表
for (TreeNode<K,V> e = b, next; e != null; e = next) {
next = (TreeNode<K,V>)e.next;
e.next = null;
if ((e.hash & bit) == 0) {
if ((e.prev = loTail) == null)
loHead = e;
else
loTail.next = e;
loTail = e;
++lc;
}
else {
if ((e.prev = hiTail) == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
++hc;
}
}
// 下面两个if块代码逻辑相同，分别处理位于数组的下标不变和变化两种情况。只会处理一个，
// 并且根据红黑树中节点数量是否小于UNTREEIFY_THRESHOLD，来判断是否将红黑树退化为链表
if (loHead != null) {
if (lc <= UNTREEIFY_THRESHOLD)
// 将红黑树退化为链表，因为当前已经将红黑树遍历成链表了
// 因此只需要将各个节点从treeNode对象转为Node对象即可
tab[index] = loHead.untreeify(map);
else {
tab[index] = loHead;
if (hiHead != null) // (else is already treeified)
// 将遍历出的链表再转为红黑树
loHead.treeify(tab);
}
}
if (hiHead != null) {
if (hc <= UNTREEIFY_THRESHOLD)
tab[index + bit] = hiHead.untreeify(map);
else {
tab[index + bit] = hiHead;
if (loHead != null)
hiHead.treeify(tab);
}
}
}
如何将链表转为红黑树，其实它的原理与HashMap的关系不大了，可以参考一下我们之前的文章红黑树
4、通过图例理解扩容细节
现在我们通过图片好好分析一下扩容原理，以下图为例，对其进行扩容，其实按照扩容阈值threshold = capcity * 0.75早就应该扩容了，这里只是为了演示。
首先遍历到原数组的下标为0的节点W，发现该位置存在链表，如下图所示
遍历到原数组的下标为1的节点X，发现该位置仅有一个节点X，不存在链表和红黑树，如下图所示
遍历到原数组的下标为3的节点X，发现该位置存在链表，如下图所示
遍历到原数组的下标为7的节点Z，发现该位置存在红黑树，如下图所示
5、如何判断出下标是否变化
在源码中，我们看到，节点位于原数组与新数组的下标是否相同，可以通过(e.hash & oldCap) == 0来判断，
例如我们有一个原数组oldTab.length = 8，一个新数组newTab.length = 16。在原数组中有两个节点A和B，且A.hash=9，B.hash=3。
如下图所示
以上就是HashMap的扩容原理啦，我们下期再见。
