【JUC并发编程】 10 ConCurrentHashMap源码面试大全

喜欢ヅ旅行 2023-10-01 18:18 9阅读 0赞

#### 文章目录 ####

*   *  前言
     *  1. 面试官：多线程环境下如何安全的使用Map结构？
     *  2. 面试官：JDK1.7 与 JDK1.8 中ConcurrentHashMap 的区别？
     *  3. 面试官：ConcurrentHashMap中变量使用final和volatile修饰的作用？
     *  4. 面试官：在多线程场景下，如何保证插入数据线程安全？
     *   *  1、put流程图
         *  2、put源码
     *  5. 哪些情况下，会触发扩容⾏为？
     *  6. 在多线程场景下，当发⽣哈希冲撞的时候，如何知道table数组正在扩容中？
     *  7. 在多线程场景下，它是如何进⾏扩容的？
     *  即 8. ConcurrentHashMap是如何对旧数据进⾏迁移的？
     *   *  1、针对普通链表节点
         *  2、针对红黑树节点
     *  9. 为什么计算总参与扩容操作线程数的时候，是从2开始的？为什么不从1开始计算？
     *  10. 扩容期间在未迁移到的hash桶插入数据会发生什么？
     *  11. ConcurrentHashMap是如何计算拥有的kv总量？
     *  12. CounterCell数组何时会扩容？扩容的原因是什么？
     *  13. ConcurrentHashMap的get方法是否要加锁，为什么？
     *  14. 正在迁移的hash桶遇到 get 操作会发生什么？
     *  15. ConcurrentHashMap迭代器是强一致性还是弱一致性？HashMap呢？

### 前言 ###

一般的面试官会接着HashMap的并发安全问题，聊到ConCurrentHashMap；接着一顿连环炮：

1.  多线程环境下如何安全的使用Map结构？
2.  ConcurrentHashMap1.7和1.8的区别？
3.  ConcurrentHashMap中变量使用final和volatile修饰的作用？
4.  在多线程场景下，如何保证插入数据线程安全？
5.  哪些情况下，会触发扩容⾏为呢？
6.  在多线程场景下，当发⽣哈希冲撞的时候，如何知道table数组正在扩容中？
7.  在多线程场景下，它是如何进⾏扩容的？
8.  ConcurrentHashMap是如何对旧数据进⾏迁移的？
9.  为什么计算总参与扩容操作线程数的时候，是从2开始的？为什么不从1开始计算？
10. 扩容期间在未迁移到的hash桶插入数据会发生什么？
11. ConcurrentHashMap是如何计算拥有的kv总量？
12. CounterCell数组何时会扩容？扩容的原因是什么？  
    16. 聊一下探针哈希值的作用？  
    17. 探针哈希值和map里使用的哈希值的区别什么？  
    18. 标注CounterCell的注解`@sun.misc.Contended`的作用是什么？  
    19. 单独使用一个缓存行有什么作用？  
    20. Java8之前避免伪共享的方案是什么？  
    21. @sun.misc.Contended有什么适用场景？
13. ConcurrentHashMap的get方法是否要加锁，为什么？
14. 正在迁移的hash桶遇到 get 操作会发生什么？
15. ConcurrentHashMap迭代器是强一致性还是弱一致性？HashMap呢？

### 1. 面试官：多线程环境下如何安全的使用Map结构？ ###

要从线程不安全的HashMap开始往ConCurrentHashMap过度了呀！这里一般会有三种方式：

*  使用Collections.synchronizedMap()方法对HashMap的所有方法加全表锁；不过在竞争激烈的多线程环境下性能非常差、不推荐使用。
 *  使用HashTable替代HashMap，HashTable内部使用针对get、put、remove等操作均采用同步方法实现，即给整个Hash表加一个全表锁，任何时候只能由一个线程访问或操作对象；同样在竞争激烈的多线程环境下性能非常差、不推荐使用。
 *  使用线程安全的ConCurrentHashMap；  
    1> 比如Spring框架底层的数据结构（比如`DefaultSingletonBeanRegistry类中的一级缓存、二级缓存`）、  
    2> Nacos / Eureka框架的服务注册信息、  
    3> RocketMQ框架中group和消费者/生产者对应关系、消费队列的Offset信息等 就是使用的ConCurrentHashMap；  
    4> 我以前做的XX项目中也使用到ConCurrentHashMap来保存热点配置信息（这里则表示，我即研究过框架源码 又在实际项目中使用过）。  
    不过注意哈，如果对Spring源码 / Nacos源码 / Eureka源码 / RocketMQ源码不是特别了解，换成自己了解的源码（1-2个即可）；万一面试官顺势走到Spring源码…，等于是搬起石头砸了自己的脚。

**面试官OS；** 走到这里，针对下一个问题面试官可能就出现纠结了；你小子说了那么多源码、是想引我过去问源码嘛？我先摁着你ConCurrentHashMap源码一堆怼，先看看你基础掌握的怎么样，时间够就再问你框架、否则答的好的话框架部分先交给后面的面试官（面试评价里记你一记）。

### 2. 面试官：JDK1.7 与 JDK1.8 中ConcurrentHashMap 的区别？ ###

好嘛！这个我会，网上一大堆。我就分几个角度来概述，表现一下总结能力。

1.  **从数据结构上**：  
    1> JDK1.7 ConCurrentHashMap使用Segment数组 + 键值对主体HashEntry，一个Segment中又包含一个HashEntry数组，每个HashEntry是一个链表结构的元素；  
    2> JDK1.8 ConCurrentHashMap改用数组、链表、红黑树相结合的数据结构。
2.  **从线程安全机制上：**  
    1> JDK1.7 采用 Segment 的分段锁机制实现线程安全，其中 Segment 继承自 ReentrantLock ；  
    2> JDK1.8 采用CAS+synchronized 保证线程安全；对数组 / 链表 / 红黑树节点数据修改时使用CAS，操作链表 / 红黑树时加Synchronized锁。
3.  **从锁的粒度上：**  
    1> JDK1.7 是对需要进行数据操作的 Segment 加锁，也就是对一段HashEntry数组加锁；  
    2> JDK1.8 则是对每个数组元素Node加锁；相较于JDK1.7而言锁更加细粒度，并发度更高。
4.  **从查询时间复杂度上：**  
    1> JDK1.7当发生Hash冲突时一直往链表尾部追加，遍历链表的时间复杂度为O(n)；  
    2> JDK1.8当链表节点数量大于 8（且数据总量大于等于 64）时，会将链表转化为红黑树进行存储；此时遍历红黑树的时间复杂度为O(logn)。

**面试官OS；** 小伙子总结的还可以，下面我就看看你是不是真的看过源码；

### 3. 面试官：ConcurrentHashMap中变量使用final和volatile修饰的作用？ ###

嘿嘿嘿，从变量开始问起嘛，咱研究过呀。

*  final域确保变量的初始化安全性，初始化安全性让不可变对象不需要同步就可以被自由的访问和共享。
 *  volatile关键字保证某个变量内存的改变对其他线程即时可见；再配合CAS可以实现无锁并发操作。  
    **比如：** Node的元素val和指针next使用volatile修饰，因此在多线程环境下线程A修改Node节点的val或者新增节点对线程B是可见的。以及控制扩容的sizeCtl、存放数据的table、扩容用的nextTable。
 *  另外，树节点TreeNode中没加volatile关键字，因为操作树节点时，一定加了synchronized关键字。
 *  而get()方法可以无锁，是由于Node的元素val和指针next都是volatile修饰的，在多线程环境下线程A修改节点的val或者新增节点对线程B是可见的。

**面试官：** 那么volatile修饰数组有什么效果？  
**秃秃：****其实就是为了使得Node数组table在扩容的时候对其他线程具有可见性.**

**面试官OS；**小伙子，研究挺多呀，还没问倒你，再来再来。

**PS：附相关变量解释；额外注意一下sizeCtl。**

transient volatile Node<K, V>[] table;
    
    // 扩容时使用的数组
    private transient volatile Node<K, V>[] nextTable;
    
    // 基本计数器值，主要在没有线程竞争时使用，也可作为表初始化竞争期间的后备。其通过CAS更新
    private transient volatile long baseCount;
    
    /**
     * 用来表示table初始化 或 扩容，默认为0；
     * 负值表示正在初始化 / 扩容
     *     -1：表示table数组正在被别的线程初始化；
     *     -(1+n)：n表示正在进行扩容的线程数量；
     * 当table数组初始化或者扩容完毕后，sizeCtl表示扩容阈值。
     */
    private transient volatile int sizeCtl;
    
    /**
     * 扩容时时要拆分的下一个表索引（加一）。
     */
    private transient volatile int transferIndex;
    
    /**
     * Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
     * 调整大小 / 创建CounterCell时，使用的自旋锁（通过CAS锁定）。
     * 0：空闲 1：繁忙
     */
    private transient volatile int cellsBusy;
    
    /**
     * 计数器单元格表
     * 最初大小是2，如果线程较多，那么为了避免冲突，会进行2倍扩容。
     * 最终计算ConcurrentHashMap中所有元素的时候，其中一步，就是会统计counterCells数组中所有元素的value值之和。
     */
    private transient volatile CounterCell[] counterCells;
    
    // 数据节点，链表结构
    static class Node<K,V> implements Map.Entry<K,V> {
        
    
        final int hash;
        final K key;
        //val和next都会在扩容时发生变化，所以加上volatile来保持可见性和禁止重排序
        volatile V val;
        volatile Node<K,V> next;
    }
    
    // 提供转换黑红树的一些条件和锁的控制
    static final class TreeBin<K,V> extends Node<K,V> {
        
    
        //指向TreeNode列表和根节点
    
        TreeNode<K,V> root;
    
        volatile TreeNode<K,V> first;
    
        volatile Thread waiter;
    
        volatile int lockState;
    
        // 读写锁状态
    
        static final int WRITER = 1; // 获取写锁的状态
        static final int WAITER = 2; // 等待写锁的状态
        static final int READER = 4; // 增加数据时读锁的状态
    }
    
    // 树节点
    static final class TreeNode<K, V> extends Node<K, V> {
        
        TreeNode<K, V> parent;  // red-black tree links
        TreeNode<K, V> left;
        TreeNode<K, V> right;
        TreeNode<K, V> prev;    // needed to unlink next upon deletion
        boolean red;
    }

<table> 
 <tbody> 
  <tr> 
   <td> 注意：TreeBin中维护了一个读写锁，强制writer (持有bin锁的写程序) 要等待reader (不持有bin锁的写程序)完成树结构的重组操作。</td> 
  </tr> 
 </tbody> 
</table>

### 4. 面试官：在多线程场景下，如何保证插入数据线程安全？ ###

好嘛，这等于是在问我ConCurrentHashMap的put流程呀，单纯的只聊如何加锁的，有点浪费机会了； 我们要尽可能的表现自己，遇到会的题一定要多聊聊。

ConCurrentHashMap的put流程大致上分为一层校验和两个阶段。

首先，校验key和value不能为null，否者会抛出空指针异常。检验通过之后会通过`使用异或和与操作`的扰动函数计算key的hash值。

其次，两个阶段分别为：

*  第一阶段对table数组做无限循环进行插入KV键值对操作，其中包含四种情况；
 *  第二阶段将ConcurrentHashMap中存储的KV键值对总数+1。

**将第一阶段的四种情况拆开来看：**

**part1>** 第一种情况：table数组需要被创建时，即table数组为null 或 长度为0时，则**懒汉式初始化数组（第一次put时才初始化）**。  
由于可能存在多个线程并发的初始化数组，所以首先**初始化数组要保证线程安全**：

*  `initTable()`中while死循环table数组为空的场景：
 *  **如果sizeCtl < 0** 表示有其他线程正在初始化数组，此时使用 Thread.yield() 将当前线程由运行态进入到就绪态，让出CPU资源；即当前线程在外面自旋，直到table初始化完毕才能跳出while循环。
 *  否则，如果通过**CAS成功将sizeCtl设置为-1**，则当前线程进行数组的初始化，并将sizeCtl设置为扩容阈值（默认为12）。
 *  CAS竞争失败的线程；同样在外面自旋，直到table数组初始化完毕才能跳出While循环。
 *  **<1>总的来说`initTable()`初始化数组的线程安全性是<1>通过一个volatile修饰的变量sizeCtl 结合 CAS来实现的**。

**part2>** 第二种情况：table数组已经被创建，并且寻址后的数组位置没有被占用。

*  因为table数组是线程间可见的，但数组元素不是。所以**采用volatile读的方式来读取数组中的元素**，保证每次拿到的数据都是最新的。
 *  然后直接**基于主内存地址，通过CAS**将创建的Node节点插入到当前位置；CAS失败则进入下一次table数组循环。

**part3>** 第三种情况：寻址到的位置正在进行扩容/迁移操作，即：数组位置的hash值 = MOVED = -1；

*  将当前线程加入到扩容/迁移大军，通过执行`helpTransfer()`方法来协助其他线程进行扩容/迁移操作。

**part4>** 第四种情况：出现hash冲突的场景；

*  首先只针对单个数组元素`加synchronized锁`（而不是对整个数组加锁），确保线程安全的将节点插入到链表 或 红黑树中；
 *  **其次这种情况大致分为三个部分**：

1.  遍历链表，将节点插入到链表中；如果链表中存在相同key的节点，则根据onlyIfAbsent判断是否替换value值；否者将新Node放入到链表尾部。
2.  如果节点类型是红黑树节点，将节点插入到红黑树中；如果找到相同key的节点，则根据onlyIfAbsent判断是否替换value值。
3.  如果链表长度大于8，则转换元素存储类型，即链表转红黑树。

**总的来说针对第一阶段（除数组初始化）：**

*  **<2>当不存在hash冲突时，采用基于主内存的volatile读来读取数组元素、采用CAS确保存储数据的线程安全性**；
 *  **<3>当存在hash冲突时，针对单个数组位置加synchronized锁；链表转红黑树时也是对单个数组位置加synchronized锁**；
 *  **<4>帮助其他线程进行数据迁移/扩容时，通过对volatile修饰的变量nextTable、sizeCtl进行volatile读确保线程安全性**。

**第二阶段调用addCount()方法将ConcurrentHashMap中存储的KV键值对总数+1。**

*  **<5>通过对volatile修饰的变量baseCount、sizeCtl进行CAS，对CounterCell进行CAS确保对数量修改的线程安全性**。

PS：**附流程图 + putVal()方法主流程源码**

#### 1、put流程图 ####

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

#### 2、put源码 ####

public V put(K key, V value) {
        
        return putVal(key, value, false);
    }
    
    /**
     * Implementation for put and putIfAbsent
     */
    final V putVal(K key, V value, boolean onlyIfAbsent) {
        
        // key和value都不允许为空，因为如果为空的话，线程不安全，会出现数据错乱。
        if (key == null || value == null) throw new NullPointerException();
        // 使用扰动函数计算key的hash值
        int hash = spread(key.hashCode());
        int binCount = 0;
        // phase1：对数组做无限循环，其中包含四种情况的判断
        for (Node<K, V>[] tab = table; ; ) {
        
            Node<K, V> f;
            int n, i, fh;
    
            /**
             * part1, table数组需要被创建，即table数组为null 或 长度为0，则懒汉式初始化数组
             */
            if (tab == null || (n = tab.length) == 0)
                // todo 如何保证初始化数组是线程安全的？
                tab = initTable();
    
            /**
             * part2，table数组已经被创建，并且寻址后的数组位置没有被占用。
             * 因为table数组是线程间可见的，但数组元素不是。所以采用volatile读的方式来读取数组中的元素，保证每次拿到的数据都是最新的。
             * tabAt(tab, i = (n - 1) & hash)) 相当于 table[i]
             */
            else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
        
                // 直接基于主内存地址，创建Node节点 并 通过CAS将其插入到当前位置；CAS失败则进入下一次table数组循环
                if (casTabAt(tab, i, null,
                        new Node<K, V>(hash, key, value, null)))
                    break;                   // no lock when adding to empty bin
            }
    
            // part3: 寻址到的位置正在进行扩容/迁移操作，即：数组位置的hash值 = MOVED = -1，
            else if ((fh = f.hash) == MOVED)
                // 当前线程加入到扩容/迁移大军，帮助数组进行扩容/迁移。
                tab = helpTransfer(tab, f);
    
                // part4：其他情况，即：hash冲突的场景
            else {
        
                V oldVal = null;
                // 只针对单个数组元素采用synchronized锁（而不是对整个数组加锁），确保线程安全的将节点插入到链表 或 红黑树中
                synchronized (f) {
        
                    if (tabAt(tab, i) == f) {
        
                        // 当前节点的hash值大于0，表明该节点是正常节点，不是被扩容/迁移中的节点。
                        if (fh >= 0) {
        
                            binCount = 1;
                            // phase1: 遍历链表，将节点插入到链表中
                            for (Node<K, V> e = f; ; ++binCount) {
        
                                K ek;
                                // 待插入的key与已有链表节点f的key相同
                                if (e.hash == hash &&
                                        ((ek = e.key) == key ||
                                                (ek != null && key.equals(ek)))) {
        
                                    oldVal = e.val;
                                    // 如果onlyIfAbsent为false对value值进行替换
                                    if (!onlyIfAbsent)
                                        e.val = value;
                                    break;
                                }
                                Node<K, V> pred = e;
                                // 如果链表中没有key和待插入的key相同，封装新节点插入到链表的尾部。
                                if ((e = e.next) == null) {
        
                                    pred.next = new Node<K, V>(hash, key,
                                            value, null);
                                    break;
                                }
                            }
                        }
                        /**
                         * 红黑树的操作
                         *
                         * phase2: 如果节点类型是红黑树节点，将节点插入到红黑树中，如果找到相同key的节点，则根据onlyIfAbsent判断是否替换value值
                         */
                        else if (f instanceof TreeBin) {
        
                            Node<K, V> p;
                            binCount = 2;
                            if ((p = ((TreeBin<K, V>) f).putTreeVal(hash, key,
                                    value)) != null) {
        
                                oldVal = p.val;
                                if (!onlyIfAbsent)
                                    p.val = value;
                            }
                        }
                    }
                }
                /**
                 * phase3: 转换元素存储类型，即：链表转红黑树的操作
                 */
                if (binCount != 0) {
        
                    // 如果链表的个数大于等于8，则将链表转为红黑树
                    if (binCount >= TREEIFY_THRESHOLD)
                        treeifyBin(tab, i);
                    // 如果存在旧的value值，则将旧的value值返回
                    if (oldVal != null)
                        return oldVal;
                    break;
                }
            }
        }
        // phase2：将ConcurrentHashMap中存储的KV键值对总数+1
        addCount(1L, binCount);
        return null;
    }

**面试官OS：** 这小伙子是真看过源码，还分阶段总结，不错不错，我再探探你对ConCurrentHashMap的理解有多深。

### 5. 哪些情况下，会触发扩容⾏为？ ###

当往ConCurrentHashMap中成功插入一个key/value节点时，有可能触发扩容动作，其中包括两种情况：

1.  如果在新增节点之后，链表的长度达到了阈值8，会调用`treeifyBin(tab, i)`方法将链表转为红黑树；不过在`treeifyBin(tab, i)`方法中会先对数组长度进行判断，如果数组长度 小于 64，则会调用`tryPresize(n << 1)`方法对数组进行两倍扩容，进而通过`transfer()`方法重新调整节点位置。  
    ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16]
2.  新增节点之后，会调用`addCount()`方法将元素个数+1，并检查是否需要进行扩容，当数组元素个数达到扩容阈值`sizeCtl`时，会触发`transfer()`方法，对数组进行两倍扩容，进而重新调整节点的位置。  
    ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16 1]

**面试官OS：** 这个等于是在上一题的基础上从扩容的维度重新总结了一遍，细节点扣的不错。

### 6. 在多线程场景下，当发⽣哈希冲撞的时候，如何知道table数组正在扩容中？ ###

在`putVal()`方法中，

1.  不存在hash冲突时，通过判断数组位置链表头节点 或 红黑树根节点 key的hash值是否为-1来确定table数组是否正在扩容中，如果hash值为-1表示table数组正在被其他线程扩容，当前线程会加入到扩容线程大军帮助一起扩容；
2.  存在hash冲突时，也是通过判断数组位置的节点hash值是否大于等于0（即是否为负数），判断当前节点是否为正常节点，即不是被扩容/迁移中的节点；大于等于0表示正常节点。
3.  此外sizeCtl为负值（`-(1 + n)`）时，表示正有n个线程正在进行扩容。  
    ![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16 2]

### 7. 在多线程场景下，它是如何进⾏扩容的？ ###

**秃秃：**我丢，硬核起来了呀；嘿嘿嘿，这个我也会。

当第一个线程开始对ConCurrentHashMap进行扩容时，直接进入到`transfer(tab, null)`方法进行扩容；后面的线程全部进入到`transfer(tab, nextTab)`方法加入扩容线程大军，协助其他线程进行扩容操作。

其他线程想协助第一个线程扩容有很多条件限制，比如：

*  全局变量`nextTable`不为空、当前节点类型必须是`ForwardingNode`，以表明数组正在迁移中；
 *  根据全局变量`transferIndex`判断是否还允许协助扩容线程的参与，如果`transferIndex <= 0`则不允许。
 *  另外：出现并发扩容时，全局变量transferIndex用来给各个线程分配的数组槽位个数。

假如允许协助扩容线程的加入，首先那通过CAS将sizeCtl 的低16位 +1，即将扩容总线程数 +1；然后调用`transfer(tab, nextTab)`方法进行真正的扩容操作。

**transfer()方法大致可以分为三个阶段，分别做的是：**

1.  计算扩容时每个扩容线程的步长；
2.  扩容：如果方法入参nextTab为空，则创建一个原2倍长度的新数组；
3.  在无限循环中做数据迁移。

**第一阶段：根据计算机NCPU的配置计算每个扩容线程的步长；**  
**计算规则为：** 如果NCPU大于1，则stride=n/8/NCPU，否则stride=n；但是，如果计算出来的stride小于16，那么stride就被赋值为16；一般情况下stride都为16。  
![在这里插入图片描述][6498c7e8e32643a391a55a626cbc0d96.png]  
假设有两个线程A、B通知执行transfer，入参的tab为32，nextTable=null；则

*  n = tab.length = 32
 *  NCPU = 8 （每个人的电脑不一样，大多都为8）
 *  最后stride = 32 / 8 / 8 = 0.5，由于0.5<16，所以stride=16。

**第二阶段：若方法入参nextTab为空，则创建一个原2倍长度的新数组；**  
并将创建的新数组赋值给全局变量nextTable，将旧数组容量n赋值给全局变量transferIndex。

**第三阶段：在无限循环中做数据迁移**  
数据迁移时有分为两个部分：第一个部分计算当前线程需要转移的节点范围，第二部分进行数据迁移。

**part1> 首先在无限循环中计算当前线程需要迁移的节点范围，主要做两件事：**

*  对当前要迁移的数组下标进行–操作，表示一步一步往前遍历；
 *  transferIndex表示下一个待迁移的边界，如果是多线程执行扩容，会在CAS赋值transferIndex的时候发生碰撞，而transferIndex是volatile线程共享的。每个线程迁移数据的范围是从bound到i，迁移长度为stride。

**假设旧数组容量为32，stride为16：**

*  则第一个线程进入的时候，会将全局变量transferIndex赋值为16，表示下一个待迁移的边界为16；线程私有的bound为16，i为 32-1=31；即第一个线程的迁移范围为\[16，31\]。
 *  第二线程在第一个线程执行完一轮扩容操作之前进入时，即transferIndex=16时，会将全局变量transferIndex赋值为0，表示下一个待迁移的边界为0（即不再允许其他线程参与扩容、当前扩容个是最后一轮）；线程私有的bound为0，i为 16-1=15；即第二个线程的迁移范围为\[0，15\]。
 *  如果第二个线程要进入的时候，第一个线程已经做完了一轮扩容，开始了第二轮扩容，则此时的transferIndex为0，第二线程无法参与扩容。

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

**part2> 然后再将待转移节点范围中的每个节点的数据进行转移（这里分为四种情况）：**

**case1）扩容的活儿都分配完毕了：**  
     1、如果数据全部扩容完了，则更新table的引用为nextTab，设置数组的扩容阈值sizeCtl为0.75\*2n（n为旧数组容量）。  
     2、否则表示当前线程不需要再执行扩容迁移任务了，将总参与线程数减一；

**case2）如果【旧table】下标i处没有节点，则不需要进行扩容迁移操作：**  
     直接通过CAS将`为空值的ForwardingNode节点`赋值到【旧table】的位置i，表示该位置已经处理过了，不需要在执行迁移操作了。

**case3）【旧数组】下标为i的这个位置已经被处理过了：**  
     则重新计算当前线程需要迁移的节点范围。

**case4）执行数据迁移操作（同第8. 个问题）：**

### 即 8. ConcurrentHashMap是如何对旧数据进⾏迁移的？ ###

首先，对在数组下标i的元素加synchronized锁；其次定义两个Node变量ln和hn，分别永用来存储扩容后低位（原数组下标）的node元素、高位（原数组下标 + 原数组容量）的node元素；然后针对普通链表节点和红黑树节点采用不同的迁移方式。

#### 1、针对普通链表节点 ####

1）首先通过将节点的hash值 与 旧数组容量n做`按位与运算`（int runBit = fh & n;）得出runBit的值；如果runBit=0，表示元素f在低位，否者在高位。

2）接着遍历链表找到lastRun节点，lastRun节点表示`从lastRun节点开始其后的所有节点都在高位或低位链表`；同步将lastRun节点的runBit计算出来。**如果runBit ==0（即从lastRun节点开始其后的所有节点都在低位链表上），则令ln = lastRun, hn = null；**否者令 hn = lastRun, ln = null。  
3）从链表头结点遍历到lastRun节点（lastRun节点不遍历），通过按位与运算 计算出当前节点应该在高位还是低位，然后通过**头插法**插入到链表中。  
4）最后直接基于主内存地址，通过volatile写操作将高位链表hn、低位链表ln写入到扩容后的数组nextTable，将旧数组位置赋值为空的ForwardingNode节点（标志这个这个位置已经处理过了）。

**链表的数据迁移过程：**  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16 4]

#### 2、针对红黑树节点 ####

1）首先构造树节点lo和hi，通过遍历红黑树中的节点，根据hash & n算法，将节点分别插入到lo和hi为头的TreeNode链表中  
2）然后根据lo和hi TreeNode链表中的元素个数分别生成对应ln和hn节点；  
3）ln和hn的生成逻辑一致，以ln节点为例：

*  如果lo链表的元素个数小于等于6，则通过`untreeify()`方法把TreeNode树节点链表转化成Node普通节点链表；
 *  否则先判断hi链表中的元素个数是否等于0：
 *   *  如果等于0，表示lo链表中包含了所有原始节点，则设置原始红黑树给ln（即红黑树结构不需要迁移）；
 *   *  否则根据lo 树节点链表重新构造红黑树。

4）最后同样直接基于主内存地址，通过volatile写操作将高位hn、低位ln写入到扩容后的数组nextTable，将旧数组位置赋值为空的ForwardingNode节点（标志这个这个位置已经处理过了）。

**红黑树迁移过程：**  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16 5]

### 9. 为什么计算总参与扩容操作线程数的时候，是从2开始的？为什么不从1开始计算？ ###

因为数组初始化时，sizeCtl被设置为了-1，所以1的那个位置被占了，所以从2开始计算。  
![在这里插入图片描述][1dc0e3fdc63048b9b11ccbf95db06b85.png]

*  在调用`treeifyBin()`方法进行链表转红黑树时，如果数组的容量 小于 64，则会调用tryPresize()方法对数组进行扩容，其中会调用上图代码，将sizeCtl的低16位进行 + 2操作，表明数组有一个线程正在进行扩容；
 *  在调用`addCount()`方法将ConcurrentHashMap中存储的KV键值对总数+1，如果需要扩容，也会调用上图代码…

### 10. 扩容期间在未迁移到的hash桶插入数据会发生什么？ ###

*  只要插入的位置扩容线程还未迁移到，就可以直接插入；
 *  如果当前要插入的位置正在迁移，会帮助其他扩容线程一起扩容直到扩容结束，然后再加synchronized锁执行插入操作。

### 11. ConcurrentHashMap是如何计算拥有的kv总量？ ###

*  对于size的计算，在扩容和addCount()方法已经有所处理了；
 *  JDK1.8 ConCurrentHashMap的大小 size 通过 `baseCount` 和 `counterCells` 两个变量维护：
    
    1.  在没有并发的情况下，使用一个`volatile修饰`的 `baseCount` 变量即可；
    2.  当有并发时，CAS `修改 baseCount 失败后`，会`使用 CounterCell 类`，即 创建一个CounterCell对象，设置其`volatile修饰`的 `value` 属性为 1，并将其放在ConterCells数组的随机位置；
 *  最终在sumCount()方法中通过累加 baseCount和CounterCells数组里每个CounterCell的值 得出Map的总大小Size。
 *  然而 返回的值是一个估计值；如果有并发插入或者删除操作，和实际的数量可能有所不同。
 *  另外`size()方法的最大值`是 `Integer` 类型的`最大值`，而 Map 的 size 有可能超过 Integer.MAX\_VALUE，所以JAVA8 `建议使用 mappingCount()`。

**源码分析以及更多内容参考**：[https://blog.csdn.net/Saintmm/article/details/121311201][https_blog.csdn.net_Saintmm_article_details_121311201]。

### 12. CounterCell数组何时会扩容？扩容的原因是什么？ ###

多线程之间设置CounterCell的value值时发生碰撞，那么扩展CounterCell的长度，以减少多线程竞争 / 碰撞的次数；（即：后来的线程CAS失败，由其进行CounterCell数组的扩容）

此外：我们通过两张图分别介绍一下：有线程竞争CAS修改同一counterCells下标位置的值、和无线程竞争时的场景：

**1）无线程竞争时：**  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16 6]

**2）有线程竞争CAS修改同一counterCells下标位置的值：**  
![在这里插入图片描述][watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16 7]

**addCount()相关源码分析以及更多内容参考**：[https://blog.csdn.net/Saintmm/article/details/121311201][https_blog.csdn.net_Saintmm_article_details_121311201]。

**另外在addCount()中可能还可能聊到到其他问题：**

**面试官：聊一下探针哈希值的作用？**  
**秃秃：**探针哈希值的作用是哈希线程，将线程和数组中的不同元素对应起来，尽量避免线程争用同一数组元素。

**面试官：探针哈希值和map里使用的哈希值的区别什么？**  
**秃秃：**当线程发生数组元素争用后，可以改变线程的探针哈希值，让线程去使用另一个数组元素，而map中key对象的哈希值，由于有定位value的需求，所以它是一定不能变的。

**面试官：标注CounterCell的注解`@sun.misc.Contended`的作用是什么？**

**秃秃：**`@sun.misc.Contended`是Java8新增的一个注解，对某个字段加上该注解 则表示该字段会单独占用一个缓存行（Cache Line）；

*  缓存行是指CPU缓存（L1、L2、L3）的存储单元，常见的缓存行大小为64字节；
 *  JVM添加-XX:-RestrictContended参数后@sun.misc.Contended注解才有效。

**面试官：单独使用一个缓存行有什么作用？**

**秃秃：**避免伪共享；

*  为了提高读取速度，每个CPU都有自己的缓存，CPU读取数据后会存到自己的缓存里；并且为了节省空间，一个缓存行可能存储着多个变量，即**伪共享**。
 *  但是伪共享对于共享变量，会造成性能问题，比如：
    
    1.  当一个CPU要修改共享变量A时会先锁定自己缓存里 A所在的缓存行，并且把其他CPU缓存上相关的缓存行设置为无效。
    2.  但如果被锁定或失效的缓存行里，还存储了其他不相干的变量B，其他线程此时就访问不了B。
    3.  或者由于缓存行失效需要重新从内存中读取加载到缓存里，也就造成了开销。
    4.  所以让共享变量A单独使用一个缓存行就不会影响到其他线程对其他共享变量的访问。

**面试官：Java8之前避免伪共享的方案是什么？**

**秃秃：**在Java8之前，是通过代码里手动添加属性的方式解决的，比如类A中有一个long类型的value；因为一个long占8个字节，所以再添加7个long属性就会变成64个字节，刚好是一个缓存行大小。

class A {
        
    	long value;
    	long p0, p1, p2, p3, p4, p5, p6;
    }

*  但是，Java7开始，JVM做优化时可能会把不用的变量给去掉，所以不推荐使用这种方案。

**面试官：@sun.misc.Contended有什么适用场景？**

**秃秃：**主要适用于会被频繁写的共享数据上。如果不是被频繁写的数据，那么CPU缓存行被锁的几率就不大，所以没必要使用；否则不仅占空间还会浪费CPU访问/操作数据的时间。

### 13. ConcurrentHashMap的get方法是否要加锁，为什么？ ###

1）java8中ConcurrentHashMap的`get()`操作`正常情况是不需要加锁`的，这也是它比其他并发集合，如hashtable、用Collections.synchronizedMap()包装的hashmap；效率高的原因之一。  
2）正常情况`get()`操作全程`不需要加锁`是因为：

> 1.  get()方法访问的大多数变量是`volatile关键字修饰`的，比如：Node.val、Node.next、count，volatile保证了其值的修改对其他线程的可见性。  
>     **即**：在多线程环境下线程A修改Node节点的val或者新增节点对线程B是可见的。
> 2.  像引用类型：数组`table`用volatile修饰，在`数组扩容`的时候就保证了其`引用的改变`对其他线程的可见性。

3）但是当节点是`红黑树`的时候，如果树正在`变色旋转`并且要`查询的值不是红黑树的头节点`，会加一个`读写锁`。  
4）另外其`迭代器iterator是弱一致性`的，因为在迭代过程中可以向map中添加元素；而`HashMap是强一致性`的。

**源码分析以及更多内容参考**：[https://blog.csdn.net/Saintmm/article/details/121281918][https_blog.csdn.net_Saintmm_article_details_121281918]。

### 14. 正在迁移的hash桶遇到 get 操作会发生什么？ ###

在扩容过程期间形成的 hn 和 ln链 使用的是复制引用的方式，也就是说 ln 和 hn 链是复制出来的，而非直接在旧数组的链表 / 红黑树上操作；所以旧数组 hash 桶上的链表 / 红黑树并没有受到影响。

因此从迁移开始 到 结束 这段时间都是可以正常访问旧数组 hash 桶上面的链表 / 红黑树；迁移结束后放旧数组位置上赋值为fwd，往后的访问请求会直接转发到扩容后的数组去了。

### 15. ConcurrentHashMap迭代器是强一致性还是弱一致性？HashMap呢？ ###

ConcurrentHashMap 的迭代器创建后，就会按照哈希表结构遍历每个元素，但在遍历过程中，内部元素可能会发生变化，但不会抛出fail-fast异常。如果变化的数据在已遍历过的部分，迭代器就不会反映出来，而如果变化的数据在未遍历过的部分，迭代器就会发现并反映出来，这就是弱一致性。

这样迭代器线程可以使用原来老的数据，而写线程也可以并发的完成改变，更重要的，这保证了多个线程并发执行的连续性和扩展性，是性能提升的关键。

PS：文中数据迁移的图片摘自：[https://blog.csdn.net/ZOKEKAI/article/details/90051567][https_blog.csdn.net_ZOKEKAI_article_details_90051567]

[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_18_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/39d53c59c0db41d2b786be4362850dcd.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA56eD5aS054ix5YGl6Lqr,size_18,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16]: https://img-blog.csdnimg.cn/105e77b0d7ff4fa4932efae2f207d3f4.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA56eD5aS054ix5YGl6Lqr,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16 1]: https://img-blog.csdnimg.cn/04db7ebd6c59427182d433691f3e5467.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA56eD5aS054ix5YGl6Lqr,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16 2]: https://img-blog.csdnimg.cn/56958846221f466ab87c475dfa929b0f.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA56eD5aS054ix5YGl6Lqr,size_20,color_FFFFFF,t_70,g_se,x_16
[6498c7e8e32643a391a55a626cbc0d96.png]: https://img-blog.csdnimg.cn/6498c7e8e32643a391a55a626cbc0d96.png
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16 3]: https://img-blog.csdnimg.cn/0e6e0dc7e1d34bd1be6fbb252b346438.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA56eD5aS054ix5YGl6Lqr,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16 4]: https://img-blog.csdnimg.cn/68f3d89fb7f34b2ca7683e7dc5c8079b.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA56eD5aS054ix5YGl6Lqr,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16 5]: https://img-blog.csdnimg.cn/3747abf0f02d4bd4ae40f2f9962be4ad.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA56eD5aS054ix5YGl6Lqr,size_20,color_FFFFFF,t_70,g_se,x_16
[1dc0e3fdc63048b9b11ccbf95db06b85.png]: https://img-blog.csdnimg.cn/1dc0e3fdc63048b9b11ccbf95db06b85.png
[https_blog.csdn.net_Saintmm_article_details_121311201]: https://blog.csdn.net/Saintmm/article/details/121311201
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16 6]: https://img-blog.csdnimg.cn/f0b6bea470784eaaa99c1c3e87ecdbb4.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA56eD5aS054ix5YGl6Lqr,size_20,color_FFFFFF,t_70,g_se,x_16
[watermark_type_d3F5LXplbmhlaQ_shadow_50_text_Q1NETiBA56eD5aS054ix5YGl6Lqr_size_20_color_FFFFFF_t_70_g_se_x_16 7]: https://img-blog.csdnimg.cn/b23f5ae18229463cb820e84512ad501a.png?x-oss-process=image/watermark,type_d3F5LXplbmhlaQ,shadow_50,text_Q1NETiBA56eD5aS054ix5YGl6Lqr,size_20,color_FFFFFF,t_70,g_se,x_16
[https_blog.csdn.net_Saintmm_article_details_121281918]: https://blog.csdn.net/Saintmm/article/details/121281918
[https_blog.csdn.net_ZOKEKAI_article_details_90051567]: https://blog.csdn.net/ZOKEKAI/article/details/90051567