ConcurrentHashMap 的 size 方法原理分析

面试题

这是同一个面试的时候别人问的，我只是记得看过，在concurrenthashmap中会统计多次，当时就说会统计两次进行比较，人家接着问为啥。。。我傻了一下，这不是明摆着两次统计的中间有新的变化了，会导致统计不准确吗？当时也不知道说啥好，以为他有新的点，就说不知道。面试时很多问题其实冷静下来想一下，可以更进一步的，有时候其实也是怕他更进一步后下面的挖坑挖大了。

下面具体说一下这个size方法：
代码就不贴了。只说原理。

众所周知，concurrenthashmap有很多歌segments，首先遍历segments将每个segment的count加起来作为整个concurrenthashMap的size。如果没有并发的情况下这自然就可以了，但这是多线程的，如果前脚统计完后脚有变化了，这就不准确了，源码中引入了，modCount和两次比较来实现size的确认。具体过程是：

1.进行第一遍遍历segments数组，将每个segemnt的count加起来作为总数，期间把每个segment的modCount加起来sum作为结果是否被修改的判断依据。
这里需要提一下modCount，这个是当segment有任何操作都会进行一次增量操作，代表的是对Segment中元素的数量造成影响的操作的次数，这个值只增不减！！！！只增不减很重要，这样就不会出现一个segment+1，导致modcount+1,而另一个segment-1，即modcount-1 ,从而在统计所有的时候modcount没有变化。

2.size操作就是遍历了两次所有的Segments，每次记录Segment的modCount值，然后将两次的modCount进行比较，如果相同，则表示期间没有发生过写入操作，就将原先遍历的结果返回，如果不相同，则把这个过程再重复做一次，如果再不相同，则就需要将所有的Segment都锁住，然后一个一个遍历了。

3.如果经判断发现两次统计出的modCount并不一致，那就如上所说，要重新启用全部segment加锁的方式来进行count的获取和统计了，这样在此期间每个segement都被锁住，无法进行其他操作，统计出的count自然很准确。

而之所以之所以要先不加锁进行判断，道理很明显，就是不希望因为size操作获取这么多锁，因为获取锁不光占用资源，也会影响其他线程对ConcurrentHash的使用，影响并发情况下程序执行的效率。使用锁要谨慎！

原理大概就是这样的，具体的代码可以去看源码，而且源码1.7和1.8有差别。。。有空再贴出来比较比较吧。
————————————————

实际代码

在 JDK1.7 版本中，ConcurrentHashMap 的数据结构是由一个 Segment 数组和多个 HashEntry 组成。简单理解就是ConcurrentHashMap 是一个 Segment 数组，Segment 通过继承 ReentrantLock 来进行加锁，所以每次需要加锁的操作锁住的是一个 Segment，这样只要保证每个 Segment 是线程安全的，也就实现了全局的线程安全。

JDK1.8 的实现已经摒弃了 Segment 的概念，而是直接用 Node 数组 + 链表 + 红黑树的数据结构来实现，并发控制使用 Synchronized 和 CAS 来操作，整个看起来就像是优化过且线程安全的 HashMap，虽然在 JDK1.8 中还能看到 Segment 的数据结构，但是已经简化了属性，只是为了兼容旧版本。通过 HashMap 查找的时候，根据 hash 值能够快速定位到数组的具体下标，如果发生 Hash 碰撞，需要顺着链表一个个比较下去才能找到我们需要的，时间复杂度取决于链表的长度，为 O(n)。为了降低这部分的开销，在 Java8 中，当链表中的元素超过了 8 个以后，会将链表转换为红黑树，在这些位置进行查找的时候可以降低时间复杂度为 O(logN)。

如何计算 ConcurrentHashMap Size
由上面分析可知，ConcurrentHashMap 更适合作为线程安全的 Map。在实际的项目过程中，我们通常需要获取集合类的长度，那么计算 ConcurrentHashMap 的元素大小就是一个有趣的问题，因为他是并发操作的，就是在你计算 size 的时候，它还在并发的插入数据，可能会导致你计算出来的 size 和你实际的 size 有差距。本文主要分析下 JDK1.8 的实现。关于 JDK1.7 简单提一下。

在 JDK1.7 中，第一种方案他会使用不加锁的模式去尝试多次计算 ConcurrentHashMap 的 size，最多三次，比较前后两次计算的结果，结果一致就认为当前没有元素加入，计算的结果是准确的。第二种方案是如果第一种方案不符合，他就会给每个 Segment 加上锁，然后计算 ConcurrentHashMap 的 size 返回。其源码实现:

JDK1.8 实现相比 JDK 1.7 简单很多，只有一种方案，我们直接看 size() 代码：

public int size() {
    long n = sumCount();
    return ((n < 0L) ? 0 : (n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE : (int)n);
}

最大返回 int 最大值，但是这个 Map 的长度是有可能超过 int 最大值的，所以 JDK 8 增了 mappingCount 方法。代码如下：

public long mappingCount() {
    long n = sumCount();
    return (n < 0L) ? 0L : n; // ignore transient negative values
}

相比较 size 方法，mappingCount 方法的返回值是 long 类型。所以不必限制最大值必须是 Integer.MAX_VALUE。而 JDK 推荐使用这个方法。但这个返回值依然不一定绝对准确。

从这两个方法中可以看出，sumCount 方法是核心。

sumCount 方法实现

代码如下：

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;
        }
    }
    return sum;
}

上面的方法逻辑：当 counterCells 不是 null，就遍历元素，并和 baseCount 累加。

两个属性： baseCount 和 counterCells。

先看 baseCount。

    /**
     * Base counter value, used mainly when there is no contention,
     * but also as a fallback during table initialization
     * races. Updated via CAS.
     * 当没有争用时，使用这个变量计数。
     */
    private transient volatile long baseCount;

一个 volatile 的变量，在 addCount 方法中会使用它，而 addCount 方法在 put 结束后会调用。在 addCount 方法中，会对这个变量做 CAS 加法。

但是如果并发导致 CAS 失败了，怎么办呢？使用 counterCells。

如果上面 CAS 失败了，在 fullAddCount 方法中，会继续死循环操作，直到成功。

而这个 CounterCell 类又是上面鬼呢？

// 一种用于分配计数的填充单元。改编自LongAdder和Striped64。请查看他们的内部文档进行解释。
@sun.misc.Contended 
static final class CounterCell {
    volatile long value;
    CounterCell(long x) { value = x; }
}

使用了 @sun.misc.Contended 标记的类，内部一个 volatile 变量。注释说，改编自LongAdder和Striped64,关于这两个类，请看 Java8 Striped64 和 LongAdder。

而关于这个注解，有必要解释一下。这个注解标识着这个类防止需要防止 "伪共享".

说说伪共享。引用一下别人的说法：

避免伪共享(false sharing)。先引用个伪共享的解释：缓存系统中是以缓存行（cache line）为单位存储的。缓存行是2的整数幂个连续字节，一般为32-256个字节。最常见的缓存行大小是64个字节。当多线程修改互相独立的变量时，如果这些变量共享同一个缓存行，就会无意中影响彼此的性能，这就是伪共享。

所以伪共享对性能危害极大。

JDK 8 版本之前没有这个注解，Doug Lea 使用拼接来解决这个问题，把缓存行加满，让缓存之间的修改互不影响。

在我的机器上测试，加和不加这个注解的性能差距达到了 5 倍。

总结

JDK 8 推荐使用mappingCount 方法，因为这个方法的返回值是 long 类型，不会因为 size 方法是 int 类型限制最大值（size 方法是接口定义的，不能修改）。

在没有并发的情况下，使用一个 baseCount volatile 变量就足够了，当并发的时候，CAS 修改 baseCount 失败后，就会使用 CounterCell 类了，会创建一个这个对象，通常对象的 volatile value 属性是 1。在计算 size 的时候，会将 baseCount 和 CounterCell 数组中的元素的 value 累加，得到总的大小，但这个数字仍旧可能是不准确的。

还有一个需要注意的地方就是，这个 CounterCell 类使用了 @sun.misc.Contended 注解标识，这个注解是防止伪共享的。是 1.8 新增的。使用时，需要加上 -XX:-RestrictContended 参数。