ConcurrentHashMap transfer分析·

清疚 2022-12-12 04:53 189阅读 0赞

### 文章目录 ###

*  前言
 *  transfer初始化
 *  transfer哈希桶范围确定
 *  transfer 拷贝旧数据到新的哈希表
 *  参考文献

# 前言 #

> 本文分析1.8之下的源码。本文需要读者之前对HashMap有一定了解，如HashMap中的红黑树和链表等。

我们回顾下HashMap基本结构：

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmYW5taW5neWlx_size_16_color_FFFFFF_t_70_pic_center]

`ConcurrentHashMap`的扩容算法极其精妙，也是最晦涩难懂的部分.

我首先将代码分段梳理各个部分的功能，在做细节说明。

//ConcurrentHashMap.java
     private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
        
            int n = tab.length, stride;
            
            //stride 决定一个线程处理的哈希表中多少个位置.比如为10那么处理，10个哈希桶的数据迁移工作
            if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
                stride = MIN_TRANSFER_STRIDE; // subdivide range
            
            if (nextTab == null) {
                    // initiating
             	//(1)构造一个新的数组容量为旧数据的两倍
            }
            int nextn = nextTab.length;
            ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
            boolean advance = true;
            boolean finishing = false; // to ensure sweep before committing nextTab
            for (int i = 0, bound = 0;;) {
        
                Node<K,V> f; int fh;
                while (advance) {
        
                   //这里作用使用确定 i和bound的数值。
                   //i和bound决定当前线程处理哈希表中 从i到bound位置的哈希桶拷贝到新表
                }
                if (i < 0 || i >= n || i + n >= nextn) {
        
                  //判断是否结束
                }
                else if ((f = tabAt(tab, i)) == null)
    
                    advance = casTabAt(tab, i, null, fwd);
                else if ((fh = f.hash) == MOVED)
                    advance = true; 
                else {
        
                    synchronized (f) {
        
                        if (tabAt(tab, i) == f) {
        
                            Node<K,V> ln, hn;
                            if (fh >= 0) {
        
                               //链表哈希桶 迁移到新的扩容数组。
                            }
                            else if (f instanceof TreeBin) {
        
                               //红黑树哈希桶 迁移到新的扩容数组。本文只分析链表情况
                            }
                        }
                    }
                }
            }
        }

# transfer初始化 #

此部分代码用于创建一个新的hash表，和确定每个线程处理`hash`表最大长度。（比如处理3个哈希桶的数据拷贝到新表）

//ConcurrentHashMap.java
       //forwarding nodes节点的哈希值
        static final int MOVED     = -1; // hash for forwarding nodes
    
    	//仅当扩容时不为空，其他时候都为空。扩容完成自动为null
        private transient volatile Node<K,V>[] nextTable;
       /**
        * 当扩容时nextTable分割的位置(+1)
         * The next table index (plus one) to split while resizing.
         */
        private transient volatile int transferIndex;
        
      //入参：tab 旧的哈希表
      //入参：nextTab 要么传入ConcurrentHashMap的nextTable属性，要么和参入null。这个参数表示构造的新哈希表				
      private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
        
            //旧表的长度
            int n = tab.length;
            //决定一个线程最大处理的哈希桶数量
            int stride;
            //NCPU表示cpu数量。
            //MIN_TRANSFER_STRIDE 数值为16 
            //(n >>> 3)表示旧表长度除以8。至于为什么要将表除以8我就不得而知，
            //笔者认为是Doug Lea的实践经验除以8可以更高效。
            //综上以及结合代码此处：max( 旧表长度/8/cpu数量 ,MIN_TRANSFER_STRIDE)
            if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
                stride = MIN_TRANSFER_STRIDE; // subdivide range
            
            //新哈希表为空那么创建一个新的哈希表   
            if (nextTab == null) {
                    // initiating
                try {
        
                    //构造一个容量为旧表两倍的数组。n << 1表示为旧表长度*2 
                    Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
                    nextTab = nt;
                } catch (Throwable ex) {
              // try to cope with OOME
                    sizeCtl = Integer.MAX_VALUE;
                    return;
                }
                //赋值给成员属性，防止在多线程下多次初始化
                nextTable = nextTab;
                //设置成员属性
                transferIndex = n;
            }
            //新哈希表长度
            int nextn = nextTab.length;
            //占位节点。并且哈希值为-1，对应为成员字段MOVED
            ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
            //...略
    }

总结就是构造了一个新的哈希表并设置了最大处理长度.

# transfer哈希桶范围确定 #

//ConcurrentHashMap.java
     
      //入参：tab 旧的哈希表
      //入参：nextTab 要么传入ConcurrentHashMap的nextTable属性，要么和参入null。这个参数表示构造的新哈希表				
      private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
        
            //...初始化代码略
            //...
            boolean advance = true;
            boolean finishing = false; // to ensure sweep before committing nextTab
            //for循环就是用来做旧表迁移到新表的逻辑
            //死循环。直到迁移完成。i表示当前线程处理哈希桶的初始下标，bound表示当前显示线程处理哈希桶的结束下标
            for (int i = 0, bound = 0;;) {
        
                Node<K,V> f; 
                int fh;
            	//    
                while (advance) {
        
                    int nextIndex;
                    int nextBound;
                    //--i的寓意 是在确定bound和i之后的下次循环才有意义
                    //这里--i 是表示处理区间的下一个哈希桶元素列表，因为上次已经处理过i位置。
                    if (--i >= bound || finishing)
                        advance = false;
                    else if ((nextIndex = transferIndex) <= 0) {
        
                    	//如果下标不合法就结束
                        i = -1;
                        advance = false;
                    }
                    //cas方式设置ConcurrentHashMap的transferIndex属性
                    //transferIndex在transfer初始化阶段赋值为旧哈希表长度
                    //nextIndex此时等于transferIndex。
                    // nextBound = (nextIndex > stride ? nextIndex - stride : 0))
                    // nextIndex > stride 如果当前分割点位置(transferIndex)大于最大处理阈值stride
                    //就返回nextIndex - stride 作为处理哈希桶区间的起始下标，否则是0 
                    else if (U.compareAndSwapInt
                             (this, TRANSFERINDEX, nextIndex,
                              nextBound = (nextIndex > stride ?
                                           nextIndex - stride : 0))) {
        
    					//确定起始下标和终止下标
                        bound = nextBound;
                        i = nextIndex - 1;
                        advance = false;
                    }
                }
    		 //...略
    		}//for            
         
    }

总结 ： 确定当前要处理哪部分哈希桶.`bound`起始坐标，`i`结束坐标。

# transfer 拷贝旧数据到新的哈希表 #

private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
        
    
    		//...
    		//..初始化新的哈希表
    		//略
    		//固定哈希值为MOVE，用于标识正在扩容
    		ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
    
    		//此for循环用于拷贝旧哈希表数据到新的哈希表
    		for (int i = 0, bound = 0;;) {
        
    		            
    		            Node<K,V> f; 
    					
    					int fh;
    		            
    		            while (advance) {
        
    		               //确定bound和i数值 然后 advance=false 略
    		            }
    		            //i < 0 数据不合法
    		            // i >= n 当前处理的范围大于旧链表最大长度，已经不需要拷贝越界数据
    		            // i + n >= nextn 。nextn表示新哈希表长度，如果当前长度超过新哈希表长度，
    		            //证明是不合法的
    		            if (i < 0 || i >= n || i + n >= nextn) {
        
    		                int sc;
    		                if (finishing) {
        
    		                    nextTable = null;
    		                    table = nextTab;
    		                    sizeCtl = (n << 1) - (n >>> 1);
    		                    return;
    		                }
    		                if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
        
    		                    if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
    		                        return;
    		                    finishing = advance = true;
    		                    i = n; // recheck before commit
    		                }
    		            }
    		            //如果旧的哈希表第i个位置不存在元素那么，放置一个fwd对象，且hash值为MOVED
    		            //可以让其他插入线程感知
    		            else if ((f = tabAt(tab, i)) == null)
    		                advance = casTabAt(tab, i, null, fwd);
    		            else if ((fh = f.hash) == MOVED)
    		            	//当前位置已经被其他线程替换成fwd对象，那么重新拷贝其他哈希桶位置到新哈希表
    		            	//advance标志为true 让其重新选择哈希桶拷贝到新哈希表
    		                advance = true; // already processed
    		            else {
        
    		            //else负责移动哈希桶元素到新的哈希表
    		            
    		                //所有哈希桶移动删除必须加锁头节点
    		                synchronized (f) {
        
    		                	//需要二次判断 当前哈希桶头结点是否改变，因为在获取到锁时
    		                	//哈希桶头结点已经改变了
    		                    if (tabAt(tab, i) == f) {
        
    		                        //用于移动哈希桶元素到新的低地址元素
    		                        Node<K,V> ln;
    		                        //用于移动哈希桶元素到新的高地址元素 
    		                        Node<K,V> hn;
    		                        //如果哈希值大于0证明哈希桶是链表结构
    		                        if (fh >= 0) {
        
    		                            //n表示旧的哈希表长度且为2的n次方(方便利用位运算得到哈希位置)
    									//所以n的字节特点就是 只有一个1其余都是0.比如16二进制为1 0000
    									//因此跟n做位运算的与预算 结果只能为 0或者为n。
    									//如果fh & n 为n:
    									//证明此元素在新哈希表中的 x+n 位置上。（x为当前哈希表数组下标所在位置）
    									//对应下面代码  setTabAt(nextTab, i + n, hn);
    									//如果 fh & n 为0 ：
    									//那么此元素在新的哈希表中的位置和当前在旧的哈希表位置下标是一样,
    									//对应下面代码  setTabAt(nextTab, i, ln);
    									//上述数理逻辑读者可自行思考。
    									//逻辑不是太难理解，因为如果元素哈希值能于旧哈希表长度N按位与得到N,那么证明此元素在新哈希表长度M（为旧数组两倍M=2N）的下标必然大于n且为当前数组位置+n。
    									//比如 旧哈希表长度 等于8 新数组长度为16，某个元素的哈希值为15
    									//在旧的哈希表中：元素哈希对应数组下标为7。在新的数组中下标为15（旧数组下标+旧数组长度=7+8）.
    		                            int runBit = fh & n;
    		                            //当前指向哈希桶头结点
    		                            //在后面紧跟的for循环中改变指向为最后一个runBit不同的节点
    		                            Node<K,V> lastRun = f;
    		                            
    		                            //这里目的是不知道怎么用言语去表述
    		                            //寻找到一个全部后续节点哈希值和旧数组长度相同哈希结果相同的第一个节点
    		                            //比如某个lastRun的p.hash & n为0，那么后续所有子元素都要求p.hash & n为0
    		                            //或者说某个lastRun的p.hash & n为n，那么后续所有子元素都要求p.hash & n为n
    		                            //这里这么做是方便移动哈希桶元素的到新哈希表的两种情况。（一种是保持位在新的哈希表不变，另一种是当前位置加旧哈希表长度）
    		                            for (Node<K,V> p = f.next; p != null; p = p.next) {
        
    		                                int b = p.hash & n;
    		                                if (b != runBit) {
        
    		                                    runBit = b;
    		                                    lastRun = p;
    		                                }
    		                            }
    		                            //判断lastRun是那种类型
    		                            if (runBit == 0) {
        
    		                                ln = lastRun;
    		                                hn = null;
    		                            }
    		                            else {
        
    		                                hn = lastRun;
    		                                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;
    		                                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);
    		                            setTabAt(nextTab, i + n, hn);
    		                            setTabAt(tab, i, fwd);
    		                            //设置advance为true让当前线程继续计算处理其他旧哈希桶位置的拷贝
    		                            advance = true;
    		                        }
    		                        else if (f instanceof TreeBin) {
        
    		                          //..红黑树部分略
    		                        }
    		                    }
    		                }
    		            }
    		        }
    }

任何哈希桶下插入删除的操作需要加锁说明：

情况一：  
多个线程想同时插入新的节点到同一个哈希桶的链表中。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmYW5taW5neWlx_size_16_color_FFFFFF_t_70_pic_center 1]  
**情况二：**

一个线程插入哈希桶，另一个线程进行移除操作。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmYW5taW5neWlx_size_16_color_FFFFFF_t_70_pic_center 2]  
虽然上述操作可以使用CAS加自旋完成，但是会增加复杂度。

# 参考文献 #

1.  [并发编程——ConcurrentHashMap\#transfer() 扩容逐行分析][ConcurrentHashMap_transfer_]
2.  [并发容器之ConcurrentHashMap详解(JDK1.8版本)与源码分析][ConcurrentHashMap_JDK1.8]
3.  [HashMap位运算你可知一二][HashMap]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmYW5taW5neWlx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/556fa4c239f742f5b55845fe79ffb495.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmYW5taW5neWlx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/e0eb9566fd1e411cb8a36330963bddd4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FmYW5taW5neWlx_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/6181f2c51dd74d3a9683c7d57e8b9e5c.png
[ConcurrentHashMap_transfer_]: https://juejin.im/post/6844903607901356046
[ConcurrentHashMap_JDK1.8]: https://blog.csdn.net/ThinkWon/article/details/102506447
[HashMap]: https://www.cnblogs.com/augustrush/p/13195141.html