Java中的ConcurrentHashMap实现原理
字数 2591 2025-11-02 19:16:42

Java中的ConcurrentHashMap实现原理

描述
ConcurrentHashMap是Java集合框架中一个支持高并发访问的线程安全HashMap实现。与Hashtable和Collections.synchronizedMap()这种对整个集合进行同步的“粗粒度”锁机制不同，ConcurrentHashMap通过更精细的锁策略（在JDK 1.7及之前是分段锁，在JDK 1.8及之后是CAS+synchronized）来实现更高的并发性能，是面试中高频且深入的知识点。

知识讲解

第一部分：演进背景与核心目标

  1. 为什么需要ConcurrentHashMap？

    • 问题1：HashMap非线程安全。 在多线程环境下，多个线程同时对HashMap进行put操作可能导致内部链表形成环，引发CPU占用100%的死循环问题，或者导致数据覆盖丢失。
    • 问题2：Hashtable效率低下。 Hashtable是线程安全的，但它使用synchronized关键字修饰所有方法，相当于对整个数组对象加锁。同一时间只有一个线程能进行操作，虽然安全但并发性能极差。

  2. 核心目标： 在保证线程安全的前提下，实现高吞吐量的并发访问。关键在于将锁的“粒度”变细，让多个线程在访问不同数据时不会相互阻塞。

第二部分：JDK 1.7的实现（分段锁机制）

JDK 1.7的ConcurrentHashMap使用了一个称为“分段锁”（Segment Locking）的设计。

  1. 数据结构：Segment + HashEntry

    • ConcurrentHashMap内部由一个Segment数组组成。你可以把每个Segment想象成一个小型的Hashtable。
    • 每个Segment内部又由一个HashEntry数组组成，这才是真正存储键值对的地方。每个HashEntry是一个链表的节点。

  2. “分段”思想：

    • 整个Map被分成了很多段（默认为16段）。当需要put一个元素时，首先根据key的哈希值计算出它应该属于哪一个Segment。
    • 然后，只对这个特定的Segment进行加锁操作。其他线程可以同时访问其他未被锁住的Segment。
    • 比喻： 这就像一个大型图书馆有16个阅览室（Segment），每个阅览室有自己的门锁。一个读者（线程）要进入A阅览室看书（修改数据），只需要锁上A阅览室的门，其他读者仍然可以同时进入B、C、D等阅览室。这比锁上整个图书馆大门（Hashtable的方式）效率高得多。

  3. 操作步骤（以put为例）：

    • 步骤1：定位Segment。 对key的hashCode进行再散列，用高位哈希值确定元素属于哪个Segment。
    • 步骤2：Segment加锁。 获取这个Segment对象对应的锁（ReentrantLock）。如果获取失败，线程会进入等待队列。
    • 步骤3：定位HashEntry。 在已锁住的Segment内部，再次对key的hashCode进行散列，确定它在HashEntry数组中的位置（即哪个桶）。
    • 步骤4：操作链表。 在找到的桶的链表上进行插入、更新或遍历操作。
    • 步骤5：释放锁。 操作完成后，释放Segment锁。

第三部分：JDK 1.8及之后的实现（CAS + synchronized）

JDK 1.8对ConcurrentHashMap进行了重大重构，放弃了分段锁，采用了更优化的技术。

  1. 数据结构简化：Node数组

    • 结构变得和HashMap 1.8类似，直接是一个Node数组（代替了HashEntry）。Node可以形成链表或红黑树（当链表长度超过阈值时）。

  2. 新核心机制：CAS + synchronized

    • CAS（Compare-And-Swap）： 一种乐观锁，是无锁操作。它包含三个操作数：内存位置（V）、预期原值（A）和新值（B）。如果V的值等于A，则将V的值更新为B，否则什么都不做。整个操作是原子的。在ConcurrentHashMap中，初始化数组、向空桶插入节点等操作都使用CAS，避免了直接加锁，效率极高。
    • synchronized： 用于锁定链表的头节点（或树的根节点）。注意，锁的粒度从JDK 1.7的一个Segment（包含多个桶）细化到了一个桶。

  3. 操作步骤详解（以put为例）：

    • 步骤1：计算哈希。 计算key的哈希值。这个哈希值经过特殊处理，保证是正数。
    • 步骤2：判断表是否为空。 如果Node数组尚未初始化，则首先初始化数组（通过CAS操作保证只有一个线程能初始化成功）。
    • 步骤3：定位桶并判断是否为空。 根据哈希值定位到数组的某个下标位置（桶）。如果这个桶是空的（null），则使用CAS操作尝试将新节点放入此桶。
      • 成功： put操作即将结束，非常高效。
      • 失败： 说明有其他线程抢先在这个位置插入了节点，当前线程的CAS操作失败。则进入下一步。
    • 步骤4：桶不为空时的处理。 如果桶不为空，或者步骤3的CAS失败了，则使用synchronized关键字锁住这个桶的头节点。
      • 在锁住的情况下，检查当前是链表还是红黑树。
      • 如果是链表： 遍历链表，更新已有节点或插入新节点到链表尾部。
      • 如果是红黑树： 按照红黑树的方式插入节点。
    • 步骤5：判断是否需要转树。 插入链表后，如果链表长度达到阈值（默认为8），并且数组总长度达到最小树化容量（64），则将该链表转换为红黑树，以提高查询效率。
    • 步骤6：统计大小。 使用一个名为baseCount的变量和CounterCell数组来辅助计数（一种分片计数的思想），避免更新size时成为性能瓶颈。

总结对比

  • JDK 1.7： 分段锁技术。锁粒度是“段”，包含多个桶。写操作需要获取段锁。
  • JDK 1.8+： CAS + synchronized。锁粒度是“单个桶”。只有在发生哈希冲突（桶非空）时才使用synchronized锁住头节点，而无冲突时（桶为空）使用高效的CAS，大大提升了并发性能。同时引入了红黑树来解决哈希冲突严重时链表过长导致的查询效率下降问题。

通过这种循序渐进的演进，ConcurrentHashMap在保证线程安全的同时，实现了近乎极致的并发性能，成为高并发场景下最常用的Map实现。

Java中的ConcurrentHashMap实现原理 描述 ConcurrentHashMap是Java集合框架中一个支持高并发访问的线程安全HashMap实现。与Hashtable和Collections.synchronizedMap()这种对整个集合进行同步的“粗粒度”锁机制不同，ConcurrentHashMap通过更精细的锁策略（在JDK 1.7及之前是分段锁，在JDK 1.8及之后是CAS+synchronized）来实现更高的并发性能，是面试中高频且深入的知识点。 知识讲解 第一部分：演进背景与核心目标 为什么需要ConcurrentHashMap？ 问题1：HashMap非线程安全。 在多线程环境下，多个线程同时对HashMap进行put操作可能导致内部链表形成环，引发CPU占用100%的死循环问题，或者导致数据覆盖丢失。 问题2：Hashtable效率低下。 Hashtable是线程安全的，但它使用 synchronized 关键字修饰所有方法，相当于对整个数组对象加锁。同一时间只有一个线程能进行操作，虽然安全但并发性能极差。 核心目标： 在保证线程安全的前提下，实现高吞吐量的并发访问。关键在于将锁的“粒度”变细，让多个线程在访问不同数据时不会相互阻塞。 第二部分：JDK 1.7的实现（分段锁机制） JDK 1.7的ConcurrentHashMap使用了一个称为“分段锁”（Segment Locking）的设计。 数据结构：Segment + HashEntry ConcurrentHashMap内部由一个 Segment 数组组成。你可以把每个Segment想象成一个小型的Hashtable。 每个Segment内部又由一个 HashEntry 数组组成，这才是真正存储键值对的地方。每个HashEntry是一个链表的节点。 “分段”思想： 整个Map被分成了很多段（默认为16段）。当需要put一个元素时，首先根据key的哈希值计算出它应该属于哪一个Segment。 然后，只对这个特定的Segment进行加锁操作。其他线程可以同时访问其他未被锁住的Segment。 比喻： 这就像一个大型图书馆有16个阅览室（Segment），每个阅览室有自己的门锁。一个读者（线程）要进入A阅览室看书（修改数据），只需要锁上A阅览室的门，其他读者仍然可以同时进入B、C、D等阅览室。这比锁上整个图书馆大门（Hashtable的方式）效率高得多。 操作步骤（以put为例）： 步骤1：定位Segment。 对key的hashCode进行再散列，用高位哈希值确定元素属于哪个Segment。 步骤2：Segment加锁。 获取这个Segment对象对应的锁（ReentrantLock）。如果获取失败，线程会进入等待队列。 步骤3：定位HashEntry。 在已锁住的Segment内部，再次对key的hashCode进行散列，确定它在HashEntry数组中的位置（即哪个桶）。 步骤4：操作链表。 在找到的桶的链表上进行插入、更新或遍历操作。 步骤5：释放锁。 操作完成后，释放Segment锁。 第三部分：JDK 1.8及之后的实现（CAS + synchronized） JDK 1.8对ConcurrentHashMap进行了重大重构，放弃了分段锁，采用了更优化的技术。 数据结构简化：Node数组 结构变得和HashMap 1.8类似，直接是一个 Node 数组（代替了HashEntry）。Node可以形成链表或红黑树（当链表长度超过阈值时）。 新核心机制：CAS + synchronized CAS（Compare-And-Swap）： 一种乐观锁，是无锁操作。它包含三个操作数：内存位置（V）、预期原值（A）和新值（B）。如果V的值等于A，则将V的值更新为B，否则什么都不做。整个操作是原子的。在ConcurrentHashMap中，初始化数组、向空桶插入节点等操作都使用CAS，避免了直接加锁，效率极高。 synchronized： 用于锁定链表的头节点（或树的根节点）。注意，锁的粒度从JDK 1.7的一个Segment（包含多个桶）细化到了 一个桶 。 操作步骤详解（以put为例）： 步骤1：计算哈希。 计算key的哈希值。这个哈希值经过特殊处理，保证是正数。 步骤2：判断表是否为空。 如果Node数组尚未初始化，则首先初始化数组（通过CAS操作保证只有一个线程能初始化成功）。 步骤3：定位桶并判断是否为空。 根据哈希值定位到数组的某个下标位置（桶）。如果这个桶是空的（ null ），则使用CAS操作尝试将新节点放入此桶。 成功： put操作即将结束，非常高效。 失败： 说明有其他线程抢先在这个位置插入了节点，当前线程的CAS操作失败。则进入下一步。 步骤4：桶不为空时的处理。 如果桶不为空，或者步骤3的CAS失败了，则使用 synchronized 关键字锁住这个桶的头节点。 在锁住的情况下，检查当前是链表还是红黑树。 如果是链表： 遍历链表，更新已有节点或插入新节点到链表尾部。 如果是红黑树： 按照红黑树的方式插入节点。 步骤5：判断是否需要转树。 插入链表后，如果链表长度达到阈值（默认为8），并且数组总长度达到最小树化容量（64），则将该链表转换为红黑树，以提高查询效率。 步骤6：统计大小。 使用一个名为 baseCount 的变量和 CounterCell 数组来辅助计数（一种分片计数的思想），避免更新size时成为性能瓶颈。 总结对比 JDK 1.7： 分段锁技术。锁粒度是“段”，包含多个桶。写操作需要获取段锁。 JDK 1.8+： CAS + synchronized 。锁粒度是“单个桶”。只有在发生哈希冲突（桶非空）时才使用synchronized锁住头节点，而无冲突时（桶为空）使用高效的CAS，大大提升了并发性能。同时引入了红黑树来解决哈希冲突严重时链表过长导致的查询效率下降问题。 通过这种循序渐进的演进，ConcurrentHashMap在保证线程安全的同时，实现了近乎极致的并发性能，成为高并发场景下最常用的Map实现。