ConcurrentHashMap1.8源码学习之扩容(链表结构)

    科技2023-09-26  79

    读源码时,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;

    扩容后节点如图:

     

     

    Processed: 0.009, SQL: 8