Jie Cao 炼丹师

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
2
3
public V put(K key, V value) {
synchronized (mutex) {return m.put(key, 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)做两件事:

  1. 创建一个新的、两倍大的数组
  2. 把旧数组里的所有元素重新哈希(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 → null

Thread-B 先执行完扩容,把链表迁移到了自己的 newTable,变成:

1
Thread-B 的 newTable:  C → B → A → null   (头插法反转了顺序)

这时 Thread-B 把 table = newTable 赋值完成。

然后 Thread-A 恢复执行,它手里还拿着旧链表的引用 e = A,next = B。它继续从头插法迁移:

  1. newTable[i] = e(A 放到新桶头)→ newTable: A → null
  2. e = next(e 指向 B)
  3. next = e.next(这里出问题了!)

注意:由于 Thread-B 已经修改了 B 的 next 指针,B.next 现在指向的是 A(而不是原来的 C)。

  1. e.next = newTable[i](B 插到头部)→ newTable: B → A → null
  2. e = next(e 指向 A)
  3. next = e.next(A.next 指向谁?——是 B!)
  4. 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。

Powered by Hexo & Theme Keep
This site is deployed on