10、ConCurrentHashMap源码面试大全

前言

一般的面试官会接着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;
}
注意:TreeBin中维护了一个读写锁,强制writer (持有bin锁的写程序) 要等待reader (不持有bin锁的写程序)完成树结构的重组操作。

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流程图

&nbsp;

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()方法重新调整节点位置;
&nbsp;
2、 新增节点之后,会调用addCount()方法将元素个数+1,并检查是否需要进行扩容,当数组元素个数达到扩容阈值sizeCtl时,会触发transfer()方法,对数组进行两倍扩容,进而重新调整节点的位置;
&nbsp;

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

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

putVal()方法中,

1、 不存在hash冲突时,通过判断数组位置链表头节点或红黑树根节点key的hash值是否为-1来确定table数组是否正在扩容中,如果hash值为-1表示table数组正在被其他线程扩容,当前线程会加入到扩容线程大军帮助一起扩容;
2、 存在hash冲突时,也是通过判断数组位置的节点hash值是否大于等于0(即是否为负数),判断当前节点是否为正常节点,即不是被扩容/迁移中的节点;大于等于0表示正常节点;
3、 此外sizeCtl为负值(-(1+n))时,表示正有n个线程正在进行扩容;
&nbsp;

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。
&nbsp;
假设有两个线程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,第二线程无法参与扩容。

&nbsp;

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节点(标志这个这个位置已经处理过了)。

链表的数据迁移过程:
&nbsp;

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节点(标志这个这个位置已经处理过了)。

红黑树迁移过程:
&nbsp;

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

因为数组初始化时,sizeCtl被设置为了-1,所以1的那个位置被占了,所以从2开始计算。
&nbsp;

  • 在调用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://www.feiz.vip/?p=3374

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

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

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

1)无线程竞争时:
&nbsp;

2)有线程竞争CAS修改同一counterCells下标位置的值:
&nbsp;

addCount()相关源码分析以及更多内容参考https://www.feiz.vip/?p=3374

另外在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://www.feiz.vip/?p=3354

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

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

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

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

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

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