并发集合介绍（九）

1.7 ConcurrentHashMap计数器

1.7.1 addCount方法分析

addCount方法本身就是为了记录ConcurrentHashMap中元素的个数。
两个方向组成：
● 计数器，如果添加元素成功，对计数器 + 1
● 检验当前ConcurrentHashMap是否需要扩容
计数器选择的不是AtomicLong，而是类似LongAdder的一个功能
[image]
addCount源码分析

private final void addCount(long x, int check) {
// ================================计数=====================================
// as： CounterCell[]
 // s：是自增后的元素个数
// b：原来的baseCount
CounterCell[] as; long b, s;
// 判断CounterCell不为null，代表之前有冲突问题，有冲突直接进到if中
// 如果CounterCell[]为null，直接执行||后面的CAS操作，直接修改baseCount
if ((as = counterCells) != null ||
// 如果对baseCount++成功。直接告辞。 如果CAS失败，直接进到if中
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
// 导致，说明有并发问题。
// 进来的方式有两种：
// 1. counterCell[] 有值。
// 2. counterCell[] 无值，但是CAS失败。
// m：数组长度 - 1
// a：当前线程基于随机数，获得到的数组上的某一个CounterCell
CounterCell a; long v; int m;
// 是否有冲突，默认为true，代表没有冲突
boolean uncontended = true;
// 判断CounterCell[]没有初始化，执行fullAddCount方法，初始化数组
if (as == null || (m = as.length - 1) < 0 ||
// CounterCell[]已经初始化了，基于随机数拿到数组上的一个CounterCell，如果为null，执行fullAddCount方法，初始化CounterCell
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
// CounterCell[]已经初始化了，并且指定索引位置上有CounterCell
// 直接CAS修改指定的CounterCell上的value即可。
// CAS成功，直接告辞！
// CAS失败，代表有冲突，uncontended = false，执行fullAddCount方法
!(uncontended = U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
fullAddCount(x, uncontended);
 return;
}
// 如果链表长度小于等于1，不去判断扩容
if (check <= 1)
return;
// 将所有CounterCell中记录的信累加，得到最终的元素个数
s = sumCount();
}
// ================================判断扩容=======================================
// 判断check大于等于，remove的操作就是小于0的。 因为添加时，才需要去判断是否需要扩容
if (check >= 0) {
// 一堆小变量
Node<K,V>[] tab, nt; int n, sc;
// 当前元素个数是否大于扩容阈值，并且数组不为null，数组长度没有达到最大值。
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);
}
// 没有线程执行扩容，我来扩容
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
// 重新计数。
s = sumCount();
}
}
}
// CounterCell的类，就类似于LongAdder的Cell
@sun.misc.Contended static final class CounterCell {
// volatile修饰的value，并且外部基于CAS的方式修改
volatile long value;
CounterCell(long x) { value = x; }
}
@sun.misc.Contended（JDK1.8）：
这个注解是为了解决伪共享的问题（解决缓存行同步带来的性能问题）。
CPU在操作主内存变量前，会将主内存数据缓存到CPU缓存（L1,L2,L3）中，
CPU缓存L1，是以缓存行为单位存储数据的，一般默认的大小为64字节。
缓存行同步操作，影响CPU一定的性能。
@Contented注解，会将当前类中的属性，会独占一个缓存行，从而避免缓存行失效造成的性能问题。
@Contented注解，就是将一个缓存行的后面7个位置，填充上7个没有意义的数据。
long value; long l1,l2,l3,l4,l5,l6,l7;
// 整体CounterCell数组数据到baseCount
final long sumCount() {
// 拿到CounterCell[]
CounterCell[] as = counterCells; CounterCell a;
// 拿到baseCount
long sum = baseCount;
// 循环走你，遍历CounterCell[]，将值累加到sum中，最终返回sum
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}
// CounterCell数组没有初始化
// CounterCell对象没有构建
// 什么都有，但是有并发问题，导致CAS失败
private final void fullAddCount(long x, boolean wasUncontended) {
// h：当前线程的随机数
int h;
// 判断当前线程的Probe是否初始化。
 if ((h = ThreadLocalRandom.getProbe()) == 0) {
// 初始化一波
ThreadLocalRandom.localInit();
// 生成随机数。
h = ThreadLocalRandom.getProbe();
// 标记，没有冲突
wasUncontended = true;
}
// 阿巴阿巴
boolean collide = false;
// 死循环…………
for (;;) {
// as：CounterCell[]
// a：CounterCell对 null
// n：数组长度
// v：value值
CounterCell[] as; CounterCell a; int n; long v;
// CounterCell[]不为null时，做CAS操作
if ((as = counterCells) != null && (n = as.length) > 0) {
// 拿到当前线程随机数对应的CounterCell对象，为null
// 第一个if：当前数组已经初始化，但是指定索引位置没有CounterCell对象，构建CounterCell对象放到数组上
if ((a = as[h & (n - 1)]) == null) {
// 判断cellsBusy是否为0，
if (cellsBusy == 0) {
// 构建CounterCell对象
CounterCell r = new CounterCell(x);
// 在此判断cellsBusy为0，CAS从0修改为1，代表可以操作当前数组上的指定索引，构建CounterCell，赋值进去
 if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
// 构建未完成
boolean created = false;
try {
// 阿巴阿巴
CounterCell[] rs; int m, j;
// DCL，还包含复制
if ((rs = counterCells) != null && (m = rs.length) > 0 &&
// 再次拿到指定索引位置的值，如果为null，正常将前面构建的CounterCell对象，赋值给数组
rs[j = (m - 1) & h] == null) {
// 将CounterCell对象赋值到数组
rs[j] = r;
// 构建完成
created = true;
}
} finally {
// 归位
cellsBusy = 0;
}
if (created)
// 跳出循环，告辞
break;
continue; // Slot is now non-empty
}
}
collide = false;
 }
// 指定索引位置上有CounterCell对象，有冲突，修改冲突标识
else if (!wasUncontended)
wasUncontended = true;
// CAS，将数组上存在的CounterCell对象的value进行 + 1操作
else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
// 成功，告辞。
break;
// 之前拿到的数组引用和成员变量的引用值不一样了，
// CounterCell数组的长度是都大于CPU内核数，不让CounterCell数组长度大于CPU内核数。
else if (counterCells != as || n >= NCPU)
// 当前线程的循环失败，不进行扩容
collide = false;
// 如果没并发问题，并且可以扩容，设置标示位，下次扩容
else if (!collide)
collide = true;
// 扩容操作
// 先判断cellsBusy为0，再基于CAS将cellsBusy从0修改为1。
else if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
try {
// DCL!
if (counterCells == as) {
// 构建一个原来长度2倍的数组
CounterCell[] rs = new CounterCell[n << 1];
// 将老数组数据迁移到新数组
for (int i = 0; i < n; ++i)
 rs[i] = as[i];
// 新数组复制给成员变量
counterCells = rs;
}
} finally {
// 归位
cellsBusy = 0;
}
// 归位
collide = false;
// 开启下次循环
continue;
}
// 重新设置当前线程的随机数，争取下次循环成功！
h = ThreadLocalRandom.advanceProbe(h);
}
// CounterCell[]没有初始化
// 判断cellsBusy为0.代表没有其他线程在初始化或者扩容当前CounterCell[]
// 判断counterCells还是之前赋值的as，代表没有并发问题
else if (cellsBusy == 0 && counterCells == as &&
// 修改cellsBusy，从0改为1，代表当前线程要开始初始化了
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
// 标识，init未成功
boolean init = false;
try {
// DCL!
if (counterCells == as) {
 // 构建CounterCell[]，默认长度为2
CounterCell[] rs = new CounterCell[2];
// 用当前线程的随机数，和数组长度 - 1，进行&运算，将这个位置上构建一个CounterCell对象，赋值value为1
rs[h & 1] = new CounterCell(x);
// 将声明好的rs，赋值给成员变量
counterCells = rs;
// init成功
init = true;
}
} finally {
// cellsBusy归位。
cellsBusy = 0;
}
if (init)
// 退出循环
break;
}
// 到这就直接在此操作baseCount。
else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
break; // Fall back on using base
}
}

1.7.2 size方法方法分析

size获取ConcurrentHashMap中的元素个数

public int size() {
// 基于sumCount方法获取元素个数
long n = sumCount();
// 做了一些简单的健壮性判断
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
// 整体CounterCell数组数据到baseCount
final long sumCount() {
// 拿到CounterCell[]
CounterCell[] as = counterCells; CounterCell a;
// 拿到baseCount
long sum = baseCount;
// 循环走你，遍历CounterCell[]，将值累加到sum中，最终返回sum
if (as != null) {
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}