ConcurrentHashMap的扩容方法详解

男娘i 2021-09-28 12:42 484阅读 0赞

# 一、ConcurrentHashMap扩容 #

（jdk1.7）  
扩容只针对ConcurrentHashMap中的hashEntry类型的table数组进行扩容。  
方法在Segment类中：rehash（） ， 扩容倍数为：2倍扩容

*  **源码解析：**

private void rehash(HashEntry<K,V> node) { 
       //先将需要扩容的table数组进行拷贝
           HashEntry<K,V>[] oldTable = table;  
       //获取数组的长度
           int oldCapacity = oldTable.length;
       // 新table的容量为：旧数组容量*2
           int newCapacity = oldCapacity << 1;
       //阈值=新容量*加载因子
           threshold = (int)(newCapacity * loadFactor);
       //创建新的数组并定义容量为扩容后的容量
           HashEntry<K,V>[] newTable =(HashEntry<K,V>[]) new HashEntry[newCapacity];
           //哈希要用到的参数
           int sizeMask = newCapacity - 1;
           //遍历旧的数组
            for (int i = 0; i < oldCapacity ; i++) { 
                //e为头结点
                HashEntry<K,V> e = oldTable[i];
                //判断头结点是否为null
                if (e != null) { 
                //头结点不为空时，获取头结点的next节点
                    HashEntry<K,V> next = e.next;
                   //idx为头结点在扩容后的新表里重新哈希的位置
                     int idx = e.hash & sizeMask;
                   //此时只有一个节点，直接将当前头结点给新表对应的idx位置
                   if (next == null)  
                      newTable[idx] = e;
                      //多于一个节点
                    else { 
                    //将头结点赋给lastRun
                    HashEntry<K,V> lastRun = e;
                    //头结点在新表里重哈希的位置
                    int lastIdx = idx;
                    //从头结点的next节点开始，一直往后遍历
                    //（这个for循环的作用是从next节点开始遍历，直到找到后续节点新的index不变的节点lastRun）
                  for (HashEntry<K,V> last = next; last != null;last = last.next) { 
                      int k = last.hash & sizeMask;  //通过last的哈希值和 sizeMask 进行与操作，得到k
                     //如果k和头结点在扩容后的新表里重哈希的位置不相等
                     if (k != lastIdx) {    
                       //将头结点冲哈希的位置改为k
                        lastIdx = k; 
                        //更新lastRun的节点表示
                     lastRun = last;
                                }
                            }
     //for循环结束，将lastRun节点添加到新表中头结点的位置，因为lastRun表示的节点的next域不变，所以它之后的所有节点一起被链到了新表中头结点的位置
                      newTable[lastIdx] = lastRun;
               //这个for循环的作用是复制链表中lastRun之前的所有节点
             for (HashEntry<K,V> p = e; p != lastRun; p = p.next) { 
                     V v = p.value;  //头结点的值
                     int h = p.hash; //头结点的哈希值
                     int k = h & sizeMask;    //头结点的哈希值 位与 sizeMask， 计算新创节点的位置
                   //新创节点，用头插法插入lastRun之前的所有节点
                   HashEntry<K,V> n = newTable[k]; 
                   newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
                    }
                  }
                    }
                }
                //求出node节点扩容后哈希的位置
                int nodeIndex = node.hash & sizeMask; // add the new node
                //将哈希的位置设为新表中的头结点
                node.setNext(newTable[nodeIndex]);
                newTable[nodeIndex] = node;
                //更新table为扩容后的数组
                table = newTable;
            }

*  **举例说明：**（建议对照源码 看例子的步骤）
    
    假设扩容前的oldTable的长度oldCapacity为4，则扩容后的长度newCapacity为8。如下图所示  
    假设oldTable的table\[0\]下的链表的哈希值如下：（由index = hash & （oldCapacity-1）可知，扩容之前，这四个节点都在0号下标的位置）  
    ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70]  
    根据源码：  
    **sizeMask** = 8-1 = 7  
    **外层for循环**遍历旧的数组：  
    e为头结点，且不为空， 得到头结点的next节点  
    计算出扩容后头结点在新表重哈希的位置：**idx** = e.hash & sizeMask = 16 & 7 = 0  
    next！=null，所以if语句跳过，直接进入else：将头结点赋给lastRun  
    将头结点在新表里重哈希的位置0赋给**lastIdx**  
    **中层for循环**从头结点的next节点开始遍历，条件是**last！= null**，步进是每次的last更新为其next节点  
    **第①次循环**  
    计算k的值：last.hash & sizeMask = 4 & 7 = 4  
    k (4)!= lastIdx(0), 更新lastIdx = 4， 更新lastRun的节点表示  
    **第②次循环**  
    计算k的值：last.hash & sizeMask =8 & 7 = 0;  
    k (0)!= lastIdx(4), 更新lastIdx = 0， 更新lastRun的节点表示  
    **第③次循环**  
    计算k的值：last.hash & sizeMask = 32 & 7 = 0  
    k (0)= lastIdx(0), 不进入if语句，  
    步进：last = last.next ，此时为null，所以for循环结束  
    此时的lastIdx为0；lastRun表示的节点为hash=8的节点。  
    其实中层for循环就是为了寻找第一个所有的next节点在扩容后index都保持不变的节点  
    将lastRun节点添加到扩容后新表的头结点的位置，因为其next域不变，所以其后面的节点会跟随当前节点一起添加到头结点的位置
    
    **最后的for循环**为了将头结点到lastRun节点的内容插入到新创建的节点中  
    创建一个节点p，为未扩容的头结点，条件是 节点p不等于lastRun节点，步进是每次更新p为其next节点  
    通过头结点的哈希值和sizeMask求出新创节点的位置 k = 16 & 7 = 0；  
    用头插法将当前节点插入到0号位置，直到p节点=lastRun。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQxMzg0MzUx_size_16_color_FFFFFF_t_70]: /images/20210923/c63b86754b93475a8f265cba78c6b32f.png