前言
这是一篇对 transfer 方法的拾遗，关于之前那篇文章的一些一笔带过，或者当时不知道的地方进行回顾。
疑点 1. 为什么将链表拆成两份的时候，0 在低位，1 在高位？
回顾一下 transfer 的相关代码：
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 值获取下标。具体代码如下：
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.
然后开始推导：
(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) 的结果是 17，17 - 1，刚好是 16，而这个 16 的原因是我们的二进制进了一位。
现在明白了吧？0 在低位，1 在高位不是随便设计的。这里让我想到了一致性 hash 算法：当桶的数量变化了，那么 hash 的位置也会变化。
这里的设计是为了防止下次取值的时候，hash 不到正确的位置。
实际上，JDK 1.8 的 HashMap 也是这么实现的重新散列。文章深入理解 HashMap put 方法（JDK 8逐行剖析）。其中 resize 方法和这里高度类似。
疑点 2：为什么会有 i >= n || i + n >= nextn 的判断？
回顾一下代码：
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
这个判断在当时看来是没有可能存在的。到现在也没明白为什么。。。。
如果有大佬知道，请指点一二。
网友评论