并发编程——ConcurrentHashMap#addCount()-分析

## 前言

ConcurrentHashMap 精华代码很多,前面分析了 helpTransfer 和 transfer 和 putVal 方法,今天来分析一下 addCount 方法,该方法会在 putVal 方法中调用。

该方法可以配合 size 方法一起查看,关于该方法,楼主也写了一篇文章分析过:并发编程 —— ConcurrentHashMap size 方法原理分析

具体代码如下:

1
2
addCount(1L, binCount);
return null;

当插入结束的时候,会调用该方法,并传入一个 1 和 binCount 参数。从方法名字上,该方法应该是对哈希表的元素进行计数的。

一起来看看 addCount 是如何操作的。

源码分析

源码加注释:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
// 从 putVal 传入的参数是 1, binCount,binCount 默认是0,只有 hash 冲突了才会大于 1.且他的大小是链表的长度(如果不是红黑数结构的话)。
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
// 如果计数盒子不是空 或者
// 如果修改 baseCount 失败
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
// 如果计数盒子是空(尚未出现并发)
// 如果随机取余一个数组位置为空 或者
// 修改这个槽位的变量失败(出现并发了)
// 执行 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();
}
// 如果需要检查,检查是否需要扩容,在 putVal 方法调用时,默认就是要检查的。
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
// 如果map.size() 大于 sizeCtl(达到扩容阈值需要扩容) 且
// table 不是空;且 table 的长度小于 1 << 30。(可以扩容)
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
// 根据 length 得到一个标识
int rs = resizeStamp(n);
// 如果正在扩容
if (sc < 0) {
// 如果 sc 的低 16 位不等于 标识符(校验异常 sizeCtl 变化了)
// 如果 sc == 标识符 + 1 (扩容结束了,不再有线程进行扩容)(默认第一个线程设置 sc ==rs 左移 16 位 + 2,当第一个线程结束扩容了,就会将 sc 减一。这个时候,sc 就等于 rs + 1)
// 如果 sc == 标识符 + 65535(帮助线程数已经达到最大)
// 如果 nextTable == null(结束扩容了)
// 如果 transferIndex <= 0 (转移状态变化了)
// 结束循环
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
// 如果可以帮助扩容,那么将 sc 加 1. 表示多了一个线程在帮助扩容
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
// 扩容
transfer(tab, nt);
}
// 如果不在扩容,将 sc 更新:标识符左移 16 位 然后 + 2. 也就是变成一个负数。高 16 位是标识符,低 16 位初始是 2.
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
// 更新 sizeCtl 为负数后,开始扩容。
transfer(tab, null);
s = sumCount();
}
}
}

方法加了注释以后,还是挺长的。

总结一下该方法的逻辑:

x 参数表示的此次需要对表中元素的个数加几。check 参数表示是否需要进行扩容检查,大于等于0 需要进行检查,而我们的 putVal 方法的 binCount 参数最小也是 0 ,因此,每次添加元素都会进行检查。(除非是覆盖操作)

  1. 判断计数盒子属性是否是空,如果是空,就尝试修改 baseCount 变量,对该变量进行加 X。
  2. 如果计数盒子不是空,或者修改 baseCount 变量失败了,则放弃对 baseCount 进行操作。
  3. 如果计数盒子是 null 或者计数盒子的 length 是 0,或者随机取一个位置取于数组长度是 null,那么就对刚刚的元素进行 CAS 赋值。
  4. 如果赋值失败,或者满足上面的条件,则调用 fullAddCount 方法重新死循环插入。
  5. 这里如果操作 baseCount 失败了(或者计数盒子不是 Null),且对计数盒子赋值成功,那么就检查 check 变量,如果该变量小于等于 1. 直接结束。否则,计算一下 count 变量。
  6. 如果 check 大于等于 0 ,说明需要对是否扩容进行检查。
  7. 如果 map 的 size 大于 sizeCtl(扩容阈值),且 table 的长度小于 1 << 30,那么就进行扩容。
  8. 根据 length 得到一个标识符,然后,判断 sizeCtl 状态,如果小于 0 ,说明要么在初始化,要么在扩容。
  9. 如果正在扩容,那么就校验一下数据是否变化了(具体可以看上面代码的注释)。如果检验数据不通过,break。
  10. 如果校验数据通过了,那么将 sizeCtl 加一,表示多了一个线程帮助扩容。然后进行扩容。
  11. 如果没有在扩容,但是需要扩容。那么就将 sizeCtl 更新,赋值为标识符左移 16 位 —— 一个负数。然后加 2。 表示,已经有一个线程开始扩容了。然后进行扩容。然后再次更新 count,看看是否还需要扩容。

总结一下

总结下来看,addCount 方法做了 2 件事情:

  1. 对 table 的长度加一。无论是通过修改 baseCount,还是通过使用 CounterCell。当 CounterCell 被初始化了,就优先使用他,不再使用 baseCount。

  2. 检查是否需要扩容,或者是否正在扩容。如果需要扩容,就调用扩容方法,如果正在扩容,就帮助其扩容。

有几个要点注意:

  1. 第一次调用扩容方法前,sizeCtl 的低 16 位是加 2 的,不是加一。所以 sc == rs + 1 的判断是表示是否完成任务了。因为完成扩容后,sizeCtl == rs + 1。

  2. 扩容线程最大数量是 65535,是由于低 16 位的位数限制。

  3. 这里也是可以帮助扩容的,类似 helpTransfer 方法。


并发编程——ConcurrentHashMap#addCount()-分析
http://thinkinjava.cn/2018/05/16/2018/2018-05-16-并发编程——ConcurrentHashMap$addCount()-分析/
作者
莫那·鲁道
发布于
2018年5月16日
许可协议