ConcurrentHashMap底层实现原理（（JDK1.71.8））
⽬录
前⾔
我们都知道HashMap在多线程情况下，在put的时候，插⼊的元素超过了容量（由负载因⼦决定）的范围就会触发扩容操作，就是rehash，这个会重新将原数组的内容重新hash到新的扩容数组中，在多线程的环境下，存在同时其他的元素也在进⾏put操作，如果hash 值相同，可能出现同时在同⼀数组下⽤链表表⽰，造成闭环，导致在get时会出现死循环，所以HashMap是线程不安全的。
我们来了解另⼀个键值存储集合HashTable，它是线程安全的，它在所有涉及到多线程操作的都加上了synchronized关键字来锁住整个table，这就意味着所有的线程都在竞争⼀把锁，在多线程的环境下，它是安全的，但是⽆疑是效率低下的。
其实HashTable有很多的优化空间，锁住整个table这么粗暴的⽅法可以变相的柔和点，⽐如在多线程的环境下，对不同的数据集进⾏操作时其实根本就不需要去竞争⼀个锁，因为他们不同hash值，不会因为rehash造成线程不安全，所以互不影响，这就是锁分离技术，将锁的粒度降低，利⽤多个锁来控制多个⼩的table
ConcurrentHashMap （JDK1.7的实现）
在JDK1.7版本中，ConcurrentHashMap的数据结构是由⼀个Segment数组和多个HashEntry组成，如下图所⽰：
Segment数组的意义就是将⼀个⼤的table分割成多个⼩的table来进⾏加锁，也就是上⾯的提到的锁分离技术，⽽每⼀个Segment元素存储的是HashEntry数组+链表，这个和HashMap的数据存储结构⼀样
初始化
ConcurrentHashMap的初始化是会通过位与运算来初始化Segment的⼤⼩，⽤ssize来表⽰，如下所⽰
int size =1;
while(size < concurrencyLevel) {
++a;
size <<=1;
}
如上所⽰，因为ssize⽤位于运算来计算（ ssize <<=1 ），所以Segment的⼤⼩取值都是以2的N次⽅，⽆关concurrencyLevel的取值，当然concurrencyLevel最⼤只能⽤16位的⼆进制来表⽰，即65536，换句话说，Segment的⼤⼩最多65536个，没有指定concurrencyLevel元素初始化，Segment的⼤⼩ssize默认为16
每⼀个Segment元素下的HashEntry的初始化也是按照位于运算来计算，⽤cap来表⽰，如下所⽰
int cap =1;
while(cap < c)
cap <<=1;
如上所⽰，HashEntry⼤⼩的计算也是2的N次⽅（cap <<=1）， cap的初始值为1，所以HashEntry最⼩的容量为2
put操作
对于ConcurrentHashMap的数据插⼊，这⾥要进⾏两次Hash去定位数据的存储位置
static class Segment<K,V> extends ReentrantLock implements Serializable {
}
从上Segment的继承体系可以看出，Segment实现了ReentrantLock，也就带有锁的功能，当执⾏put操作时，会进⾏第⼀次key的hash来定位Segment的位置，如果该Segment还没有初始化，即通过CAS操作进⾏赋值，然后进⾏第⼆次hash操作，找到相应的HashEntry的位置，这⾥会利⽤继承过来的锁的特性，在将数据插⼊指定的HashEntry位置时（链表的尾端），会通过继承ReentrantLock的
tryLock（）⽅法尝试去获取锁，如果获取成功就直接插⼊相应的位置，如果已经有线程获取该Segment的锁，那当前线程会以⾃旋的⽅式去继续的调⽤tryLock（）⽅法去获取锁，超过指定次数就挂起，等待唤醒
get操作
ConcurrentHashMap的get操作跟HashMap类似，只是ConcurrentHashMap第⼀次需要经过⼀次hash定位到Segment的位置，然后再hash定位到指定的HashEntry，遍历该HashEntry下的链表进⾏对⽐，成功就返回，不成功就返回null
size操作
计算ConcurrentHashMap的元素⼤⼩是⼀个有趣的问题，因为他是并发操作的，就是在你计算size的时候，他还在并发的插⼊数据，可能会导致你计算出来的size和你实际的size有相差（在你return size的时候，插⼊了多个数据），要解决这个问题，JDK1.7版本⽤两种⽅案
for(;;) {
if(retries++ == RETRIES_BEFORE_LOCK) {
for(int j = 0 ; j < gments.length; ++j) ensureSegment(j).lock(); // force creation
}
sum = 0L;
size = 0 ;
overflow = fal ;
for ( int j = 0 ; j < gments.length; ++j) {
Segment<K,V> g = gmentAt(gments, j);
if (g != null ) { sum += g.modCount; int c = g.count; if (c < 0 || (size += c) < 0 )
overflow = true ;
} }
if (sum == last) break ;
last = sum; } }
finally {
if (retries > RETRIES_BEFORE_LOCK) {
for ( int j = 0 ; j < gments.length; ++j)
gmentAt(gments, j).unlock();
}
}
1. 第⼀种⽅案他会使⽤不加锁的模式去尝试多次计算ConcurrentHashMap的size，最多三次，⽐较前后两次计算的结果，结果⼀致就
认为当前没有元素加⼊，计算的结果是准确的
2. 第⼆种⽅案是如果第⼀种⽅案不符合，他就会给每个Segment加上锁，然后计算ConcurrentHashMap的size返回ConcurrentHashMap （JDK1.8的实现）
JDK1.8的实现已经摒弃了Segment的概念，⽽是直接⽤Node数组+链表+红⿊树的数据结构来实现，
并发控制使⽤Synchronized和CAS 来操作，整个看起来就像是优化过且线程安全的HashMap，虽然在JDK1.8中还能看到Segment的数据结构，但是已经简化了属性，只是为了兼容旧版本
说明：ConcurrentHashMap的数据结构（数组+链表+红⿊树），桶中的结构可能是链表，也可能是红⿊树，红⿊树是为了提⾼查找效率。
在深⼊JDK1.8的put和get实现之前要知道⼀些常量设计和数据结构，这些是构成ConcurrentHashMap实现结构的基础，下⾯看⼀下基本属性：
// node数组最⼤容量：2^30=1073741824
private static final int MAXIMUM_CAPACITY = 1 << 30 ;
// 默认初始值，必须是2的幕数
private static final int DEFAULT_CAPACITY = 16 ;
//数组可能最⼤值，需要与toArray（）相关⽅法关联
static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8 ;
/
/并发级别，遗留下来的，为兼容以前的版本
private static final int DEFAULT_CONCURRENCY_LEVEL = 16 ;
// 负载因⼦
private static final float LOAD_FACTOR = 0 .75f;
// 链表转红⿊树阀值,> 8 链表转换为红⿊树
static final int TREEIFY_THRESHOLD = 8 ;
//树转链表阀值，⼩于等于6（tranfer时，lc、hc=0两个计数器分别++记录原bin、新binTreeNode数量，<=UNTREEIFY_THRESHOLD 则untreeify(lo)）
static final int UNTREEIFY_THRESHOLD = 6 ;
static final int MIN_TREEIFY_CAPACITY = 64 ;
private static final int MIN_TRANSFER_STRIDE = 16 ;
private static int RESIZE_STAMP_BITS = 16 ;
// 2^15-1，help resize的最⼤线程数
private static final int MAX_RESIZERS = ( 1 << ( 32 - RESIZE_STAMP_BITS)) - 1 ;
// 32-16=16，sizeCtl中记录size⼤⼩的偏移量
// 32-16=16，sizeCtl中记录size⼤⼩的偏移量
private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;
// forwarding nodes的hash值
static final int MOVED = - 1 ;
// 树根节点的hash值
static final int TREEBIN = - 2 ;
// RervationNode的hash值
static final int RESERVED = - 3 ;
/
/ 可⽤处理器数量
static final int NCPU = Runtime().availableProcessors();
//存放node的数组
transient volatile Node<K,V>[] table;
/*控制标识符，⽤来控制table的初始化和扩容的操作，不同的值有不同的含义
*当为负数时：- 1 代表正在初始化，-N代表有N- 1 个线程正在进⾏扩容
*当为 0 时：代表当时的table还没有被初始化
*当为正数时：表⽰初始化或者下⼀次进⾏扩容的⼤⼩
*/
private transient volatile int sizeCtl;
基本属性定义了ConcurrentHashMap的⼀些边界以及操作时的⼀些控制，下⾯看⼀些内部的⼀些结构组成，这些是整个ConcurrentHashMap整个数据结构的核⼼
Node
Node是ConcurrentHashMap存储结构的基本单元，继承于HashMap中的Entry，⽤于存储数据，源代码如下
static class Node<K,V> implements Map.Entry<K,V> {
//链表的数据结构
final int hash;
final K key;
//val和next都会在扩容时发⽣变化，所以加上volatile来保持可见性和禁⽌重排序
volatile V val;
volatile Node<K,V> next;
Node( int hash, K key, V val, Node<K,V> next) {
this .hash = hash;
this .key = key;
this .val = val;
this .next = next;
