为什么要用ConcurrentHashMap
为什么要用ConcurrentHashMap
一、HashMap的线程安全问题
1、线程安全
在我刚开始接触并发的时候，对于线程安全这个词语很不理解，线程有什么安全性可言呢！后来慢慢地发
现线程安全实际上指的是线程的内存安全，多个线程在对共享数据进行操作时，可能会出现数据不一致的情况
所以HashMap的线程安全问题，我们可以理解为多个线程在HashMap这种数据结构中的数据进行操作可能
会出现的数据不一致的情况；显然HashMap不是线程安全的，在并发插入元素时，有可能出现环形链表，让下
一次读操作出现死循环，下面会进行详细的阐述
2、ReHash的问题
HashMap的容量是有限的，当经过多次元素插入时，HashMap达到一定的饱和度时，Key映射位置发生冲突
的几率会逐渐提高的，这个时候HashMap需要扩展它的长度，也就是Resize，ReHash就是Resize过程中的一个
步骤，影响Resize的因素主要有两个：
Capacity : HashMap的当前长度，HashMap的长度一定是2的幂次方
LoadFactor：HashMap的负载因子，默认值为0.75f
判断HashMap是否进行Resize的条件如下：HashMap.Size >= Capacity*LoadFactor
Resize的具体过程：
扩容：创建一个新的Entry数组，长度是原数组的2倍
ReHash：遍历原数组，将所有的Entry重新Hash到新数组（在长度改变后，Hash规则也随之改变），
Hash的具体公式如下： index = HashCode（Key）& （Length - 1）,当原数组长度为8的时候,
Hash之后的结果是和111B做运算；新数组的长度为16，Hash运算是和1111B做运算，结果不同
//ReHash的源码如下
public void transfer(Entry[] newTable,boolean rehash){
int newCapacity = newTable.length;
for(Entry<K,V> e:table){
while(e!= null){
Entry<K,V> next = e.next;
if(rehash){
e.hash = null == e.key? 0:hash(e.key);
}
int i = indexFor(e.hash,newCapacity);
e.next = newTable[i];
newTable[i] = e;
e = next;
}
}
}
- 至于ReHash形成环的过程实在是太复杂了，这里我就不说了，形成的效果图如下：
如果说调用Get查找一个不存在的Key时，而这个Key的Hash结果恰好等于3的时候，由于位置3带有环形
链表，所以程序将会进入死循环。这就是高并发环境下HashMap的线程安全问题
（3）解决方案
对于HashMap的线程安全问题可以使用HashTable和Collections.synchronizedMap来解决，但是这两种方案
在性能方面比较低下，无论是读操作还是写操作，它们都会给整个的集合加锁，导致同一时间其他的操作被阻塞
此时，兼具线程安全和运行效率的ConcurrentHashMap就应运而生了
二、ConcurrentHashMap原理 JDK 1.7
1.ConcurrentHashMap的结构
ConcurrentHashMap相比HashMap其实就是多了一个锁分段技术（Segment），Segment本身就是
HashMap对象，同HashMap一样，Segment包含一个HashEntry数组，数组的每一个HashEntry既是一个
键值对，也是一个链表的头节点；在ConcurrentHashMap集合中一共有2的N次方个，共同保存在一个名为
segments的数组中
从ConcurrentHashMap的结构图中可以看出它是一个二级哈希表，在一个总的哈希表下面，有若干个子
哈希表，这跟数据库的水平拆分非常相似；每一个Segment就像一个自治区，读写是高度自治的，Segment
之间是互不影响的，这就是我们说的锁分段技术
2.典型场景下的工作方式
不同Segment的写入是可以并发执行的
同一Segment的写和读是可以并发执行的
同一个Segment的写入是需要上锁的，线程会出现阻塞状态
由此可见，ConcurrentHashMap当中每个Segment各自持有一把锁，在保证线程安全的同时降低了
锁的粒度，让并发操作的效率更高
3.ConcurrentHashMap的读写过程
（1）读过程(Get方法)
为输入的Key做Hash运算，得到Hash值
通过Hash值，定位到对应的Segment对象
再次通过hash值，定位到Segment当中数组的具体位置
（2）写过程 (Put方法)
为输入的Key做Hash运算，得到hash值
通过hash值，定位到对应的Segment对象
获取可重入锁
再次通过hash值，定位到Segment当中数组的具体位置
插入或者覆盖HashEntry对象
释放锁
从读写的步骤中可以看出，ConcurrentHashMap在读写时都需要二次定位，首先定位到Segment，之后定位
到Segment内的具体数组下标
4.size()方法如何解决一致性的问题
size（）方法的目的是统计ConcurrentHashMap的总元素数量，自然需要把每个Segment内部的元素数量
汇总起来，但是如果在统计Segment元素数量的过程中，已经统计过的Segment瞬间插入新的元素，会不出现
不一致的情况呢？size()方法的执行过程是这样的
遍历所有的Segment
把Segment的元素数量累加起来
把Segment的修改次数累加起来
判断Segment的总修改次数是否大于上一次的总修改次数；如果大于，说明统计过程中有修改，重新统计
尝试次数加1；如果不是，说明没有修改，统计结束
如果尝试次数超过阈值，则对每一个Segment加锁，再重新统计
再次判断所有Segment的总修改次数是否大于上一次的总修改次数。由于已经加锁，次数一定和上次相等
释放锁，统计结束
这样设计是因为尽量不锁住所有Segment，首先假设Size过程中不会有修改，当尝试一定次数时，才会转化
成悲观锁，锁住所有的Segment保证强一致性
三、ConcurrentHashMap原理 JDK 1.8
1.JDK 1.8相较于1.7有哪些改进
JDK 1.7已经解决了并发的问题，并且能支持N个Segment这么多次数的并发，但是查询遍历链表的效率太低
所以在JDK 1.8中采用了红黑树，保证了查询的效率是O（logn）；而且抛弃了原有的Segment分段锁，而采用了
CAS + synchronized来保证并发的安全性
2.JDK 1.8的结构图
3.源码解析
JDK 1.8中使用Node代替HashEntry，但所用是相同的
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; //哈希值
final K key;
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;
}
public final K getKey() { return key; }
public final V getValue() { return val; }
public final int hashCode() { return key.hashCode() ^ val.hashCode(); }
public final String toString(){ return key + "=" + val; }
public final V setValue(V value) {
throw new UnsupportedOperationException();
}
put（）方法的过程，由于put（）方法源码较多，我们只看关键步骤即可
根据key计算出hashcode
判断是否需要进行初始化
f即为当前key定位出的Node,如果为空表示当前位置可以写入数据，利用CAS尝试写入，失败则自旋保证成功
如果当前位置的hashcode == MOVED == -1，则需要进行扩容
如果都不满足，则利用synchronized 锁写入数据
如果数量大于TREEIFY_THRESHOLD（默认为8），则要转换成红黑树
get（）方法的过程
根据计算出的hashcode 寻址，如果在桶上直接返回值
如果是红黑树，那就按照树的方式获取值
如果都不满足那就按照链表的方式遍历获取值