CurrentHashMap

高并发环境下，HashMap可能出现的致命问题

假设一个hashMAp已经到了Resize的临界点，此时有两个线程AB,在同一时刻对HashMap进行put操作，链表可能会出现环形。此时如果使用get, 由于带有环形链表，所以程序会进入死循环！
想要避免HashMap的线程安全问题，可以改用HashTable或者Collections.synchronizedMap
但是两者性能都不高，无论是读还是写，它们都会给整个集合加锁，导致同一时间的其他操作为之阻塞。
这时候，兼顾安全和效率，ConcurrentHashMap应运而生

ConcurrentHashMap 实现原理：最关键是要理解一个概念 Segment

Segment本身就相当于一个HashMap对象。同HashMap一样，Segment包含一个HashEntry数组，数组中的每一个HashEntry既是一个键值对，也是一个链表的头节点。单一的Segment结构如下：

像这样的Segment对象，在ConcurrentHashMap集合中有多少个呢？有2的N次方个且共同保存在一个名为segments的数组当中。
因此整个ConcurrentHashMap的结构如下：

可以说，ConcurrentHashMap是一个二级哈希表。在一个总的哈希表下面，有若干个子哈希表。这样的二级结构，和数据库的水平拆分有些相似。

ConcurrentHashMap采用了锁分段(lock segment)技术，每一个segment就好比一个自治区，读写高度自治，segment之间互不影响。
Case1：不同Segment的并发写入：可以
Case2：同一Segment的一写一读：可以
Case3：同一Segment的并发写入：上锁，不能并发写入，会阻塞
由此可见，ConcurrentHashMap当中每个Segment各自持有一把锁。在保证线程安全的同时降低了锁的粒度，让并发操作效率更高。

ConcurrentHashMap在对Key求Hash值的时候，为了实现Segment均匀分布，进行了两次Hash。首先定位segment然后定位segment内的数组下标。
Get方法：
1.为输入的Key做Hash运算，得到hash值。
2.通过hash值，定位到对应的Segment对象
3.再次通过hash值，定位到Segment当中数组的具体位置。

Put方法：
1.为输入的Key做Hash运算，得到hash值。
2.通过hash值，定位到对应的Segment对象
3.获取可重入锁
4.再次通过hash值，定位到Segment当中数组的具体位置。
5.插入或覆盖HashEntry对象。
6.释放锁。

ConcurrentHashMap的size()操作：
ConcurrentHashMap的size()方法是一个嵌套循环，大体逻辑如下：
1.遍历所有的Segment。
2.把Segment的元素数量累加起来。
3.把Segment的修改次数累加起来。
4.判断所有Segment的总修改次数是否大于上一次的总修改次数。如果大于，说明统计过程中有修改，重新统计，尝试次数+1；如果不是。说明没有修改，统计结束。
5.如果尝试次数超过阈值，则对每一个Segment加锁，再重新统计。
6.再次判断所有Segment的总修改次数是否大于上一次的总修改次数。由于已经加锁，次数一定和上次相等。
7.释放锁，统计结束。

总结：为了尽量不锁住所有Segment，首先乐观地假设Size过程中不会有修改。当尝试一定次数，才无奈转为悲观锁，锁住所有Segment保证强一致性。