深入理解HashMap(四): 关键源码逐行分析之resize扩容
前言
系列文章目录
上一篇我们说明了HashMap的构造函数, 谈到构造函数中并不会初始化table 变量, table 变量是在 resize过程中初始化的.
本篇我们就来聊聊HashMap的扩容: resize
本文的源码基于 jdk8 版本.
resize
resize用于以下两种情况之一
- 初始化table
- 在table大小超过threshold之后进行扩容
下面我们直接来对照源码分析:
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
// 原table中已经有值
if (oldCap > 0) {
// 已经超过最大限制, 不再扩容, 直接返回
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
// 注意, 这里扩容是变成原来的两倍
// 但是有一个条件: `oldCap >= DEFAULT_INITIAL_CAPACITY`
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY)
newThr = oldThr << 1; // double threshold
}
// 在构造函数一节中我们知道
// 如果没有指定initialCapacity, 则不会给threshold赋值, 该值被初始化为0
// 如果指定了initialCapacity, 该值被初始化成大于initialCapacity的最小的2的次幂
// 这里是指, 如果构造时指定了initialCapacity, 则用threshold作为table的实际大小
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
// 如果构造时没有指定initialCapacity, 则用默认值
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
// 计算指定了initialCapacity情况下的新的 threshold
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
//从以上操作我们知道, 初始化HashMap时,
//如果构造函数没有指定initialCapacity, 则table大小为16
//如果构造函数指定了initialCapacity, 则table大小为threshold, 即大于指定initialCapacity的最小的2的整数次幂
// 从下面开始, 初始化table或者扩容, 实际上都是通过新建一个table来完成的
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
// 下面这段就是把原来table里面的值全部搬到新的table里面
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node<K,V> e;
if ((e = oldTab[j]) != null) {
// 这里注意, table中存放的只是Node的引用, 这里将oldTab[j]=null只是清除旧表的引用, 但是真正的node节点还在, 只是现在由e指向它
oldTab[j] = null;
// 如果该存储桶里面只有一个bin, 就直接将它放到新表的目标位置
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;
}resize时的链表拆分
下面我们单独来看看这段设计的很精妙的代码
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;
}首先我们看源码时要抓住一个大框架, 不要被它复杂的流程唬住, 我们一段一段来看:
第一段
Node<K,V> loHead = null, loTail = null; Node<K,V> hiHead = null, hiTail = null;
上面这段定义了四个Node的引用, 从变量命名上,我们初步猜测, 这里定义了两个链表, 我们把它称为 lo链表 和 hi链表, loHead 和 loTail 分别指向 lo链表的头节点和尾节点, hiHead 和 hiTail以此类推.
第二段
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);上面这段是一个do-while循环, 我们先从中提取出主要框架:
do {
next = e.next;
...
} while ((e = next) != null);从上面的框架上来看, 就是在按顺序遍历该存储桶位置上的链表中的节点.
我们再看if-else 语句的内容:
// 插入lo链表
if (loTail == null)
loHead = e;
else
loTail.next = e;
loTail = e;
// 插入hi链表
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;上面结构类似的两段看上去就是一个将节点e插入链表的动作.
最后再加上 if 块, 则上面这段的目的就很清晰了:
我们首先准备了两个链表lo和hi, 然后我们顺序遍历该存储桶上的链表的每个节点, 如果(e.hash & oldCap) == 0, 我们就将节点放入lo链表, 否则, 放入hi链表.
第三段
第二段弄明白之后, 我们再来看第三段:
if (loTail != null) {
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}这一段看上去就很简单了:
如果lo链表非空, 我们就把整个lo链表放到新table的j位置上
如果hi链表非空, 我们就把整个hi链表放到新table的j+oldCap位置上
综上我们知道, 这段代码的意义就是将原来的链表拆分成两个链表, 并将这两个链表分别放到新的table的 j 位置和 j+oldCap 上, j位置就是原链表在原table中的位置, 拆分的标准就是:
(e.hash & oldCap) == 0
为了帮助大家理解，我画了个示意图：
（ps: 画个图真的好累啊， 大家有什么好的画图工具推荐吗？）
关于 (e.hash & oldCap) == 0 j 以及 j+oldCap
上面我们已经弄懂了链表拆分的代码, 但是这个拆分条件看上去很奇怪, 这里我们来稍微解释一下:
首先我们要明确三点:
- oldCap一定是2的整数次幂, 这里假设是2^m
- newCap是oldCap的两倍, 则会是2^(m+1)
- hash对数组大小取模
(n - 1) & hash其实就是取hash的低m位
例如:
我们假设 oldCap = 16, 即 2^4,
16 - 1 = 15, 二进制表示为 0000 0000 0000 0000 0000 0000 0000 1111
可见除了低4位, 其他位置都是0（简洁起见，高位的0后面就不写了）, 则 (16-1) & hash 自然就是取hash值的低4位,我们假设它为 abcd.
以此类推, 当我们将oldCap扩大两倍后, 新的index的位置就变成了 (32-1) & hash, 其实就是取 hash值的低5位. 那么对于同一个Node, 低5位的值无外乎下面两种情况:
0abcd 1abcd
其中, 0abcd与原来的index值一致, 而1abcd = 0abcd + 10000 = 0abcd + oldCap
故虽然数组大小扩大了一倍，但是同一个key在新旧table中对应的index却存在一定联系： 要么一致，要么相差一个 oldCap。
而新旧index是否一致就体现在hash值的第4位(我们把最低为称作第0位), 怎么拿到这一位的值呢, 只要:
hash & 0000 0000 0000 0000 0000 0000 0001 0000
上式就等效于
hash & oldCap
故得出结论:
如果(e.hash & oldCap) == 0则该节点在新表的下标位置与旧表一致都为j
如果(e.hash & oldCap) == 1则该节点在新表的下标位置j + oldCap
根据这个条件, 我们将原位置的链表拆分成两个链表, 然后一次性将整个链表放到新的Table对应的位置上.
怎么样? 这个设计是不是很巧妙, 反正LZ是无比佩服源码作者的!
总结
- resize发生在table初始化, 或者table中的节点数超过
threshold值的时候,threshold的值一般为负载因子乘以容量大小. - 每次扩容都会新建一个table, 新建的table的大小为原大小的2倍.
- 扩容时,会将原table中的节点re-hash到新的table中, 但节点在新旧table中的位置存在一定联系: 要么下标相同, 要么相差一个
oldCap(原table的大小).
（完）
下一篇: 深入理解HashMap(五): 关键源码逐行分析之put
查看更多系列文章：系列文章目录