一、前言
我们都知道，ConcurrentHashmap这个并发集合框架是线程安全的。然而，他的size()操作中并没有加任何锁，它是如何在多线程环境下 线程安全的计算出Map的size的？下面我们就来看一下size()方法。
二、ConCurrentHashMap#size()方法
1、原理
size()使用sumCount()方法计算map的size。
- 对于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()。
2、源码分析
我们直接看一下JAVA8 ConCurrentHashMap的size()方法代码：
public int size() {
// 真正计算Size的地方
long n = sumCount();
return ((n < 0L) ? 0 : // if n < 0 return 0
(n > (long) Integer.MAX_VALUE) ? Integer.MAX_VALUE : // else if n > int.maxValue return int.maxValue
(int) n); // else return (int)n。
}
size()的最大值是 Integer 类型的最大值，但是 Map 的 size 可能会超过 Integer.MAX_VALUE， 然而还有一个用来计算Map 的 size 的方法 mappingCount()返回的最大值是Long的最大值，所以JAVA8建议使用 mappingCount() 而不是size()。
mappingCount() 的代码如下：
public long mappingCount() {
long n = sumCount();
return (n < 0L) ? 0L : n; // ignore transient negative values
}
以上可以看出，无论是 size() 还是 mappingCount(), 计算Map大小的核心方法都是 sumCount()。
sumCount()方法：
若counterCells不为null，
sumCount()中迭代 counterCells ，然后和baseCount累加来统计Map的Size。
final long sumCount() {
CounterCell[] as = counterCells;
// CAS修改baseCount失败后，使用CounterCell用来统计那个线程要修改的
CounterCell a;
// 当没有并发竞争的时候，只使用baseCount统计map的size。
long sum = baseCount;
// 遍历counterCells，将CounterCell数组中元素的 value 累加 到 sum变量上。
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
// 这个数字可能是不准确的,所以ConCurrentHashMap的size是一个参考值，并不是实时确切值。
return sum;
}
ConcurrentHashMap 提供了 baseCount、counterCells 两个变量和一个 CounterCell 内部类用来统计Map的大小size。
// size的基本计数值，主要在没有线程并发争用时使用
private transient volatile long baseCount;
/**
* Table of counter cells. When non-null, size is a power of 2.
*/
private transient volatile CounterCell[] counterCells;
/**
* @sun.misc.Contended 这个注解的作用是防止伪共享，
* 使用时，需要加上 -XX:-RestrictContended 参数
*/
@sun.misc.Contended
static final class CounterCell {
volatile long value;
CounterCell(long x) {
value = x;
}
}
伪共享概述：
缓存系统中是以缓存行（cache line）为单位存储的。缓存行是2的整数幂个连续字节，一般为32-256个字节；最常见的缓存行大小是64个字节。- 当
多线程修改互相独立的变量时，如果这些变量共享同一个缓存行，就会无意中影响彼此的性能，这就是伪共享。
既然统计Map的size需要迭代counterCells，那么counterCells是哪里维护的？
我们看一下Map的put()操作，它指定会影响counterCells。put()方法中最终会调用addCount()修改Map的size。
addCount()方法：
addCount()方法分为两个阶段，分别为：
1、 计算当前存入的KV键值对总数size；
2、 存储的总kv数量达到了阈值，执行扩容；
针对第一阶段：
- 首先第一次执行addCount()方法时，counterCells数组为null，则(as = counterCells) != null为false，所以线程直接使用CAS将baseCount执行 +v操作；
- 如果CAS失败 或 第N次执行addCount()方法时发现counterCells不为空，会做进一步判断，包括：
1> counterCells等于null（第一次CAS修改baseCount值失败时）
2> 或 counterCells初始化了但是其中没有数据 或 counterCells中随机一个下标位置a处没有存储数据
3> 或 对counterCells下标位置a处执行CAS做 + v操作失败了；
- 进入到fullAddCount()方法中进一步处理多线程竞争下的键值对size维护操作；
- 并使用一个boolean类型的变量uncontended标记是否为对counterCells下标位置a处执行CAS失败才进入的fullAddCount()方法，false表示是。
private final void addCount(long x, int check) {
CounterCell[] as;
long b, s;
/**
* part1: 计算当前存入的KV键值对总数
*/
if ((as = counterCells) != null || /** 第一次执行这段的时候，counterCells等于null */
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
/** 如果此处产生多线程竞争，则只有一条线程可以执行成功，且不用进入if语句中 */
CounterCell a;
long v;
int m;
boolean uncontended = true;
if (as == null || /** 如果counterCells等于null */
(m = as.length - 1) < 0 || /** 如果counterCells初始化了但是里面没有元素 */
(a = as[ThreadLocalRandom.getProbe() & m]) == null || /** 如果随机一个下标位置但是没有存储数据 */
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
/** 如果多线程竞争失败，则会执行fullAddCount方法 */
// 使用CounterCell来计数
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
// 统计所有count值
s = sumCount();
}
if (check >= 0) {
Node<K, V>[] tab, nt;
int n, sc;
/**
* part2: 存储的总kv数量达到了阈值，执行扩容
*
* s>=sizeCtl，表示达到了扩容的阈值
*/
while (s >= (long) (sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
// sc为负值，表明正在执行扩容操作中
if (sc < 0) {
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || /** sc右移16位，则读取的就是原高16位的内容，即：table容量相关信息;不等于rs说明table容量发生了不一致的情况 */
sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
// 加入1个共同扩容的线程，即：sc+1
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
} else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
// 统计所有count值
s = sumCount();
}
}
}
扩容部分后面博文介绍。
我们接着看fullAddCount()是怎么处理多线程竞争条件下的key-value键值对的size。
fullAddCount()方法：
fullAddCount()又可以分为两个阶段：
- 第一阶段，计算当前线程的探针哈希值；
- 第二阶段，在无限循环中，利用CounterCell进行计数。
第一阶段比较简单：
主要逻辑为：如果获取到的随机数为0，则初始化当前线程的探针哈希值；并再次获取到当前线程的探针哈希值。探针哈希值的操作主要涉及三个方法：
- ThreadLocalRandom.getProbe()：用来获得随机数；
- ThreadLocalRandom.localInit()：初始化当前线程的探针哈希值；
- ThreadLocalRandom.advanceProbe(h)：更改当前线程的探针哈希值。
面试官：聊一下探针哈希值的作用？
秃秃：探针哈希值的作用是哈希线程，将线程和数组中的不同元素对应起来，尽量避免线程争用同一数组元素。
面试官：探针哈希值和map里使用的哈希值的区别什么？
秃秃：当线程发生数组元素争用后，可以改变线程的探针哈希值，让线程去使用另一个数组元素，而map中key对象的哈希值，由于有定位value的需求，所以它是一定不能变的。
第二阶段包含三种情况：
1、 counterCells不为空且其中有元素；
2、 counterCells为空，且没有其他线程正在操作counterCells；
3、 尝试直接通过CAS修改baseCount的值；
我们先通过两张图分别介绍一下：有线程竞争CAS修改同一counterCells下标位置的值、和无线程竞争时的场景：
1）无线程竞争时：
2）有线程竞争CAS修改同一counterCells下标位置的值：
part1> 第一种情况：counterCells不为空且其中有元素；
这其中又包含四种case：
1、随机数h待插入的counterCells数组下标位置没有数据；并且没有线程正在操作counterCells数组，则通过CAS将cellsBusy设置为1，然后新建一个CounterCell插入到 随机数h & counterCells.length下标位置，在将cellsBusy设置为0；
2、随机数h待插入的counterCells数组下标位置有数据，则通过CAS将原数据值 + v；CAS成功退出循环；
3、否则，判断counterCells数组是否发生了变化（即是否已经扩容），发生变化 则将collide设置为true，表示发生了碰撞。
4、如果多线程CAScounterCells 指定下标位置的value值时发生碰撞，CAS的失败的线程会对counterCells数组进行两倍扩容，以减少碰撞次数。
part2> 第二种情况：counterCells为空，且没有其他线程正在操作counterCells；
- 直接创建一个长度为2的CounterCell数组counterCells，并将x赋值进数组的 h & 1下标位置，跳出循环。
part3> 第三种情况：尝试直接通过CAS修改baseCount的值；
- 如果CAS修改baseCount成功，则跳出循环，否则继续下一轮循环。
面试官：标注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之前避免伪共享的方案是什么？
秃秃：在Java7之前，是通过代码里手动添加属性的方式解决的，比如类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访问/操作数据的时间。
三、总结
Java8的ConCurrentHashMap的size在addCount()中已经有了初步的维护，非并发场景下使用一个volatile关键字修饰的baseCount变量即可，单在并发场景下针对每个线程会创建一个CounterCell；最后在sumCount()方法中通过累加baseCount和CounterCell数组的counterCell值获取到Map的总大小Size，但是这个size只是一个约数，如果获取size的同时纯在插入或者删除操作，size和实际的数量可能有所不同。