ConcurrentHashMap1.8源码学习之扩容（链表结构）

读源码时，transfer(Node<K,V>[] tab, Node<K,V>[] nextTab)方法总是看不懂，咋整呢？画图吧，梳理下执行过程。初始容量16，标号为0的槽位下各节点Hash值如下图，

int n = tab.length

int runBit = fh & n;

Node<K,V> lastRun = f;

如图，n=16,二进制位10000，如果fh是10000，那么runBit=10000&10000（16&16）=10000

第一次执行100000节点;b=0,runBit=10000,b!=runBit为true，runBit=0,lastRun=100000节点。

第二次执行110000节点，b=10000（16），runBit=0，b!=runBit为true。runBit=10000（16）,lastRun=110000节点。

第三次执行1100000节点，b=0，runBit=10000（16），b!=runBit为true，runBit=0,lastRun=1100000节点。

第四次执行1110000节点，b=10000（16）,runBit=0,b!=runBit为true，runBit=10000（16）,lastRun=1110000节点。

结束。

//得到最后一个和前面的节点 高位 不一样的节点和高位（0或10000）

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

      int b = p.hash & n;

      if (b != runBit) {

      runBit = b;

      lastRun = p;

       }

}

 

//如果最后一个高位不一样的节点高位是0，则设置低位节点

if (runBit == 0) {

   ln = lastRun;

   hn = null;

 }

//如果最后一个高位不一样的节点高位是1，则设置高位节点

 else {

     hn = lastRun;

    ln = null;

}

//具体到该例子，hn=1110000,ln=null

//这里从该槽位的根节点开始

//第一次执行10000&10000(16&16)=10000,走else分支，ln=null,

hn=new Node<K,V>(10000, Node10000.key, Node10000.val, Node1110000);新节点如图：

//第二次执行100000&10000（32&16）=0，走if分支，

ln=new Node<K,V>(100000, node10000.key,  ndoe100000.val,   null)，新节点如图：

1100000（96）节点执行后由于最后一个节点和lastRun是同一个节点，故1110000（112）节点不参与执行。

最终hn节点如图：

Ln节点如图：

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

      int ph = p.hash; K pk = p.key; V pv = p.val;

      if ((ph & n) == 0)

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

      else

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

 }

//低位节点仍然挂在了新数组同样的下标位置，

setTabAt(nextTab, i, ln);

//高位节点挂在了新数组i+n的位置

setTabAt(nextTab, i + n, hn);

//节点处理完毕

setTabAt(tab, i, fwd);

advance = true;

扩容后节点如图：