网站不备案做seo没用,沂水网站建设,做微信公众号微网站吗,网站建设类别ConcurrentHashMap 是 HashMap 的多线程版本#xff0c;HashMap 在并发操作时会有各种问题#xff0c;比如死循环问题、数据覆盖等问题。而这些问题#xff0c;只要使用 ConcurrentHashMap 就可以完美解决了#xff0c;那问题来了#xff0c;ConcurrentHashMap 是如何保证…ConcurrentHashMap 是 HashMap 的多线程版本HashMap 在并发操作时会有各种问题比如死循环问题、数据覆盖等问题。而这些问题只要使用 ConcurrentHashMap 就可以完美解决了那问题来了ConcurrentHashMap 是如何保证线程安全的它的底层又是如何实现的接下来我们一起来看。
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 写入前先确保获取到锁HashEntryK,V node tryLock() ? null : scanAndLockForPut(key, hash, value); V oldValue;try {// Segment 内部数组HashEntryK,V[] tab table;int index (tab.length - 1) hash;HashEntryK,V first entryAt(tab, index);for (HashEntryK,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 时链表就会升级为红黑树的结构。 PSConcurrentHashMap 在 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 (NodeK,V[] tab table;;) {NodeK,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 NodeK,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 来实现线程安全的并且它的锁粒度更小查询性能也更高。
