1. 今日面试题

ConcurrentHashMap的底层原理是什么？

你知道ConcurrentHashMap是怎么统计大小的？

ConcurrentHashMap的读操作为什么不需要加锁？

.......

2. 题目剖析

壹哥在前面4篇文章中，给大家介绍了ConcurrentHashMap的通用功能、特点，以及JDK 7、8中ConcurrentHashMap的底层数据结构，还有ConcurrentHashMap中的核心属性等内容，文章链接如下：

高薪程序员&面试题精讲系列45之你熟悉ConcurrentHashMap吗？

高薪程序员&面试题精讲系列46之说说JDK7中ConcurrentHashMap的底层原理，有哪些数据结构

高薪程序员&面试题精讲系列47之说说JDK8中ConcurrentHashMap的底层原理，HashMap与ConcurrentHashMap有什么区别？

高薪程序员&面试题精讲系列48之说说JDK8中ConcurrentHashMap的sizeCtl是什么意思？最大容量、负载因子是多少？

高薪程序员&面试题精讲系列49之说说ConcurrentHashMap#put方法的源码及数据添加流程

从本文开始，壹哥给大家重点分析JDK 8中ConcurrentHashMap#size()方法的源码，重点讲解ConcurrentHashMap是如何进行统计集合中元素数量的，这一块也是咱们面试时的高频考点。

二. size()计算方法实现详解

1. size计算容量方法

分析完了以上这些重要的源码之后，面试官有时候还会问我们如何计算ConcurrentHashMap中到底存了多少条数据。对于ConcurrentHashMap来说，这个table里到底装了多少个数据元素，其实是个不确定的数量。因为我们不可能在调用size()方法的时候，像GC的“stop the world”一样让其他线程都停下来让你去统计，因此只能说这个数量是个估计值。对于这个估计值，ConcurrentHashMap也是大费周章才计算出来的。

2. 辅助定义

为了统计内部存储的元素个数，ConcurrentHashMap定义了一些变量和一个内部类。

/**
* A padded cell for distributing counts.  Adapted from LongAdder
* and Striped64.  See their internal docs for explanation.
*/
@sun.misc.Contended static final class CounterCell {
    volatile long value;
    CounterCell(long x) { 
        value = x; 
    }
}

/**
* 实际上保存的是hashmap中的元素个数，利用CAS锁进行更新。但它并不用返回当前hashmap的元素个数 
*/
private transient volatile long baseCount;
    
/**
* Spinlock (locked via CAS) used when resizing and/or creating CounterCells.
*/
private transient volatile int cellsBusy;

/**
* Table of counter cells. When non-null, size is a power of 2.
*/
private transient volatile CounterCell[] counterCells;

3. mappingCount与size方法

size()方法的作用是为我们返回哈希表中实际存在的键值对总数，mappingCount()方法与size()方法类似。 从Java工程师给出的注释来看，应该使用mappingCount代替size方法。但这两个方法都没有直接返回basecount，而是统计一个值，而这个值其实也是一个大概的数值，因此可能在统计的时候有其他线程正在执行插入或删除操作。

public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 :
                (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :(int)n);
}
    
public long mappingCount() {
        long n = sumCount();
        return (n < 0L) ? 0L : n; // ignore transient negative values
}

final long sumCount() {
    CounterCell[] as = counterCells; CounterCell a;
    long sum = baseCount;
    if (as != null) {
        for (int i = 0; i < as.length; ++i) {
            if ((a = as[i]) != null)
                sum += a.value;//所有counter的值求和
        }
    }
    return sum;
}

我们会发现，无论是size()方法还是mappingCount()方法，内部都是在调用sumCount()方法，该方法的代码其实也并不复杂，其内部使用的算法其实是如下算法：

总的来说，ConcurrentHashMap的计数主要是延用了分段计数的思路。

另外可能你还会有疑问，ConcurrentHashMap 中的 baseCount 属性，不就是记录了所有键值对的总数吗？直接返回它不就行了吗？

之所以没有这么做，是因为ConcurrentHashMap中的 addCount() 方法用于 通过CAS来更新 baseCount，但有可能在高并发的情况下更新失败，即这些节点虽然已经被添加到哈希表中了，但数量却没有被统计。

addCount 方法在更新 baseCount 失败时，会调用 fullAddCount()方法 将这些失败的结点包装成一个 CounterCell 对象，保存在 CounterCell 数组中。那么整张表实际的 size，其实是 baseCount 加上 CounterCell 数组中元素的个数。

4. addCount方法

在put()方法结尾处调用了addCount方法，该方法会把当前ConcurrentHashMap的元素个数+1。这个方法一共做了两件事：更新baseCount的值，检测是否进行扩容。该方法的源码如下：

private final void addCount(long x, int check) {
        CounterCell[] as; long b, s;
        //利用CAS方法更新baseCount的值 
        if ((as = counterCells) != null ||
            !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
            CounterCell a; long v; int m;
            boolean uncontended = true;
            if (as == null || (m = as.length - 1) < 0 ||
                (a = as[ThreadLocalRandom.getProbe() & m]) == null ||
                !(uncontended =
                  U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
                fullAddCount(x,uncontended);
                return;
            }
            if (check <= 1)
                return;
            s = sumCount();
        }
        
        //如果check值大于等于0 则需要检验是否需要进行扩容操作
        if (check >= 0) {
            Node<K,V>[] tab, nt; int n, sc;
            while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
                   (n = tab.length) < MAXIMUM_CAPACITY) {
                int rs = resizeStamp(n);
                //
                if (sc < 0) {
                    if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
                        sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
                        transferIndex <= 0)
                        break;
                        
					//如果已经有其他线程在执行扩容操作
                    if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
                        transfer(tab, nt);
                }
                
				//当前线程是唯一的或是第一个发起扩容的线程  此时nextTable=null
                else if (U.compareAndSwapInt(this, SIZECTL, sc,
                                             (rs << RESIZE_STAMP_SHIFT) + 2))
                    transfer(tab, null);
                s = sumCount();
            }
    }
}

最后我们总结一下，ConcurrentHashMap统计容器大小其实是用了两种思路：

CAS方式直接递增：在线程竞争不大的时候，直接使用CAS操作递增baseCount值，这里说的竞争不大指的是CAS操作不会失败的情况；

分而治之的桶计数：若出现了CAS操作失败的情况，则证明此时有线程竞争了，计数方式从CAS方式转变为分而治之的桶计数方式。

三. 为什么ConcurrentHashMap的读操作不需要加锁？

1. 简述

我们知道ConcurrentHashMap(JDK 8)是一个并发集合，所以是线程安全的。但当我们阅读源码中的get()方法时，会发现get()方法是没有添加任何锁的。所以我们想知道，get操作为什么不需要加锁呢？

实际上在JDK 8中，ConcurrentHashMap的get()方法之所以不需要加锁，主要是因为相关变量都加上了volatile修饰符，所以get操作自身几乎无需考虑线程安全性和变量可见性，只需要注意原子性即可。

这里的原子性，指的是get操作时被多个线程共享的table变量及节点属性，这些变量可能会被其他线程修改，所以需要一开始就把它们保存到局部变量中，然后再使用，这样就不必担心有其他线程修改了。

2. volatile的作用

普通的成员变量不能保证线程间的可见性。因为普通成员变量被修改之后，什么时候被写入主内存是不确定的。而当其他线程去读取时，此时内存中可能还是原来的旧值，因此无法保证可见性。

所以此时我们可以使用Java提供的volatile关键字，来保证线程间变量的可见性、有序性，一旦某个变量添加了volatile关键字，它就成了一个共享变量，但它不能保证原子性。volatile作用如下:

• volatile关键字可以保证对基本类型变量的修改，在多个线程中的读操作保持一致。但对于引用类型如数组，实体bean，仅仅保证引用的可见性，但并不保证引用内容的可见性。
• 禁止进行指令重排序。

为了提高处理速度，CPU处理器不会直接和内存进行通信，而是先将系统内存中的数据读到内部缓存(L1，L2或其他)后再进行操作，但操作完不知道何时会写到内存。

如果某个线程对声明了volatile的变量进行写操作，JVM就会向处理器发送一条指令，将这个变量所在的内存缓存写回到系统内存中。

但是就算写回到了系统内存，如果其他处理器缓存的值还是旧的，再执行计算操作就会有问题。

所以在多处理器环境下，为了保证各个处理器的缓存结果是一致的，就需要实现 缓存一致性协议。

当某个CPU在写数据时，如果发现操作的变量是共享变量，则会通知其他CPU，告知该变量的缓存行是无效的。因此其他CPU在读取该变量时，如果发现其无效，则会重新从主内存中加载数据。

3. get()不加锁原因

最后我们再梳理一下get操作不加锁的原因。

• 使用volatile关键字，会强制将修改后的值立即写入主内存；
• 当线程2进行变量修改时，volatile可以使得线程1所在工作内存中缓存变量的缓存行无效(反映到硬件层的话，就是CPU的L1或者L2缓存中对应的缓存行无效)；
• 由于线程1的工作内存中缓存变量的缓存行无效，所以当线程1再次读取该变量的值时会去主内存重新读取；
• 所以get()操作全程不需要加锁，是因为Node类的成员变量val，是用volatile关键字来修饰的，和table数组用volatile修饰是没有关系的。

四. 结语

最后，壹哥 再把两个版本中的ConcurrentHashMap进行一个简单总结。

1. JDK 7的ConcurrentHashMap小结

• JDK 7中的ConcurrentHashMap，当长度过长时，碰撞会很频繁的发生，链表的增改删查操作都会消耗很长的时间，影响性能。
• JDK 7中的ConcurrentHashMap主要使用Segment分段锁来实现并发控制，把Map分割成若干个Segment。在put()时需要锁住Segment，get()时候不需要加锁，使用volatile来保证可见性。
• 当统计全局数量时(比如size)，首先会尝试多次计算modCount来确定。这几次尝试时，会判断是否有其他线程进行了修改操作，如果没有，则直接返回size；如果有，则需要依次锁住所有的Segment来计算。

2. JDK 8的ConcurrentHashMap小结

• 不采用Segment而是采用Node，减小了锁的粒度；
• 设计了MOVED状态，在resize过程中，线程2还在put数据时，线程1会帮助resize；
• 使用3个CAS操作来确保Node中的一些原子性操作，这种方式代替了锁；
• sizeCtl的不同值代表了不同含义，起到了控制的作用；
• 使用synchronized而不是ReentrantLock。

五. 结语

至此，壹哥 用了几万字，终于带各位认真的研究了一遍ConcurrentHashMap，尤其是其底层原理和源码，不知道你现在对ConcurrentHashMap是否有了足够的了解呢？如果还有什么疑问，可以给壹哥留言评论哦！