ConcurrentHashMap

字数: 0 字 时长: 0 分钟

1. ConcurrentHashMap 概述

ConcurrentHashMap 是 Java 中专门用于：

多线程并发环境

的线程安全 Map。

它解决的核心问题就是：

HashMap 在多线程环境下线程不安全，而 ConcurrentHashMap 可以在保证线程安全的同时，尽量提高并发性能。

简单理解：

HashMap
    ↓
性能高
    ↓
线程不安全


Hashtable
    ↓
线程安全
    ↓
大量方法直接 synchronized
    ↓
并发性能较差


ConcurrentHashMap
    ↓
线程安全
+
尽量减少锁竞争

基本使用：

Map<String, Integer> map =
        new ConcurrentHashMap<>();

map.put(
        "张无忌",
        20
);

map.put(
        "赵敏",
        18
);

System.out.println(
        map.get(
                "赵敏"
        )
);

2. 为什么需要 ConcurrentHashMap

前面在 HashMap 中已经提到：

HashMap
    ↓
线程不安全

多个线程同时进行：

put()

remove()

resize()

时，可能出现：

数据丢失

读取异常

内部结构被破坏

那最简单的思路是什么？

直接给整个 Map 加锁。

比如早期的：

Hashtable

它的很多方法直接使用：

synchronized

例如可以简单理解成：

public synchronized V put(
        K key,
        V value) {

    // ...
}

这种方式确实能够保证线程安全。

但问题也很明显：

线程 A 操作 Map
    ↓
锁住整个对象
    ↓
线程 B 等待
    ↓
线程 C 等待

即使多个线程操作的是：

不同的 Key

也可能互相阻塞。

ConcurrentHashMap 的目标就是：

保证线程安全，但尽可能不要让所有线程争抢同一把大锁。

3. JDK 7 和 JDK 8 的区别

ConcurrentHashMap 是一个非常典型的：

JDK 7

JDK 8

实现差异比较大的类。

3.1 JDK 7

JDK 7 中，ConcurrentHashMap 主要使用：

Segment

也就是：

分段锁

整体结构可以简单理解成：

ConcurrentHashMap

├── Segment 0
│   └── HashEntry[]
│
├── Segment 1
│   └── HashEntry[]
│
├── Segment 2
│   └── HashEntry[]
│
└── ...

不同 Segment：

拥有不同的锁

因此：

线程 A
    ↓
操作 Segment 1


线程 B
    ↓
操作 Segment 5

两者可以同时进行。

这就比：

Hashtable

锁整个 Map 的方式并发能力更强。

所以 JDK 7 的 ConcurrentHashMap 经常被总结成：

Segment
+
分段锁

3.2 JDK 8

到了 JDK 8，ConcurrentHashMap 取消了：

Segment

这一套主要结构。

改成：

Node 数组
+
链表
+
红黑树
+
CAS
+
synchronized

整体结构和 HashMap 越来越像：

ConcurrentHashMap

table
 ↓

Node[]
├── Node
├── Node → Node → Node
├── TreeBin
├── Node
└── ...

所以 JDK 8 以后可以简单记：

ConcurrentHashMap 不再通过 Segment 分段锁实现并发，而是通过 CAS + synchronized 对更细粒度的位置进行控制。

4. JDK 8 底层结构

核心数组：

transient volatile Node<K, V>[] table;

可以简单理解：

table
    ↓
Node[]
    ↓
一个个桶

每一个桶：

没有哈希冲突
    ↓
一个 Node


存在哈希冲突
    ↓
链表


链表达到条件
    ↓
红黑树

和 HashMap 比较类似：

HashMap
    ↓
数组 + 链表 + 红黑树


ConcurrentHashMap
    ↓
数组 + 链表 + 红黑树
    +
并发控制

Node 大致可以理解成：

static class Node<K, V>
        implements Map.Entry<K, V> {

    final int hash;

    final K key;

    volatile V val;

    volatile Node<K, V> next;
}

其中：

hash
    ↓
哈希值


key
    ↓
Key


val
    ↓
Value


next
    ↓
链表下一个节点

需要注意：

val

和：

next

使用：

volatile

保证线程之间的可见性。

5. put() 原理

ConcurrentHashMap 最重要的方法之一：

put()

最终会进入：

putVal()

整个流程可以先简单理解成：

put(key, value)
    ↓
计算 hash
    ↓
找到数组桶位置
    ↓
判断桶当前状态

然后根据情况分别处理。

5.1 Key 或 Value 为 null

ConcurrentHashMap 不允许：

null Key

null Value

所以：

map.put(
        null,
        "赵敏"
);

或者：

map.put(
        "赵敏",
        null
);

都会抛出：

NullPointerException

所以 put 一开始会进行检查：

if (
        key == null
                || value == null
) {

    throw new NullPointerException();
}

5.2 计算 hash

接下来计算 Key 的 hash。

整体思想和 HashMap 类似：

key.hashCode()
    ↓
扰动
    ↓
得到 hash

然后：

hash
    ↓
计算数组桶下标

5.3 table 还没有初始化

如果：

table == null

或者：

table.length == 0

说明数组还没有初始化。

此时会调用：

initTable()

完成数组初始化。

也就是说 ConcurrentHashMap 同样采用：

延迟初始化

的方式。

5.4 当前桶为空

假设计算得到：

index = 5

然后发现：

table[5] == null

也就是：

这个桶现在没人

这时候就没有必要加锁整个桶。

可以通过：

CAS

直接尝试把新节点放进去。

流程：

桶为空
    ↓
CAS
    ↓
尝试放入新节点

如果成功：

插入完成

如果失败：

说明其他线程抢先修改了
    ↓
重新尝试

这也是 ConcurrentHashMap 性能比较高的一个重要原因。

5.5 当前桶正在扩容

如果发现当前节点是：

ForwardingNode

说明：

ConcurrentHashMap 正在扩容

此时当前线程不会简单地一直等待。

它可能会：

帮助完成扩容

也就是：

多个线程
    ↓
一起迁移数据

这也是 JDK 8 ConcurrentHashMap 扩容设计中非常重要的一点。

5.6 当前桶已经有元素

如果桶中已经存在节点：

table[index] != null

说明发生了：

哈希冲突

这时候会锁住：

当前桶的头节点

而不是锁整个 ConcurrentHashMap。

可以简单理解：

synchronized (f) {

    // 操作当前桶
}

所以：

线程 A
    ↓
操作桶 3


线程 B
    ↓
操作桶 10

只要操作的是不同的桶：

互不影响

这就是所谓：

更细粒度的锁

5.7 链表插入

如果当前桶还是链表：

Node
 ↓
Node
 ↓
Node

就会遍历链表。

如果找到相同 Key：

更新 Value

如果没有：

添加新节点

整个过程：

找到桶
    ↓
synchronized 锁住当前桶
    ↓
遍历链表
    ↓
Key 相同
    ├── 是 → 更新 Value
    │
    └── 否 → 插入新节点

5.8 红黑树插入

如果当前桶已经树化：

TreeBin

那么就按照红黑树的方式：

查找

插入

更新

数据。

所以 JDK 8 ConcurrentHashMap 的整体结构同样可以理解为：

数组
+
链表
+
红黑树

6. CAS 是什么

ConcurrentHashMap 中会大量看到：

CAS

CAS：

Compare And Swap

也就是：

比较并交换

可以简单理解成：

我认为当前值还是 A
    ↓
如果真的还是 A
    ↓
修改成 B


如果已经不是 A
    ↓
说明被其他线程修改了
    ↓
本次操作失败

例如当前桶：

table[index] == null

线程 A 想插入：

Node A

线程 B 也想插入：

Node B

此时：

线程 A
    ↓
CAS 成功
    ↓
Node A 放入桶


线程 B
    ↓
CAS 发现桶已经不是 null
    ↓
失败
    ↓
重新处理

CAS 的好处就是：

某些简单操作
    ↓
不需要 synchronized

从而减少锁竞争。

7. get() 原理

ConcurrentHashMap 的：

get()

相比 put() 要简单很多。

基本流程：

Key
    ↓
计算 hash
    ↓
计算数组下标
    ↓
找到桶

如果桶中第一个节点就是目标：

直接返回 Value

如果不是：

继续查找链表 / 红黑树

整个过程：

get(key)
    ↓
计算 hash
    ↓
定位桶
    ↓
比较第一个节点
    ↓
继续查找
    ↓
返回 Value

7.1 为什么 get 不需要像 put 一样加锁

因为：

get()

主要是：

读取

而 ConcurrentHashMap 内部关键字段使用了：

volatile

例如：

volatile V val;

volatile Node<K, V> next;

从而保证线程间的可见性。

所以在大多数普通读取场景下：

get()
    ↓
不需要 synchronized

这也是 ConcurrentHashMap 读取效率很高的重要原因。

8. synchronized 锁的是什么

这里非常容易和 Hashtable 搞混。

Hashtable 可以简单理解成：

put()
    ↓
锁整个 Hashtable

而 JDK 8 ConcurrentHashMap：

put()
    ↓
桶为空
        ↓
        CAS

桶不为空
        ↓
        synchronized 当前桶

所以锁的粒度明显更小。

例如：

table

[0]
[1]
[2] → Node A
[3]
[4]
[5] → Node B
[6]

线程 A：

操作桶 2

线程 B：

操作桶 5

它们可以并发执行。

所以可以简单理解：

JDK 8 ConcurrentHashMap 使用 CAS 处理无冲突插入，发生冲突时再对当前桶进行 synchronized，而不是锁整个 Map。

9. 扩容机制

ConcurrentHashMap 底层仍然使用：

数组

所以随着元素不断增加：

数组空间不足
    ↓
需要扩容

扩容的核心思想和 HashMap 类似：

旧数组
    ↓
新数组
    ↓
容量扩大
    ↓
元素迁移

但 ConcurrentHashMap 最大的问题是：

扩容时可能还有其他线程正在 put、get。

所以它的扩容过程需要解决：

并发扩容

的问题。

9.1 ForwardingNode

在扩容过程中，会看到一种特殊节点：

ForwardingNode

它可以简单理解成：

当前桶的数据
    ↓
已经迁移 / 正在迁移

同时它还保存：

新数组的信息

当其他线程看到：

ForwardingNode

就知道：

这里正在扩容

于是可以：

继续去新数组查找

或者

帮助进行扩容

9.2 多线程协助扩容

HashMap 扩容通常可以理解成：

一个线程
    ↓
完成整个迁移

ConcurrentHashMap 为了提高效率，可以让：

多个线程

共同参与数组迁移。

简单理解：

旧 table

├── 一部分桶 → 线程 A 负责
├── 一部分桶 → 线程 B 负责
└── 一部分桶 → 线程 C 负责

多个线程一起把数据迁移到：

nextTable

最终：

nextTable
    ↓
成为新的 table

所以 ConcurrentHashMap 的扩容不是简单地：

锁整个 Map
    ↓
一个线程慢慢搬

而是支持：

并发迁移

10. 为什么不允许 null

HashMap 可以：

一个 null Key

多个 null Value

但是 ConcurrentHashMap：

Key 不能为 null

Value 不能为 null

一个重要原因是：

并发场景下会产生歧义

例如：

V value =
        map.get(
                "赵敏"
        );

如果返回：

null

到底代表：

这个 Key 不存在

还是：

这个 Key 存在
但是 Value 本身就是 null

？

在普通 HashMap 中，可以继续：

containsKey()

判断。

但在并发环境中：

get()
    ↓
containsKey()

两次操作之间可能已经被其他线程修改。

所以 ConcurrentHashMap 直接规定：

Key != null

Value != null

这样：

get(key) == null

就可以明确表示：

当前没有这个映射

11. ConcurrentHashMap 和 HashMap

简单对比：

特性	HashMap	ConcurrentHashMap
线程安全	否	是
null Key	允许一个	不允许
null Value	允许	不允许
底层结构	数组 + 链表 + 红黑树	数组 + 链表 + 红黑树
并发控制	无	CAS + synchronized
适用场景	单线程或外部保证线程安全	多线程共享 Map

核心区别：

HashMap
    ↓
没有并发控制


ConcurrentHashMap
    ↓
CAS
+
synchronized
+
volatile
+
并发扩容

12. ConcurrentHashMap 和 Hashtable

再来看：

ConcurrentHashMap

Hashtable

的区别。

Hashtable：

线程安全
    ↓
大量方法 synchronized
    ↓
锁粒度较大

ConcurrentHashMap：

线程安全
    ↓
CAS
+
桶级 synchronized
    ↓
锁粒度更细

简单理解：

Hashtable
    ↓
一把大锁


ConcurrentHashMap
    ↓
尽量只锁当前操作区域

所以在高并发场景下：

ConcurrentHashMap

通常具有更好的并发性能。

13. 小结

ConcurrentHashMap 是 Java 中非常重要的：

线程安全 Map

主要用于：

多线程共享 Map

JDK 7：

ConcurrentHashMap
    ↓
Segment
    ↓
分段锁

JDK 8 以后：

ConcurrentHashMap
    ↓
Node[]
    ↓
链表 / 红黑树
    ↓
CAS + synchronized

put()：

计算 hash
    ↓
找到桶
    ↓
桶为空
    ├── CAS 插入
    │
    └── 桶不为空
            ↓
       synchronized 当前桶
            ↓
       链表 / 红黑树处理

get()：

计算 hash
    ↓
定位桶
    ↓
查找 Node
    ↓
返回 Value

读取过程主要依靠：

volatile

保证可见性，通常不需要加锁。

扩容时：

旧数组
    ↓
nextTable
    ↓
ForwardingNode
    ↓
多个线程协助迁移

ConcurrentHashMap 不允许：

null Key

null Value

整个 ConcurrentHashMap 最核心的一句话可以记成：

JDK 8 以后，ConcurrentHashMap 通过 CAS + synchronized + volatile，在保证线程安全的同时，将锁粒度尽可能缩小，从而提高并发性能。