引言
当我们需要在多线程的环境中使用 Map 的时候我们可能就会想到
- SynchronizedMap
- ConcurrentHashMap
SynchronizedMap 就是对 HashMap 的一些需要同步的方法做了进行了一层同步包装，调用的时候线程必须持有锁才能执行如下图所示
这样的同步粒度比较大，我们知道 HashMap 的存储结构是如下图，在插入数据的时候，每个数据都可能处于 table 数组不同的索引位置，可能添加到对应索引位置后面的链表或者红黑树中
这样的话我们使用 SynchronizedMap 线程 A 在 table[0] 中插入数据，线程 B 在 table[1] 插入数据，二者本来就不冲突的但是也只能排队进行 A 插完了 B 在进行插入，这样当在并发量较大的时候性能会急剧下降。
针对上述情况如果我们能分别对每个 table 索引位置进行加锁的话，那么就能提升我们 map 的并发性，ConcurrentHashMap 就是以此作为基本原理来实现的
ConcurrentHashMap
数据结构
它的数据结构和 HashMap 是一致的，由 table[], 对应索引位置的链表或者红黑树组成
插入数据
插入数据代码量有点大从上往下依次看
1、 对 key 值求 hash
2、 如果 table 没有初始化则进行初始化
3、 用 key 求得 table 索引位置i ，然后取出对应的值 f
1. 如果 f 值为 null 的话说明是初次插入，这样情况如果是 HashMap 的话就会直接将值插入了即 table\[i\] = val
2. 但是在 ConcurrentHashMap 为了保证多个线程同时插入该索引位置可能导致数据被覆盖的情况，这里使用了 CAS
3. CAS 设置成功的线程插入成功，失败的会再次进入 for 循环寻找位置插入
4、 如果发现结点的 hash 值为 MOVED 表示容器可能在扩容结点的位置会有所变化
5、 只需要对 table 对应的索引位置加锁即可，其它索引位置仍然允许同时插入数据
6、 初始化 binCount 的值，这个值决定链表书否需要转化为红黑树
7、 如果发现 table 对应索引位置是链表，那么遍历链表每次 +binCount
1. 发现第一个结点就是它自身那么直接更新数据即可
2. 如果链表只有一个节点，那么直接插入到头结点后面就可以了，不需要再遍历寻找
8、 如果发现 table 对应索引位置是树，那么数据直接插入到红黑树中
9、 检查 binCount 的值这个值代表了链表当前节点数目如果大于 TREEIFY_THRESHOLD 那么会调用 treeifyBin() 将可能将其转化为红黑树
10、 为什么是可能呢，因为 treeifyBin 中还需要判断 table.length 如果长度小于 MIN_TREEIFY_CAPACITY 进行扩容，否则才会进行红黑树的转换
11、 调用 addCount 记录其容量，如果满足扩容条件需要对其进行扩容
treeifyBin
1、 如果 table.length < 64 则进行扩容
2、 扩容 table
3、 对应的 table 索引位置进行加锁，并且其对应的链表转化为红黑树
addCount(long x, int check)
1、 CounterCell 是什么呢，当 CAS 设置 baseCount 失败的时候，会 CAS 将值添加分布到 CounterCell[] 中的某个位置，这样冲突的概率会大大降低
2、 baseCount 作为基础容量计数，CAS 等成功的会记录到其中，它不是最终的容量大小
3、 如果 CAS baseCount 增加失败，表明存在竞争
4、 此时来设置 CounterCell 中对应的值 ThreadLocalRandom.getProbe() & m 作为索引位置取出 CounterCell 值 CAS + 1
5、 如果 CAS 设置 CounterCell 中对应的值还失败了的话调用 fullAddCount(x, uncontended); 它会死循环 CAS 增加值直到成功位置
6、 如果当前 map 数据容量 >= sizeCtl 这个需要扩容的点并且 table 数组容量小于 MAXIMUM_CAPACITY 这个最大容量那么表明需要进行扩容
7、 对 table 进行扩容，扩容成功后需要调用 transfer 对数据进行迁移
获取数据
1、 获取 key 的 hash 值
2、 根据 hash 值获得索引位置发现在 table 数组中
3、 key 正好是一个节点返回值
4、 如果发现数据在红黑树中则调用 find 去查询
5、 否则就是在链表中，遍历链表每一个节点依次判断是否是当前 key 直到找到为止返回
size()
统计计数的时候首先获取 baseCount 然后遍历 CounterCell 中的每一个值累加最终得到容量的大小