ConcurrentHashMap-扩容分析拾遗

## 前言

这是一篇对 transfer 方法的拾遗,关于之前那篇文章的一些一笔带过,或者当时不知道的地方进行回顾。

疑点 1. 为什么将链表拆成两份的时候,0 在低位,1 在高位?

回顾一下 transfer 的相关代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
int runBit = fh & n;
Node<K,V> lastRun = f;
for (Node<K,V> p = f.next; p != null; p = p.next) {
// 取于桶中每个节点的 hash 值
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {// 如果最后更新的 runBit 是 0 ,设置低位节点
ln = lastRun;
hn = null;
}
else {
hn = lastRun; // 如果最后更新的 runBit 是 1, 设置高位节点
ln = null;
}
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
// 如果与运算结果是 0,那么就还在低位
if ((ph & n) == 0) // 如果是0 ,那么创建低位节点
ln = new Node<K,V>(ph, pk, pv, ln);
else // 1 则创建高位
hn = new Node<K,V>(ph, pk, pv, hn);
}

关键看上面注释的代码,如果 runBit 是 0,那么就设置在低位节点,反之,如果是 1,设置在高位。

为什么这么设计呢?当时楼主一笔带过,称之为这个貌似没有什么特殊含义,实在是愚蠢之极。

今天解释一下。

这要从 ConcurrentHashMap 的取于下标算法开始说起。

我们知道,在 putVal 方法中,会通过取于对象的 hash 值获取下标。具体代码如下:

1
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {

也就是 (n - 1) & hash),这个 n 就是 length。这个其实相当于 hash % n(n 必须是2的指数)。但是比 % 更高效。

复习一下与运算:第一个操作数的的第n位于第二个操作数的第n位如果都是1,那么结果的第n为也为1,否则为0.

然后开始推导:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
(n - 1) & hash),取于算法。
假设,我们的 table 长度是 16,也就是 10000,减一就是 01111. 取于下面这个数。这个数特别之处在于,
他的右起第 5 位是 0。如果是 10000 & 这个数,结果是 0.
000000001111 000000010000
010101001001 // 结果 9 010101001001 // &运算结果: 0

当我们扩容后,16 变成 32,也就是 10000. 再看看 (n - 1) & hash) 的结果:

000000011111
010101001001 // 结果还是 9

从这里可以看出,如果 & 运算是 0 ,那么即使扩容,下标也是不变的。

再看看另一种情况,换一个 hash 数字,右起第五位是 1
000000001111 000000010000
010101010001 // 结果 1 010101010001 // &运算结果: 1

这里的 & 与运算后,结果是 1,和上面的不同。同时, (n - 1) & hash) 的结果也是 1.

当扩容后,结果是什么样子呢?
000000011111
010101010001 // 结果变化:10001 == 17

可以看到,(n - 1) & hash) 的结果是 1717 - 1,刚好是 16,而这个 16 的原因是我们的二进制进了一位。

现在明白了吧?0 在低位,1 在高位不是随便设计的。这里让我想到了一致性 hash 算法:当桶的数量变化了,那么 hash 的位置也会变化

这里的设计是为了防止下次取值的时候,hash 不到正确的位置。

实际上,JDK 1.8 的 HashMap 也是这么实现的重新散列。文章深入理解 HashMap put 方法(JDK 8逐行剖析)。其中 resize 方法和这里高度类似。

疑点 2:为什么会有 i >= n || i + n >= nextn 的判断?

回顾一下代码:

1
2
3
4
5
6
7
8
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}

这个判断在当时看来是没有可能存在的。到现在也没明白为什么。。。。

如果有大佬知道,请指点一二。


ConcurrentHashMap-扩容分析拾遗
http://thinkinjava.cn/2018/05/16/2018/2018-05-16-ConcurrentHashMap-扩容分析拾遗/
作者
莫那·鲁道
发布于
2018年5月16日
许可协议