基于本文回答

播面

0
评论

ConcurrentHashMap实现原理

知识点图片

本文详解ConcurrentHashMap：JDK 1.7用分段锁提高并发，锁粒度为Segment；JDK 1.8则采用CAS+synchronized锁住哈希桶头节点，粒度更细，性能更优，并通过引入红黑树优化查询。

我们来深入浅出地讲解一下 ConcurrentHashMap 的工作原理。这部分内容通常会涉及其在 JDK 1.7 和 JDK 1.8+ 两个重要版本中的不同实现，因为 1.8 版本做出了革命性的改进。

核心思想：如何保证线程安全并提升性能？

在 ConcurrentHashMap 出现之前，我们通常使用 Hashtable 来实现线程安全的 Map。Hashtable 的做法非常简单粗暴：给所有公共方法（如 put, get, remove）都加上 synchronized 关键字。

  • 优点：简单，绝对线程安全。
  • 缺点：性能极差。synchronized 锁住了整个对象 (this)，意味着任何时候只有一个线程能访问这个 Map。如果一个线程在进行写操作（可能耗时较长），其他所有线程（即使是读操作）都必须等待。这被称为全局锁或表锁，锁的粒度太大了。

ConcurrentHashMap 的核心思想就是 “降低锁的粒度”，允许多个线程同时对 Map 的不同部分进行操作，从而大大提高并发性能。

JDK 1.7 的实现原理：分段锁 (Segment Locking)

在 JDK 1.7 版本中，ConcurrentHashMap 采用了一种叫做“分段锁”的巧妙设计。

1. 数据结构

它将整个哈希表在逻辑上分成了多个段 (Segment)。其内部结构如下：

  • 一个 ConcurrentHashMap 包含一个 Segment[] 数组。
  • 每个 Segment 都是一个独立的小型哈希表，它继承自 ReentrantLock，自带锁的功能。
  • 每个 Segment 内部包含一个 HashEntry[] 数组，HashEntry 存储了键值对，并通过链表解决哈希冲突。

可以把它想象成：一个 ConcurrentHashMap 里面有多个小 Hashtable。

2. 工作流程

  • 初始化：

    • 在创建 ConcurrentHashMap 时，可以指定一个 concurrencyLevel (并发级别，默认为 16)。
    • 程序会根据这个级别初始化相应数量的 Segment。每个 Segment 都是一个独立的锁。

  • put 操作：

    1. 定位 Segment：根据 key 的 hashCode() 计算出它应该属于哪个 Segment。
    2. 锁定 Segment：对该 Segment 加锁 (lock())。注意：此时只锁定了这一个 Segment，其他 Segment 不受影响，其他线程仍然可以访问它们。
    3. 执行 put：在当前 Segment 内部进行 put 操作，这与 HashMap 的过程类似（计算哈希值、找到 HashEntry 数组中的位置、处理哈希冲突等）。
    4. 释放锁：操作完成后，释放 Segment 的锁 (unlock())。

  • get 操作：

    • get 操作大部分情况下是无锁的，因此速度非常快。
    • 它利用了 volatile 关键字来保证内存可见性。Segment 内部的 HashEntry 数组和 HashEntry 的 value 字段都是用 volatile 修饰的。
    • 这确保了当一个线程修改了某个 value 后，其他线程能立刻看到这个更新，无需加锁。

  • size() 操作：

    • 这是一个比较复杂的操作。要计算全局大小，不能简单地把每个 Segment 的大小加起来，因为在相加的过程中，某个 Segment 的大小可能又变化了。
    • 它的策略是：先尝试不加锁，循环两次计算所有 Segment 的 modCount (修改次数) 之和。如果在两次计算期间，modCount 没变，说明没有发生修改，结果是准确的。
    • 如果 modCount 变了，说明有线程在修改，这时它会依次锁住所有的 Segment，然后计算总大小，最后释放所有锁。

3. 优缺点

  • 优点：通过分段锁，大大提高了并发度。理论上，最大并发度就是 Segment 的数量。
  • 缺点：
    • 分段锁的设计相对复杂，占用的内存也更多。
    • size() 操作的代价较大。
    • 并发级别在初始化后就固定了，无法动态调整。

JDK 1.8+ 的实现原理：CAS + synchronized

到了 JDK 1.8，ConcurrentHashMap 的实现被完全重写，放弃了 Segment 的设计，转而采用了一种更细粒度的锁机制。

1. 数据结构

JDK 1.8 的 ConcurrentHashMap 结构与 HashMap 在 1.8 中的实现非常相似：

  • Node[] 数组：一个 volatile 修饰的 Node 数组 (table)，作为哈希桶。
  • Node：存储键值对的基本单位。当哈希冲突发生时，Node 会形成一个链表。
  • TreeNode：当某个哈希桶中的链表长度超过一个阈值 (默认为 8)，并且数组总长度大于 64 时，链表会转化为红黑树，以提高查询效率。

2. 工作流程

它摒弃了分段锁，而是采用了 CAS (Compare-And-Swap) 和 synchronized 结合的方式来保证线程安全。锁的粒度被缩小到了哈希桶的头节点。

  • put 操作：

    1. 计算哈希值：根据 key 计算出在 Node[] 数组中的索引位置。
    2. 检查该位置是否为空：
      • 如果该位置为 null，说明没有哈希冲突。它会使用 CAS 操作尝试将新的 Node 放置到这个位置。
      • 如果 CAS 成功，说明插入完成。
      • 如果 CAS 失败，说明有其他线程抢先一步占用了这个位置，此时会进入下一步（自旋或锁）。
    3. 处理哈希冲突：
      • 如果该位置不为 null，说明发生了哈希冲突。
      • 此时，它会使用 synchronized 锁住该位置的头节点（链表或红黑树的第一个节点）。
      • 注意：锁住的只是这个桶的头节点，而不是整个 Map。其他线程仍然可以并发地访问其他桶。
      • 在 synchronized 代码块内部，遍历链表或红黑树，判断是更新已有 key 的值还是在末尾追加新节点。

  • get 操作：

    • 与 1.7 类似，get 操作也是无锁的。
    • Node 数组和 Node 的 val 及 next 字段都用 volatile 修饰，保证了多线程环境下的内存可见性。直接读取即可。

  • size() 操作：

    • 1.8 中对 size() 的计算也做了优化。它不再是实时精确的，而是“近似值”。
    • 它通过一个 baseCount 变量和一个 CounterCell[] 数组来协同计数。
    • 在没有并发竞争时，直接通过 CAS 更新 baseCount。
    • 当并发竞争激烈，CAS 更新 baseCount 失败时，线程会把计数分散到 CounterCell 数组的不同槽位上。
    • size() 方法最终返回的是 baseCount 和所有 CounterCell 中值的总和。这个值在没有并发修改时是精确的，但在高并发时是一个估算值。

3. 优缺点

  • 优点：
    • 锁的粒度更细，只锁住冲突的哈希桶头节点，而不是整个 Segment，并发性能更高。
    • 数据结构更简单，内存占用更少。
    • 引入红黑树，解决了哈希冲突严重时链表过长导致的性能下降问题。
  • 缺点：
    • 实现非常复杂，需要深入理解 volatile, CAS 和 synchronized 的底层原理。
    • size() 方法返回的是一个估算值，不保证绝对精确。

总结与对比：JDK 1.7 vs JDK 1.8

特性 JDK 1.7 (分段锁) JDK 1.8 (CAS + synchronized)
底层结构 Segment[] + HashEntry[] volatile Node[] + 链表/红黑树
锁机制 ReentrantLock 锁住整个 Segment synchronized 锁住桶的头节点 + CAS
锁粒度 Segment 级别（较粗） 哈希桶级别（更细）
get 操作 volatile 读取，无锁 volatile 读取，无锁
size() 计算 复杂，高并发时可能锁住所有Segment baseCount + CounterCell，高效，但为估算值
并发度 取决于 Segment 数量，固定 理论上是哈希桶的数量，动态
性能 良好 更优，尤其是在高并发场景

总而言之，ConcurrentHashMap 的演进过程，就是一部锁优化史：从 Hashtable 的全局锁，到 JDK 1.7 的分段锁，再到 JDK 1.8 的更细粒度的 CAS + 节点锁，其目标始终是尽可能地减少锁的范围，从而最大化并发性能。 在现代 Java 开发中，ConcurrentHashMap 是处理高并发键值存储场景的首选。

其中刚才提到的

检查该位置是否为空：

  • 如果该位置为 null，说明没有哈希冲突。它会使用 CAS 操作尝试将新的 Node 放置到这个位置。
  • 如果 CAS 成功，说明插入完成。
  • 如果 CAS 失败，说明有其他线程抢先一步占用了这个位置，此时会进入下一步（自旋或锁）。

这个过程是 ConcurrentHashMap 高性能的关键之一，因为它是一种乐观的、无锁的尝试。

一、 什么是 CAS (Compare-And-Swap)？

CAS，即“比较并交换”，是一个原子操作。它不是 Java 语言层面的东西，而是由 CPU 指令直接支持的。正因为是硬件级别的原子操作，所以它能保证在多线程环境下的正确性，而不需要操作系统的锁介入。

CAS 操作包含三个核心参数：

  1. V (Variable/Memory Location)：要被修改的内存地址中的值。
  2. E (Expected Value)：你期望这个内存地址中当前的值。
  3. N (New Value)：如果内存地址中的值确实和你期望的一样，那么就把它更新为这个新值。

操作逻辑可以描述为：
“我认为内存地址 V 的值应该是 E，如果是，那就把它更新成 N。如果不是（说明在我检查后、更新前，有别的线程修改了它），那就算了，什么也别做，并告诉我操作失败了。”

整个“比较”和“交换”的过程是一条 CPU 指令，是不可中断的。

二、 CAS 在 ConcurrentHashMap 初始化哈希桶时的应用

让我们把这个原理应用到 ConcurrentHashMap 的 put 场景中。

假设一个线程（我们称之为 线程 A）要执行 put("myKey", "myValue")。

  1. 计算位置：ConcurrentHashMap 计算出 "myKey" 应该放在内部 Node[] table 数组的索引 i 处。
  2. 读取并检查：线程 A 读取 table[i] 的值，发现它是 null。太好了！一个空位。
  3. 乐观尝试：线程 A 不会立即加锁。它乐观地认为，在它把新节点放进去之前，不会有其他线程来捣乱。于是，它准备执行一个 CAS 操作。

此时，CAS 的三个参数是：

  • V: table[i] 这个内存位置。
  • E: null (线程 A 期望这个位置现在仍然是 null)。
  • N: 一个新创建的 Node 对象，它包含了 "myKey" 和 "myValue"。

接下来，CPU 执行这个原子性的 CAS 指令。这里会出现两种结果：

场景 1：CAS 成功 (无竞争)

  • 过程：
    1. CPU 读取 table[i] 的当前值。
    2. 发现它的值确实是 null，与线程 A 的期望值 E (null) 相匹配。
    3. CPU 立刻将 table[i] 的值更新为 N (新的 Node 对象)。
    4. CAS 操作返回 true (成功)。
  • 结果：put 操作成功，并且全程没有使用任何锁。线程 A 可以直接返回。这是最高效的情况。

场景 2：CAS 失败 (发生竞争)

这是一个非常经典的并发场景，我们用两个线程来演示：

  1. 初始状态：table[i] 是 null。
  2. 线程 A 计算出索引 i，检查发现 table[i] 是 null。它准备执行 CAS(table[i], null, nodeA)。
  3. 发生线程切换！ 操作系统暂停了线程 A，开始执行 线程 B。
  4. 线程 B 也要 put 一个同样会落在索引 i 的键。它也检查到 table[i] 是 null，于是准备执行 CAS(table[i], null, nodeB)。
  5. 线程 B 执行 CAS：CPU 读取 table[i]，发现是 null，和线程 B 的期望值匹配。于是，CPU 将 table[i] 更新为 nodeB。线程 B 的 CAS 操作成功，它的 put 完成了。
  6. 再次线程切换！ 操作系统换回线程 A 执行。
  7. 线程 A 执行 CAS：轮到线程 A 执行它准备好的 CAS(table[i], null, nodeA) 了。
    • CPU 读取 table[i] 的当前值。但此时，table[i] 的值已经是 nodeB 了，不再是 null。
    • CPU 将这个实际值 (nodeB) 与线程 A 的期望值 E (null) 进行比较。
    • 比较失败！ (nodeB 不等于 null)。
    • 因此，CPU 不会执行交换操作。table[i] 的值仍然是 nodeB。
    • CAS 操作返回 false (失败)。
  • 结果：线程 A 的 CAS 尝试失败了。ConcurrentHashMap 的代码会捕捉到这个 false 返回值，并意识到：“我的乐观假设是错的，在我操作的期间，有别的线程已经占了这个位置。”

三、 CAS 失败后怎么办？

此时，线程 A 知道它不能再简单地尝试 CAS 了，因为 table[i] 已经不是 null 了。代码会进入一个自旋（Spin）循环，通常这个循环会做以下事情：

  1. 重新读取：重新读取 table[i] 的值，现在它得到的是 nodeB。
  2. 改变策略：线程 A 的任务目标从“在空位上放一个新节点”变成了“在一个已经存在的链表/红黑树上追加一个新节点”。
  3. 获取锁：要修改一个已经存在的链表，就必须防止其他线程也来修改。此时，ConcurrentHashMap 会退回到更传统的锁机制：使用 synchronized 关键字锁住 table[i] 的头节点（也就是 nodeB）。
  4. 执行操作：在获得锁之后，线程 A 安全地遍历 nodeB 开始的链表，并将自己的 nodeA 追加到链表的末尾。
  5. 释放锁。

总结

CAS 在这里的应用，体现了 ConcurrentHashMap 的一个核心设计哲学：乐观优先，失败后回退（Optimistic First, Fallback on Failure）。

  • 优势：在绝大多数没有并发冲突的情况下，put 操作通过一次无锁的 CAS 就能完成，速度极快，避免了线程挂起和恢复的开销。
  • 保障：在极少数发生并发冲突的情况下（CAS 失败），它能够检测到冲突，并安全地退回到使用 synchronized 锁这种更“悲观”但绝对安全的方式来完成操作。

这种设计使得 ConcurrentHashMap 在不同并发烈度下都能表现出色。

右滑查看面试常问