摘要：前言系列文章目录上一篇我们说明了的构造函数谈到构造函数中并不会初始化变量变量是在过程中初始化的本篇我们就来聊聊的扩容本文的源码基于版本用于以下两种情况之一初始化在大小超过之后进行扩容下面我们直接来对照源码分析原中已经有值已经超过最大限制不再
前言
系列文章目录
上一篇我们说明了HashMap的构造函数, 谈到构造函数中并不会初始化table 变量, table 变量是在 resize过程中初始化的.
本篇我们就来聊聊HashMap的扩容: resize
本文的源码基于 jdk8 版本.
resize
resize用于以下两种情况之一
初始化table
在table大小超过threshold之后进行扩容
下面我们直接来对照源码分析:
final Node[] resize() {
Node[] 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[] newTab = (Node[])new Node[newCap];
table = newTab;
// 下面这段就是把原来table里面的值全部搬到新的table里面
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) {
Node 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)e).split(this, newTab, j, oldCap);
// 下面这段代码很精妙, 我们多带带分一段详细来讲
else { // preserve order
Node loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node 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 loHead = null, loTail = null;
Node hiHead = null, hiTail = null;
Node 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 loHead = null, loTail = null;
Node 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
查看更多系列文章：系列文章目录
