基础--Concurrenthashmap的实现原理分析

一、为什么用ConcurrentHashMap？

        ConcurrentHashMap线程安全且高效的操作，如下图对比所示。而HashMap非线程安全，在put操作时，易出现死循环，即：链表会形成环形（next元素指向前一个元素）。

jdk1.7中采用Segment[] + HashEntry的方式进行实现

对于segment片段的理解

Segment是一种可重入锁（ReentrantLock：是一种过程可以多次声明该锁而不会对其自身进行阻塞的锁），在ConcurrentHashMap里扮演锁的角色 

ConcurrentHashMap初始化时，计算出Segment数组的大小size和每个Segment中HashEntry数组的大小cap，并初始化Segment数组的第一个元素；其中size大小为2的幂次方，默认为16，cap大小也是2的幂次方，最小值为2，最终结果根据根据初始化容量initialCapacity进行计算，其中Segment在实现上继承了ReentrantLock，这样就自带了锁的功能。

当执行put方法插入数据时，根据key的hash值，在Segment数组中找到相应的位置，如果相应位置的Segment还未初始化，则通过CAS进行赋值，接着执行Segment对象的put方法通过加锁机制插入数据。

1、线程A执行tryLock()方法成功获取锁，则把HashEntry对象插入到相应的位置；
2、线程B获取锁失败，则执行scanAndLockForPut()方法，在scanAndLockForPut方法中，会通过重复执行tryLock()方法尝试获取锁，在多处理器环境下，重复次数为64，单处理器重复次数为1，当执行tryLock()方法的次数超过上限时，则执行lock()方法挂起线程B；

3、当线程A执行完插入操作时，会通过unlock()方法释放锁，接着唤醒线程B继续执行；

size实现
因为ConcurrentHashMap是可以并发插入数据的，所以在准确计算元素时存在一定的难度，一般的思路是统计每个Segment对象中的元素个数，然后进行累加，但是这种方式计算出来的结果并不一样的准确的，因为在计算后面几个Segment的元素个数时，已经计算过的Segment同时可能有数据的插入或则删除，在1.7的实现中，采用了如下方式：

先采用不加锁的方式，连续计算元素的个数，最多计算3次： 
1、如果前后两次计算结果相同，则说明计算出来的元素个数是准确的； 
2、如果前后两次计算结果都不同，则给每个 Segment 进行加锁，再计算一次元素的个数； 

1.8实现

设计：Node对象+synchronized+CAS的设计方式来保证并发安全。
ConcurrentHashMap在1.8中的实现，相比于1.7的版本基本上全部都变掉了。首先，取消了Segment分段锁的数据结构，取而代之的是数组+链表（红黑树）的结构。而对于锁的粒度，调整为对每个数组元素加锁（Node）。然后是定位节点的hash算法被简化了，这样带来的弊端是Hash冲突会加剧。因此在链表节点数量大于8时，会将链表转化为红黑树进行存储。这样一来，查询的时间复杂度就会由原先的O(n)变为O(logN)。下面是其基本结构：
  

1.8中放弃了Segment臃肿的设计，取而代之的是采用Node + CAS + Synchronized来保证并发安全进行实现，

只有在执行第一次put方法时才会调用initTable()初始化Node数组，实现如下

总结1.8：

1.结构：Node数组 + 链表/红黑树的结构 .数组某下标位置对应的链表元素突破8个以后，转变为红黑树。红黑树元素小于6个变回成链表。

（TREEIFY_THRESHOLD=8 ；UNTREEIFY_THRESHOLD = 6;这里需要注意，不是元素小于6的时候一定会变成链表，只有resize的时候才会根据UNTREEIFY_THRESHOLD 进行转换，同样也不是到8的时候就变成红黑树（不是等到扩容的时候） 链表与红黑树的转换详情）

2.其线程安全都是使用volatile修饰且自旋CAS操作。

3.HashMap线程不安全
在put的时候，Resize（扩容）会造成数据的覆盖
JDK1.7 因为是头插法，可能会造成循环链表
JDK1.8 是尾插法

参考：

ConcurrentHashMap的实现原理_爱我所爱0505的博客-CSDN博客_concurrenthashmap的实现原理