ConcurrentHashMap与HashMap的区别

HashMap是线程不安全的，在多线程的环境下，使用HashMap的put方法会引起死循环，导致CPU的使用率接近100%

HashTable

HashTable与hashmap的实现类似，但是HashTable不允许key和value为null

HashTable是线程安全的，但是HashTable线程安全的策略实现代价太大了，get/put所有相关操作都是synchronized的，相当于给整个哈希表加了把大锁。
多线程访问的时候，只要有一个线程方位或者操作该对象，那么其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景会非常的差。

ConcurrentHashMap

该集合主要是为了应对hashMap在并发环境中不安全而诞生的。大量使用了Volatile，final，CAS等lock-free技术来减少锁竞争对于性能的影响。

Map一般是通过数组+链表的结构（JDK1.8之后为数组和红黑树）

ConcurrentHashMap避免对整个集合都加锁，改成局部加锁操作。

JDK1.7中的ConcurrenthashMapd的实现原理

采用数组+Segment+分段锁的方式实现。

Segment(分段锁)--减少锁的粒度

segment，类似HashMap的结构，即内部拥有一个Entry数组，数组中的每隔元素又是一个链表，同时又是一个ReentrantLock(Segment继承了ReentrantLock)

内部结构

concurentHashMap使用分段所技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程方位，实现并发访问。

从上述结构中，我们能看出，concurrentHashMap定位一个元素的过程需要进习两次Hash操作。

第一次Hash定位到Segment，第二次Hash定位到元素所在的链表头部。

结构的优劣势

坏处：这种结构的副作用是Hash的过程要比普通的HashMap要长。

好处：写操作的时候可以只对元素所在的Segment进行加锁即可，不会影响到其他的Segment。这样，在最理想的情况下，concurrenthashMap可以最高同时支持Segment数量大小的写操作（这些写操作正好对应每一个Segment）。

1.8中的实现原理

ConcurrentHashMap参考了JDK8 Hash Map的实现，采用了数组+链表+红黑树的实现方式来设计，内部采取大量的CAS操作。

CAS操作即 compara and swap 比较交换。
JDK8中放弃使用Segment，使用Node，设计思想也不再是JDK1.7中的分段锁思想。

Node:

保存key，value以及key的hash值的数据结构。其中value和next都用volatile修饰，保证并发的可见性。

class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    volatile V val;
    volatile Node<K,V> next;
    //... 省略部分代码
}

结构上与1.8的Hashmap基本一样，不过保证线程安全了。

由于ConcurrentHashMap引入红黑树的结构，使得其实现变得复杂，我们都知道，红黑树是一种性能非常好的二叉排序树。

总结

相比较1.8中的HashMap，这两者的结构已经非常相近了，只是ConcurrentHashMap只是增加了同步的操作来控制并发。

从JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本的Synchronized+CAS+HashEntry+红黑树。

1、数据结构：取消了Segment分段锁的数据结构，使用了数组+链表+红黑树的结构。

2、保证线程安全机制：JDK1.7使用Segment的分段锁机制实现线程安全，其中segment继承自ReentrantLock。JDK1.8则是通过CAS+Synchronized来保证线程安全。

3、锁的粒度：原本是对每个Segment加锁，现在是对每隔数组元素加锁（Node）

4、链表准换为红黑树：定位节点的Hash算法简化会带来弊端，Hash冲突加剧，因此在链表节点数量大于8时，会将链表转换成红黑树进行存储。

5、查询时间复杂度：从原来的遍历链表O(n)，变成遍历红黑树O(logN)