ConcurrentHashMap源码分析(04)-size()方法

前言

HashMap.size()的代码非常简单，直接返回成员变量size即可。可是在ConcurrentHashMap里面，是否也是这样呢？答案是否定的，因为我们需要考虑并发的情况。若我们继续沿用HashMap.size()的思想，并发的效率可以想象得到，将变得非常得低效。

那么ConcurrentHashMap.size()又是怎么实现的呢？我们这一小节将进行分析~

size()

这个方法内部调用sumCount()方法，但是sumCount()返回的是long类型的，而size()返回的是int类型的，需要进行一定的适配。

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

sumCount()

这个方法用于返回节点的个数，有用到两个关键的成员变量

baseCount -- 基本的计数器，当没有竞争的时候，使用这个值
counterCells -- 数组结构，当有竞争的时候使用它来进行计算

sumCount()实现的逻辑如下：

首先判断counterCells是否为null，为null说明没有竞争，直接返回baseCount。
如果counterCells不为null，说明有竞争，通过遍历counterCells数组，将所有元素的value进行求和。

/**
 * 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;

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

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，那么它又是什么时候生成的呢？在前面的分析我们看到了counterCells的影子，那就是在addCount()方法中，那么接下来我们就再来分析一下关于counterCells的代码。

addCount()方法再分析

private final void addCount(long x, int check) {
    CounterCell[] as; long b, s;
    // 1. 初始的时候，counterCells一定为null，第一个条件此时将不会被满足
    // 2. 在第一个条件不满足的时候，需要判断第二个条件。
    // 3. 第二个条件在存在竞争的情况下将返回false，也就是需要进入到if里面
    if ((as = counterCells) != null ||
        !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
        CounterCell a; long v; int m;
        boolean uncontended = true;
        // 这儿有三个或条件，只需要满足其一，就可以进入到if
        // 1. counterCells为null
        // 2. counterCells为空数组
        // 3. counterCells指定位置元素为null
        // 4. CAS设置counterCell.value失败的时候
        // 这几种情况将进入到`fullAddCount()`进行自旋操作
        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();
    }
    // 省略掉扩容的代码...
}

fullAddCount()方法

这个方法非常得复杂，代码也很长，如果深入进去将陷入到细节中去。在此我们只需要知道这个方法的用途，那就是通过自旋的方式新增或更新counterCells，使用counterCells来统计节点个数将不会得到准确的结果。

CounterCell类

既然竞争的情况下是围绕counterCells来展开的，那么我们需要看看这个成员变量所属的类型，CounterCell。

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

这个类有几个需要注意的地方

value使用volatile修饰，可保证其可见性
CounterCell使用@sun.misc.Contended修饰

@sun.misc.Contended这个注释需要明确说明一下。如果类上面使用该注释，标识需要防止伪共享。

那么什么又是伪共享呢？借鉴一下网上大神的阐述。

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

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

mappingCount()

我们额外分析一下这个方法，这是jdk8新加的一个方法，内部同样调用了sumCount()，和size()有同样的效果，但是它的返回值却是long，可以避免精度的损失。同时这个方法也是被推荐用来替代size()。

/**
 * Returns the number of mappings. This method should be used
 * instead of {@link #size} because a ConcurrentHashMap may
 * contain more mappings than can be represented as an int. The
 * value returned is an estimate; the actual count may differ if
 * there are concurrent insertions or removals.
 *
 * @return the number of mappings
 * @since 1.8
 */
public long mappingCount() {
    long n = sumCount();
    return (n < 0L) ? 0L : n; // ignore transient negative values
}

总结

期初，我们还以为size()会很简单，但是一通分析下来却发现它并不是想象得那么简单，尤其是addCount()内部调用的fullAddCount()方法，其复杂度不下于扩容方法。

为了省事，本节并没有对这个方法进行分析，后续有时间再来分析。