开篇
相比jdk1.7，ConcurrentHashMap在jdk1.8当中有了很大的变化，从大神们的总结中拷贝了一些改进点便于大家有个印象，总结出来有以下几点：
- jdk1.8的ConcurrentHashMap不再使用Segment代理Map操作这种设计，整体结构变为HashMap这种结构，但是依旧保留分段锁的思想。之前版本是每个Segment都持有一把锁，1.8版本改为锁住恰好装在一个hash桶本身位置上的节点，也就是hash桶的第一个节点 tabAt(table, i)，后面直接叫第一个节点。它可能是Node链表的头结点、保留节点ReservationNode、或者是TreeBin节点（TreeBin节点持有红黑树的根节点）。
- 可以多线程并发来完成扩容这个耗时耗力的操作。在之前的版本中如果Segment正在进行扩容操作，其他写线程都会被阻塞，jdk1.8改为一个写线程触发了扩容操作，其他写线程进行写入操作时，可以帮助它来完成扩容这个耗时的操作。
- 因为多线程并发扩容的存在，导致的其他操作的实现上会有比较大的改动，常见的get/put/remove/replace/clear，以及迭代操作，都要考虑并发扩容的影响。
- 使用新的计数方法。不使用Segment时，如果直接使用一个volatile类变量计数，因为每次读写volatile变量的开销很大，高并发时效率不如之前版本的使用Segment时的计数方式。jdk1.8新增了一个用与高并发情况的计数工具类java.util.concurrent.atomic.LongAdder，此类是基本思想和1.7及以前的ConcurrentHashMap一样，使用了一层中间类，叫做Cell（类似Segment这个类）的计数单元，来实现分段计数，最后合并统计一次。因为不同的计数单元可以承担不同的线程的计数要求，减少了线程之间的竞争，在1.8的ConcurrentHashMap基本结果改变时，继续保持和分段计数一样的并发计数效率。
- 同1.8版本的HashMap，当一个hash桶中的hash冲突节点太多时，把链表变为红黑树，提高冲突时的查找效率。
ConcurrentHashMap类图
image.png
ConcurrentHashMap的构造函数
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
implements ConcurrentMap<K,V>, Serializable {
transient volatile Node<K,V>[] table;
public ConcurrentHashMap() {
}
public ConcurrentHashMap(int initialCapacity) {
if (initialCapacity < 0)
throw new IllegalArgumentException();
int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
MAXIMUM_CAPACITY :
tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
// 用这个重要的变量保存hash桶的接下来的初始化使用的容量
this.sizeCtl = cap;
}
public ConcurrentHashMap(Map<? extends K, ? extends V> m) {
// 用这个重要的变量保存hash桶的接下来的初始化使用的容量
this.sizeCtl = DEFAULT_CAPACITY;
putAll(m);
}
public ConcurrentHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 1);
}
// concurrencyLevel只是为了此方法能够兼容之前的版本，它并不是实际的并发级别，loadFactor也不是实际的加载因子了
// 这两个都失去了原有的意义，仅仅对初始容量有一定的控制作用
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) {
if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (initialCapacity < concurrencyLevel) // Use at least as many bins
initialCapacity = concurrencyLevel; // as estimated threads
long size = (long)(1.0 + (long)initialCapacity / loadFactor);
int cap = (size >= (long)MAXIMUM_CAPACITY) ?
MAXIMUM_CAPACITY : tableSizeFor((int)size);
// 用这个重要的变量保存hash桶的接下来的初始化使用的容量
this.sizeCtl = cap;
}
}
ConcurrentHashMap的initTable操作
对于ConcurrentHashMap来说，调用它的构造方法仅仅是设置了一些参数而已。而整个table的初始化是在向ConcurrentHashMap中插入元素的时候发生的。如调用put、computeIfAbsent、compute、merge等方法的时候，调用时机是检查table==null。
初始化方法主要应用了关键属性sizeCtl，如果sizeCtl<0，表示其他线程正在进行初始化，就放弃这个操作。在这也可以看出ConcurrentHashMap的初始化只能由一个线程完成。如果获得了初始化权限，就用CAS方法将sizeCtl置为-1，防止其他线程进入。初始化数组后，将sizeCtl的值改为0.75*n。
在initTable()过程中为了保证线程安全总共使用了两步操作，1、通过CAS方法将sizeCtl置为-1保证只有一个线程进入；2、线程获取初始化权限后内部通过if ((tab = table) == null || tab.length == 0) 保证只有在未初始化的情况下完成初始化。
initTable()操作当中Thread.yield()方法让出cpu的线程再重新获取cpu的时候会发现while循环已经不满足就跳出了初始化流程。
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
while ((tab = table) == null || tab.length == 0) {
if ((sc = sizeCtl) < 0)
Thread.yield(); // lost initialization race; just spin
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
//判断是否需要初始化table
if ((tab = table) == null || tab.length == 0) {
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
// n为总容量,下面的算式相当于n * 3/4
sc = n - (n >>> 2);
}
} finally {
sizeCtl = sc;
}
break;
}
}
return tab;
}
ConcurrentHashMap的put操作
- 1、先传入一个k和v的键值对，不可为空（HashMap是可以为空的），如果为空就直接报错。
- 2、接着去判断table是否为空，如果为空就进入初始化阶段。
- 3、如果判断数组中某个指定的桶是空的，那就直接把键值对插入到这个桶中作为头节点，而且这个操作不用加锁，主要是通过casTabAt实现无锁操作。
- 4、如果这个要插入的桶中的hash值为-1，也就是MOVED状态（也就是这个节点是forwordingNode），那就是说明有线程正在进行扩容操作，那么当前线程就进入协助扩容阶段。
- 5、需要把数据插入到链表或者树中，如果这个节点是一个链表节点，那么就遍历这个链表，如果发现有相同的key值就更新value值，如果遍历完了都没有发现相同的key值，就需要在链表的尾部插入该数据。插入结束之后判断该链表节点个数是否大于8，如果大于就需要把链表转化为红黑树存储。
- 6、如果这个节点是一个红黑树节点，那就需要按照树的插入规则进行插入。
- 7、put结束之后，需要给map已存储的数量+1，在addCount方法中判断是否需要扩容。
- 8、扩容过程见后面的分析，整个流程还是比较复杂，我也只能理解其中的一部分。
public V put(K key, V value) {
return putVal(key, value, false);
}
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
// for循环在这里是个死循环，内部通过break或者return跳出循环
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// 初始化Table对象
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// 如果对应的hash桶元素为空就直接完成put操作直接返回
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// 如果刚好在进行扩容那么就协助扩容待扩容完成后继续执行put操作
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
// 完成扩容后put数据
else {
V oldVal = null;
// 对于第一个元素进行加锁操作
synchronized (f) {
if (tabAt(tab, i) == f) {
// 处理链表场景，fh大于0表示链表
if (fh >= 0) {
binCount = 1;
// 遍历hash桶采用尾插入法添加到末尾，binCount统计链表元素个数
for (Node<K,V> e = f;; ++binCount) {
K ek;
//如果遍历到一个值，这个值和当前的key是相同的，那就更改value值
if (e.hash == hash &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent)
e.val = value;
break;
}
Node<K,V> pred = e;
//如果遍历到结束都没有遇到相同的key，且后面没有节点了，那就直接在尾部插入一个
if ((e = e.next) == null) {
pred.next = new Node<K,V>(hash, key,
value, null);
break;
}
}
}
// 处理红黑树情况
else if (f instanceof TreeBin) {
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
// 确认是否需要由链表转为红黑树
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
// 计数增加1，有可能触发transfer操作(扩容)
addCount(1L, binCount);
return null;
}
ConcurrentHashMap的get操作
ConcurrentHashMap的get方法主要步骤是：
- 1、先判断数组的桶中的第一个节点是否寻找的对象是为链表还是红黑树。
- 2、如果是红黑树另外做处理，红黑树查找的逻辑暂时不展开，也暂时没能力展开。
- 3、如果是链表就先判断头节点是否为要查找的节点，如果不是那么就遍历这个链表查询
- 4、如果都不是，那就返回null值。
public V get(Object key) {
Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;
int h = spread(key.hashCode());
if ((tab = table) != null && (n = tab.length) > 0 &&
(e = tabAt(tab, (n - 1) & h)) != null) {
// 如果找到值则直接返回
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
// eh<0表示这个节点是红黑树
// hash桶的第一个节点的hash值小于0，代表它是特殊节点，使用特化的查找方式进行查找
// ForwardingNode会把find转发到nextTable上再去执行一次；
// TreeBin则根据自身读写锁情况，判断是用红黑树方式查找，还是用链表方式查找；
// ReservationNode本身只是为了synchronized有加锁对象而创建的空的占位节点，
// 因此本身hash桶是没节点的，一定找不到，直接返回null）
else if (eh < 0)
// 这里的e.find()根据e的实例对象访问不同的方法
return (p = e.find(h, key)) != null ? p.val : null;
//如果首节点不是查找对象且不是红黑树结构，那边就遍历这个链表
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
ConcurrentHashMap的扩容操作
ConcurrentHashMap的扩容的addCount()方法的主要步骤是：
- 判断map中元素个数是否大于map的阈值，超过后就进行扩容。
- 如果已经在进行扩容那么就协助扩容。
- 如果没有扩容那么就开始进行扩容。
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
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;
// 统计map当中元素的总个数
s = sumCount();
}
// 如果添加的个数大于0,那么就判断是否需要扩容
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
// s >= (long)(sc = sizeCtl) 的s代表元素总个数,sc=sizeCtl代表的是扩容的阈值
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
//如果小于0就说明已经再扩容或者已经在初始化
if (sc < 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);
}
//如果未初始化就首次发起扩容，通过unsafe保证了唯一性
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))
transfer(tab, null);
s = sumCount();
}
}
}
ConcurrentHashMap的扩容步骤
扩容大致的过程：首先有且只能由一个线程构建一个nextTable，这个nextTable主要是扩容后的数组（容量已经扩大），然后把原table复制到nextTable中，这个过程可以多线程共同操作。但是一定要清楚，这个复制并不是简单的把原table的数据直接移动到nextTable中，而是需要有一定的规律和算法操控的（不然怎么把树转化为链表呢）。
整个复制的过程如下：
- 数组中（桶中）总共分为3种存储情况：空，链表头，TreeBin头
- 遍历原来的数组（原table），如果数组中某个值为空，则直接放置一个forwordingNode（上篇博文介绍过）。
- 如果数组中某个值不为空，而是一个链表头结点，那么就对这个链表进行拆分为两个链表，存储到nextTable对应的两个位置。
- 如果数组中某个值不为空，而是一个TreeBin头结点，那么这个地方就存储的是红黑树的结构，这样一来，处理就会变得相对比较复杂，就需要先判断需不需要把树转换为链表，做完一系列的处理，然后把对应的结果存储在nextTable的对应两个位置。
private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {
int n = tab.length, stride;
// 计算扩容的线程负责的hash桶的范畴
// private static final int MIN_TRANSFER_STRIDE = 16;
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
stride = MIN_TRANSFER_STRIDE; // subdivide range
// 第一个线程进入的时候会初始化扩容后的数组，以2倍的速度扩容
if (nextTab == null) { // initiating
try {
// 以2倍的速率扩容 n<<1
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
// 保存新创建的扩容后的数组
nextTable = nextTab;
// 记录原数组的大小
transferIndex = n;
}
// 扩容后数组的大小
int nextn = nextTab.length;
// 转发节点，在扩容后的数组和原来数组之间建立桥梁的转发节点，
// 在扩容的过程中访问旧数组可以访问到新数组
// 在旧数组的一个hash桶中所有节点都被迁移完后，放置在这个hash桶中，
// 表明已经迁移完，对它的读操作会转发到新数组
ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);
boolean advance = true;
// 扩容中收尾的线程把做个值设置为true，
// 进行本轮扩容的收尾工作（两件事，重新检查一次所有hash桶，给属性赋新值）
boolean finishing = false; // to ensure sweep before committing nextTab
// for循环的是一个死循环直至扩容完成
for (int i = 0, bound = 0;;) {
Node<K,V> f; int fh;
// while循环的作用特别多，其中之一就是分配线程这次扩容负责的hash桶范围
while (advance) {
int nextIndex, nextBound;
// 一次transfer任务还没有执行完毕
if (--i >= bound || finishing)
advance = false;
// transfer任务已经没有了，表明可以准备退出扩容了
else if ((nextIndex = transferIndex) <= 0) {
i = -1;
advance = false;
}
// 尝试申请一个transfer任务
else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
// 申请到任务后标记自己的任务区间
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
// 跳出循环的if判断，这个逻辑不是特别懂
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) {
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1);
return;
}
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
finishing = advance = true;
i = n; // recheck before commit
}
}
// 如果原数组指定位置的hash桶为空那么就设置为转发节点类型fwd表明迁移完毕
else if ((f = tabAt(tab, i)) == null)
advance = casTabAt(tab, i, null, fwd);
// 这个逻辑也不是特别明白
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
// 锁定原数组hash桶对应的第一个元素，这个f是在f = tabAt(tab, i)赋值的
synchronized (f) {
// 这里需要标明每次都需要比较是否还是第一个元素是否有变化
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
// 处理链表形式节点的迁移
if (fh >= 0) {
int runBit = fh & n;
Node<K,V> lastRun = f;
// 这部分逻辑挺有意思的，是有一定的优化
// 遍历同一个hash桶下面的所有元素
// 将末尾连续处于新扩容数组高位或者地位的元素打包一起提升迁移数组
// A->B->A->B->A->A->A->A的场景，最后连续的A的连接是不会打断的
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
for (Node<K,V> p = f; p != lastRun; p = p.next) {
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
ln = new Node<K,V>(ph, pk, pv, ln);
else
hn = new Node<K,V>(ph, pk, pv, hn);
}
// 放在新table的hash桶中
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
// 把旧table的hash桶中放置转发节点，表明此hash桶已经被处理
setTabAt(tab, i, fwd);
// 让线程去处理下一个区间的扩容
advance = true;
}
// 处理红黑树形式节点的迁移
else if (f instanceof TreeBin) {
TreeBin<K,V> t = (TreeBin<K,V>)f;
TreeNode<K,V> lo = null, loTail = null;
TreeNode<K,V> hi = null, hiTail = null;
int lc = 0, hc = 0;
for (Node<K,V> e = t.first; e != null; e = e.next) {
int h = e.hash;
TreeNode<K,V> p = new TreeNode<K,V>
(h, e.key, e.val, null, null);
if ((h & n) == 0) {
if ((p.prev = loTail) == null)
lo = p;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.next = p;
hiTail = p;
++hc;
}
}
ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :
(hc != 0) ? new TreeBin<K,V>(lo) : t;
hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :
(lc != 0) ? new TreeBin<K,V>(hi) : t;
// 放在新table的hash桶中
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
// 把旧table的hash桶中放置转发节点，表明此hash桶已经被处理
setTabAt(tab, i, fwd);
// 让线程去处理下一个区间的扩容
advance = true;
}
}
}
}
}
}
ConcurrentHashMap的协助扩容
协助扩容的过程其实比较简单，基本上先判断下是否需要协助扩容，如果需要且满足扩容的条件那么就为扩容尽自己的绵薄之力。
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {
Node<K,V>[] nextTab; int sc;
// 判断是否满足扩容的前提条件
if (tab != null && (f instanceof ForwardingNode) &&
(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {
int rs = resizeStamp(tab.length);
// 再次判断是否满足扩容条件
while (nextTab == nextTable && table == tab &&
(sc = sizeCtl) < 0) {
// 处理扩容已经完成的情况
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || transferIndex <= 0)
break;
// 增加扩容的线程数并开始进入transfer扩容阶段
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
transfer(tab, nextTab);
break;
}
}
// 返回扩容完成后的新数组
return nextTab;
}
return table;
}
ConcurrentHashMap的size()读过程操作
ConcurrentHashMap的size()的操作比较简单，通过一个baseCount的元素的基础个数+遍历hash桶统计各个桶上的新增的元素个数就返回了整个map的元素个数。
ConcurrentHashMap的计数的核心点在于baseCount和counterCells是如何计算的，需要进一步分析。也就是说读的逻辑非常简单，难的在于写的逻辑。
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
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;
}
ConcurrentHashMap的size()写过程的变更逻辑
ConcurrentHashMap的addCount对于计数的更新分三步走：
- 首先尝试去更新BASECOUNT的值，失败后继续执行下个步骤。
- 更新失败后尝试开始更新counterCells数组中随机的某个值，失败后继续执行下个步骤。也就是说随机更新值，和Map的映射没有任何关系。
- 执行fullAddCount()操作。
private final void addCount(long x, int check) {
CounterCell[] as; long b, s;
// 在as不存在的情况或添加baseCount失败的情况下会将值添加到counterCells当中
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
boolean uncontended = true;
// 如果as为空或者未初始化
// 如果CELLVALUE设置冲突
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();
}
private final void fullAddCount(long x, boolean wasUncontended) {
int h;
if ((h = ThreadLocalRandom.getProbe()) == 0) {
ThreadLocalRandom.localInit(); // force initialization
h = ThreadLocalRandom.getProbe();
wasUncontended = true;
}
boolean collide = false; // True if last slot nonempty
for (;;) {
CounterCell[] as; CounterCell a; int n; long v;
// cells数组已经被成功初始化
if ((as = counterCells) != null && (n = as.length) > 0) {
// 通过该值与当前线程probe求与，获得cells的下标元素，和hash 表获取索引是一样的
if ((a = as[(n - 1) & h]) == null) {
// cellsBusy 为0表示cells数组不在初始化或者扩容状态下
if (cellsBusy == 0) { // Try to attach new Cell
//创建新cell
CounterCell r = new CounterCell(x); // Optimistic create
// CAS设置cellsBusy，防止其它线程来破坏数据结构
if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean created = false;
try { // Recheck under lock
CounterCell[] rs; int m, j;
if ((rs = counterCells) != null &&
(m = rs.length) > 0 &&
rs[j = (m - 1) & h] == null) {
//将新创建的cell放入对应下标位置
rs[j] = r;
created = true;
}
} finally {
//恢复标识位(未占用)
cellsBusy = 0;
}
//操作成功，则退出死循环
if (created)
break;
continue; // Slot is now non-empty
}
}
collide = false;
}
// 获取了probe对应cells数组中的下标元素，发现不为空
// 并且调用该函数前，调用方CAS操作也已经失败（已经发生竞争）
else if (!wasUncontended) // CAS already known to fail
wasUncontended = true; // Continue after rehash
else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
break;
// 如果数组比较大了，则不需要扩容，继续重试，或者已经扩容了，重试
else if (counterCells != as || n >= NCPU)
collide = false; // At max size or stale
// 过期了，重试
else if (!collide)
collide = true;
// 对Cell数组进行扩容，CAS设置cellsBusy值
else if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
try {
if (counterCells == as) {// Expand table unless stale
//容量增加1倍
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; // Retry with expanded table
}
//重新生成一个probe值
h = ThreadLocalRandom.advanceProbe(h);
}
// 初始化Cell 数组
else if (cellsBusy == 0 && counterCells == as &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
boolean init = false;
try { // Initialize table
if (counterCells == as) {
CounterCell[] rs = new CounterCell[2];
rs[h & 1] = new CounterCell(x);
counterCells = rs;
init = true;
}
} finally {
cellsBusy = 0;
}
if (init)
break;
}
//竞争激烈，其它线程占据cell 数组，直接累加在base变量中
else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
break; // Fall back on using base
}
}
![Java小案例——随机数猜测随机数猜测[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)