上一篇说到了ConcurrentHashMap初始化
🍀添加元素 put(K key, V value)和putVal(K key, V value, boolean onlyIfAbsent)
// 将指定的键映射到此表中的指定值。 键和值都不能为空。
public V put(K key, V value) {
return putVal(key, value, false);
} // put的实现方法
final V putVal(K key, V value, boolean onlyIfAbsent) {
// 如果键值存在空值，抛出异常（键值都不允许空值）
if (key == null || value == null) throw new NullPointerException();
// 计算key的hash值，一定是个正数。（在添加元素时会判断该节点类型）
int hash = spread(key.hashCode());
// 记录某个桶的元素个数，若数超过8，会树化成红黑树
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh;
// 数组若未初始化，进行初始化。初始化方法在文章后方介绍
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// 计算hash值所在桶位置
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 如果为空则使用CAS将元素添加，与外侧的for现在自旋锁，保证线程安全
if (casTabAt(tab, i, null,
new Node<K,V>(hash, key, value, null)))
break; // no lock when adding to empty bin
}
// 由hash计算得到的桶位置元素的hash值=MOVED，表示正在扩容
else if ((fh = f.hash) == MOVED)
// 协助扩容
tab = helpTransfer(tab, f);
else {
// hash计算的桶位置元素不为空，且不在扩容状态，进行元素添加
V oldVal = null;
// 对当前桶加锁，保证线程安全，执行元素添加操作（区别于hashtable的锁全局<整张表>）
// 文章后方补充有图解
synchronized (f) {
// 再次判断，防止树化后节点位置发送变化。
//（可能的情况：两个线程同时拿到f，一个线程执行插入操作，红黑树根节点可能发送变化，释放锁。另一个线程加锁后发现根节点不是f后，需要重新获取根节点）
if (tabAt(tab, i) == f) {
// hash值大于0，是一个普通链表节点
if (fh >= 0) {
// 执行添加元素操作
binCount = 1;
for (Node<K,V> e = f;; ++binCount) {
K ek;
// 若存在该元素的hash值，则更新
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;
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;
}
}
}
}
// 添加完元素，需要判断元素个数是否>=8，即是否树化
if (binCount != 0) {
// 链表长度>=8，链表转化成红黑树
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
// 若添加的是重复键值，则返回旧值
if (oldVal != null)
return oldVal;
break;
}
}
}
// 若添加的是新元素，维护集合长度，判断是否需要扩容
addCount(1L, binCount);
return null;
}添加元素过程中，对该桶加锁的图解
🍀数组初始化 initTable
初始化表的时候用到CAS自旋锁，这样来保证线程安全。有关介绍可以参考CAS自旋锁介绍
// 使用 sizeCtl 中记录的大小初始化表。
private final Node<K,V>[] initTable() {
Node<K,V>[] tab; int sc;
// CAS 自旋，保证线程安全
while ((tab = table) == null || tab.length == 0) {
// sizeCtl 小于0，表示正在初始化 或 正在扩容
if ((sc = sizeCtl) < 0)
// 让出线程
Thread.yield(); // lost initialization race; just spin
// CAS（自旋锁） 修改sizeCtl的值为-1.成功则继续初始化，失败则继续自旋
// compareAndSwapInt 读取传入当前内存中偏移量为SIZECTL位置的值与期望值sc作比较。相等就把-1赋值给SIZECTL位置的值，再返回true。不相等则返回false。
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
if ((tab = table) == null || tab.length == 0) {
// sizeCtl为0，取默认长度DEFAULT_CAPACITY=16，否则用sizeCtl的值（回顾：sizeCtl为正数且未初始化表示数组初始容量）
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
@SuppressWarnings("unchecked")
// 构建数组对象
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
table = tab = nt;
// 计算扩容阈值=数组初始容量*0.75（回顾：sizeCtl为正数且已初始化表示数组的扩容阈值）
sc = n - (n >>> 2);
}
} finally {
// 扩容阈值赋值给sizeCtl
sizeCtl = sc;
}
break;
}
}
return tab;
}🍀链表树化成红黑树 treeifyBin
// 若表大小>=64，则链表树化成红黑树；若表大小<64，则扩容
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) {
// 表大小<64，扩容
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
// 执行扩容，变成原来的两倍，具体扩容操作下篇博文介绍
tryPresize(n << 1);
// 链表树化成红黑树
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
synchronized (b) {
if (tabAt(tab, index) == b) {
TreeNode<K,V> hd = null, tl = null;
for (Node<K,V> e = b; e != null; e = e.next) {
TreeNode<K,V> p =
new TreeNode<K,V>(e.hash, e.key, e.val,
null, null);
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
setTabAt(tab, index, new TreeBin<K,V>(hd));
}
}
}
}
}🍀维护集合长度，判断是否扩容 addCount
比如，我的初始容量是32，则扩容阈值是24（32*0.75），添加完元素后，其大小刚好24，则需要进行扩容操作。
- 当CounterCell数组不为空时，优先利用数组中的CounterCellj记录数量
- 如果数组为空，尝试对baseCount进行累加，失败之后会执行fullAddCount(x, uncontended)
- 如果是添加元素，会对数组是否需要扩容进行判断
// 添加计数，如果表太小且尚未调整大小，则启动传输。 如果已经调整大小，则在工作可用时帮助执行转移。在转移后重新检查占用情况，以查看是否已经需要再次调整大小，因为调整大小是滞后添加的。
private final void addCount(long x, int check) {
// 维护集合长度
CounterCell[] as; long b, s;
// 当CounterCell数组不为空 or 当baseCount的累加操作失败 进入此判断
if ((as = counterCells) != null ||
// 数组为空，尝试对baseCount进行累加
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
CounterCell a; long v; int m;
// 标识是否有多线程竞争
boolean uncontended = true;
// counterCells数组为空 or counterCells数组长度为0 or 当前线程对应的counterCells数组桶位的元素为空 or 当前线程对应的counterCells数组桶位不为空，但是累加失败时进入此判断
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
// 此时uncontended=false
fullAddCount(x, uncontended);
return;
}
if (check <= 1)
return;
// 计算元素个数
s = sumCount();
}
if (check >= 0) {
Node<K,V>[] tab, nt; int n, sc;
// 判断是否需要扩容操作
// 元素个数达到扩容阈值 and 数组不为空 and 数组长度小于限定的最大值时进入此判断
while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&
(n = tab.length) < MAXIMUM_CAPACITY) {
int rs = resizeStamp(n);
// sc小于0，说明有线程正在扩容，那么会协助扩容
if (sc < 0) {
// 扩容结束 or 扩容线程数达到最大值 or 扩容后的数组为null or 没有更多的桶位需要转移时，退出
if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||
sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||
transferIndex <= 0)
break;
// 扩容线程加1，成功后，进行协助扩容操作
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
// 没有其他线程在进行扩容，达到扩容阈值后，给sizeCtl赋了一个很大的负数
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2))// rs << RESIZE_STAMP_SHIFT)是一个很大的负数
// 扩容
transfer(tab, null);
s = sumCount();
}
}
}维护集合长度的具体实现源码fullAddCount解析
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;
if ((as = counterCells) != null && (n = as.length) > 0) {
if ((a = as[(n - 1) & h]) == null) {
if (cellsBusy == 0) { // Try to attach new Cell
CounterCell r = new CounterCell(x); // Optimistic create
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) {
rs[j] = r;
created = true;
}
} finally {
cellsBusy = 0;
}
if (created)
break;
continue; // Slot is now non-empty
}
}
collide = false;
}
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;
else if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
try {
if (counterCells == as) {// Expand table unless stale
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
}
h = ThreadLocalRandom.advanceProbe(h);
}
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;
}
else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
break; // Fall back on using base
}
}
🍀集合长度获取size()和sumCount()
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;
// 先获得baseCount值
long sum = baseCount;
// 如果counterCells不为空
if (as != null) {
// 遍历counterCells数组，将counterCells中每一个value相加
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
sum += a.value;
}
}
return sum;
}🍀Unsafe.compareAndSwapInt()方法解读
// 最底层是native方法，由C语言实现
public final native boolean compareAndSwapInt(Object var1, long var2, int var4, int var5);方法的作用是，读取传入对象var1在内存中偏移量为var2位置的值与期望值var4作比较。
相等就把var5值赋值给var2位置的值。方法返回true。
不相等，就取消赋值，方法返回false。
这也是CAS（比较并交换）的思想。用于保证并发时的无锁并发的安全性。
