为什么ConcurrentHashMap是线程安全的？
为什么ConcurrentHashMap是线程安全的？
ConcurrentHashMap是Java中用于实现线程安全的哈希表，其在不同JDK版本中的实现机制有所不同。本文将详细解析ConcurrentHashMap在JDK 1.7和JDK 1.8中的底层实现原理及其线程安全机制。
JDK 1.7 底层实现
ConcurrentHashMap在不同的JDK版本中实现是不同的。在JDK 1.7中，它使用的是数组加链表的形式实现的，而数组又分为：大数组Segment和小数组HashEntry。大数组Segment可以理解为MySQL中的数据库，而每个数据库（Segment）中又有很多张表HashEntry，每个HashEntry中又有多条数据，这些数据是用链表连接的，如下图所示：
JDK 1.7 线程安全实现
了解了ConcurrentHashMap的底层实现，再看它的线程安全实现就比较简单了。接下来，我们通过添加元素put方法，来看JDK 1.7中ConcurrentHashMap是如何保证线程安全的，具体实现源码如下：
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
// 在往该Segment写入前，先确保获取到锁
HashEntry<K,V> node = tryLock() ? null : scanAndLockForPut(key, hash, value);
V oldValue;
try {
// Segment内部数组
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
// 更新已有值...
}
else {
// 放置HashEntry到特定位置，如果超过阈值则进行rehash
// 忽略其他代码...
}
}
} finally {
// 释放锁
unlock();
}
return oldValue;
}
从上述源码可以看出，Segment本身是基于ReentrantLock实现的加锁和释放锁的操作，这样就能保证多个线程同时访问ConcurrentHashMap时，同一时间只有一个线程能操作相应的节点，这样就保证了ConcurrentHashMap的线程安全了。也就是说ConcurrentHashMap的线程安全是建立在Segment加锁的基础上的，所以我们把它称之为分段锁或片段锁，如下图所示：
JDK 1.8 底层实现
在JDK 1.7中，ConcurrentHashMap虽然是线程安全的，但因为它的底层实现是数组+链表的形式，所以在数据比较多的情况下访问是很慢的，因为要遍历整个链表，而JDK 1.8则使用了数组+链表/红黑树的方式优化了ConcurrentHashMap的实现，具体实现结构如下：
链表升级为红黑树的规则：当链表长度大于8，并且数组的长度大于64时，链表就会升级为红黑树的结构。
PS：ConcurrentHashMap在JDK 1.8虽然保留了Segment的定义，但这仅仅是为了保证序列化时的兼容性，不再有任何结构上的用处了。
JDK 1.8 线程安全实现
在JDK 1.8中ConcurrentHashMap使用的是CAS+volatile或synchronized的方式来保证线程安全的，它的核心实现源码如下：
final V putVal(K key, V value, boolean onlyIfAbsent) { if (key == null || value == null) throw new NullPointerException();
int hash = spread(key.hashCode());
int binCount = 0;
for (Node<K,V>[] tab = table;;) {
Node<K,V> f; int n, i, fh; K fk; V fv;
if (tab == null || (n = tab.length) == 0)
tab = initTable();
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { // 节点为空
// 利用CAS去进行无锁线程安全操作，如果bin是空的
if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value)))
break;
}
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else if (onlyIfAbsent
&& fh == hash
&& ((fk = f.key) == key || (fk != null && key.equals(fk)))
&& (fv = f.val) != null)
return fv;
else {
V oldVal = null;
synchronized (f) {
// 细粒度的同步修改操作...
}
}
// 如果超过阈值，升级为红黑树
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD)
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount);
return null;
}
从上述源码可以看出，在JDK 1.8中，添加元素时首先会判断容器是否为空，如果为空则使用volatile加CAS来初始化。如果容器不为空则根据存储的元素计算该位置是否为空，如果为空则利用CAS设置该节点；如果不为空则使用synchronize加锁，遍历桶中的数据，替换或新增节点到桶中，最后再判断是否需要转为红黑树，这样就能保证并发访问时的线程安全了。
我们把上述流程简化一下，我们可以简单的认为在JDK 1.8中，ConcurrentHashMap是在头节点加锁来保证线程安全的，锁的粒度相比Segment来说更小了，发生冲突和加锁的频率降低了，并发操作的性能就提高了。而且JDK 1.8使用的是红黑树优化了之前的固定链表，那么当数据量比较大的时候，查询性能也得到了很大的提升，从之前的O(n)优化到了O(logn)的时间复杂度，具体加锁示意图如下：
总结
ConcurrentHashMap在JDK 1.7时使用的是数据加链表的形式实现的，其中数组分为两类：大数组Segment和小数组HashEntry，而加锁是通过给Segment添加ReentrantLock锁来实现线程安全的。而JDK 1.8中ConcurrentHashMap使用的是数组+链表/红黑树的方式实现的，它是通过CAS或synchronized来实现线程安全的，并且它的锁粒度更小，查询性能也更高。