五分钟搞定Java并发编程之ConcurrentHashMap（带你装B带你飞！）
CJYD 2019-03-30
引言
ConcurrentHashMap是线程安全并且高效的HashMap，在并发编程中经常可见它的使用，在开始分析它的高并发实现机制前，先讲讲废话，看看它是如何被引入jdk的。
为什么引入ConcurrentHashMap？
HashMap线程不安全，它的线程不安全主要发生在put等对HashEntry有直接写操作的地方:
HashMap线程不安全操作源码示例
从put操作的源码不难看出，线程不安全主要可能发生在这两个地方：
key已经存在，需要修改HashEntry对应的value； key不存在，在HashEntry中做插入。
Hashtable线程安全，但是效率低下：
Hashtable源码示例.png
从Hashtable示例的源码可以看出，Hashtable是用synchronized关键字来保证线程安全的，由于synchronized的机制是在同一时刻只能有一个线程操作，其他的线程阻塞或者轮询等待，在线程竞争激烈的情况下，这种方式的效率会非常的低下。
注：小小的多嘴一句，Hashtable扩容的时候newSize = 2 * oldSize + 1，这个是常识性的点，但是由于整个jdk源码封装比较好，而且Hashtable效率低下，使用较少，貌似好多程序员都不太知道这一点。
ConcurrentHashMap的为什么高效？
Hashtable低效主要是因为所有访问Hashtable的线程都争夺一把锁。如果容器有很多把锁，每一把锁控制容器中的一部分数据，那么当多个线程访问容器里的不同部分的数据时，线程之前就不会存在锁的竞争，这样就可以有效的提高并发的访问效率。这也正是ConcurrentHashMap使用的分段锁技术。将ConcurrentHashMap容器的数据分段存储，每一段数据分配一个Segment（锁），当线程占用其中一个Segment时，其他线程可正常访问其他段数据。 ConcurrentHashMap实现分析 在分析ConcurrentHashMap的源码之前先来看看它的结构：
ConcurrentHashMap类图
.从类图可以看出：ConcurrentHashMap由Segment和HashEntry组成。
.Segment是可重入锁，它在ConcurrentHashMap中扮演分离锁的角色；
.HashEntry主要存储键值对；
.CurrentHashMap包含一个Segment数组，每个Segment包含一个HashEntry数组并且守护它，当修改HashEntry数组数据时，需要先获取它对应的Segment锁；而HashEntry数组采用开链法处理冲突，所以它的每个HashEntry元素又是链表结构的元素。
ConcurrentHashMap结构图
初始化ConcurrentHashMap
ConcurrentHashMap构造方法
可以看出，ConcurrentHashMap的构造方法都调用了public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)，初始化部分都由它来完成，我们来看一看它是怎么来初始化ConcurrentHashMap的。
ConcurrentHashMap初始化具体实现
整个初始化是通过参数initialCapacity，loadFactor和concurrencyLevel来初始化segmentShift（段偏移量）、segmentMask（段掩码）和segment数组。
ConcurrentHashMap初始化具体实现
计算segment数组长度
segment数组长度ssize是由concurrencyLevel计算得出，当ssize < concurrencyLevel时，ssize *= 2，至于为什么一定要保证ssize是2的N次方是为了可以通过按位与来定位segment；
注：concurrencyLevel的最大值是65535，那么，ssize的最大值就为65536，对应到二进制就是16位。
初始化segmentShift、segmentMask
segmentShift和segmentMask在定位segment使用，segmentShift = 32 - ssize向左移位的次数，segmentMask = ssize - 1。ssize的最大长度是65536，对应的 segmentShift最大值为16，segmentMask最大值是65535，对应的二进制16位全1；
初始化segment、
1、初始化每个segment的HashEntry长度；
2、创建segment数组和segment[0]。
注：HashEntry长度cap同样也是2的N次方，默认情况，ssize = 16，initialCapacity = 16，loadFactor = 0.75f，那么cap = 1，threshold = (int) cap * loadFactor = 0。
Segment定位
•Hash算法
ConcurrentHashMap使用分段锁segment来保护数据，也就是说，在插入和读取元素，需要先通过hash算法定位segment。ConcurrentHashMap使用了变种hash算法对元素的hashCode再散列。
ash算法
注：为什么需要再散列？
再散列的目的是为了减少冲突，让元素可以近似均匀的分布在不同的Segment上，从而提升存储效率。如果hash算法不好，最差的情况是所有的元素都在一个Segment中，这时候hash表将退化成链表，查询插入的时间复杂度都会从理想的o(1)退化成o(n^2)，同时，分段锁也会失去存在的意义。
Segment定位
默认情况下，segmentShift = 28， segmentMask = 15，hashCode最大是32位的二进制数，向右无符号移动28位，让高4位参与位运算（& segmentMask）。
ConcurrentHashMap相关操作实现分析 主要分析ConcurrentHashMap常用的三个操作：get/put/size的具体实现。
get操作
get实现
1、根据key，计算出hashCode；
2、根据步骤1计算出的hashCode定位segment，如果segment不为null && segment.table也不为null，跳转到步骤3，否则，返回null，该key所对应的value不存在；
3、根据hashCode定位table中对应的hashEntry，遍历hashEntry，如果key存在，返回key对应的value；
4、步骤3结束仍未找到key所对应的value，返回null，该key锁对应的value不存在。
比起Hashtable，ConcurrentHashMap的get操作高效之处在于整个get操作不需要加锁。如果不加锁，ConcurrentHashMap的get操作是如何做到线程安全的呢？原因是volatile，所有的value都定义成了volatile类型，volatile可以保证线程之间的可见性，这也是用volatile替换锁的经典应用场景。
HashEntry value定义
put操作
ConcurrentHashMap提供两个方法put和putIfAbsent来完成put操作，它们之间的区别在于put方法做插入时key存在会更新key所对应的value，而putIfAbsent不会更新。
put实现
put实现
1、参数校验，value不能为null，为null时抛出NPE；
2、计算key的hashCode；
3、定位segment，如果segment不存在，创建新的segment；
4、调用segment的put方法在对应的segment做插入操作。
putIfAbsent实现
putIfAbsent实现
segment的put方法实现
segment的put方法是整个put操作的核心，它实现了在segment的HashEntry数组中做插入
（segment的HashEntry数组采用开链法来处理冲突）。
segment put实现
具体的执行流程如下：
1、获取锁，保证put操作的线程安全；
2、定位到HashEntry数组中具体的HashEntry；
3、遍历HashEntry链表，假若待插入key已存在：
需要更新key所对应value（!onlyIfAbsent），更新oldValue -> newValue，跳转到步骤5；
否则，直接跳转到步骤5；
4、遍历完HashEntry链表，key不存在，插入HashEntry节点，oldValue = null，跳转到步骤5；
5、释放锁，返回oldValue。
步骤4在做插入的时候实际上经历了两个步骤：
第一：HashEntry数组扩容；
是否需要扩容
在插入元素前会先判断Segment的HashEntry数组是否超过threshold，如果超过阀值，则需要对HashEntry数组扩容；
如何扩容
在扩容的时候，首先创建一个容量是原来容量两倍的数组，将原数组的元素再散列后插入到新的数组里。为了高效，ConcurrentHashMap只对某个Segment进行扩容，不会对整个容器扩容。
第二：定位添加元素对应的位置，然后将其放到HashEntry数组中。
size实现
如果需要统计整个ConcurrentHashMap的容量，需要统计所有Segment容量然后求和，Segment提供变量count用于存储当前Segment的容量。但是ConcurrentHashMap为了保证线程安全，并不是直接把所有的Segment的count相加来得到整个容器的大小，我们来看看ConcurrentHashMap是怎么来统计容量的。
默认情况下，segmentShift = 28， segmentMask = 15，hashCode最大是32位的二进制数，向右无符号移动28位，让高4位参与位运算（& segmentMask）。
ConcurrentHashMap相关操作实现分析
主要分析ConcurrentHashMap常用的三个操作：get/put/size的具体实现。
get操作
1、根据key，计算出hashCode；
2、根据步骤1计算出的hashCode定位segment，如果segment不为null && segment.table也不为null，跳转到步骤3，否则，返回null，该key所对应的value不存在；
3、根据hashCode定位table中对应的hashEntry，遍历hashEntry，如果key存在，返回key对应的value；
4、步骤3结束仍未找到key所对应的value，返回null，该key锁对应的value不存在。
比起Hashtable，ConcurrentHashMap的get操作高效之处在于整个get操作不需要加锁。如果不加锁，ConcurrentHashMap的get操作是如何做到线程安全的呢？原因是volatile，所有的value都定义成了volatile类型，volatile可以保证线程之间的可见性，这也是用volatile替换锁的经典应用场景。
put操作
ConcurrentHashMap提供两个方法put和putIfAbsent来完成put操作，它们之间的区别在于put方法做插入时key存在会更新key所对应的value，而putIfAbsent不会更新。
put实现
1、参数校验，value不能为null，为null时抛出NPE；
2、计算key的hashCode；
3、定位segment，如果segment不存在，创建新的segment；
4、调用segment的put方法在对应的segment做插入操作。
segment的put方法实现
segment的put方法是整个put操作的核心，它实现了在segment的HashEntry数组中做插入
（segment的HashEntry数组采用开链法来处理冲突）。
具体的执行流程如下：
1、获取锁，保证put操作的线程安全；
2、定位到HashEntry数组中具体的HashEntry；
3、遍历HashEntry链表，假若待插入key已存在：
需要更新key所对应value（!onlyIfAbsent），更新oldValue -> newValue，跳转到步骤5；
否则，直接跳转到步骤5；
4、遍历完HashEntry链表，key不存在，插入HashEntry节点，oldValue = null，跳转到步骤5；
5、释放锁，返回oldValue。
步骤4在做插入的时候实际上经历了两个步骤：
第一：HashEntry数组扩容；
是否需要扩容
在插入元素前会先判断Segment的HashEntry数组是否超过threshold，如果超过阀值，则需要对HashEntry数组扩容；
如何扩容
在扩容的时候，首先创建一个容量是原来容量两倍的数组，将原数组的元素再散列后插入到新的数组里。为了高效，ConcurrentHashMap只对某个Segment进行扩容，不会对整个容器扩容。
第二：定位添加元素对应的位置，然后将其放到HashEntry数组中。
size实现
如果需要统计整个ConcurrentHashMap的容量，需要统计所有Segment容量然后求和，Segment 提供变量count用于存储当前Segment的容量。但是ConcurrentHashMap为了保证线程安全，并不是直接把所有的Segment的count相加来得到整个容器的大小，我们来看看ConcurrentHashMap是怎么来统计容量的。
由于在累加count的操作的过程中之前累加过的count发生变化的几率非常小
所以ConcurrentHashMap先尝试2次不锁住Segment的方式来统计每个Segment的大小，如果在统计的过程中Segment的count发生了变化，这时候再加锁统计Segment的count。
ConcurrentHashMap如何判断统计过程中Segment的cout发生了变化？
Segment使用变量modCount来表示Segment大小是否发生变化，在put/remove/clean操作里都会将modCount加1，那么在统计size的前后只需要比较modCount是否发生了变化，如果发生变化，Segment的大小肯定发生了变化。
