Java集合HashMap不安全后果及ConcurrentHashMap 原理
HashMap
Map是我们在集合中非常重要的一个集合、我们刚学习HashMap的时候就说它不安全、可是不知道不安全会发生什么后果
我们先来看看JDK7和JDK8当中的HashMap有什么不一样
| JDK7 | JDK8 | |
|---|---|---|
| 数据结构 | 数组+ 链表。复杂度：O(n) | 数组 + 链表 + 红黑树 |
| 插入位置 | 头插法 | 尾插法 |
JDK7 HashMap链表循环造成死循环
造成HasMap链表循环列表的原因就是因为在hash冲突的时候采用了头插法且没有加锁的方式插入链表、在HashMap put的时候，put函数会检查元素是否超出了阈值【数组的总的添加元素数大于了 数组长度 * 0.75(默认,也可自己设定)】，如果超出了数组长度扩容为两倍，下面是它扩容时将旧hash表转到新hash表从而完成扩容的源代码
/**
* 作用：将旧数组上的数据（键值对）转移到新table中，从而完成扩容
* 过程：按旧链表的正序遍历链表、在新链表的头部依次插入。但是这样会导致扩容完成后，链表逆序
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
//通过遍历 旧数组，将旧数组上的数据（键值对）转移到新数组中
for (Entry<K,V> e : table) {
// 遍历hash碰撞形成的链表
while(null != e) {
// 拿到当前头节点的下一个节点
Entry<K,V> next = e.next;
// 是否要重新计算hashCode
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
//通过hashCode计算出hash表的槽
int i = indexFor(e.hash, newCapacity);
// 新hash表的hash槽赋值给e 的下一个节点
e.next = newTable[i];
// 讲当前元素，赋给新数组的对应下标位置。
newTable[i] = e;
// 访问下1个Entry链上的元素，如此不断循环，直到遍历完该链表上的所有节点
e = next;
}
}
}
在单线程中，这样的代码是没有什么问题，问题就是有很多个线程，我们假设有两个线程t1和t2，他们都执行到Entry<K,V> next = e.next;这一行，此时图示：
，t1的时间片已经用完了，t2还在继续执行，此时t1、t2获取的e和next分别为e1、e2、next1、next2，再之后t2完成了扩容操作，链表顺序已经从原来的abcd变成了dcba，t1线程的e在next的上方，如下图示：
此时t1线程醒过来了，继续执行就会出现链表循环，造成while死循环
JDK8 HashMap中已经采用尾插法进行插入避免了链表循环、且链表长度大于8会变成红黑树
HashMap数据丢失
jdk7：hashMap put的时候有hash冲突如果没有超过阈值，就会采用头插法来插入链表，假如有t1和t2线程，它们都同时获得了，链表的头节点，此时t1线程的时间片没有了，t2线程还在继续，t2线程已经执行完了put操作，t1线程醒过来，t1线程会将自己的下一个节点指向头节点，这样刚刚t2线程put的节点就丢失了
jdk8: 采用的是尾插法、一样的两个线程都同时获取了尾节点、后执行的那个线程会覆盖掉前一个线程的节点、造成丢失
HashMap在官方的设定的就是线程不安全的，要安全选ConcurrentHashMap
JDK7 ConcurrentHashMap
在jdk7 ConcurrentHashMap当中采用了一个分段锁的方式（Segment[]）来保证线程安全
Segment类继承了ReentrantLock，Segment类里有多个槽。
put：
计算出key在那个Segment，然后上锁，再算出在哪个槽里，此时如果有其它线程访问这个Segment会被阻塞住，直到unlock。
get：
CAS + volatile
在HashTable当中是锁住了整个对象，线程t1 get("key1") 、线程t2 put("key2", "value2")，线程t2也会被阻塞住，在ConcurrentHashMap中这两个操作是不会阻塞且不受影响。
值得注意的是Segment[]的初始长度，默认是16，不会因为数据的多少而改变，所以默认最多只有16个线程获得锁，这个初始值可以设置，但是需要我们自己去评估多少合适。
Segment分段锁实现下的ConcurrentHashMap的劣势：
- 寻找元素需要经过两次hash
- 并发级别（Segment[]长度）的合理设置问题。虽然提供了默认的并发级别，但是是否在大多数场景下都适用？归根结底，就是需要用户自己来评估需要多少把锁来分段治理的问题。
- 在存储成本比HashMap高。每个Segment管理的最少容量是2，而默认的并发级别为16，即16个Segment。假如我只需要存储的是16个元素，那么ConcurrentHashMap会需要占用2倍的存储空间。
JDK8 ConcurrentHashMap
在JDK8中，ConcurrentHashMap采用更加细粒度的锁取消分段锁，synchronized + CAS
put：
如果发现该槽没有数据，初始化头节点时，ConcurrentHashMap并没有加锁，而是CAS的方式进行原子替换（原子操作，基于Unsafe类的原子操作API）
如果发现该槽有数据，判断是否正在扩容，如果是则会去帮助扩容，扩容时会进行加锁处理，锁定是头节点。
如果发现该槽有节点且不在扩容，则会去锁（synchronized）住该槽的头节点，进行插入
get：
没有什么加锁的操作，hash表被volatile修饰