ConcurrentHashMap原理详解：从分段锁到CAS操作的优化之路

ConcurrentHashMap原理详解：从分段锁到CAS操作的优化之路

引用

CSDN

1.

https://m.blog.csdn.net/weixin_65696001/article/details/144209430

在多线程环境中，如何保证数据结构的线程安全同时保持高性能是一个重要的问题。ConcurrentHashMap作为Java中专门设计的线程安全哈希表，通过一系列优化技术如分段锁、CAS操作和锁分桶等，实现了高并发性能。本文将详细介绍ConcurrentHashMap的工作原理及其性能优化机制。

1. 分段锁机制 (Segment-based Locking)

在Java 7及之前版本中，ConcurrentHashMap使用了一种称为“分段锁”的机制来实现并发控制。具体来说：

• 分段：ConcurrentHashMap内部维护了一个由多个Segment组成的数组，每个Segment实际上是一个小型的ReentrantLock锁。默认情况下，ConcurrentHashMap会创建16个Segment。一旦初始化之后中间不可扩容
• 锁粒度：每个Segment负责保护一部分桶（bucket）意思是在每个segment中都可以挂一个HashEntry数组，数组里面可以存储具体的元素，HashEntry数组是可以扩容的。在HashEntry存储的数组中存储的元素，如果发生冲突，则可以挂单向链表。当一个线程对某个桶进行写操作时，只会锁定对应的Segment，而不会影响其他Segment。这样可以允许多个线程同时对不同的Segment进行写操作，从而提高了并发度。
• 读操作：读操作不需要加锁，因为ConcurrentHashMap使用了非阻塞算法（如CAS操作）来保证数据的一致性。即使在写操作发生时，读操作也可以继续进行，但可能会看到旧版本的数据（弱一致性）。

2. CAS操作与无锁编程

从Java 8开始，ConcurrentHashMap的内部实现进行了重大改进，去除了Segment，转而使用更细粒度的锁和CAS操作来提高性能。具体改进包括：

• 节点结构：ConcurrentHashMap使用了链表和红黑树来处理哈希冲突。每个桶可以是一个链表或红黑树，具体取决于该桶中的元素数量。当链表长度超过一定阈值（默认为8）时，链表会转换为红黑树，以提高查找效率。
• CAS操作：ConcurrentHashMap广泛使用了CAS操作来实现无锁编程。CAS是一种原子操作，可以在不使用锁的情况下更新共享变量。例如，在插入新节点时，ConcurrentHashMap会尝试使用CAS操作将新节点添加到链表的头部或尾部。如果CAS操作失败（即有其他线程同时修改了链表），则会重试或采取其他措施。
• 锁分桶：虽然Segment被移除，但ConcurrentHashMap仍然使用了锁分桶的思想。每个桶都有自己的锁，只有在必要时才会锁定整个链表或红黑树。这种细粒度的锁机制使得多个线程可以同时对不同的桶进行写操作，从而提高了并发性能。

3. 动态扩容

ConcurrentHashMap支持动态扩容，以确保在大量数据插入时仍能保持高效的性能。扩容机制的主要特点包括：

• 并行扩容：在扩容过程中，ConcurrentHashMap允许多个线程同时参与扩容操作。每个线程负责迁移一部分桶中的元素，从而加快了扩容的速度。
• 懒惰初始化：ConcurrentHashMap的底层数组是按需初始化的，即只有在实际插入元素时才会分配内存。这减少了不必要的内存占用。
• 渐进式迁移：在扩容过程中，ConcurrentHashMap采用了渐进式迁移策略。即在扩容的同时，仍然可以继续进行读写操作。迁移过程会在后台逐步完成，不会阻塞主线程。

4. 线程安全的操作

ConcurrentHashMap提供了一系列线程安全的操作，确保在多线程环境下能够正确地进行读写操作。以下是一些常见的线程安全方法：

• put(K key, V value)：插入键值对。如果键已经存在，则更新其对应的值。
• get(Object key)：根据键获取对应的值。读操作不需要加锁，因此具有较高的性能。
• putIfAbsent(K key, V value)：如果指定的键不存在，则插入键值对。这是一个原子操作，确保不会发生竞态条件。
• remove(Object key, Object value)：仅当当前映射到指定值时，才移除指定键的条目。这也是一个原子操作。
• replace(K key, V oldValue, V newValue)：仅当当前键映射到指定的旧值时，用新值替换之。这也是一个原子操作。
• computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)：如果指定的键没有关联的值，则尝试使用提供的映射函数计算其值，并将其放入此映射中。

5. 性能优化

ConcurrentHashMap在设计上做了许多性能优化，以确保在高并发环境下仍能保持高效的性能：

• 减少锁竞争：通过分段锁和锁分桶机制，ConcurrentHashMap将锁的粒度细化到了单个桶级别，从而减少了锁竞争的可能性。
• 非阻塞读操作：读操作不需要加锁，利用CAS操作和弱一致性模型，确保读操作的高性能。
• 渐进式扩容：扩容过程不会阻塞主线程，允许在扩容的同时继续进行读写操作，从而减少了扩容对性能的影响。
• 高效的哈希函数：ConcurrentHashMap使用了高效的哈希函数，减少了哈希冲突的概率，进一步提高了查找和插入的效率。