19-谈谈ConcurrentHashMap，HashMap，Hashtable的区别

1，首先，来看看其他几个相关的类

Hashtable是线程安全的，但效率低
HashMap是线程不安全的，但效率高
Collections.synchronizedMap()，工具类提供了同步包装器的方法，来返回具有线程安全的集合对象
性能依然有问题

public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m) {
return new SynchronizedMap<>(m);
}
//在这个类的内部方法实现上，也只是单纯加上了锁
public V put(K key, V value) {
synchronized (mutex) {return m.put(key, value);}
}

为解决这样的矛盾问题，所以JDK提供了并发包，来平衡这样的问题（java.util.concurrent）

2，ConcurrentHashMap（重点）

• 兼顾了线程安全和效率的问题

分析：HashTable锁了整段数据（用户操作是不同的数据段，依然需要等待）
解决方案：把数据分段，执行分段锁（分离锁），核心把锁的范围变小，这样出现并发冲突的概率就变小
在保存的时候，计算所存储的数据是属于哪一段，只锁当前这一段

• 注意：分段锁（分离锁）是JDK1.8之前的一种的方案，JDK1.8之后做了优化。

JDK1.7跟JDK1.8在ConcurrentHashMap的实现上存在以下区别：

1，数据结构

JDK1.7采用链表的方式，而JDK1.8则采用链表+红黑树的方式

2，发生hash碰撞之后

JDK1.7发生碰撞之后，会采用链表的方式来解决

JDK1.8发生碰撞之后，默认采用链表，但当链表的长度超过8，且数组容量超过64时，会转换为红黑树存储

3，保证并发安全

JDK1.7采用分段锁的方式，而JDK1.8采用CAS和synchronized的组合模式

4，查询复杂度

JDK1.7采用链表的方式，时间复杂度为O(n)，而JDK1.8在采用红黑树的方式时，时间复杂度为O(log(n))

题外话：

不过红黑树其实是一种兜底方案，因为当链表数量达到8个的时候，其发生的概率是千万分之几，所以作者考虑到这种极端情况下，需要用红黑树的方式来优化