Java并发容器和框架--ConcurrentHashMap
一、ConcurrentHashMap的引入
ConcurrentHashMap是线程安全并且高效的HashMap，在并发编程中经常可见它的使用，在开始分析它的高并发实现机制前，看看它是如何被引入jdk的。
1、HashMap线程不安全：可以借鉴：https://www.jianshu.com/p/e2f75c8cce01
2、Hashtable线程安全，但是效率低下：Hashtable是用synchronized关键字来保证线程安全的，由于synchronized的机制是在同一时刻只能有一个线程操作，其他的线程阻塞或者轮询等待，在线程竞争激烈的情况下，这种方式的效率会非常的低下。
3、ConcurrentHashMap的锁分段技术可有效提升并发访问率
Hashtable低效主要是因为所有访问Hashtable的线程都争夺一把锁。如果容器有很多把锁，每一把锁控制容器中的一部分数据，那么当多个线程访问容器里的不同部分的数据时，线程之前就不会存在锁的竞争，这样就可以有效的提高并发的访问效率。这也正是ConcurrentHashMap使用的分段锁技术。将ConcurrentHashMap容器的数据分段存储，每一段数据分配一个Segment（锁），当线程占用其中一个Segment时，其他线程可正常访问其他段数据。
二、ConcurrentHashMap的结构
ConcurrentHashMap是由Segment数组结构和HashEntry数组结构组成。Segment是一种可重入锁（ReentrantLock），在ConcurrentHashMap里扮演锁的角色；HashEntry则用于存储键值对数据。
一个ConcurrentHashMap里包含一个Segment数组。Segment的结构和HashMap类似，是一种数组和链表结构。一个Segment里包含一个HashEntry数组，每个HashEntry是一个链表结构的元素，每个Segment守护着一个HashEntry数组里的元素，当对HashEntry数组的数据进行修改时，必须首先获得与它对应的Segment锁。
三、初始化ConcurrentHashMap
ConcurrentHashMap的构造方法都调用了
public ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel)，
初始化部分都由它来完成，我们来看一看它是怎么来初始化ConcurrentHashMap的。
1、ConcurrentHashMap初始化具体实现
整个初始化是通过参数initialCapacity，loadFactor和concurrencyLevel来初始化segmentShift（段偏移量）、segmentMask（段掩码）和segment数组。
可以看出，segment数组长度ssize是由concurrencyLevel计算得出，为了可以通过按位与的散列算法来定位segment数组的索引，必须要保证ssize是2的N次方：当ssize < concurrencyLevel时，ssize *= 2;
注：concurrencyLevel的最大值是65535，那么，ssize的最大值就为65536，对应到二进制就是16位。
2、初始化segmentShift（段偏移量）、segmentMask（段掩码）
segmentShift和segmentMask在定位segment时的散列算法里使用。
（1） segmentShift 用于定位参与散列运算的位数， segmentShift = 32 - sshift 。sshift = ssize从1向左移的次数，segment数组长度ssize是由concurrencyLevel计算得出，concurrencyLevel默认值为16，所以需要左移4次，sshift = 4; 所以segmentShift = 28。
（2）segmentMask是散列运算的掩码，等于ssize - 1;
3、初始化每个segment
输入参数initialCapacity是ConcurrentHashMap的初始化容量，，loadFactor是每个segment的负载因子，在构造方法中通过这两个参数来初始化数组中的每个segment。
segment的容量threshold = (int)cap * loadFactor;
cap就是segment里HashEntry数组的长度，c = initialCapacity / ssize，如果 c > 1,则cap取大于等于c的2的N次方值，小于1，取2的N次方。
注：HashEntry长度cap同样也是2的N次方，默认情况，ssize = 16，initialCapacity = 16，loadFactor = 0.75f，那么cap = 1，threshold = (int) cap * loadFactor = 0。
4、定位Segment
ConcurrentHashMap使用分段锁segment来保护不同段数据，在插入和读取元素，必须先通过hash(散列)算法定位segment。ConcurrentHashMap使用了变种hash算法对元素的hashCode再散列。
为什么需要再散列？
再散列的目的是为了减少冲突，让元素可以近似均匀的分布在不同的Segment上，从而提升存储效率。如果hash算法不好，最差的情况是所有的元素都在一个Segment中，这时候hash表将退化成链表，查询插入的时间复杂度都会从理想的o(1)退化成o(n^2)，同时，分段锁也会失去存在的意义。
默认情况下，segmentShift = 28， segmentMask = 15，hashCode最大是32位的二进制数，向右无符号移动28位，让高4位参与位运算（& segmentMask）。
四、ConcurrentHashMap的操作
主要分析ConcurrentHashMap常用的三个操作：get操作、put操作和size操作。
1、get(Object key)：先经过一次再散列，然后使用这个散列值通过散列运算定位到Segment，再通过散列算法定位到元素。
- 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操作是如何做到线程安全的呢？get()方法中的所有的共享变量都定义成了volatile类型，volatile可以保证线程之间的可见性，这也是用volatile替换锁的经典应用场景。
2、put操作
put需要对共享变量进行写入，因此为了线程安全需要加锁。put方法首先定位到Segment，然后在Segment里面进行插入操作。
具体的执行流程如下：
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在做插入的时候实际上经历了两个步骤：
第一：
1）是否需要扩容
在插入元素前会先判断Segment的HashEntry数组是否超过threshold，如果超过阀值，则需要对HashEntry数组扩容；
2）如何扩容
在扩容的时候，首先创建一个容量是原来容量两倍的数组，将原数组的元素再散列后插入到新的数组里。为了高效ConcurrentHashMap只对某个Segment进行扩容，不会对整个容器扩容。
第二：定位添加元素对应的位置，然后将其放到HashEntry数组中。
3、size操作：
如果需要统计整个ConcurrentHashMap的容量，需要统计所有Segment容量然后求和，Segment提供变量count用于存储当前Segment的容量。统计size的安全方式：在put()、clean()、 remove()方法时锁住变量，防止累加count的操作的过程中之前累加过的count发生变化，但这种效率非常低下的。
由于在累加count的操作的过程中之前累加过的count发生变化的几率非常小，所以ConcurrentHashMap先尝试2次不锁住Segment的方式来统计每个Segment的大小，如果在统计的过程中Segment的count发生了变化，这时候再加锁统计Segment的count。
ConcurrentHashMap如何判断统计过程中Segment的cout发生了变化？
Segment使用变量modCount来表示Segment大小是否发生变化，在put/remove/clean操作里都会将modCount加1，那么在统计size的前后只需要比较modCount是否发生了变化，如果发生变化，Segment的大小肯定发生了变化。
借鉴书籍：《java并发编程的艺术》