这是一篇对 transfer 方法的拾遗,关于之前那篇文章的一些一笔带过,或者当时不知道的地方进行回顾。
回顾一下 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 的位置也会变化
。
实际上,JDK 1.8 的 HashMap 也是这么实现的重新散列。文章 深入理解 HashMap put 方法(JDK 8逐行剖析) 。其中 resize 方法和这里高度类似。
回顾一下代码:
if (i < 0 || i >= n || i + n >= nextn) { int sc; if (finishing) { nextTable = null; table = nextTab; sizeCtl = (n << 1) - (n >>> 1); return; }
这个判断在当时看来是没有可能存在的。到现在也没明白为什么。。。。
如果有大佬知道,请指点一二。
本文由创作,采用 知识共享署名4.0 国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: 2018/06/27 22:39