ConcurrentHashMap源码解析4.transfer()方法(核心)

总结：

• 第一次进来扩容的线程会创建出一个新表。长度为原来的2倍。
• 迁移元素从后往前(索引从大到小)。
• 迁移完成的桶在当前桶位置放一个ForwardIngNode类型的节点，表示该桶迁移完成
• 迁移时通过hash&n(原长度)就是判断高位来判断在新链表中的索引位置，跟HashMap扩容原理一样。
• 低位链表(树)存储到新表的原索引位置
• 高位链表(树)存储到新表的原索引 + n(原数组长度)的位置
• 迁移元素时会使用synchronized锁定当前桶位，锁对象就是当前桶位的头结点，这是分段锁的思想。
• 迁移时，会根据原桶中的节点创建一个新的节点(除了lastRun机制的节点外)。
• 最后一个扩容的线程在退出时会重新扫描原表判断是否有遗漏的桶没有迁移节点，然后将nextTable赋值给table，然后将nextTable置为NULL，将sizeCtl设置为新数组长度的3/4即扩容阈值。

LastRun机制

LastRun机制就是为了省掉最后连续一段高位相同的节点的创建过程(只有原桶位是链表是才会有lastRun机制)

当最后一段的节点高位相同时，就不必创建了，直接引用这一串节点即可。

源码解析

   
   private final void transfer(Node[] tab, Node[] nextTab) {
         
        
        int n = tab.length, stride;
        
        if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
            stride = MIN_TRANSFER_STRIDE; //16
       
        
        if (nextTab == null) {            // initiating
            try {
                
                //创建了一个是原来长度2倍的Node数组
                Node[] nt = (Node[])new Node[n << 1];
                nextTab = nt;
            } catch (Throwable ex) {      // try to cope with OOME
                sizeCtl = Integer.MAX_VALUE;
                return;
            }
            //赋值给nextTable数组，方便协助扩容线程拿到新表。
            nextTable = nextTab;
            //记录迁移数据整体位置的一个标记。index计数是从1开始计算的，从高到底进行计数
            //transferIndex <=0 表示迁移完毕
            transferIndex = n;
        }
       
        //表示新数组的长度
        int nextn = nextTab.length;
       
        
        ForwardingNode fwd = new ForwardingNode(nextTab);
       
        //推进标记
        boolean advance = true;
        //完成标记
        boolean finishing = false; // to ensure sweep before committing nextTab
       
        
        int i = 0, bound = 0;
       
        //自旋
        for (;;) {
            
            Node f; int fh;
            
               
            while (advance) {
                
                int nextIndex, nextBound;
                
                
                if (-- i >= bound || finishing)
                    advance = false;
                
                
                else if ((nextIndex = transferIndex) <= 0) {
                    i = -1;
                    advance = false; //推进标记置为false
                }
                
                else if (U.compareAndSwapInt
                         (this, TRANSFERINDEX, nextIndex,
                          nextBound = (nextIndex > stride ?
                                       nextIndex - stride : 0))) {
                    //分配任务成功 设置下界
                    bound = nextBound; 
                    //设置开始下标
                    i = nextIndex - 1; //-1是变为下标
                    advance = false; //分配任务后跳出
                }
            }
//---------------------------START----------------------------------------//                
                 
            if (i < 0 || i >= n || i + n >= nextn) {
                //保存sizeCtl的变量
                int sc;
                
                //只有最终完成整个迁移后，才会来到这个逻辑里
                if (finishing) {
                    //将nextTable置为NULL
                    nextTable = null;
                    //迁移后的新表赋值给table
                    table = nextTab;
                    //(n << 1) - (n >>> 1) = 0.75 * 2 * n
                    //下一次的扩容阈值就是新表的0.75
                    sizeCtl = (n << 1) - (n >>> 1);
                    //最终return。
                    return;
                }
                
               
               if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
                    //表示当前线程不是最后一个退出的线程。不需要干最后的活，直接return。
                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
                        return;
                    
                    //最后一个线程会一直检查是否有遗漏的桶位没有迁移，然后去做迁移。
                    finishing = advance = true;
                    i = n; // recheck before commit
                }
            }
//------------------------------END-------------------------------------------            
//下面的代码表示线程处理一个桶位数据的迁移工作，处理完毕后设置advance为true，表示继续推进，一直循环下去直接任务完毕。
            
            //来到下面这一堆代码(CASE2 - 4)的前置条件，当前线程任务尚未处理完，正在进行中
            
            
            else if ((f = tabAt(tab, i)) == null)
                //CAS操作，期望为NULL，设置为fwd节点。
                advance = casTabAt(tab, i, null, fwd);
            
            
            else if ((fh = f.hash) == MOVED)
                advance = true; // already processed
            
            
            else {
                //加锁 锁住当前桶位头结点(分段锁思想)
                synchronized (f) {
                    //再次判断。保证在加锁时当前桶位的头结点被其他线程修改了。
                    if (tabAt(tab, i) == f) {
                        
                        Node ln, hn;
                        
                        
                        if (fh >= 0) {
                            
                            
                           int runBit = fh & n;
                           Node lastRun = f;
                           //遍历链表，
                           for (Node p = f.next; p != null; p = p.next) {
                                int b = p.hash & n;
                                //当前节点的高位与lastRun节点的哈希值不一致，就更新
                                //lastRun，最终lastRun指向一串高位相同的节点
                                //这一串节点一定是链表的最后一段。
                                if (b != runBit) {
                                    runBit = b;
                                    lastRun = p;
                                }
                            }
                            
                            //如果lastRun指向的一串节点的高位是0，将ln也引用这一串节点
                            if (runBit == 0) {
                                ln = lastRun;
                                hn = null;
                            }
                            //否则将hn(高位链表)引用这一串节点
                            else {
                                hn = lastRun;
                                ln = null;
                            }
                            
                          
                          for (Node 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(ph, pk, pv, ln);
                                else
                                    hn = new Node(ph, pk, pv, hn);
                            }
                            //低位链设置到新哈希表的原索引位置(i)
                            setTabAt(nextTab, i, ln);
                            //高位链设置到新哈希表的i + n位置
                            setTabAt(nextTab, i + n, hn);
                            //设置原表的位置为fwd节点，表示当前桶位迁移完毕。
                            setTabAt(tab, i, fwd);
                            advance = true; 
                        }
                        
                        
                        else if (f instanceof TreeBin) {
                            //转换头结点为TreeBin节点。
                            TreeBin t = (TreeBin)f;
                            
                            //低位双向链表
                            TreeNode lo = null, loTail = null;
                            //高位双向链表
                            TreeNode hi = null, hiTail = null;
                            
                          
                            
                          int lc = 0, hc = 0;
                            
                          for (Node e = t.first; e != null; e = e.next) {
                                //表示循环处理当前元素的hash值
                                int h = e.hash;
                              
                                //使用当前节点构建出来的新的TreeNode节点
                                TreeNode p = new TreeNode
                                    (h, e.key, e.val, null, null);
                                
                                //构造低位链节点 (尾插法)
                                if ((h & n) == 0) {
                                    if ((p.prev = loTail) == null)
                                        lo = p;
                                    else
                                        loTail.next = p;
                                    loTail = p;
                                    ++lc;
                                }
                                //构造高位链节点 (尾插法)
                                else {
                                    if ((p.prev = hiTail) == null)
                                        hi = p;
                                    else
                                        hiTail.next = p;
                                    hiTail = p;
                                    ++hc;
                                }
                            }
                            
                          
                            ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
                                (hc != 0) ? new TreeBin(lo) : t;
                            
                            //跟上面类似
                            hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
                                (lc != 0) ? new TreeBin(hi) : t;
                            
                            
                            setTabAt(nextTab, i, ln);
                            setTabAt(nextTab, i + n, hn);
                            setTabAt(tab, i, fwd);
                            advance = true;
                        }
                    }
                }
            }
        }
    }

在put操作时，会判断当前桶位是否是fwd节点，如果是的话，就会进入**helpTransfer()**方法尝试帮助扩容。

  // -------------- put()方法中的片段--------------------------------------
  else if ((fh = f.hash) == MOVED)
                tab = helpTransfer(tab, f);
  //---------------------------------------
	
    
    final Node[] helpTransfer(Node[] tab, Node f) {
        
        
        Node[] nextTab; int sc;
        
        
        //三个条件都是恒成立
        if (tab != null && (f instanceof ForwardingNode) &&
            (nextTab = ((ForwardingNode)f).nextTable) != null) {
            
            //拿当前表的长度获取扩容戳
            int rs = resizeStamp(tab.length);
            
            //判断扩容是否已经完成。
            while (nextTab == nextTable && table == tab &&
                   (sc = sizeCtl) < 0) {
                
                    
                
                if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                    sc == rs + MAX_RESIZERS || transferIndex <= 0)
                    break;
                
                //CAS尝试更新扩容线程数 然后加入到扩容中去。
                if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
                    transfer(tab, nextTab);
                    break;
                }
            }
            return nextTab; 
        }
        return table;
    }