巩义便宜网站建设公司,常州网站建设哪家便宜,wordpress哪里找域名,wordpress可以自己写代码吗第10讲 | 如何保证集合是线程安全的? ConcurrentHashMap如何实现高效地线程安全#xff1f; 我在之前两讲介绍了 Java 集合框架的典型容器类#xff0c;它们绝大部分都不是线程安全的#xff0c;仅有的线程安全实现#xff0c;比如 Vector、Stack#xff0c;在性能方面也…第10讲 | 如何保证集合是线程安全的? ConcurrentHashMap如何实现高效地线程安全 我在之前两讲介绍了 Java 集合框架的典型容器类它们绝大部分都不是线程安全的仅有的线程安全实现比如 Vector、Stack在性能方面也远不尽如人意。幸好 Java 语言提供了并发包java.util.concurrent为高度并发需求提供了更加全面的工具支持。
今天我要问你的问题是如何保证容器是线程安全的ConcurrentHashMap 如何实现高效地线程安全
典型回答
Java 提供了不同层面的线程安全支持。在传统集合框架内部除了 Hashtable 等同步容器还提供了所谓的同步包装器Synchronized Wrapper我们可以调用 Collections 工具类提供的包装方法来获取一个同步的包装容器如 Collections.synchronizedMap但是它们都是利用非常粗粒度的同步方式在高并发情况下性能比较低下。
另外更加普遍的选择是利用并发包提供的线程安全容器类它提供了
各种并发容器比如 ConcurrentHashMap、CopyOnWriteArrayList。
各种线程安全队列Queue/Deque如 ArrayBlockingQueue、SynchronousQueue。
各种有序容器的线程安全版本等。
具体保证线程安全的方式包括有从简单的 synchronize 方式到基于更加精细化的比如基于分离锁实现的 ConcurrentHashMap 等并发实现等。具体选择要看开发的场景需求总体来说并发包内提供的容器通用场景远优于早期的简单同步实现。
考点分析
谈到线程安全和并发可以说是 Java 面试中必考的考点我上面给出的回答是一个相对宽泛的总结而且 ConcurrentHashMap 等并发容器实现也在不断演进不能一概而论。
如果要深入思考并回答这个问题及其扩展方面至少需要
理解基本的线程安全工具。
理解传统集合框架并发编程中 Map 存在的问题清楚简单同步方式的不足。
梳理并发包内尤其是 ConcurrentHashMap 采取了哪些方法来提高并发表现。
最好能够掌握 ConcurrentHashMap 自身的演进目前的很多分析资料还是基于其早期版本。
今天我主要是延续专栏之前两讲的内容重点解读经常被同时考察的 HashMap 和 ConcurrentHashMap。今天这一讲并不是对并发方面的全面梳理毕竟这也不是专栏一讲可以介绍完整的算是个开胃菜吧类似 CAS 等更加底层的机制后面会在 Java 进阶模块中的并发主题有更加系统的介绍。
知识扩展
为什么需要 ConcurrentHashMap
Hashtable 本身比较低效因为它的实现基本就是将 put、get、size 等各种方法加上“synchronized”。简单来说这就导致了所有并发操作都要竞争同一把锁一个线程在进行同步操作时其他线程只能等待大大降低了并发操作的效率。
前面已经提过 HashMap 不是线程安全的并发情况会导致类似 CPU 占用 100% 等一些问题那么能不能利用 Collections 提供的同步包装器来解决问题呢
看看下面的代码片段我们发现同步包装器只是利用输入 Map 构造了另一个同步版本所有操作虽然不再声明成为 synchronized 方法但是还是利用了“this”作为互斥的 mutex没有真正意义上的改进 private static class SynchronizedMapK,Vimplements MapK,V, Serializable {private final MapK,V m; // Backing Mapfinal Object mutex; // Object on which to synchronize// …public int size() {synchronized (mutex) {return m.size();}}// …
}
所以Hashtable 或者同步包装版本都只是适合在非高度并发的场景下。
2.ConcurrentHashMap 分析
我们再来看看 ConcurrentHashMap 是如何设计实现的为什么它能大大提高并发效率。
首先我这里强调ConcurrentHashMap 的设计实现其实一直在演化比如在 Java 8 中就发生了非常大的变化Java 7 其实也有不少更新所以我这里将比较分析结构、实现机制等方面对比不同版本的主要区别。
早期 ConcurrentHashMap其实现是基于
分离锁也就是将内部进行分段Segment里面则是 HashEntry 的数组和 HashMap 类似哈希相同的条目也是以链表形式存放。
HashEntry 内部使用 volatile 的 value 字段来保证可见性也利用了不可变对象的机制以改进利用 Unsafe 提供的底层能力比如 volatile access去直接完成部分操作以最优化性能毕竟 Unsafe 中的很多操作都是 JVM intrinsic 优化过的。
你可以参考下面这个早期 ConcurrentHashMap 内部结构的示意图其核心是利用分段设计在进行并发操作的时候只需要锁定相应段这样就有效避免了类似 Hashtable 整体同步的问题大大提高了性能。 在构造的时候Segment 的数量由所谓的 concurrencyLevel 决定默认是 16也可以在相应构造函数直接指定。注意Java 需要它是 2 的幂数值如果输入是类似 15 这种非幂值会被自动调整到 16 之类 2 的幂数值。
具体情况我们一起看看一些 Map 基本操作的源码这是 JDK 7 比较新的 get 代码。针对具体的优化部分为方便理解我直接注释在代码段里get 操作需要保证的是可见性所以并没有什么同步逻辑。 public V get(Object key) {SegmentK,V s; // manually integrate access methods to reduce overheadHashEntryK,V[] tab;int h hash(key.hashCode());//利用位操作替换普通数学运算long u (((h segmentShift) segmentMask) SSHIFT) SBASE;// 以Segment为单位进行定位// 利用Unsafe直接进行volatile accessif ((s (SegmentK,V)UNSAFE.getObjectVolatile(segments, u)) ! null (tab s.table) ! null) {//省略}return null;}而对于 put 操作首先是通过二次哈希避免哈希冲突然后以 Unsafe 调用方式直接获取相应的 Segment然后进行线程安全的 put 操作
public V put(K key, V value) {SegmentK,V s;if (value null)throw new NullPointerException();// 二次哈希以保证数据的分散性避免哈希冲突int hash hash(key.hashCode());int j (hash segmentShift) segmentMask;if ((s (SegmentK,V)UNSAFE.getObject // nonvolatile; recheck(segments, (j SSHIFT) SBASE)) null) // in ensureSegments ensureSegment(j);return s.put(key, hash, value, false);}
其核心逻辑实现在下面的内部方法中 final V put(K key, int hash, V value, boolean onlyIfAbsent) {// scanAndLockForPut会去查找是否有key相同Node// 无论如何确保获取锁HashEntryK,V node tryLock() ? null :scanAndLockForPut(key, hash, value);V oldValue;try {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;// 更新已有value...}else {// 放置HashEntry到特定位置如果超过阈值进行rehash// ...}}} finally {unlock();}return oldValue;}
所以从上面的源码清晰的看出在进行并发写操作时
ConcurrentHashMap 会获取再入锁以保证数据一致性Segment 本身就是基于 ReentrantLock 的扩展实现所以在并发修改期间相应 Segment 是被锁定的。
在最初阶段进行重复性的扫描以确定相应 key 值是否已经在数组里面进而决定是更新还是放置操作你可以在代码里看到相应的注释。重复扫描、检测冲突是 ConcurrentHashMap 的常见技巧。
我在专栏上一讲介绍 HashMap 时提到了可能发生的扩容问题在 ConcurrentHashMap 中同样存在。不过有一个明显区别就是它进行的不是整体的扩容而是单独对 Segment 进行扩容细节就不介绍了。
另外一个 Map 的 size 方法同样需要关注它的实现涉及分离锁的一个副作用。
试想如果不进行同步简单的计算所有 Segment 的总值可能会因为并发 put导致结果不准确但是直接锁定所有 Segment 进行计算就会变得非常昂贵。其实分离锁也限制了 Map 的初始化等操作。
所以ConcurrentHashMap 的实现是通过重试机制RETRIES_BEFORE_LOCK指定重试次数 2来试图获得可靠值。如果没有监控到发生变化通过对比 Segment.modCount就直接返回否则获取锁进行操作。
下面我来对比一下在 Java 8 和之后的版本中ConcurrentHashMap 发生了哪些变化呢
总体结构上它的内部存储变得和我在专栏上一讲介绍的 HashMap 结构非常相似同样是大的桶bucket数组然后内部也是一个个所谓的链表结构bin同步的粒度要更细致一些。
其内部仍然有 Segment 定义但仅仅是为了保证序列化时的兼容性而已不再有任何结构上的用处。
因为不再使用 Segment初始化操作大大简化修改为 lazy-load 形式这样可以有效避免初始开销解决了老版本很多人抱怨的这一点。
数据存储利用 volatile 来保证可见性。
使用 CAS 等操作在特定场景进行无锁并发操作。
使用 Unsafe、LongAdder 之类底层手段进行极端情况的优化。
先看看现在的数据存储内部实现我们可以发现 Key 是 final 的因为在生命周期中一个条目的 Key 发生变化是不可能的与此同时 val则声明为 volatile以保证可见性。
static class NodeK,V implements Map.EntryK,V {final int hash;final K key;volatile V val;volatile NodeK,V next;// … }我这里就不再介绍 get 方法和构造函数了相对比较简单直接看并发的 put 是如何实现的。 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) {// 细粒度的同步修改操作... }}// Bin超过阈值进行树化if (binCount ! 0) {if (binCount TREEIFY_THRESHOLD)treeifyBin(tab, i);if (oldVal ! null)return oldVal;break;}}}addCount(1L, binCount);return null;
}
初始化操作实现在 initTable 里面这是一个典型的 CAS 使用场景利用 volatile 的 sizeCtl 作为互斥手段如果发现竞争性的初始化就 spin 在那里等待条件恢复否则利用 CAS 设置排他标志。如果成功则进行初始化否则重试。
请参考下面代码 private final NodeK,V[] initTable() {NodeK,V[] tab; int sc;while ((tab table) null || tab.length 0) {// 如果发现冲突进行spin等待if ((sc sizeCtl) 0)Thread.yield(); // CAS成功返回true则进入真正的初始化逻辑else if (U.compareAndSetInt(this, SIZECTL, sc, -1)) {try {if ((tab table) null || tab.length 0) {int n (sc 0) ? sc : DEFAULT_CAPACITY;SuppressWarnings(unchecked)NodeK,V[] nt (NodeK,V[])new Node?,?[n];table tab nt;sc n - (n 2);}} finally {sizeCtl sc;}break;}}return tab;
}
当 bin 为空时同样是没有必要锁定也是以 CAS 操作去放置。
你有没有注意到在同步逻辑上它使用的是 synchronized而不是通常建议的 ReentrantLock 之类这是为什么呢现代 JDK 中synchronized 已经被不断优化可以不再过分担心性能差异另外相比于 ReentrantLock它可以减少内存消耗这是个非常大的优势。
与此同时更多细节实现通过使用 Unsafe 进行了优化例如 tabAt 就是直接利用 getObjectAcquire避免间接调用的开销。
static final K,V NodeK,V tabAt(NodeK,V[] tab, int i) {return (NodeK,V)U.getObjectAcquire(tab, ((long)i ASHIFT) ABASE);
}
再看看现在是如何实现 size 操作的。阅读代码你会发现(http://hg.openjdk.java.net/jdk/jdk/file/12fc7bf488ec/src/java.base/share/classes/java/util/concurrent/ConcurrentHashMap.java)真正的逻辑是在 sumCount 方法中 那么 sumCount 做了什么呢
final long sumCount() {CounterCell[] as counterCells; CounterCell a;long sum baseCount;if (as ! null) {for (int i 0; i as.length; i) {if ((a as[i]) ! null)sum a.value;}}return sum;
}我们发现虽然思路仍然和以前类似都是分而治之的进行计数然后求和处理但实现却基于一个奇怪的 CounterCell。 难道它的数值就更加准确吗数据一致性是怎么保证的
static final class CounterCell {volatile long value;CounterCell(long x) { value x; }
}其实对于 CounterCell 的操作是基于 java.util.concurrent.atomic.LongAdder 进行的是一种 JVM 利用空间换取更高效率的方法利用了Striped64内部的复杂逻辑。这个东西非常小众大多数情况下建议还是使用 AtomicLong足以满足绝大部分应用的性能需求。
今天我从线程安全问题开始概念性的总结了基本容器工具分析了早期同步容器的问题进而分析了 Java 7 和 Java 8 中 ConcurrentHashMap 是如何设计实现的希望 ConcurrentHashMap 的并发技巧对你在日常开发可以有所帮助。
一课一练
关于今天我们讨论的题目你做到心中有数了吗留一个道思考题给你在产品代码中有没有典型的场景需要使用类似 ConcurrentHashMap 这样的并发容器呢
请你在留言区写写你对这个问题的思考我会选出经过认真思考的留言送给你一份学习鼓励金欢迎你与我一起讨论。
c.LongAdder 进行的是一种 JVM 利用空间换取更高效率的方法利用了Striped64内部的复杂逻辑。这个东西非常小众大多数情况下建议还是使用 AtomicLong足以满足绝大部分应用的性能需求。
今天我从线程安全问题开始概念性的总结了基本容器工具分析了早期同步容器的问题进而分析了 Java 7 和 Java 8 中 ConcurrentHashMap 是如何设计实现的希望 ConcurrentHashMap 的并发技巧对你在日常开发可以有所帮助。
一课一练
关于今天我们讨论的题目你做到心中有数了吗留一个道思考题给你在产品代码中有没有典型的场景需要使用类似 ConcurrentHashMap 这样的并发容器呢
请你在留言区写写你对这个问题的思考我会选出经过认真思考的留言送给你一份学习鼓励金欢迎你与我一起讨论。
你的朋友是不是也在准备面试呢你可以“请朋友读”把今天的题目分享给好友或许你能帮到他。
