前言

這是一篇對(duì) transfer 方法的拾遺，關(guān)于之前那篇文章的一些一筆帶過，或者當(dāng)時(shí)不知道的地方進(jìn)行回顧。

疑點(diǎn) 1. 為什么將鏈表拆成兩份的時(shí)候，0 在低位，1 在高位？

回顧一下 transfer 的相關(guān)代碼：

int runBit = fh & n;

Node<K,V> lastRun = f;

for (Node<K,V> p = f.next; p != null; p = p.next) {

    // 取于桶中每個(gè)節(jié)點(diǎn)的 hash 值

    int b = p.hash & n;

    if (b != runBit) {

        runBit = b;

        lastRun = p;

    }

}

if (runBit == 0) {// 如果最后更新的 runBit 是 0 ，設(shè)置低位節(jié)點(diǎn)

    ln = lastRun;

    hn = null;

}

else {

    hn = lastRun; // 如果最后更新的 runBit 是 1， 設(shè)置高位節(jié)點(diǎn)

    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;

    // 如果與運(yùn)算結(jié)果是 0，那么就還在低位

    if ((ph & n) == 0) // 如果是0 ，那么創(chuàng)建低位節(jié)點(diǎn)

        ln = new Node<K,V>(ph, pk, pv, ln);

    else // 1 則創(chuàng)建高位

        hn = new Node<K,V>(ph, pk, pv, hn);

}

關(guān)鍵看上面注釋的代碼，如果 runBit 是 0，那么就設(shè)置在低位節(jié)點(diǎn)，反之，如果是 1，設(shè)置在高位。

為什么這么設(shè)計(jì)呢？當(dāng)時(shí)樓主一筆帶過，稱之為這個(gè)貌似沒有什么特殊含義，實(shí)在是愚蠢之極。

今天解釋一下。

這要從 ConcurrentHashMap 的取于下標(biāo)算法開始說起。

我們知道，在 putVal 方法中，會(huì)通過取于對(duì)象的 hash 值獲取下標(biāo)。具體代碼如下：

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

也就是 (n - 1) & hash)，這個(gè) n 就是 length。這個(gè)其實(shí)相當(dāng)于 hash % n（n 必須是2的指數(shù)）。但是比 % 更高效。

復(fù)習(xí)一下與運(yùn)算：第一個(gè)操作數(shù)的的第n位于第二個(gè)操作數(shù)的第n位如果都是1，那么結(jié)果的第n為也為1，否則為0.

然后開始推導(dǎo)：

(n - 1) & hash),取于算法。

假設(shè)，我們的 table 長度是 16，也就是 10000，減一就是 01111. 取于下面這個(gè)數(shù)。這個(gè)數(shù)特別之處在于,

他的右起第 5 位是 0。如果是 10000 & 這個(gè)數(shù)，結(jié)果是 0.

000000001111                     000000010000

010101001001 // 結(jié)果 9            010101001001 // &運(yùn)算結(jié)果： 0

當(dāng)我們擴(kuò)容后，16 變成 32，也就是 10000. 再看看 (n - 1) & hash) 的結(jié)果：

000000011111

010101001001 // 結(jié)果還是 9

從這里可以看出，如果 & 運(yùn)算是 0 ，那么即使擴(kuò)容，下標(biāo)也是不變的。

再看看另一種情況，換一個(gè) hash 數(shù)字，右起第五位是 1 ：

000000001111                      000000010000

010101010001 // 結(jié)果 1             010101010001 // &運(yùn)算結(jié)果： 1

這里的 & 與運(yùn)算后，結(jié)果是 1，和上面的不同。同時(shí)， (n - 1) & hash) 的結(jié)果也是 1.

當(dāng)擴(kuò)容后，結(jié)果是什么樣子呢？

000000011111

010101010001 // 結(jié)果變化：10001 == 17

可以看到，(n - 1) & hash) 的結(jié)果是 17，17 - 1，剛好是 16，而這個(gè) 16 的原因是我們的二進(jìn)制進(jìn)了一位。

現(xiàn)在明白了吧？0 在低位，1 在高位不是隨便設(shè)計(jì)的。這里讓我想到了一致性 hash 算法：當(dāng)桶的數(shù)量變化了，那么 hash 的位置也會(huì)變化。

這里的設(shè)計(jì)是為了防止下次取值的時(shí)候，hash 不到正確的位置。

實(shí)際上，JDK 1.8 的 HashMap 也是這么實(shí)現(xiàn)的重新散列。文章深入理解 HashMap put 方法（JDK 8逐行剖析）。其中 resize 方法和這里高度類似。

疑點(diǎn) 2：為什么會(huì)有 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;

    }

這個(gè)判斷在當(dāng)時(shí)看來是沒有可能存在的。到現(xiàn)在也沒明白為什么。。。。

如果有大佬知道，請(qǐng)指點(diǎn)一二。

總結(jié)

以上是生活随笔為你收集整理的ConcurrentHashMap 扩容分析拾遗的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。