ConcurrentHashMap
存储结构
基础知识
concurrentHashMap是线程安全的。之前安全的map用的是hashTable，但是hashTable的每一个方法都加了synchronized关键字，效率很低。
在JDK1.8中存储方式：数组+链表+红黑树。加锁的方式是桶锁。以CAS+synchronized的方式实现线程安全的。
synchronized：在出现hash冲突时（也就是node的位置已经有数据了）
JDK1.7是segment，分段锁。
put方法
实际调用的是putVal()方法
// 实际调用putval()方法，第三个参数默认传递false
public V put(K key, V value) {
// 第三个参数false，代表的是onlyIfAbsent
// 也就是如果key相同，那就进行value的覆盖操作
return putVal(key, value, false);
}
// 第三个参数为true,也就是如果key相同，那么不进行覆盖value
// 类似redis的setnx
public V putIfAbsent(K key, V value) {
return putVal(key, value, true);
}
代码演示put()和putIfAbsent()
package com.xqm.juc.concurrentHashMap;
import java.util.concurrent.ConcurrentHashMap;
public class Test01_base {
public static void main(String[] args) {
ConcurrentHashMap<String,Object> map=new ConcurrentHashMap<>();
Object result = map.put("111", "aaa");
// 返回的是null
System.out.println(result);
Object result2 = map.put("111", "bbb");
// 返回的是aaa,也就是将之前的结果覆盖掉，并且返回之前的结果
System.out.println(result2);
Object result3 = map.putIfAbsent("222", "ccc");
// 返回的是null
System.out.println(result3);
Object result4 = map.putIfAbsent("222", "ddd");
// ccc
System.out.println(result4);
// {111=bbb, 222=ccc}
// 普通的put方法会覆盖，如果key相同的话
// putIfAbsent()方法，如果key相同，不会进行覆盖操作
System.out.println(map);
}
}
putVal方法
属性变量
spread尽可能打散分散到数组的不同位置
hash不同含义
// hash值为-1时，代表当前hash位置的数据正在扩容
static final int MOVED = -1; // hash for forwarding nodes
// 代表当前Hash位置下挂载的是一个红黑树
static final int TREEBIN = -2; // hash for roots of trees
// 代表占用/预留当前索引位置
static final int RESERVED = -3; // hash for transient reservations
// 进行&运算，为了最高位一定为0
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
sizeCtl：是数组初始化和扩容操作时的一个控制变量
-1：代表当前数组正在初始化
小于-1：低16位代表当前数组正在扩容的线程个数（如果一个线程扩容，值-2，如果两个线程扩容，值为-3）
0：代表数据还没初始化
大于0：代表当前数组的扩容阈值，或者是当前数组的初始化大小
sizeCtl的高16位是基于数组长度计算的扩容戳，低16位是当前正在扩容的线程数
putVal()方法
1.判断当前数组是否为Null，也就是没有初始化，如果没有，则进行初始化
2.判断当前数组索引位置是否没有数据，如果没有，就将value放在此位置
3.判断当前数组是否正在扩容，如果正在扩容，其他线程协助进行扩容
4.到这步说明当前数组已经初始化，并且索引位置有值，并且没有在扩容。那么就对索引位置的值进行加锁。
5.DCL判断，查看是否有并发操作
6.判断是否为链表，如果是链表的话，那就循环遍历到最后一个节点，将数据加在末尾
7.判断是否为红黑树，加在红黑树中
8.如果是链表的话，判断链表长度是否超过8，如果超过8并且数组长度超过64，链表转化为红黑树
9.最后使用addCount统计数组的元素个数
final V putVal(K key, V value, boolean onlyIfAbsent) {
// concurrentHashMap的key和value不能为null
// 但是hashMap是允许为null
if (key == null || value == null) throw new NullPointerException();
// 根据key的hashcode计算出一个hash值
// 也就是散列hash值
int hash = spread(key.hashCode());
// 一个标识，表示hash所在节点下的链表的长度
int binCount = 0;
// 将ConcurrentHashMap的数组赋值给tab
// 这里是一个死循环，第一次循环进行数组的初始化
for (Node<K, V>[] tab = table;;) {
// 声明一堆变量
// n：数组长度
// i：当前Node需要存放的索引位置
// f：根据索引i获取到数组对应的值
// fh：f值的hash值
Node<K, V> f; int n, i, fh;
// 判断当前数组是否还没初始化
if (tab == null || (n = tab.length) == 0)
// 初始化数组
tab = initTable();
// (n - 1) & hash：计算数组放到哪个索引位置
// tabAt：根据索引获取数组对应的值
// 如果数组索引位置没有值
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {
// 代表当前数组位置没有数据
// 基于CAS的方式将数据存放在i位置
if (casTabAt(tab, i, null,
new Node<K, V>(hash, key, value, null)))
// 如果成功插入数据，则break跳出循环
break;
// 判断当前位置是否正在扩容
} else if ((fh = f.hash) == MOVED)
// 如果当前位置正在扩容，则让当前插入数据的线程帮助扩容
tab = helpTransfer(tab, f);
// 到这里代表数组初始化和扩容完成，并且如果数组索引位置已经有值了
else {
// 声明旧值标识符oldVal为null
V oldVal = null;
// 对当前索引位置的值进行加锁——————————————————————
synchronized (f) {
// 判断当前索引的数据是否还是之前的数据（避免并发操作带来的安全问题）
if (tabAt(tab, i) == f) {
// 如果是之前的数据，判断f的hashcode是否大于0
// 如果小于0，要么是在扩容，要么是颗树
// 大于0 说明是链表
if (fh >= 0) {
// binCount=1,用来记录链表的长度
binCount = 1;
// 死循环，每次循环，binCount+1,也就是链表长度+1
for (Node<K, V> e = f;; ++binCount) {
// 声明标识ek，就是Node的key
K ek;
// e是当前桶的位置
// 当前索引位置的数据，是否和当前put的key的hash相同
if (e.hash == hash &&
// 如果ek==key或者k.equals(ek)的话，说明key值相同
((ek = e.key) == key || (ek != null && key.equals(ek)))) {
// key值相同，那么就覆盖数据
// oldVal就是老值
oldVal = e.val;
// onlyIfAbsent为false就覆盖数据
if (!onlyIfAbsent)
e.val = value;
break;
}
// 到这，说明key值都不相同，那么就是新增在链表中，而不是覆盖
// 拿到当前桶这个节点
Node<K, V> pred = e;
// 拿到e.next节点，如果e.next为null，如果不是null,进行下一次循环
if ((e = e.next) == null) {
// 新增节点
pred.next = new Node<K, V>(hash, key, value, null);
// 跳出循环
break;
}
}
// 判断f的hashCode是否是红黑树
} 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;
}
}
}
}
// 链表长度不为0
if (binCount != 0) {
// 如果链表长度是否大于等于8
if (binCount >= TREEIFY_THRESHOLD)
// 尝试将链表转为红黑树
// tab就是当前的数组，i是当前数组的索引下标
treeifyBin(tab, i);
// 如果出现了数据覆盖的情况
if (oldVal != null)
// 直接返回被覆盖的数据
return oldVal;
break;
}
}
}
//统计数组元素个数
addCount(1L, binCount);
return null;
}
1
tabAt()-获取数组索引位置的值
// 计算数组放到哪个索引位置的方法
// 这里的n-1，如果数组长度是17，那么n-1就是16，那么计算索引的时候冲突很大，因为0001 0000,只和1位有关
// 所以要求数组长度为2^n
f = tabAt(tab, i = (n - 1) & hash)) == null
spread()方法：计算散列hash值
// 计算hash值
// h是key的hashcode
// static final int HASH_BITS = 0x7fffffff; 也就是01111111 11111111 11111111 11111111
static final int spread(int h) {
// 将key的hashcode进行高低16位的异或运算，然后和HASH_BITS进行&运算
// h^(h>>>16)的目的就是为了让h的高16位也参与到计算索引运算中。
// 因为数组长度一开始比如16位，那高位全部都是0，进行&运算的时候，key的hashCode的高位没法参与到计算索引的运算中
// 为什么hashMap、currentHashMap都要求数组长度为2^n,为了计算数组索引时冲突小一点
// & HASH_BITS 这个操作的目的就是为了让最高位符号位一定为0，也就是默认为正数。因为hash值为负数时，有特殊的含义
return (h ^ (h >>> 16)) & HASH_BITS;
}
Node()-新建Node节点
// new Node,next是下一个节点
Node(int hash, K key, V val, Node<K, V> next) {
this.hash = hash;
this.key = key;
this.val = val;
this.next = next;
}
initTable()-数组初始化
1.循环判断数组是否没有初始化
2.通过sizeCtl<0，表示数组正在扩容或初始化，那么当前线程yield
3.否则就通过CAS方式将sizeCtl从0改为1，进行数组初始化操作
4.加锁
5.DCL判断，数组是否已被修改
6.没有修改的话，初始化数组，长度为自定义的sizeCtl，如果sizeCtl<0，那就初始化默认值16
7.将sizeCtl设置为当前数组长度n-(n>>>2)
8.返回初始化后的数组
// initTab初始化数组方法
private final Node<K, V>[] initTable() {
// 声明两个标识
// tab：当前数组
Node<K, V>[] tab; int sc;
// 再次判断数组没有初始化，并且完成table的赋值
while ((tab = table) == null || tab.length == 0) {
// sizeCtl赋值给sc，并判断是否小于0
// 也就是如果正在初始化或者扩容，那么啥也不做
if ((sc = sizeCtl) < 0)
// 线程啥也不做
Thread.yield();
// 到这代表还没初始化，可以开始初始化
// 线程使用CAS将SIZECTL的值，从sc改为-1，代表当前线程可以初始化数组
else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
// 再次判断当前数组是否已初始化完毕，和单例模式的DCL很相似
if ((tab = table) == null || tab.length == 0) {
// 开始初始化，如果是指定大小，就初始化sc大小的数组，否则初始化默认值（16）
int n = (sc > 0) ? sc : DEFAULT_CAPACITY;
// 初始化数组
Node<K, V>[] nt = (Node<K, V>[])new Node<?, ?>[n];
// 将初始化的数组赋值给tab和table
table = tab = nt;
// sc赋值为数组长度-数组长度右移两位，也就是n-n/4
// 将sc赋值为下次扩容的值
sc = n - (n >>> 2);
}
} finally {
// 下次扩容的值
sizeCtl = sc;
}
// 扩容成功，跳出循环
break;
}
}
// 返回扩容后的数组
return tab;
}
为什么链表长度为8时转化为红黑树
泊松分布
http://en.wikipedia.org/wiki/Poisson_distribution
- 0: 0.60653066
- 1: 0.30326533
- 2: 0.07581633
- 3: 0.01263606
- 4: 0.00157952
- 5: 0.00015795
- 6: 0.00001316
- 7: 0.00000094
- 8: 0.00000006
- more: less than 1 in ten million
因为超过8之后，转化为红黑树的希望很渺茫
扩容
treeifyBin方法触发扩容操作
treePreSize方法尝试预先调整表的大小以容纳给定数量的元素
transfer方法声明新数组并迁移数据
helpTransfer方法协助扩容
treeifyBin
treeifyBin方法触发扩容操作。在插入一个数据后，判断链表的长度是否超过8，调用这个方法。
如果链长度超过8并且数组长度不超过64，那就进行扩容操作，否则将链表转化为红黑树。
1.如果数组不为null，并且数组的长度小于64，调用tryPresize(n)方法进行数组的扩容操作
2.否则当前桶的内数据不为null，并且hash值大于0（没有正在扩容的线程），那就加锁，然后将链表转化为红黑树
3.DCL判断当前桶内数据是否改变，如果未改变，遍历链表，将链表的节点数据封装成TreeNode，并按顺序进行next的连接
4.调用new TreeBin()，将TreeNode转化为红黑树
5.setTabAt方法写入数据
// 将链表转为红黑树
// tab就是当前的数组，index是当前的索引下标
private final void treeifyBin(Node<K, V>[] tab, int index) {
Node<K, V> b; int n, sc;
// 如果tab不为null
if (tab != null) {
// 如果数组的长度没有超过64，那么就尝试扩容，因为数组操作是比红黑树效率高
if ((n = tab.length) < MIN_TREEIFY_CAPACITY)
tryPresize(n << 1);
// 如果数组的长度超过64，那么就将链表转化为红黑树
// 当前桶内有数据，并且是链表结构（b.hash >= 0）
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
// 转红黑树的时候加锁，保证线程安全
synchronized (b) {
// 再次判断数据是否有变化
if (tabAt(tab, index) == b) {
// 开启准备操作，将之前链表中的Node，封装成TreeNode,作为双向链表
// 声明hd tl
// hd是指向双向链表的第一个节点
// tl是双向链表生成过程中的变量
TreeNode<K, V> hd = null, tl = null;
// 循环所有的node
for (Node<K, V> e = b; e != null; e = e.next) {
// 封装成treeNode,将prev、next都置为null
TreeNode<K, V> p = new TreeNode<K, V>(e.hash, e.key, e.val, null, null);
// 第一个节点的前置节点指向null
// 对节点的prev和next赋值
if ((p.prev = tl) == null)
hd = p;
else
tl.next = p;
tl = p;
}
// hd是双向链表的第一个节点，可以通过hd查找到整个双向链表
// TreeBin的有参构造，将双向链表转换为红黑树
setTabAt(tab, index, new TreeBin<K, V>(hd));
}
}
}
}
}
treePreSize
treePreSize方法尝试预先调整表的大小以容纳给定数量的元素
// 扩容操作，这里的size是数组长度的2倍
private final void tryPresize(int size) {
// >>>代表无符号右移
// MAXIMUM_CAPACITY为1<<30,也就是2的30次方
// 如果扩容扩到了最大长度，就使用最大值。否则需要保证数组的长度为2^n
// 这块操作是为了putAll的初始化操作准备的，因为调用putAll()方法时，也会触发tryPresize方法
int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :
// 获取离比size+(size >>> 1)+1大的最近的2的n次幂
tableSizeFor(size + (size >>> 1) + 1);
// 下面这些代码和initTable代码差不多
// 声明sc
int sc;
// 将sizeCtl赋值给sc，如果大于等于0，表示还没初始化或者正在扩容操作
// 也就是没有初始化操作，也没有扩容操作
while ((sc = sizeCtl) >= 0) {
// 将table数组赋值给tab，并声明数组的长度n
Node<K, V>[] tab = table; int n;
// 如果数组为null或者数组的长度为0，那么就需要执行初始化数组
if (tab == null || (n = tab.length) == 0) {
// 如果sc初始化长度比计算出来的数组的长度c大的话，用初始化长度
// 否则就表示sc无法容纳putAll传入的map,就用计算出来的长度
n = (sc > c) ? sc : c;
// 设置sizeCtl为-1,表示正在执行初始化操作
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
try {
// 再次判断数组的引用有没有变化
if (table == tab) {
// 初始化数组
Node<K, V>[] nt = (Node<K, V>[])new Node<?, ?>[n];
// 数组赋值
table = nt;
// 设置下一次数组扩容的长度
sc = n - (n >>> 2);
}
} finally {
// 最终赋值给sizeCtl
sizeCtl = sc;
}
}
// 如果c(计算出来的2^n)小于sc，下次扩容的长度或者n数组长度大于最大值
} else if (c <= sc || n >= MAXIMUM_CAPACITY)
// 直接退出循环
break;
// 判断当前的tab是否和table相同，防止并发操作。如果相同，说明没被修改过
else if (tab == table) {
// 计算扩容标识戳，根据当前数组的长度计算一个16位的时间戳，只占int类型的后16位
int rs = resizeStamp(n);
// sc小于0 ，说明有线程正在扩容
// 关键是，上面的while循环要求sc>=0，所以这里的代码永远不满足要求，也就是用不到这段代码
if (sc < 0) {
// 有线程正在扩容的话，其他线程应该过来帮助扩容
Node<K, V>[] nt;
// 当前线程扩容时，老数组长度是否和我当前线程扩容时的老数组长度一致
if ((sc >>> RESIZE_STAMP_SHIFT) != rs
// 这里永远不会相等，没什么意义
// 这两个判断都是有问题的，核心问题应该先将rs左移16位，再追加当前值
|| sc == rs + 1 // 应该时sc==rs<<16+1
// 判断当前扩容的线程是否达到了最大限度
|| sc == rs + MAX_RESIZERS // 应该是sc == (rs << 16) + MAX_RESIZERS
// 扩容已经结束了
|| (nt = nextTable) == null
// 记录迁移的索引位置，从高位往低位进行迁移，代表扩容即将结束
|| transferIndex <= 0)
break;
// 如果线程需要协助扩容，首先要对szieCtl进行加1操作，表示当前要进来一个线程协助扩容
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
// nt代表新数组
transfer(tab, nt);
// 说明没有线程在扩容，当前线程是第一个进行扩容的线程
// CAS操作修改sizeCtl
} else if (U.compareAndSwapInt(this, SIZECTL, sc,
// 将扩容戳rs左移16位，加2
// 左移16位，符号位为1，表示是负数
// 加2，表示是1个线程
// 每一个线程扩容完毕后，会对低16位进行-1操作，当最后一个线程扩容完毕后，减1的结果为-1
// 当值为-1时，要对老数组进行扫描，查看是否有遗漏的数据没有迁移到新数组
(rs << RESIZE_STAMP_SHIFT) + 2))
// 调用transfer方法，并且将第二个参数设置为null,就代表是第一次来扩容
transfer(tab, null);
}
}
}
tableSizeFor
tableSizeFor为了保证数组的长度为2^n
// 函数的作用是保证当前的数据长度为2^n
// 把c这个长度设置到比c大的最近的2的n次幂的值，比如15，那就返回16，17就返回32
// c=size + (size >>> 1) + 1,size是数组长度的两倍
// 加入size是17，最后c为26
// 00000000 00000000 00000000 00010001 假如size为17
//+
// 00000000 00000000 00000000 00001000 size>>>1
//+
// 00000000 00000000 00000000 00000001 1
// =
// 00000000 00000000 00000000 00011010 c=2+8+16=26
private static final int tableSizeFor(int c) {
// n=26-1=25
// 00000000 00000000 00000000 00011001
int n = c - 1;
// 00000000 00000000 00000000 00011001 n
// 00000000 00000000 00000000 00001100 n>>>1
// 00000000 00000000 00000000 00011101 |=是或运算，n=29
n |= n >>> 1;
// 00000000 00000000 00000000 00011101 n
// 00000000 00000000 00000000 00000111 n>>>2
// 00000000 00000000 00000000 00011111 |=是或运算，n=31
n |= n >>> 2;
// 00000000 00000000 00000000 00011111 n
// 00000000 00000000 00000000 00000001 n>>>2
// 00000000 00000000 00000000 00011111 |=是或运算，n=31
n |= n >>> 4;
// 还是n=31
n |= n >>> 8;
// n=31
n |= n >>> 16;
// 返回n+1，也就是32
return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
resizeStamp
计算扩容标识戳
作用：
1.后期操作时，保证sizeCtl为负数.（因为前面16位为0，后面16位的第一位为1，可以表示为负数）
2.记录当前数组是从什么长度开始扩容的
// 计算扩容标识戳
static final int resizeStamp(int n) {
// Integer.numberOfLeadingZeros(n)方法是用二进制表示n的时候，从前往后数到第一个不为0的数时，前面有多少个0
// 比如32=00000000 00000000 00000000 00100000，那么返回的就是26
// 1 << (RESIZE_STAMP_BITS - 1)就是1左移15位
// 最后进行或运算
// 00000000 00000000 00000000 00011010 26
// 00000000 00000000 10000000 00000000 1 << (RESIZE_STAMP_BITS - 1
// 00000000 00000000 10000000 00011010 或运算的结果
return Integer.numberOfLeadingZeros(n) | (1 << (RESIZE_STAMP_BITS - 1));
}
helpTransfer
helpTransfer协助扩容
// helpTransfer --协助扩容操作
// 添加数据时，如果插入节点位置的数据的hash值为-1，代表当前索引位置数据已经被迁移到新数据
// tab是旧数组，f是索引位置的数据
final Node<K, V>[] helpTransfer(Node<K, V>[] tab, Node<K, V> f) {
// nextTab：新数组
// sc:sizeCtl的临时遍历
Node<K, V>[] nextTab; int sc;
// 旧数组不为null
if (tab != null
// 桶位置数据是fwd
&& (f instanceof ForwardingNode)
// 判断新数组不为null,将新数组赋值给nextTab
&& (nextTab = ((ForwardingNode<K, V>)f).nextTable) != null) {
// 新数组和旧数组都不为null，说明正在扩容
// 获取扩容戳
int rs = resizeStamp(tab.length);
// fwd中的新数组是否等于当前正在扩容的新数组
// 如果相等，可以协助扩容，如果不相等，要么扩容结束，要么开启新扩容那个
while (nextTab == nextTable
// 老数组是否改变了
&& table == tab &&
// 如果正在扩容，sizeCtl
(sc = sizeCtl) < 0) {
// 将sc右移16位，判断是否与扩容戳一致，如果不一致，说明扩容长度不一样，退出协助扩容
if ((sc >>> RESIZE_STAMP_SHIFT) != rs
// 第二个第三个判读是bug,应该是sc==(rs << 16)+1和sc == (rs << 16) + MAX_RESIZERS
// 扩容已经到最后检查阶段
|| sc == rs + 1
// 判断协助扩容的线程是否已经到达最大值
|| sc == rs + MAX_RESIZERS
// 如果任务被领光了，transferIndex从高索引到低索引领取数据的核心属性
|| transferIndex <= 0)
// 直接退出
break;
// 扩容的线程+1
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1)) {
// 协助扩容
transfer(tab, nextTab);
break;
}
}
return nextTab;
}
return table;
}
Transfer
transfer方法声明新数组并迁移数据，真正开始扩容的方法
lastRun机制
//transfer方法 开始扩容
// tab是旧数组，netxTab第一次扩容是null
private final void transfer(Node<K, V>[] tab, Node<K, V>[] nextTab) {
// n：获得旧数组的长度
// stride：声明stride变量，每个线程每次迁移多少数据到新数组，也就是步长
int n = tab.length, stride;
// 基于CPU的内核数量来计算，每个线程一次性迁移多少长度的数据最合理
// static final int NCPU = Runtime.getRuntime().availableProcessors();
// 例子：n=1024 那么n>>>3=128 NCPU假设为4核 stride=32
// MIN_TRANSFER_STRIDE：最小迁移长度，默认为16
if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)
// 如果stride小于16，那么就设置为16
stride = MIN_TRANSFER_STRIDE; // subdivide range
// 如果是第一次扩容
if (nextTab == null) { // initiating
try {
// 初始化新数组为旧数组长度的2倍
Node<K, V>[] nt = (Node<K, V>[])new Node<?, ?>[n << 1];
// nextTab设置为新数组
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
// 到这说明已经到达数组长度的最大取值范围
sizeCtl = Integer.MAX_VALUE;
// 设置sizeCtl之后直接结束，不需要扩容，因为已经到达最大值了
return;
}
// nextTable：下一个要使用的表；仅在调整大小时为非空。
// 为ConcurrentHashMap的成员变量，其他线程也就能得到下一个数组
nextTable = nextTab;
// 迁移数据时用到的标识，默认为旧数组长度
transferIndex = n;
}
// 新数组的长度
int nextn = nextTab.length;
// 老数组迁移完做的标识 ForwardingNode
ForwardingNode<K, V> fwd = new ForwardingNode<K, V>(nextTab);
// 迁移数据时需要用到的标识
// advance：为true，代表当前线程需要接受任务，然后再执行迁移
// advance：为false,表示已接受完任务
boolean advance = true;
// finishing：表示是否已迁移结束
boolean finishing = false; // to ensure sweep before committing nextTab
// 循环
// i：代表当前线程迁移数据的索引值
for (int i = 0, bound = 0;;) {
// 声明f
// fh
Node<K, V> f; int fh;
// 代表当前线程需要接受任务
while (advance) {
// 声明nextIndex,nextBound
int nextIndex, nextBound;
// 第一次进来，这两个判断肯定进不去
// 对i进行--，并且判断当前任务是否结束
if (--i >= bound || finishing)
advance = false;
// 判断transferIndex是否小于等于0，，如果小于等于0，代表没有任务可接
// 线程领取完任务后，会对tarnsferIndex进行修改，修改为nextIndex - stride（也就是transferIndex-stride）
else if ((nextIndex = transferIndex) <= 0) {
// 索引为-1，代表全部迁移完了
i = -1;
advance = false;
// 当前线程开始尝试领取任务
// nextIndex=transferIndex
// 使用CAS将transferInex赋值为nextBound
} else if (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ? nextIndex - stride : 0))) {
// 对bound进行赋值
bound = nextBound;
// 对i赋值
i = nextIndex - 1;
// 设置advance,代表当前线程领取到任务
advance = false;
}
}
// 判断扩容是否已结束
// i<0 代表当前线程没有接收到任务
// i>=n i是迁移的索引位置，要大于等于数组长度，这个条件不可能成立
// i + n >= nextn i的最大值就是数组索引的最大值，加上n数组长度，不可能超过新数组的长度
if (i < 0 || i >= n || i + n >= nextn) {
// 因此如果进来，只代表i<0,也就是当前线程没接收到任务
int sc;
// finishing代表扩容结束
if (finishing) {
// 将变量nextTable设置为null,留待之后扩容继续使用
nextTable = null;
// 将临时代表新数组的nextTab引用指向新数组table
// table：bin 数组。在第一次插入时延迟初始化。 * 大小始终是 2 的幂。由迭代器直接访问
table = nextTab;
// 重新计算扩容阈值（0.75倍数）
sizeCtl = (n << 1) - (n >>> 1);
// 真正的结束扩容
return;
}
// 当前线程没接收到任务，让当前线程结束扩容任务
// 采用CAS的方式，将sizeCtl-1，代表当前并发扩容的线程数-1
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
// sizeCtl的高16位是基于数组长度计算的扩容戳，低16位是当前正在扩容的线程数
// 这里表示当前线程不是最后一个退出扩容的线程，直接退出
// sc-2如果低16位全部是0 ，说明是最后一个退出的线程
// resizeStamp(n) << RESIZE_STAMP_SHIFT左移16位之后低16位肯定全部是0
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)
return;
// 如果是最后一个退出的，那就说明扩容结束，finishing=true
finishing = advance = true;
// 将i设置为旧数组长度，让最后一个线程将旧数组从尾到头再检查一遍
i = n; // recheck before commit
}
// 比如数组长度为32的话，那么i从31开始，因为是索引位置，一直往前到索引为0的位置进行迁移数据
// 如果索引位置i的Node对象为null，就是没有数据
} else if ((f = tabAt(tab, i)) == null)
// 直接将当前桶位置设置为forwardingNode(特点是hash值为-1，代表当前位置已迁移完毕)
advance = casTabAt(tab, i, null, fwd);
// 拿到当前i位置的hash值，如果为MOVED也就是-1，那么代表已经迁移过了
else if ((fh = f.hash) == MOVED)
// 这个判断是给最后扫描使用的，看是否有漏迁移的数据
advance = true; // already processed
else {
// 到这里代表当前桶位置有数据，先锁住当前桶位置
synchronized (f) {
// 判断之前取出的数据是否为当前数据，防止并发操作
if (tabAt(tab, i) == f) {
// ln:null--lowNode
// hn:null--highNode
Node<K, V> ln, hn;
// fh是f的hash值，hash值大于0，代表当前Node属于正常状态，也就是是链表
if (fh >= 0) {
// 这里几行代码，被称为lastRun机制，也就是直到for循环的位置，实际为了优化迁移
// n是数组长度，2的n次方，那么二进制中只会有1个1，其他全为0
// 做与运算，结果只能有两种，，要不是0，要不是n
// 是0代表索引i位置的数据f。根据新数组的长度，计算出来的新的hash值还是原来的hash值
// 是1代表索引i位置的数据f。根据新数组的长度，计算出来的新的hash值是原来的hash值+旧数组的长度，
// 比如原来数组长度为32，索引为1位置的hash值为1，那么迁移到新数组，重新计算出来的索引位置不是1就是33（1+32）
int runBit = fh & n;
// 将f的数据赋值给lastRun
Node<K, V> lastRun = f;
// 从fNode开始，往下遍历，上面runBit的结果是第一个节点的结果，所以从f.next开始
// 循环的目的就是为了得到结果一致的最后一些数据
// 在迁移数据时，只需要迁移到lastRun位置，剩下的runBit都是相同的
for (Node<K, V> p = f.next; p != null; p = p.next) {
// 计算p节点与上数组长度后，结果是0还是n，也就是新的hash位置是原来位置还是要加上数组长度
int b = p.hash & n;
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
// 如果runBit==0,则赋值给ln,也就是低位，和旧数组相同的位置
if (runBit == 0) {
ln = lastRun;
hn = null;
// 否则赋值给hn，旧数组位置+旧数组长度的位置
} else {
hn = lastRun;
ln = null;
}
// 循环到lastRun位置指向的数据即可，后续不需要再遍历，直接全部迁移就行
for (Node<K, V> p = f; p != lastRun; p = p.next) {
// 拿到链表的hash、key、value
int ph = p.hash; K pk = p.key; V pv = p.val;
if ((ph & n) == 0)
// 将Node放到地位ln-lowNode
ln = new Node<K, V>(ph, pk, pv, ln);
else
// 将Node放到地位ln-highNode
hn = new Node<K, V>(ph, pk, pv, hn);
}
// 采用CAS的方式，将ln挂到新数组原来的位置
setTabAt(nextTab, i, ln);
// 采用CAS的方式，将hn挂到新数组+旧数组长度的位置
setTabAt(nextTab, i + n, hn);
// 采用CAS的方式，将当前桶位置设置为fwd
setTabAt(tab, i, fwd);
// 将advance设置为true,保证进入上面的while循环中，开始下一个节点的迁移
advance = true;
// 红黑树进行迁移，TreeBin中不仅有红黑树，而且还有双向链表
} 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;
// lc和hc记录高低位数据的长度，如果树的长度小于8，就会变为双向链表
int lc = 0, hc = 0;
// first是双向链表的头
// 遍历TreeBin中的双向链表
for (Node<K, V> e = t.first; e != null; e = e.next) {
// 获取节点的hash值
int h = e.hash;
TreeNode<K, V> p = new TreeNode<K, V>(h, e.key, e.val, null, null);
// n是旧数组的长度，基于结果确认树节点迁移存放到高位还是低位
// 将节点存放到低位
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;
}
}
// UNTREEIFY_THRESHOLD是6，如果小于等于6，转换成链表，否则转成红黑树
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;
// 迁移数据到新数组
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
// 当前位置迁移完毕，设置fwd
setTabAt(tab, i, fwd);
// 开启前一个节点的数据迁移
advance = true;
}
}
}
}
}
}
红黑树
红黑树的结构
是一种自平衡二叉树。
特点：
1、左子树和右子树的高度差不超过1，如果查过了，就会通过左旋和右旋的方式进行自平衡
2、每个节点不是红色就是黑色
3、根节点是黑色
4、如果当前节点是红色，那么子节点一定是黑色
5、所有的叶子节点都是黑色（如果最后的子节点是红色，会生成空的黑色节点作为叶子节点）
6、从任意节点到叶子节点的路径中，黑色节点的数量是相同的
变色操作：红色->黑色 黑色->红色。变色操作是在增删操作之后，可能发生的操作。插入数据时，插入的节点的颜色一般是红色，因为插入红色节点破坏红黑树结构的可能性比较低。如果插入红色也破坏了红黑树结构，那么就需要通过变色来调整结构。
红黑树比较复杂，完整代码400-500行，没必要全部记住。
treeifyBin
treeifyBin中封装了双向链表
TreeBin整体构造
treeBin有参构造函数，双向链表转红黑树的过程
treeBin中不但保存了红黑树结构，而且还保存了一套双向链表
treeBin中的属性
// TreeBin的锁操作
// 如果说有读线程在读取红黑树的数据，这时，写线程要阻塞（做平衡前）
// 如果说有写线程在写数据的时候（做平衡），读线程不会阻塞，读线程会读取双向链表
// 读读不会阻塞，没有写写并发操作（因为会获取锁）
static final class TreeBin<K, V> extends Node<K, V> {
// 树的根节点
TreeNode<K, V> root;
// 双向链表的头节点
volatile TreeNode<K, V> first;
// 等待获取写锁的线程
volatile Thread waiter;
// 当前TreeBin的锁状态
volatile int lockState;
// 对锁线程进行运算的值
// 有线程拿着写锁
static final int WRITER = 1;
// 有写线程，在等待获取写锁
static final int WAITER = 2;
// 读线程，在红黑树中检索时，需要先对lockState+READER
// 这个只会在读操作中遇到
static final int READER = 4;
// 判断节点应该放的位置，hash值比较的compare，如果小于等于，就赋值为-1，也就是放在左子树
// 当节点的hash相等，key相等，compare相等才会使用这个方法
static int tieBreakOrder(Object a, Object b) {
....
}
// 有参构造
TreeBin(TreeNode<K, V> b) {
...
}
/**
* 加锁-写锁
*/
private final void lockRoot() {
// 使用CAS将lockState从0设置为1，代表拿到写锁成功
if (!U.compareAndSwapInt(this, LOCKSTATE, 0, WRITER))
// 如果写锁没拿到，执行contendedLock（）
contendedLock();
}
/**
* 释放锁
*/
private final void unlockRoot() {
// 释放写锁
lockState = 0;
}
/**
* 获取写锁失败时的操作
*/
private final void contendedLock() {
// 是否有线程正在等待，默认为false
boolean waiting = false;
// 死循环，s是lockState的临时操作
for (int s;;) {
// 00000010 WAITER
// 11111101 ~WAITER
// 如果要s & ~WAITER 为0的话，s=00000000或者00000010
// 也就是当前写锁和读锁都没有线程获取
if (((s = lockState) & ~WAITER) == 0) {
// 尝试使用CAS将lockState修改为1，拿到写锁
if (U.compareAndSwapInt(this, LOCKSTATE, s, WRITER)) {
// 成功拿到锁资源，判断是否在waiting
if (waiting)
// 如果有线程在等待，那么直接将之前等待的线程设为null
waiter = null;
return;
}
// 到这说明有写线程在占用写锁
// 00000010 WAITER
// 如果要s & WAITER 为0的话，s=00000000(读锁和写锁都没被占用)或者00000100(读锁被占用)
// 说明当前没有写线程挂起等待
} else if ((s & WAITER) == 0) {
// 基于CAS，将lockstate的第二位设置为1（ s | waiter ）,或运算
if (U.compareAndSwapInt(this, LOCKSTATE, s, s | WAITER)) {
// 如果成功，代表当前线程可以挂起等待了
waiting = true;
waiter = Thread.currentThread();
}
} else if (waiting)
// 挂起当前线程，会由读线程唤醒
LockSupport.park(this);
}
}
/**
* 查找节点
*/
final Node<K, V> find(int h, Object k) {
....
}
/**
* 在红黑树中添加节点
* @return null if added
*/
final TreeNode<K, V> putTreeVal(int h, K k, V v) {
....
}
/**
* 移除树节点
*/
final boolean removeTreeNode(TreeNode<K, V> p) {
....
}
/* ------------------------------------------------------------ */
//左旋操作
static <K, V> TreeNode<K, V> rotateLeft(TreeNode<K, V> root,
TreeNode<K, V> p) {
....
}
// 右旋操作
static <K, V> TreeNode<K, V> rotateRight(TreeNode<K, V> root,
TreeNode<K, V> p) {
....
}
// 平衡红黑树操作--插入之后
static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root,
TreeNode<K, V> x) {
....
}
// 平衡红黑树操作--删除之后
static <K, V> TreeNode<K, V> balanceDeletion(TreeNode<K, V> root,
TreeNode<K, V> x) {
....
}
/**
* 操作过后，循环检查红黑树
*/
static <K, V> boolean checkInvariants(TreeNode<K, V> t) {
.....
}
private static final sun.misc.Unsafe U;
private static final long LOCKSTATE;
static {
try {
U = sun.misc.Unsafe.getUnsafe();
Class<?> k = TreeBin.class;
LOCKSTATE = U.objectFieldOffset
(k.getDeclaredField("lockState"));
} catch (Exception e) {
throw new Error(e);
}
}
}
treeBin方法具体实现
// treeBin--链表转红黑树
TreeBin(TreeNode<K, V> b) {
// 构建Node，并且将hash值设置为-2,代表node下是一个红黑树而不是链表
super(TREEBIN, null, null, null);
// 双向链表的头节点赋值给first
this.first = b;
// 声明 TreeNode类型的r，最后赋值为根节点
TreeNode<K, V> r = null;
// 循环遍历双向链表
for (TreeNode<K, V> x = b, next; x != null; x = next) {
// 当前节点的下一个节点
next = (TreeNode<K, V>)x.next;
// 一开始根节点的左节点和右节点都为null
x.left = x.right = null;
// 如果根节点为null，这是第一次循环进去做的初始化操作
if (r == null) {
// 第一个节点的父节点为null
x.parent = null;
// 第一个节点为黑色
x.red = false;
// 将第一个节点设置为root节点
r = x;
// 已经有根节点了，当前
} else {
// 拿到当前节点的key和hash值
// k:当前节点的key
// h:当前节点的hash
K k = x.key;
int h = x.hash;
Class<?> kc = null;
// 进行循环，判断插入的节点应该放在哪个位置
// 从根节点开始找,p就是当前父节点
for (TreeNode<K, V> p = r;;) {
// dirL:如果为-1，代表要插入到父节点的左边，如果为1，代表要插入到父节点的右边
// ph是父节点的hash值
int dir, ph;
// pk:父节点的key
K pk = p.key;
// 如果父节点的hash大于当前节点的hash
if ((ph = p.hash) > h)
// 那么应该放到根节点的左边
dir = -1;
// 否则放到父节点的右边
else if (ph < h)
dir = 1;
// 父节点的hash等于当前节点的hash
// 如果hash值相同，那么根据key来判断，因为key是不可能相同的
// 基于compare方式判断到底放在左子树还是右子树
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
(dir = compareComparables(kc, k, pk)) == 0)
dir = tieBreakOrder(k, pk);
// 拿到当前父节点
TreeNode<K, V> xp = p;
// 如果dir小于0，将p.left赋值给p,否则p就是p.right
// 如果这里新的p为null，代表当前节点的左子树或者右子树没有子节点，那么直接赋值就行
// 否则继续往下循环找到当前节点的位置
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// 进入if，代表已经找到当前节点存的位置
// 当前节点的父节点指向parent节点
x.parent = xp;
// 如果小于0，插入左节点
if (dir <= 0)
xp.left = x;
else
// 插入右节点
xp.right = x;
// 插入完成之后，进行平衡二叉树的操作（左旋、右旋、变色）
r = balanceInsertion(r, x);
break;
}
}
}
}
// 将根节点赋值给root
this.root = r;
// 检查红黑树结构
assert checkInvariants(root);
}
balanceInsertion
balanceInsertion()方法是红黑树进行平衡的操作，变色、左旋、右旋
// 红黑树进行平衡操作
// root：根节点，x是当前节点（插入的节点，每次插入新节点都要做平衡操作）
static <K, V> TreeNode<K, V> balanceInsertion(TreeNode<K, V> root,TreeNode<K, V> x) {
// 先将当前节点置为红色
x.red = true;
// 声明四个变量
// xp:当前节点的父节点
// xpp:当前节点的父节点的父节点
// xppl:爷爷节点的左子树
// xppr:爷爷节点的右子树
for (TreeNode<K, V> xp, xpp, xppl, xppr;;) {
// 拿到父节点，并且父节点为null，说明是第一个节点，也就是根节点，那么是黑色的，直接return
if ((xp = x.parent) == null) {
x.red = false;
// x就是根节点
return x;
// 父节点不是红色 || 爷爷节点为null
} else if (!xp.red || (xpp = xp.parent) == null)
// 那么直接返回，什么都不做，不需要做平衡
return root;
// 到这里，代表可能会需要做变色或者左旋、右旋的操作
// 左子树的操作
// 如果当前节点的父节点是爷爷节点的左节点
if (xp == (xppl = xpp.left)) {
// 爷爷节点的右节点不为null并且是红色的
// 说明满足平衡的条件，但是不满足红色节点的子节点是黑色节点这个条件
if ((xppr = xpp.right) != null && xppr.red) {
// 叔叔节点变为黑色
xppr.red = false;
// 父节点变为黑色
xp.red = false;
// 爷爷节点变为红色
xpp.red = true;
// 将x指向的当前节点修改为指向爷爷节点
// 也就是将爷爷节点作为当前节点，再次走一遍循环
x = xpp;
// 这里说明当前节点没有叔叔节点，也就是爷爷节点的右节点，需要进行旋转操作
} else {
// 当前节点是父节点的右节点，需要做左旋操作，也就是强行转成左子树
if (x == xp.right) {
root = rotateLeft(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
// 再次进行旋转操作,x就是左子树的叶子节点
if (xp != null) {
// 将父节点改为黑色
xp.red = false;
// 如果爷爷节点不为null，那么爷爷节点就需要变为红色，并进行右旋操作
if (xpp != null) {
// 爷爷节点变为红色
xpp.red = true;
// 右旋
root = rotateRight(root, xpp);
}
}
}
// 右子树的操作，和左子树一样
} else {
if (xppl != null && xppl.red) {
xppl.red = false;
xp.red = false;
xpp.red = true;
x = xpp;
} else {
if (x == xp.left) {
root = rotateRight(root, x = xp);
xpp = (xp = x.parent) == null ? null : xp.parent;
}
if (xp != null) {
xp.red = false;
if (xpp != null) {
xpp.red = true;
root = rotateLeft(root, xpp);
}
}
}
}
}
}
putTreeVal
在putVal()方法中用到，新增数据的时候，如果是红黑树的话，进行新增。
如果节点key已存在，那么就返回新增的节点，如果插入成功，就返回null
// putTreeVal
// 往红黑树中新增数据
final TreeNode<K, V> putTreeVal(int h, K k, V v) {
Class<?> kc = null;
// 搜索节点
boolean searched = false;
// 死循环，将根节点赋值给临时节点p
for (TreeNode<K, V> p = root;;) {
// dirL:如果为-1，代表要插入到父节点的左边，如果为1，代表要插入到父节点的右边
// ph：临时节点p的hash值
// pk：临时节点p的key值
int dir, ph; K pk;
// 第一次循环的p为根节点，判断是否为null
if (p == null) {
// 如果根节点为null,直接将新增的节点置为root
first = root = new TreeNode<K, V>(h, k, v, null, null);
// 新增结束，直接退出
break;
// 判断当前节点是放在左子树还是右子树
} else if ((ph = p.hash) > h)
// 如果小就放在左边
dir = -1;
else if (ph < h)
// 如果大就放在右边
dir = 1;
// 如果hash值相等，并且key值相同，那就直接返回
// 由putVal去判断是否需要修改，然后去修改
else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
return p;
// 如果hash值相同，但是key不同的话，基于compare去判断到底插入什么位置
else if ((kc == null &&
(kc = comparableClassFor(k)) == null) ||
// 如果基于compare判断也相同放入话，就必须基于搜索来查看是否有相同的数据
(dir = compareComparables(kc, k, pk)) == 0) {
// 开启搜索
if (!searched) {
TreeNode<K, V> q, ch;
// 只会执行一次
searched = true;
// 基于左子树、右子树进行搜索
if (((ch = p.left) != null &&
(q = ch.findTreeNode(h, k, kc)) != null) ||
((ch = p.right) != null &&
(q = ch.findTreeNode(h, k, kc)) != null))
// 如果找到直接返回
return q;
}
//搜索也找不到的话，再次判断hash值大小，如果是小于等于，那就返回-1，放在左子树
dir = tieBreakOrder(k, pk);
}
// xp是父节点的临时引用
TreeNode<K, V> xp = p;
// 如果应该插入左子树，p=p.left,否则p=p.right
if ((p = (dir <= 0) ? p.left : p.right) == null) {
// first引用拿到，first是双向链表的头节点
TreeNode<K, V> x, f = first;
// 将当前节点构建出来，x是当前节点
first = x = new TreeNode<K, V>(h, k, v, f, xp);
// 因为当前的TreeBin除了维护红黑树之外，还维护着双向链表
if (f != null)
// 维护的是双向链表
// 将当前节点赋值为f前置节点
f.prev = x;
// 维护红黑树操作
if (dir <= 0)
xp.left = x;
else
xp.right = x;
// 如果父节点是黑色的，当前节点红色就行，说明插入操作没有影响红黑树的平衡
if (!xp.red)
x.red = true;
else {
// 说明父节点是红色的，插入节点就必须是黑色的，说明会影响红黑树的平衡
// 自平衡前后加锁操作
lockRoot();
try {
// 进行平衡
root = balanceInsertion(root, x);
} finally {
unlockRoot();
}
}
break;
}
}
// 检查红黑树结构
assert checkInvariants(root);
// 代表插入了新节点
return null;
}
TreeBin锁操作
TreeBin的写操作，没有基于AQS,仅仅是对一个变量lockState进行CAS操作和业务判断。
每次读线程操作，对lockState+4；
写线程操作时，对lockState+1，如果读操作占用线程，就先+2，就先挂起当前线程。
具体代码见：TreeBin整体构造
Transfer红黑树数据迁移
红黑树的迁移是基于双向链表封装的数据。
如果高低位的长度小于等于6，封装为链表进行迁移
如果高低位的长度大于6，封装为红黑树进行迁移
具体见扩容-Transfer
查询数据
get()
基于key查询数据.
1.先判断key是否在数组上，如果在，返回，否则下一步。
2.在判断当前位置是否是特殊情况：数据被迁移、红黑树、位置被占用。如果查询到，返回，否则下一步
3.判断链表上是否有数据，找到返回，找不到直接返回null
// get()方法，基于key查询value
public V get(Object key) {
// tab：数组
Node<K, V>[] tab; Node<K, V> e, p; int n, eh; K ek;
// 基于查询的key，计算hash值
int h = spread(key.hashCode());
// 数组不为null
if ((tab = table) != null
// n是数组的长度大于0
&& (n = tab.length) > 0 &&
// e是获取的hash值的Node,不为null
(e = tabAt(tab, (n - 1) & h)) != null) {
// 数组数据上的hash值是否和计算出来的hash值相同，如果相同，有可能是一样的
if ((eh = e.hash) == h) {
// 判断key是否相等 || 获取equals相同
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
// 相等直接返回
return e.val;
// 如果数组上的hash值为小于0，要不是在迁移，要不是红黑树
} else if (eh < 0)
// 三种情况，数据被迁移，节点位置被占，红黑树
return (p = e.find(h, key)) != null ? p.val : null;
// 如果不在数组上，也不是红黑树，那么肯定是链表，进行循环，直到找到数据
while ((e = e.next) != null) {
// hash值相同，key值相等，获取equal相同
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
// 查询不到，返回null
return null;
}
ForwardingNode的find方法
在查询数据时，如果发现数组扩容了，数据已经迁移了，去新数组上查询数据。
在数组和链表上正常找key对应的value。可能依然存在特殊情况，也就是hash小于0 。
1.再次是fwd：说明当前线程可能没有获取到CPU时间片，导致再次扩容，重新走当前方法。
2.可能被占用或者是红黑树，再次走另外两种find方法逻辑
// forwardingNode的find方法
// 在查询数据时，发现当前桶位置已经被放置fwd，代表已经被迁移
// h是计算得到的hash，k是要查询的key
Node<K, V> find(int h, Object k) {
// outer:for循环的标识
// tab是新数组
outer: for (Node<K, V>[] tab = nextTable;;) {
// n是新数组的长度
// e是新数组上根据hash得到的位置的数据
Node<K, V> e; int n;
// k是null || 新数组是null || 新数组的长度为0 || 查询到的数组的node是null
if (k == null || tab == null || (n = tab.length) == 0 ||(e = tabAt(tab, (n - 1) & h)) == null)
// 直接返回null
return null;
// 死循环
for (;;) {
// eh是新数组数据的hash
// ek是新数组数据的key
int eh; K ek;
// 如果hash和key一样，说明找到数据
if ((eh = e.hash) == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
// 直接返回
return e;
// 如果新数据，hash还是小于0，发现又扩容
if (eh < 0) {
if (e instanceof ForwardingNode) {
tab = ((ForwardingNode<K, V>)e).nextTable;
// 返回到起点，重新走一遍最外层循环，拿到最新的nextTable
continue outer;
} else
// 这个位置要不被占了，要不是红黑树
return e.find(h, k);
}
// 说明不在数组上，往下走链表
if ((e = e.next) == null)
// 进来表示链表找不到数据，返回null
return null;
}
}
}
节点被占用find方法
ReservationNode的find方法
因为当前桶位置被占用的话，说明当前数据还没放到当前位置，当前位置可以理解为null
直接返回null
// 在 computeIfAbsent 和 compute 中使用的占位符节点
static final class ReservationNode<K, V> extends Node<K, V> {
ReservationNode() {
super(RESERVED, null, null, null);
}
// 直接返回null
Node<K, V> find(int h, Object k) {
return null;
}
}
TreeBin的find方法
红黑树中查找时，如果有写锁或者有线程正在等待写锁，那就去双向链表中查，否则去红黑树中查。
如果从红黑树中查询结束，判断是否有等待写锁的线程，如果有，则唤醒等待的写线程。
//treeBin的find方法 在红黑树中检索数据
final Node<K, V> find(int h, Object k) {
// 非空判断，k不为null
if (k != null) {
// e:首先treeBin中的双向链表的头节点
for (Node<K, V> e = first; e != null; ) {
// s:是treeBin的锁状态
// ek:e的key
int s; K ek;
// WRITER 00000001
// WAITER 00000010
// WAITER | WRITER 00000011
if (((s = lockState) & (WAITER | WRITER)) != 0) {
// 如果进来，要么有写线程持有写锁，要么有写线程等待获取锁
// 这种情况就不能让lockState+4,也就是获取不到读锁
// 这样的话就去双向链表中查询数据
if (e.hash == h &&
((ek = e.key) == k || (ek != null && k.equals(ek))))
return e;
e = e.next;
// 说明没有线程等待写锁或持有写锁，将lockState+4,代表当前线程可以去红黑树中读数据
} else if (U.compareAndSwapInt(this, LOCKSTATE, s,
s + READER)) {
TreeNode<K, V> r, p;
// 基于findTreeNode在红黑树中查数据
try {
// 查询到数据
p = ((r = root) == null ? null :
r.findTreeNode(h, k, null));
} finally {
// 查询过程中，如果有写锁过来，进入阻塞状态
Thread w;
// 对lockState-4，表示读锁结束，释放读锁，唤醒写锁
if (U.getAndAddInt(this, LOCKSTATE, -READER) ==
// 判断waiter是否为null，为null代表有线程在等待写锁
(READER | WAITER) && (w = waiter) != null)
// 唤醒写锁
LockSupport.unpark(w);
}
return p;
}
}
}
return null;
}
TreeBin中find方法的findTreeNode
红黑树的检索方法，就是基于hash值的大小去检索，小于查找左子树，大于查找右子树，相等则使用compare方法判断去查找左子树还是右子树
// 查找树节点
// h是计算的hash值，k是要查询的key,kc是key的类
final TreeNode<K, V> findTreeNode(int h, Object k, Class<?> kc) {
// k不等于null 判断
if (k != null) {
TreeNode<K, V> p = this;
do {
int ph, dir; K pk; TreeNode<K, V> q;
// 声明左子树和右子树
TreeNode<K, V> pl = p.left, pr = p.right;
// 直接比较hash值去决定判断左子树还是右子树
if ((ph = p.hash) > h)
// 查询左子树
p = pl;
else if (ph < h)
// 查询右子树
p = pr;
// 判断当前node是否和key相等
else if ((pk = p.key) == k || (pk != null && k.equals(pk)))
return p;
// 如果左子树没有了，那就查右子树
else if (pl == null)
p = pr;
// 如果右子树没有了，那就查左子树
else if (pr == null)
p = pl;
// 如果hash值相同，compare方法计算应该找左子树还是右子树
else if ((kc != null ||
(kc = comparableClassFor(k)) != null) &&
(dir = compareComparables(kc, k, pk)) != 0)
p = (dir < 0) ? pl : pr;
// 如果没找到，递归继续找
else if ((q = pr.findTreeNode(h, k, kc)) != null)
return q;
else
p = pl;
} while (p != null);
}
return null;
}
其他方法
compute方法
修改concurrentHashMap指定key的value值时，一般会选择get()出来，然后再拿到value值，基于原value值做一些修改，最后再存放到concurrentHashMap。
比如要基于原value值，通过计算来获取新值时，就可以用compute方法。
compute方法如果之前的key不存在，那就是新增操作，如果存在，就是替换操作
package com.xqm.juc.concurrentHashMap;
import java.util.concurrent.ConcurrentHashMap;
public class Test04 {
public static void main(String[] args) {
ConcurrentHashMap<String,Integer> map=new ConcurrentHashMap();
map.put("key",1);
// 修改key对应的value-----原本的方法
Integer oldValue = map.get("key");
Integer newValue=oldValue+1;
map.put("key",newValue);
// key=2
System.out.println(map);
// 修改key对应的value-----compute的方法
Integer key1 = map.compute("key", (key, value) -> {
// 这种方法也可能出问题，比如key不存在，就会报空指针异常
if (value==null){
value=0;
}
return value + 1;
});
// key=3
System.out.println(map);
}
}
compute方法源码
整个流程和putVal很相似，但是内部涉及到了占位（RESERVEL）的情况。
如果是key存在，就是替换，否则就是新增（流程和putVal方法一样）。
节点状态：moved移动，treebin是树结构，reservel占位情况
// compute计算方法
// k:就是输入的key，BiFunction：函数式编程，输入两个参数，并且有返回值
public V compute(K key,BiFunction<? super K, ? super V, ? extends V> remappingFunction) {
// key不等于null
if (key == null || remappingFunction == null)
throw new NullPointerException();
// 计算key的hash
int h = spread(key.hashCode());
// 声明value为null
V val = null;
int delta = 0;
int binCount = 0;
// 下面的操作就是：初始化，桶上赋值，链表插入值，红黑树插入值
for (Node<K, V>[] tab = table;;) {
Node<K, V> f; int n, i, fh;
// 如果表为null,则进行初始化
if (tab == null || (n = tab.length) == 0)
tab = initTable();
// 如果桶上没有值，在桶上赋值，就是key查询不到的话，就是新增操作，否则就是替换操作
else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
// 数组指定的索引位置没有数据，当前数据必定要放到数组上
Node<K, V> r = new ReservationNode<K, V>();
// 因为value要通过计算才能获取值，当前桶上又没有数据，因此放一个临时节点在桶上，用来占位
// 对占位的数据进行加锁，防止又有数据写进来
synchronized (r) {
// 以CAS的方式将数据放上去
if (casTabAt(tab, i, null, r)) {
// 往桶上放数据，因此binCount=1
binCount = 1;
Node<K, V> node = null;
try {
// 如果临时占位节点放成功，开始计算value
// value都不等于null,才能放数据上去
if ((val = remappingFunction.apply(key, null)) != null) {
delta = 1;
// 将计算的value，和传入的key放到指定的位置
node = new Node<K, V>(h, key, val, null);
}
} finally {
// 存储到指定位置
setTabAt(tab, i, node);
}
}
}
if (binCount != 0)
break;
// 如果正在扩容，协助扩容
} else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
synchronized (f) {
if (tabAt(tab, i) == f) {
// 链表插入值
if (fh >= 0) {
binCount = 1;
for (Node<K, V> e = f, pred = null;; ++binCount) {
K ek;
// 如果key存储，拿到value进行计算
if (e.hash == h &&
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
val = remappingFunction.apply(key, e.val);
if (val != null)
e.val = val;
else {
delta = -1;
Node<K, V> en = e.next;
if (pred != null)
pred.next = en;
else
// 替换新值
setTabAt(tab, i, en);
}
break;
}
pred = e;
// 如果链表上没有找到key
if ((e = e.next) == null) {
val = remappingFunction.apply(key, null);
if (val != null) {
delta = 1;
// 拿到value，直接在链表上插入新值
pred.next =
new Node<K, V>(h, key, val, null);
}
break;
}
}
// 红黑树插入值
} else if (f instanceof TreeBin) {
binCount = 1;
TreeBin<K, V> t = (TreeBin<K, V>)f;
TreeNode<K, V> r, p;
if ((r = t.root) != null)
p = r.findTreeNode(h, key, null);
else
p = null;
V pv = (p == null) ? null : p.val;
val = remappingFunction.apply(key, pv);
if (val != null) {
if (p != null)
p.val = val;
else {
delta = 1;
t.putTreeVal(h, key, val);
}
} else if (p != null) {
delta = -1;
if (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
// 是否链表长度超过8，进行tree扩容或者数组扩容
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
break;
}
}
}
// addCount
if (delta != 0)
addCount((long)delta, binCount);
return val;
}
computeIfPresent、computeIfAbsent、compute
compute方法的bug：
如果在计算结果的函数中，涉及到当前的key，会造成死锁问题。
package com.xqm.juc.concurrentHashMap;
import java.util.concurrent.ConcurrentHashMap;
/**
* 死锁问题
*/
public class Test05 {
public static void main(String[] args) {
ConcurrentHashMap<String,Integer> map=new ConcurrentHashMap();
// 修改key对应的value-----compute的方法
Integer key1 = map.compute("key", (key, value) -> {
// 由于key所在桶上的写锁被上一个compute获取，这个compute获取不到锁
// 因此会一直阻塞，上一个compute也无法释放，造成死锁
// 这个错误在JDK1.9中已经被修复
return map.compute("key",(k,v)->{
return 2;
});
});
System.out.println(map);
}
}
computeIfAbsent和computeIfPresent实际上就是将compute拆分成两个方法。
compute会在key不存在时，新增操作，key存在时，替换操作。
computeIfPresent()：要求key在map中必须存在，如果没有数据，直接break。有值的话就进行替换。
computeIfAbsent()：要求key在map中必须不存在，进行新增操作。数据存在则直接返回。
package com.xqm.juc.concurrentHashMap;
import java.util.concurrent.ConcurrentHashMap;
public class Test06 {
public static void main(String[] args) {
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap();
map.computeIfPresent("key1", (key, value) -> {
if (value == null) {
value = 0;
}
return value + 1;
});
// 不能有value的存在
map.computeIfAbsent("key1", (key) -> {
return 1;
});
}
}
replace方法
使用put方法来替换key的值时，可能不安全。但是使用replace就是安全的操作。
replace要求key必须存在，value替换之前，会先比较oldValue，如果获得的value和oldvalue相同，才会替换为newValue。类似于CAS这样的操作。
使用：
package com.xqm.juc.concurrentHashMap;
import java.util.concurrent.ConcurrentHashMap;
public class Test07 {
public static void main(String[] args) {
ConcurrentHashMap<String, Integer> map = new ConcurrentHashMap();
map.put("key",12);
// key oldValue newValue
map.replace("key",12,13);
// key=13
System.out.println(map);
}
}
源码：
// replace方法
public V replace(K key, V value) {
if (key == null || value == null)
throw new NullPointerException();
// 调用replaceNode方法
return replaceNode(key, value, null);
}
// replace方法
public boolean replace(K key, V oldValue, V newValue) {
if (key == null || oldValue == null || newValue == null)
throw new NullPointerException();
// 调用replaceNode方法
return replaceNode(key, newValue, oldValue) != null;
}
// key就是key value是newValue cv是oldValue
final V replaceNode(Object key, V value, Object cv) {
int hash = spread(key.hashCode());
for (Node<K, V>[] tab = table;;) {
Node<K, V> f; int n, i, fh;
// 如果key查找不到，或者数组为null，直接break
if (tab == null || (n = tab.length) == 0 ||
(f = tabAt(tab, i = (n - 1) & hash)) == null)
break;
// 帮助扩容
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
// key能查找到数据
else {
V oldVal = null;
boolean validated = false;
// 加锁
synchronized (f) {
if (tabAt(tab, i) == f) {
if (fh >= 0) {
validated = true;
for (Node<K, V> e = f, pred = null;;) {
K ek;
// 找到key一致的node,
if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {
// 拿到当前节点的原值
V ev = e.val;
// 拿oldValue和原值做比较，如果一致，就开始替换
// cv是旧值，不可能是null
if (cv == null || cv == ev ||
(ev != null && cv.equals(ev))) {
oldVal = ev;
if (value != null)
e.val = value;
else if (pred != null)
pred.next = e.next;
else
setTabAt(tab, i, e.next);
}
break;
}
pred = e;
if ((e = e.next) == null)
break;
}
// 红黑树一样的操作
} else if (f instanceof TreeBin) {
validated = true;
TreeBin<K, V> t = (TreeBin<K, V>)f;
TreeNode<K, V> r, p;
if ((r = t.root) != null &&
(p = r.findTreeNode(hash, key, null)) != null) {
V pv = p.val;
// 找到原值，做比较，然后替换
if (cv == null || cv == pv ||
(pv != null && cv.equals(pv))) {
oldVal = pv;
if (value != null)
p.val = value;
else if (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
}
if (validated) {
if (oldVal != null) {
if (value == null)
addCount(-1L, -1);
return oldVal;
}
break;
}
}
}
return null;
}
merge方法
merge有三个参数：key、value、function(oldValue，newValue)
public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {}
在使用merge方法时，有三种情况发生：
- 如果key不存在在map中，就和put(key,value)方法作用一样
- 如果key存在在map中，就可以基于function进行计算，得到最终结果
- 如果function的结果不为null，将key对应的value，替换为function的结果
- 如果function的结果为null，删除当前key
使用：
package com.xqm.juc.concurrentHashMap;
import java.util.concurrent.ConcurrentHashMap;
public class Test08 {
public static void main(String[] args) {
ConcurrentHashMap<String, String> map = new ConcurrentHashMap();
// 这里的key是不存在的
map.merge("key", "value", (oldValue, value) -> {
return "xxx";
});
// {key=value}
System.out.println(map);
// 这里的key是存在的,返回不为null
map.merge("key", "value", (oldValue, value) -> {
return "123";
});
//{key=123}
System.out.println(map);
// 这里的key是存在的,返回为null
map.merge("key", "value", (oldValue, value) -> {
return null;
});
// 返回{}
System.out.println(map);
}
}
源码
// merge方法
public V merge(K key, V value, BiFunction<? super V, ? super V, ? extends V> remappingFunction) {
// 判断非空
if (key == null || value == null || remappingFunction == null)
throw new NullPointerException();
// 获取hash
int h = spread(key.hashCode());
V val = null;
int delta = 0;
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();
// 如果获取到的索引位置数据为null，也就是key不存在
else if ((f = tabAt(tab, i = (n - 1) & h)) == null) {
// 新增node
if (casTabAt(tab, i, null, new Node<K, V>(h, key, value, null))) {
delta = 1;
val = value;
break;
}
// 扩容
} else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
// 获取锁
synchronized (f) {
if (tabAt(tab, i) == f) {
// 链表操作
if (fh >= 0) {
binCount = 1;
for (Node<K, V> e = f, pred = null;; ++binCount) {
K ek;
// 判断链表中有当前的key
if (e.hash == h &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {
// 基于函数，计算value
val = remappingFunction.apply(e.val, value);
// 如果计算的value不为null，直接替换
if (val != null)
e.val = val;
// 如果为null，直接新增
else {
delta = -1;
Node<K, V> en = e.next;
if (pred != null)
pred.next = en;
else
setTabAt(tab, i, en);
}
break;
}
pred = e;
// 如果链表中没有当前key,直接新增
if ((e = e.next) == null) {
delta = 1;
val = value;
pred.next =
new Node<K, V>(h, key, val, null);
break;
}
}
// 红黑树是一样的操作
} else if (f instanceof TreeBin) {
binCount = 2;
TreeBin<K, V> t = (TreeBin<K, V>)f;
TreeNode<K, V> r = t.root;
TreeNode<K, V> p = (r == null) ? null :
r.findTreeNode(h, key, null);
val = (p == null) ? value :
remappingFunction.apply(p.val, value);
if (val != null) {
if (p != null)
p.val = val;
else {
delta = 1;
t.putTreeVal(h, key, val);
}
} else if (p != null) {
delta = -1;
if (t.removeTreeNode(p))
setTabAt(tab, i, untreeify(t.first));
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
break;
}
}
}
if (delta != 0)
addCount((long)delta, binCount);
return val;
}
计数器（addCount）
描述
addCount方法是为了计算map中元素个数，addCount内部就是基于LongAddr实现的。
由两个方向组成：
- 计数器：如果添加元素成功，计数器+1
- 检查当前concurrentHashMap是否需要扩容
concurrentHashMap在计算时，第一需要保证线程安全，第二需要保证效率
为什么没有使用AtomicLong:
1.AtomicLong是基于CAS实现的计数器，可以保证线程安全
2.并发比较高的情况下，多个线程同时CAS，只会有一个线程成功，没有成功的线程会一直CAS，直到成功，这样会一直消耗CPU资源。
LongAddr:如果并发执行自增操作时，CAS失败了，会将数据单独存到一个数组中计数。等到调用sum方法时，会将数组中数据相加，然后再和内存中的数据相加，最后得到最终的结果。
CounterCell
@sun.misc.Contended注解是JDK1.8之后才有的。避免缓存行失效的问题。
之前是
Long value;
Long l1,l2,l3,l4,l5,l6,l7; 无效的数据，用来占缓存行（默认64字节）其他位置，保证缓存行中只有value。
// CountCell的类，类似于LongAddr的Cell
// @sun.misc.Contended：这个注解是为了解决伪共享的问题
// （解决缓存行同步带来的性能问题）
// CPU在操作内存遍历前，会将主内存缓存到三级缓存中(L1,L2,L3)
// CPU缓存L1,是以缓存行为单位存储数据的，一般默认大小为64字节
// 缓存行同步问题，会影响CPU的性能
// 所以加上此注解，就是缓存行只存储这一个数据，其他字节位置填充无意义的数据
// 也就是这个属性独占缓存行，因为volatile会导致缓存行中的value失效（可见性）
// @sun.misc.Contended注解，将一个缓存行后面的7个位置，填充7个没有意义的数据
@sun.misc.Contended static final class CounterCell {
// volatile修饰的value，并且外部是基于CAS的方式修饰
volatile long value;
CounterCell(long x) { value = x; }
}
sumCount
整理countCell中数组数据到baseCount
// 整理countCell中数组数据到baseCount
final long sumCount() {
// 拿到数组
CounterCell[] as = counterCells; CounterCell a;
// 拿到baseCount
long sum = baseCount;
if (as != null) {
// 遍历CounterCell数组
for (int i = 0; i < as.length; ++i) {
if ((a = as[i]) != null)
// 累加到baseCount
sum += a.value;
}
}
return sum;
}
fullAddCount
执行fullAddCount方法的几种情况
1.CounterCell数组没有初始化
2.CounterCell数组中某一个对象没有初始化
3.有并发问题
源码：
// 执行fullAddCount方法的几种情况
// 1.CounterCell数组没有初始化
// 2.CounterCell数组中某一个对象没有初始化
// 3.有并发问题
private final void fullAddCount(long x, boolean wasUncontended) {
// 当前线程的随机数，后面可能会改变
int h;
// 判断当前线程的Probe有没有初始化，0号位置
if ((h = ThreadLocalRandom.getProbe()) == 0) {
// 如果随机数没有初始化，那就进行初始化
ThreadLocalRandom.localInit(); // force initialization
// 生成随机数，每次调用getProbe方法，最后结果h是相同的，调用advanceProbe才会每次生成不同的h
h = ThreadLocalRandom.getProbe();
// 一个标记，没有冲突
wasUncontended = true;
}
//
boolean collide = false; // True if last slot nonempty
// 死循环，一直到写成功为止
for (;;) {
// as：cell数组
// a：当前线程用的cell对象
// n：cell数组的长度
// v：value值
CounterCell[] as; CounterCell a; int n; long v;
// cell数组不等于null时具体操作
if ((as = counterCells) != null && (n = as.length) > 0) {
// 拿到当前线程随机数对应的CountCell对象为null，但是数组不为null，那么需要去创建对象
if ((a = as[(n - 1) & h]) == null) {
// 为0代表没有线程去操作cell数组
if (cellsBusy == 0) { // Try to attach new Cell
// 创建一个CounterCell对象
CounterCell r = new CounterCell(x); // Optimistic create
// 再次判断cellsBusy是否为0
if (cellsBusy == 0 &&
// CAS,从0改为1，开始对cell数组进行操作
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
// 创建对象未完成
boolean created = false;
try { // Recheck under lock
CounterCell[] rs; int m, j;
// DCL，数组不为null
if ((rs = counterCells) != null &&
// 数组长度大于0
(m = rs.length) > 0 &&
// 并且指定数组索引位置为null
rs[j = (m - 1) & h] == null) {
// 将创建好的对象赋值给索引位置
rs[j] = r;
// 创建成功
created = true;
}
} finally {
// 对cell对象操作结束
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
// CAS,将数组上存在的CounterCell对象的value进行+1的操作
else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))
// 成功就退出
break;
// 之前拿到的数组引用counterCell和成员变量as不一样
// 说明进行了cell数组的扩容操作
// counterCell数组的长度是否大于CPU的内核长度,不让数组长度大于CPU核数
//
else if (counterCells != as || n >= NCPU)
// 代表当前线程的循环失败，不进行扩容
collide = false;
// 如果小于CPU个数，或者有并发问题，进行扩容
else if (!collide)
collide = true;
// 进行扩容操作
// 如果没有线程操作cellsBusy，那么将cellsBusy从0修改为1，开始扩容
else if (cellsBusy == 0 &&
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
try {
// 如果数组没变，DCL
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将归为
cellsBusy = 0;
}
// 标识位归位
collide = false;
// 开启下次循环
continue; // Retry with expanded table
}
// 只要失败一次就重新设置一次线程的随机数，争取下次循环成功
h = ThreadLocalRandom.advanceProbe(h);
// 到这里代表CounterCell数组没有初始化
// cellsBusy:int类型的成员变量，为0的话，代表没有其他线程在初始化或扩容当前CounterCell
// counterCells == as：判断counterCells还是之前的as，没有并发问题
} else if (cellsBusy == 0 && counterCells == as &&
// cAS修改cellBusy,从0到1，代表当前线程要开始初始化了
U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
// 表示初始化未成功
boolean init = false;
try { // Initialize table
// DCL操作，再次判断没有并发问题
if (counterCells == as) {
// 构建CounterCell数组，默认长度为2
CounterCell[] rs = new CounterCell[2];
// h是随机数
// 用当前线程的随机数，和数组长度-1，进行&运算，在这个位置上，构建一个CounterCell对象
// x为1，在h&1位置上，赋值1，相当于总baseCount++
rs[h & 1] = new CounterCell(x);
// 将声明好的rs，赋值给成员变量
counterCells = rs;
// 初始化成功
init = true;
}
} finally {
// cellsBusy归位，当前线程已经操作完cell数组了，
cellsBusy = 0;
}
if (init)
// 初始化成功，退出循环
break;
// 总有线程去直接去操作baseCount主内存数据，其他线程去操作cell数组
} else if (U.compareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))
break; // Fall back on using base
}
}
addCount
逻辑：
记录元素个数逻辑：如果没有并发，直接baseCount++
如果有并发，CounterCell数组和数组中随机一个元素都初始化后，记录到CounterCell随机到的数组中
如果CounterCell数组没有初始化，或者CounterCell数组中随机一个元素没有初始化，或者有并发问题，则执行fullAddCount()方法
// addCount
// x为加个数，默认为1
// 记录元素个数逻辑：如果没有并发，直接baseCount++
// 如果有并发，CounterCell数组和数组中随机一个元素都初始化后，记录到CounterCell随机到的数组中
// 如果CounterCell数组没有初始化，或者CounterCell数组中随机一个元素没有初始化，则执行fullAddCount()方法
private final void addCount(long x, int check) {
// ========================记录元素个数======================================
// 类似于LongAddr
// 声明变量
// as : CounterCell
// b: 原来的baseCount
// s: 自增后元素的个数
CounterCell[] as; long b, s;
// private transient volatile CounterCell[] counterCells; 非空的时候，大小是2的幂次方
// 判断counterCells不为null，不为null代表有并发，如果为null,代表没并发
if ((as = counterCells) != null ||
// 当没有并发的时候
// baseCount:成员变量，基本计数器值，主要在没有争用时使用，但也可作为表初始化竞赛期间的后备。通过 CAS 更新
// 直接修改baseCount,进行++，然后break,如果CAS失败，直接进入if中
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {
// 有并发冲突，执行下面的代码。
// 进来方式有两种：1.counterCells[]有值 2.counterCells[]无值，CAS失败
// a:当前线程基于随机数，获得的CounterCell数组上的某一个CounterCell
CounterCell a; long v; int m;
// 是否没有冲突，默认为true,(也就是没有冲突)
boolean uncontended = true;
// 如果as（也就是CounterCell数组）为null || 没有初始化
if (as == null || (m = as.length - 1) < 0 ||
// CounterCell已经初始化了
// ThreadLocalRandom.getProbe()：生成随机数，并且随机数不会重复
// m:数组长度-1
// 基于随机数，拿到CounterCell的一个随机数，如果为null，执行下面的初始化
// 这里是初始化数组中的某一个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，直接return,不需要进行下面的扩容操作
if (check <= 1)
return;
// 执行sumCount()方法，将会累加counterCell数组和baseCount中的数据
s = sumCount();
}
// ========================判断扩容==========================================
// 判断check大于等于0，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) {
// sc == rs + 1 || sc == rs + MAX_RESIZERS 两个是bug
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();
}
}
}
size
size获取concurrentHashMap中的元素个数
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}