ConcurrentHashMap 整理

ConcurrentHash
并发集合
发布日期:   2025-02-28
更新日期:   2025-05-02
文章字数:   3.8k
阅读时长:   13 分
阅读次数:  

ConcurrentHashMap 提供了线程安全的映射操作，可以在多线程环境下被安全地访问和修改，内部使用 数组+链表+红黑树 结构来存储元素。适用于高并发，特别是高读少写的场景。

JDK 8 之前数据结构（数组+链表）

  • 内部结构分为多个 Segment（分段）。每个 Segment 是一个静态内部类，继承了 ReentrantLock，因此 Segment 就是可重入锁。
  • 每个 Segment 包含多个 HashEntry，每个 HashEntry 是一个链表节点，包含键值对和指向下一个节点的引用。

并发操作机制

  • 并发读取：允许多个线程同时读取不同的 Segment 的数据，因为读取操作不需要锁定整个 Segment。
  • 并发写入：写入操作（如 put 和 remove）会在对应的 Segment 上加锁。这意味着不同 Segment 的写入操作可以同时进行，而相同 Segment 的写入操作则需要等待锁。

示例场景

假设有 ConcurrentHashMap 内部有四个Segment，线程A和线程B分别向不同的键写入值，他们通过哈希算法定位到不同的Segment。因此，线程A和B可以同时进行操作，不会互相堵塞，从而实现高效的并发。

那假如说线程A和B通过哈希算法定位到同一个Segment呢？

当多个线程定位到同一个 Segment 时，它们必须获得该 Segment 的锁才能进行任何操作。这意味着在任何时候，每个Segment只允许一个线程进行操作。

扩容机制

触发扩容

  • 当任何一个 Segment 的填充度达到阈值时（基于负载因子和 Segment 的容量），就会触发该 Segment 的扩容。
  • 扩容是针对于单个 Segment 的，而不是整个 ConcurrentHashMap。
  • 如果一个线程在进行插入操作时触发了扩容，该线程会锁定对应的 Segment 并开始扩容过程，其他试图访问同一个 Segment 的线程将会被堵塞（其他的Segment不会受影响），直到扩容完成。

扩容过程

当某个 Segment 的填充度达到设定阈值时，该 Segment 将独立触发扩容，这个过程包括：

  1. 创建一个新的哈系统数组，大小通常是原数组的两倍。
  2. 重新计算旧数据的哈希值并将数据迁移到新数组。
  3. 迁移完成后，将旧 Segment 的引用更新为新 Segment。

利弊点：

  • 这种扩容机制减少了整个 ConcurrentHashMap 范围内的锁竞争，因为只有被扩容的 Segment 会被锁定，扩容和数据迁移通常由触发扩容的单个线程完成的。
  • 然而会存在局限性，在单个 Segment 达到较大时，扩容过程仍可能达到性能瓶颈，因为其他线程需要等待扩容线程完成操作。

小结

  1. 提高数据访问效率
    • 在不同线程访问不同 Segment 的场景中，由于锁是分段的，线程间几乎不会相互堵塞，这大大提高了数据访问的效率。
  2. 减少锁的范围
    • 锁分段技术通过仅锁定部分数据结构，来减少锁的范围，这意味着更少的线程会因为等待锁被堵塞。
  3. 降低锁竞争
    • 锁分段机制有效降低了竞争，特别是有大量读操作和一定量写操作的情况下。

JDK 8及以后

ConcurrentHashMap 的进化

在JDK8及之后的版本中，ConcurrentHashMap的内部结构和锁机制有了重大改进，主要是引入了红黑树 来优化长链表带来的性能问题，并且取消了 Segment 的使用，改为直接对节点进行分散加锁。

数据结构

  • Node数组：使用统一的 Node 数组替代了旧版本的多个 Segment。每个 Node 包含了一个 key, value 及指向下一个 Node 的引用。
  • 链表和红黑树：当链表长度超过设定阈值时（默认为8），自动转化为红黑树，提升查找效率。

底线实现

  • CAS操作：用于无锁的读取和高效的更新，实现原子性操作。
  • Synchronized 同步块：控制复杂的写操作，如转换链表为红黑树。

特性和并发控制

  • 并发读取：无锁操作允许多线程可以同时进行读取操作，读取操作是完全无锁的。
  • 并发写入：写入操作使用了 CAS 操作和 synchronized 块。CAS 用于简单的更新，而 synchronized 块用于删除或（链表转红黑树）操作。

示例场景

假设有两个线程：线程A和线程B，两个线程分别向ConcurrentHashMap中添加值：

  • 两个键经过哈希运算之后，分别发生在不同的key中，那么更新操作主要依赖于CAS操作来安全地完成更新，而不需要锁定这个段。
  • 如果两个键恰好映射到同一个桶，且其中一个操作需要更复杂的同步（如转换链表为红黑树或删除操作），则会使用synchronized来锁定这个特定的桶或节点，另外一个线程需要被堵塞。

这种新的机制减少了锁的使用，提高了读取效率和写操作的并发控制能力。允许更多线程无锁地读取数据，同时仍然保持一定程度的写入性能。

扩容

触发条件

  • 扩容通常在两种情况下被触发：当桶的数量不足以容纳当前元素时，或者单个链表的长度过长，影响了查询效率。

扩容过程

  1. 新建数组：
    • 当扩容开始时，创建一个新的节点数组，其容量是原数组的两倍。
  2. 数据迁移：
    • ConcurrentHashMap 会将旧数组中的每个桶（bucket）中的节点迁移到新数组中。整个过程是并发进行的，多个线程可以同时参与到不同桶的迁移过程中。
  3. 重哈希：
    • 每个节点在迁移时需要重新计算其在新数组中的位置。这是因为数组大小改变后，原哈希值映射到新数组的位置也可能发生变化。
  4. 转移节点：
    • 对于链表中的每个节点，根据其哈希值确定它在新数组中的位置，并将其移动到新位置。如果原链表已经转换为红黑树，那么红黑树也会重新组织并迁移到新数组中。

并发控制：

在扩容过程中，ConcurrentHashMap 使用了精细的并发控制机制来确保数据一致性和线程安全。它允许多个线程同时参与扩容过程，每个线程可以处理一部分数据的迁移，从而加快整体扩容过程。

锁定特定桶（bucket）

  1. 粒度更细的锁：锁的粒度更细。它不再锁定整个Segment，而是锁定特定的桶。
  2. 使用synchronized关键字：Synchronized关键字来锁定特定的桶。当一个线程想要访问或修改一个桶时，它必须首先获取该桶的锁。
  3. 每个桶作为独立的锁：每个桶都作为一个独立的锁，可以被单独锁定或解锁。这减少了线程的竞争，因为不同的线程可以锁定不同的桶。

工作流程

  1. **计算桶的索引：**当一个线程想要添加、删除或访问一个元素时，它首先会计算元素的hash值。
  2. 获取桶的锁：线程在操作桶之前必须首先获取该桶的锁。如果锁不可用（已经被其他线程持有），线程将被堵塞，直到锁变为可用。
  3. 操作桶：一旦线程获取了桶的锁，它就可以安全地修改该桶。
  4. 释放锁：操作完成后，线程必须释放桶的锁，以便其他线程可以锁定该桶。

通过这种方式，Java 8的ConcurrentHashMap允许多个线程同时访问和修改不同的桶，从而实现了更高的并发性和性能。同时，通过锁定特定的桶，它确保了线程安全性，防止了多个线程同时修改同一个桶的情况。

CAS和Synchronized在ConcurrentHashMap中的应用

CAS

CAS 操作是一种无锁的同步机制。它包括三个操作数：内存位置（要操作的数据）、预期原值和新值。CAS首先检查内存位置的当前值是否与预期原值相同，如果相同，就将此位置更新为新值。整个过程是原子的。

  1. 用于插入操作：
    • 当插入一个新的键值对时，ConcurrentHashMap 使用CAS操作来确保线程安全。
    • 它首先计算键的哈希值，然后使用这个哈希值来找到对应的桶。
    • 使用CAS操作来插入新的节点到桶中，如果CAS操作失败（说明有其他线程已经修改了这个桶），它会重试操作，直到成功。
  2. 用于删除操作：
    • 当删除一个键值对时，ConcurrentHashMap 同样使用CAS操作。
    • 它找到要删除的节点，然后使用CAS操作来安全地从桶中删除节点。
  3. 用于扩容：
    • 当ConcurrentHashMap的大小超过一定的阈值，它会进行扩容。
    • 扩容操作也使用CAS来确保只有一个线程可以扩容数组，并且在扩容过程中，其他线程还可以继续安全地访问和修改 ConcurrentHashMap。

Synchronized

  1. 复杂结构的修改：
    • 当链表长度超过阈值，将链表转换为红黑树时，需要锁定整个链表。这种转换是复杂的结构修改，涉及多个节点，因此使用 synchronized 来确保在修改期间，没有其他线程可以修改这些节点。
  2. 删除操作：
    • 在删除过程中，synchronized 被用来锁定特定节点或整个桶，保证操作的原子性和一致性。

为什么使用CAS

  1. 无锁优势：
    • CAS 提供了一种无锁的同步方式。相比传统的锁机制，CAS在多线程环境下可以减少堵塞和上下文切换的开销，减少线程之间的竞争，提高系统整体性能。
  2. 原子性：
    • CAS 保证了原子性，无需使用复杂的锁定机制。
  3. 避免死锁：
    • CAS 可以避免死锁的发生，因为不会像传统锁那样持有资源。

替代方案的局限性

  • 悲观锁：使用传统的悲观锁（synchronized 或 ReentrantLock）可能会导致在高并发环境下性能下降。
  • 自旋锁：自旋锁可以作为一种替代方案，但它在等待锁释放时会占用处理器时间，这在长时间等待的情况下可能不高效。

Java 8 ConcurrentHashMap 引入了什么新的技术？

  1. 统一的 Node 数组：
    • 使用单个统一的 Node 数组替代了分段的 Segment 数组。每个 Node 包含了一个键值对。
  2. CAS 操作：
    • CAS用于在无锁的情况下实现安全的更新。在更新节点时不需要锁定整个结构。
  3. synchronized 同步块：
    • 对于需要同步的操作（如节点的删除或整个桶的更新），使用了内部的 synchronized 同步块来控制。
  4. 引入链表和红黑树：
    • 在链表长度超过一定阈值时，链表转换为红黑树，这提高了查找效率。

为什么要移除掉JDK7中的分段锁Segment？

  1. 提高并发性和性能：
    • 分段锁虽然允许多个线程同时访问不同的Segment，但如果多个线程修改同一个Segment，它们仍然会堵塞。堵塞意味着线程会被挂起，操作系统需要进行上下文切换，阻塞和上下文切换可能导致 CPU 资源的不充分利用，因为等待锁的线程不能执行任何操作。
    • 在 Java 8中，通过锁定特定的桶而不是整个Segment，引入CAS和 Synchronized 减少锁的竞争，可以进一步提高并发读。CAS 自旋是在用户态完成的，不涉及操作系统层面的线程挂起或上下文切换。
  2. 减少内存开销：
    • 每个Segment对象都是一个额外的内存开销，不需要再为每个 Segment 维护独立的哈希表和锁结构，降低了内存占用。
  3. 优化扩容过程：
    • 新的扩容机制允许多个线程协作进行，减少了扩容期间的堵塞和性能损失。

ConcurrentHashMap 一定是线程安全的吗？

高并发场景下，当涉及到符合操作的情况下，ConcurrentHashMap 还是会出现数据不一致的情况。

ConcurrentHashMap 本身确保了单个操作，如get、put、remove 等的线程安全性，这意味着每个这样的操作都是原子的。然而，当这些操作组合在一起形成复合逻辑时，例如：

  1. 检查后执行（Check-then-act）：如先通过

    get

    检查键是否存在，然后根据检查结果决定是否执行

    put

    。在多线程环境中，即使这两个操作各是安全的，组合在一起就可能不再是线程安全的。

    • 问题示例：如果两个线程同时发现某个键不存在，它们可能各自创建一个新的值，并尝试将其插入到ConcurrentHashMap 中。这可能会导致后一个线程的操作覆盖前一个线程的操作。

避免措施

  1. 使用原子操作：ConcurrentHashMap 提供了一些复合操作，如putIfAbsent、compute 、computeIfAbsent 和computeIfPresent ，这些方法可以安全地执行复合逻辑，确保整个过程的原子性。

computeIfAbsent

  • 这个方法用于在键不存在时计算其值，并将其添加到 HashMap 中。
  • 方法签名：computeIfAbsent(K key, Function mappingFunction)
  • 工作原理：如果给定的键在 HashMap 中不存在或其值为 null，computeIfAbsent 会使用提供的映射函数计算其值，并将键值对添加到 HashMap 中。如果键已经存在，则不执行任何操作。
  • 应用场景：常用于缓存实现，或者你希望键不存在时自动计算并存储值时。
Map map = new HashMap<>();
map.put("apple", 3);

// 使用 computeIfAbsent 更新不存在的键 "banana" 的值
map.computeIfAbsent("banana", k -> 6);
System.out.println(map); // 输出: {apple=3, banana=6}

// 使用 computeIfAbsent 尝试更新存在的键 "apple" 的值
map.computeIfAbsent("apple", k -> 10);
System.out.println(map); // 输出: {apple=3, banana=6}，"apple" 的值没有改变

computeIfPresent

  • 这个方法用于在键存在且值非null时，重新计算并更新其值。
  • 方法签名：computeIfPresent(K key, BiFunction remappingFunction)
  • 工作原理：如果给定的键在 HashMap 中存在且其值非 null，computeIfPresent 会使用提供的重新映射函数根据旧值计算新值，并替换旧值。如果计算出的新值为 null，则删除该建。
  • 应用场景：常用于需要基于旧值更新键值对的场合。
Map map = new HashMap<>();
map.put("apple", 3);

// 使用 computeIfPresent 更新存在的键 "apple" 的值
map.computeIfPresent("apple", (k, v) -> v + 2);
System.out.println(map); // 输出: {apple=5}

// 使用 computeIfPresent 尝试更新不存在的键 "banana" 的值
map.computeIfPresent("banana", (k, v) -> v + 2);
System.out.println(map); // 输出: {apple=5}，没有 "banana" 键
ConcurrentHash
  目录