ConcurrentHashMap
ConcurrentHashMap 是 Java 并发包 (java.util.concurrent) 中的一种线程安全的哈希表实现。
HashMap 在多线程环境下扩容会出现 CPU 接近 100% 的情况,因为 HashMap 并不是线程安全的,我们可以通过 Collections 的 Map<K,V> synchronizedMap(Map<K,V> m) 将 HashMap 包装成一个线程安全的 map。
补充阅读:[为什么 HashMap 多线程扩容会 CPU 100%?](#为什么 HashMap 多线程扩容会 CPU 100%?)
比如 SynchronzedMap 的 put 方法源码就是加锁过的:
1 | public V put(K key, V value) { |
synchronized 同步代码块的方式我们前面也讲过了,大家应该都还有印象。
不过,这并不是最优雅的方式。Doug Lea 大师不遗余力的为我们创造了一些线程安全的并发容器,让每一个 Java 开发人员都倍感幸福。相对于 HashMap,ConcurrentHashMap 就是线程安全的 map,其中利用了锁分段的思想大大提高了并发的效率。
在介绍并发容器的时候,我们也曾提到过 ConcurrentHashMap,它从 JDK 1.8 开始有了较大的变化,光是代码量就足足增加了很多。
1.8 版本舍弃了 segment,并且使用了大量的 synchronized,以及 CAS 无锁操作以保证 ConcurrentHashMap 的线程安全性。
为什么不用 ReentrantLock 而是 synchronzied 呢?
实际上,synchronzied 做了很多的优化,这个我们前面也讲过了,包括偏向锁、轻量级锁、重量级锁,可以依次向上升级锁状态,因此,synchronized 相较于 ReentrantLock 的性能其实差不多,甚至在某些情况更优。
ConcurrentHashMap 的变化
ConcurrentHashMap 在 JDK 1.7 和 JDK 1.8 中有一些区别。这里我们分开介绍一下。
JDK 1.7
ConcurrentHashMap 在 JDK 1.7 中,提供了一种粒度更细的加锁机制,这种机制叫分段锁「Lock Striping」。整个哈希表被分为多个段,每个段都独立锁定。读取操作不需要锁,写入操作仅锁定相关的段。这减小了锁冲突的几率,从而提高了并发性能。
这种机制的优点:在并发环境下将实现更高的吞吐量,而在单线程环境下只损失非常小的性能。
JDK 1.8
TODO
为什么 HashMap 多线程扩容会 CPU 100%?
这句话说的是 JDK 1.7 及之前 的经典问题。核心原因是:多线程并发扩容时,HashMap 的链表会形成环形数据结构(成环),后续操作遍历链表时进入死循环,导致 CPU 跑满。
一、先理解单线程下的扩容过程
HashMap 默认容量 16,负载因子 0.75,当元素超过 12 个时就会扩容为原来的 2 倍(32)。
扩容(
resize)做两件事:
- 创建一个新的、两倍大的数组
- 把旧数组里的所有元素重新哈希(rehash),迁移到新数组
JDK 1.7 用的是「头插法」:迁移某个桶里的链表时,新节点永远插在链表头部。这会导致一个副作用——链表的顺序被反转了。
举个例子,旧桶里是
A → B → C → null:
- 迁移 C:新表桶头是
C → null- 迁移 B:新表桶头是
B → C → null- 迁移 A:新表桶头是
A → B → C → null单线程下没问题,只是顺序倒过来了。
二、多线程并发扩容时,为什么会成环?
假设有两个线程 Thread-A 和 Thread-B,同时触发了扩容。它们各自有自己的
newTable,但操作的是同一份旧链表。关键步骤(简化版):
1 旧链表: A → B → C → nullThread-B 先执行完扩容,把链表迁移到了自己的 newTable,变成:
1 Thread-B 的 newTable: C → B → A → null (头插法反转了顺序)这时 Thread-B 把
table = newTable赋值完成。然后 Thread-A 恢复执行,它手里还拿着旧链表的引用
e = A,next = B。它继续从头插法迁移:
newTable[i] = e(A 放到新桶头)→newTable: A → nulle = next(e 指向 B)next = e.next(这里出问题了!)注意:由于 Thread-B 已经修改了 B 的 next 指针,B.next 现在指向的是 A(而不是原来的 C)。
e.next = newTable[i](B 插到头部)→newTable: B → A → nulle = next(e 指向 A)next = e.next(A.next 指向谁?——是 B!)e.next = newTable[i](A 插到头部)→newTable: A → B此时链表变成了:
1 A → B → A → B → A → B → ... (环形!永远到不了 null)
三、成环之后会发生什么?
环形链表形成后,只要任何线程对这个桶执行
get()查询,就会沿着next指针一直走:
1 A → B → A → B → A → B → ... 永远走不到 null这就是死循环(Infinite Loop)。线程卡在遍历里出不来,CPU 自然就跑到 100% 了。
四、JDK 1.8 修复了吗?
部分修复,但没有完全解决线程安全问题。
JDK 1.7 JDK 1.8 插入方式 头插法 尾插法 扩容时链表顺序 反转 保持原顺序 并发扩容死循环 会发生 不会了 数据覆盖/丢失 会 仍然会 线程安全 不安全 依然不安全 JDK 1.8 改成尾插法后,链表顺序不会反转,所以不会形成环形链表,CPU 100% 的死循环问题消失了。
但是!两个线程同时
put同一个桶位时,后写的会覆盖先写的,导致数据丢失;size 计数也会不准。所以 HashMap 依然不是线程安全的。
五、正确做法
多线程环境下应该用:
ConcurrentHashMap—— 推荐,分段锁(JDK7)/ CAS + synchronized(JDK8),性能好Collections.synchronizedMap(new HashMap<>())—— 简单粗暴,全局锁,性能差Hashtable—— 遗留类,不推荐
一句话总结:JDK 1.7 的 HashMap 扩容用头插法反转链表,多线程并发时指针交错会形成环形链表,遍历时死循环导致 CPU 100%。JDK 1.8 改尾插法消除了死循环,但 HashMap 仍然线程不安全,并发场景请用
ConcurrentHashMap。