ConcurrentHashMap的原理分析学习

ConcurrentHashMap 的初步使用及场景

CHM 的使用 
ConcurrentHashMap 是 J.U.C 包里面提供的一个线程安全并且高效的 HashMap，所以ConcurrentHashMap 在并发编程的场景中使用的频率比较高，那么这一节课我们就从ConcurrentHashMap 的使用上以及源码层面来分析 ConcurrentHashMap 到底是如何实现安全性的
api 使用 
ConcurrentHashMap 是 Map 的派生类，所以 api 基本和 Hashmap 是类似，主要就是 put、get 这些方法，接下来基于 ConcurrentHashMap 的 put 和 get 这两个方法作为切入点来分析 ConcurrentHashMap 的源码实现

ConcurrentHashMap 的源码分析

先要做一个说明，这节课分析的 ConcurrentHashMap 是基于 jdk1.8 的版本。
JDK1.7 和 Jdk1.8 版本的变化 
ConcurrentHashMap 和 HashMap 的实现原理是差不多的，但是因为 ConcurrentHashMap需要支持并发操作，所以在实现上要比 hashmap 稍微复杂一些。
在 JDK1.7 的 实 现 上 ， ConrruentHashMap 由一个个 Segment 组 成 ， 简 单 来 说 ，ConcurrentHashMap 是一个 Segment 数组，它通过继承 ReentrantLock 来进行加锁，通过每次锁住一个 segment 来保证每个 segment 内的操作的线程安全性从而实现全局线程安全。整个结构图如下

当每个操作分布在不同的 segment 上的时候，默认情况下，理论上可以同时支持 16 个线程的并发写入。
相比于 1.7 版本，它做了两个改进
1. 取消了 segment 分段设计，直接使用 Node 数组来保存数据，并且采用 Node 数组元素作为锁来实现每一行数据进行加锁来进一步减少并发冲突的概率
2. 将原本数组+单向链表的数据结构变更为了数组+单向链表+红黑树的结构。为什么要引入红黑树呢？在正常情况下，key hash 之后如果能够很均匀的分散在数组中，那么 table 数组中的每个队列的长度主要为 0 或者 1.但是实际情况下，还是会存在一些队列长度过长的情况。如果还采用单向列表方式，那么查询某个节点的时间复杂度就变为 O(n); 因此对于队列长度超过 8 的列表，JDK1.8 采用了红黑树的结构，那么查询的时间复杂度就会降低到O(logN),可以提升查找的性能；

这个结构和 JDK1.8 版本中的 Hashmap 的实现结构基本一致，但是为了保证线程安全性，ConcurrentHashMap 的实现会稍微复杂一下。接下来我们从源码层面来了解一下它的原理.我们基于 put 和 get 方法来分析它的实现即可

public V put(K key, V value) {
 return putVal(key, value, false);
}

/** Implementation for put and putIfAbsent */
final V putVal(K key, V value, boolean onlyIfAbsent) {
 if (key == null || value == null) throw new NullPointerException();
 int hash = spread(key.hashCode()); //计算 hash 值
 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 值对应的数组下标得到第一个节点; 以 volatile 读的方式来读取 table 数组中的元素，保证每次拿到的数据都是最新的
 else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { 
//如果该下标返回的节点为空，则直接通过 cas 将新的值封装成 node 插入即可；如果 cas 失败，说明存在竞争，则进入下一次循环
 if (casTabAt(tab, i, null,
 new Node<K,V>(hash, key, value, null)))
 break; // no lock when adding to empty bin
 }
点击跳转->执行到这个阶段，数据结构图
。。。
｝

假如在上面这段代码中存在两个线程，在不加锁的情况下：线程 A 成功执行 casTabAt 操作后，随后的线程 B 可以通过 tabAt 方法立刻看到 table[i]的改变。原因如下：线程 A 的casTabAt 操作，具有 volatile 读写相同的内存语义，根据 volatile 的 happens-before 规则：线程 A 的 casTabAt 操作，一定对线程 B 的 tabAt 操作可见
initTable
数组初始化方法，这个方法比较简单，就是初始化一个合适大小的数组
sizeCtl这个要单独说一下，如果没搞懂这个属性的意义，可能会被搞晕
这个标志是在 Node 数组初始化或者扩容的时候的一个控制位标识，负数代表正在进行初始化或者扩容操作
-1 代表正在初始化
-N 代表有 N-1 有二个线程正在进行扩容操作，这里不是简单的理解成 n 个线程，sizeCtl 就是-N,这块后续在讲扩容的时候会说明
0 标识 Node 数组还没有被初始化，正数代表初始化或者下一次扩容的大小

private final Node<K,V>[] initTable() {
	 Node<K,V>[] tab; int sc;
	 while ((tab = table) == null || tab.length == 0) {
	 if ((sc = sizeCtl) < 0)//被其他线程抢占了初始化的操作,则直接让出自己的 CPU时间片
	 Thread.yield(); // lost initialization race; just spin
	//通过 cas 操作，将 sizeCtl 替换为-1，标识当前线程抢占到了初始化资格
	 else if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) {
	 try {
	 if ((tab = table) == null || tab.length == 0) {
	 int n = (sc > 0) ? sc : DEFAULT_CAPACITY;//默认初始容量为
	16
	 @SuppressWarnings("unchecked")
	//初始化数组，长度为 16，或者初始化在构造 ConcurrentHashMap 的时候传入的长度
	 Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];
	 table = tab = nt;//将这个数组赋值给 table
	 sc = n - (n >>> 2); //计算下次扩容的大小，实际就是当前容量的 0.75倍，这里使用了右移来计算
	 }
	 } finally {
	 sizeCtl = sc; //设置 sizeCtl 为 sc, 如果默认是 16 的话，那么这个时候
	sc=16*0.75=12
	 }
	 break;
	}
	 }
	 return tab;
}

tabAt
该方法获取对象中offset偏移地址对应的对象field的值。实际上这段代码的含义等价于tab[i], 但是为什么不直接使用 tab[i]来计算呢？
getObjectVolatile，一旦看到 volatile 关键字，就表示可见性。因为对 volatile 写操作 happenbefore 于 volatile 读操作，因此其他线程对 table 的修改均对 get 读取可见；
虽然 table 数组本身是增加了 volatile 属性，但是“volatile 的数组只针对数组的引用具有volatile 的语义，而不是它的元素”。 所以如果有其他线程对这个数组的元素进行写操作，那么当前线程来读的时候不一定能读到最新的值。出于性能考虑，Doug Lea 直接通过 Unsafe 类来对 table 进行操作。

static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {
 return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);
}

图解分析

put 方法第二阶段
在putVal方法执行完成以后，会通过addCount来增加ConcurrentHashMap中的元素个数，并且还会可能触发扩容操作。这里会有两个非常经典的设计
1. 高并发下的扩容
2. 如何保证 addCount 的数据安全性以及性能

//将当前 ConcurrentHashMap 的元素数量加 1，有可能触发 transfer 操作(扩容)
 addCount(1L, binCount);
 return null;
}

addCount
在 putVal 最后调用 addCount 的时候，传递了两个参数，分别是 1 和 binCount(链表长度)，看看 addCount 方法里面做了什么操作
x 表示这次需要在表中增加的元素个数，check 参数表示是否需要进行扩容检查，大于等于 0都需要进行检查

private final void addCount(long x, int check) {
 CounterCell[] as; long b, s;
判断 counterCells 是否为空，
1. 如果为空，就通过 cas 操作尝试修改 baseCount 变量，对这个变量进行原子累加操
作(做这个操作的意义是：如果在没有竞争的情况下，仍然采用 baseCount 来记录元素个
数)
2. 如果 cas 失败说明存在竞争，这个时候不能再采用 baseCount 来累加，而是通过
CounterCell 来记录
if ((as = counterCells) != null ||
 !U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) 
{
 CounterCell a; long v; int m;
 boolean uncontended = true;//是否冲突标识，默认为没有冲突
这里有几个判断
1. 计数表为空则直接调用 fullAddCount
2. 从计数表中随机取出一个数组的位置为空，直接调用 fullAddCount
3. 通过 CAS 修改 CounterCell 随机位置的值，如果修改失败说明出现并发情况（这里又
用到了一种巧妙的方法），调用 fullAndCount
Random 在线程并发的时候会有性能问题以及可能会产生相同的随机
数,ThreadLocalRandom.getProbe 可以解决这个问题，并且性能要比 Random 高
 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);//执行 fullAddCount 方法
 return;
 }
 if (check <= 1)//链表长度小于等于 1，不需要考虑扩容
 return;
 s = sumCount();//统计 ConcurrentHashMap 元素个数
 }
 //….
}

CounterCells 解释
ConcurrentHashMap 是采用 CounterCell 数组来记录元素个数的，像一般的集合记录集合大小，直接定义一个 size 的成员变量即可，当出现改变的时候只要更新这个变量就行。为什么
ConcurrentHashMap 要用这种形式来处理呢？
问题还是处在并发上，ConcurrentHashMap 是并发集合，如果用一个成员变量来统计元素个数的话，为了保证并发情况下共享变量的的难全兴，势必会需要通过加锁或者自旋来实现，如果竞争比较激烈的情况下，size 的设置上会出现比较大的冲突反而影响了性能，所以在ConcurrentHashMap 采用了分片的方法来记录大小，具体什么意思，我们来分析下。

private transient volatile int cellsBusy;// 标识当前 cell 数组是否在初始化或扩容中的CAS 标志位
/**
* Table of counter cells. When non-null, size is a power of 2.
*/
private transient volatile CounterCell[] counterCells;// counterCells 数组，总数值的分值分别存在每个 cell 中
@sun.misc.Contended static final class CounterCell {
 volatile long value;
 CounterCell(long x) { value = x; }
}
//看到这段代码就能够明白了，CounterCell 数组的每个元素，都存储一个元素个数，而实际我们调用size 方法就是通过这个循环累加来得到的
//又是一个设计精华，大家可以借鉴； 有了这个前提，再会过去看 addCount 这个方法，就容易理解一些
了
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;
}

fullAddCount 源码分析
fullAddCount 主要是用来初始化 CounterCell，来记录元素个数，里面包含扩容，初始化等操作

private final void fullAddCount(long x, boolean wasUncontended) {
 int h;
//获取当前线程的 probe 的值，如果值为 0，则初始化当前线程的 probe 的值,probe 就是随机数
 if ((h = ThreadLocalRandom.getProbe()) == 0) {
 ThreadLocalRandom.localInit(); // force initialization
 h = ThreadLocalRandom.getProbe();
 wasUncontended = true; // 由于重新生成了 probe，未冲突标志位设置为 true
 }
 boolean collide = false; // True if last slot nonempty
 for (;;) {//自旋
 CounterCell[] as; CounterCell a; int n; long v;
//说明 counterCells 已经被初始化过了，我们先跳过这个代码，先看初始化部分
 if ((as = counterCells) != null && (n = as.length) > 0) { 
if ((a = as[(n - 1) & h]) == null) {// 通过该值与当前线程 probe 求与，获得cells 的下标元素，和 hash 表获取索引是一样的
 if (cellsBusy == 0) { //cellsBusy=0 表示 counterCells 不在初始化或者扩容状态下 
 CounterCell r = new CounterCell(x); //构造一个 CounterCell 的值，传入元素个数
 if (cellsBusy == 0 &&//通过 cas 设置 cellsBusy 标识，防止其他线程来对 counterCells 并发处理
 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
 boolean created = false;
 try { // Recheck under lock
 CounterCell[] rs; int m, j;
//将初始化的 r 对象的元素个数放在对应下标的位置
 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;//说明指定 cells 下标位置的数据不为空，则进行下一次循环
 }
 }
 collide = false;
 }
//说明在 addCount 方法中 cas 失败了，并且获取 probe 的值不为空
 else if (!wasUncontended) // CAS already known to fail
 wasUncontended = true; //设置为未冲突标识，进入下一次自旋
//由于指定下标位置的 cell 值不为空，则直接通过 cas 进行原子累加，如果成功，则直接退出
 else if (U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))//
 break;
//如果已经有其他线程建立了新的 counterCells 或者 CounterCells 大于 CPU 核心数（很巧妙，线程的并发数不会超过 cpu 核心数）
 else if (counterCells != as || n >= NCPU)
 collide = false; //设置当前线程的循环失败不进行扩容
 else if (!collide)//恢复 collide 状态，标识下次循环会进行扩容
 collide = true;
//进入这个步骤，说明 CounterCell 数组容量不够，线程竞争较大，所以先设置一个标识表示为正在扩容
 else if (cellsBusy == 0 &&
 U.compareAndSwapInt(this, CELLSBUSY, 0, 1)) {
 try {
 if (counterCells == as) {// Expand table unless stale
//扩容一倍 2 变成 4，这个扩容比较简单
 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);//更新随机数的值
 }
初始化 CounterCells 数组
//cellsBusy=0 表示没有在做初始化，通过 cas 更新 cellsbusy 的值标注当前线程正在做初始化操作
 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]; //初始化容量为 2
 rs[h & 1] = new CounterCell(x);//将 x 也就是元素的个数放在指定的数组下标位置
 counterCells = rs;//赋值给 counterCells
 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
 }
}