ConcurrentHashMap 是 Java 中一个用于并发操作的哈希表，它提供了一种高效的方式来处理多线程环境下的并发读写操作。其设计旨在提供 线程安全，同时避免传统 synchronized 锁机制的性能瓶颈。其内部实现基于 分段锁 和 CAS（Compare-And-Swap） 等技术，从而保证高并发情况下的线程安全和高效性能。

1. 分段锁（Segment Locking）

在早期的 ConcurrentHashMap 中（Java 7 及以前），其采用了 分段锁（Segment Locking）机制来提高并发性能。ConcurrentHashMap 会将整个哈希表分成若干个“段”（Segment），每个段内部拥有一个独立的锁。当多个线程访问不同的段时，它们可以并行工作，从而减少了锁的竞争，提高了并发性能。

分段锁的基本思想：

  • 将 ConcurrentHashMap 分成多个段（通常是 16 个段，每个段就是一个小的哈希表）。
  • 每个段有自己的锁，访问不同段的线程不会发生阻塞，因此提高了并发性能。
  • 如果多个线程访问同一个段，它们会互斥地访问该段，保证线程安全。

图示：

| Segment 0 | Segment 1 | Segment 2 | Segment 3 | ... | Segment n |(锁)        (锁)        (锁)        (锁)                (锁)

优点：

  • 可以提高并发性能，因为不同线程可以并发地操作不同的段。

缺点：

  • 在高并发的环境下，仍然可能会有某些段的锁竞争，影响性能。

分段锁的工作方式：

  1. 哈希表的键（key）根据哈希值（hash code）被映射到不同的段。
  2. 每个段独立管理一部分数据，并且每个段都使用自己的锁（ReentrantLock）。
  3. 当线程访问一个段时，它只需要锁定该段的锁，而不会影响其他段的访问。

2. Java 8 之后的改进：桶级锁（Bucket Locking）

从 Java 8 开始，ConcurrentHashMap 做了显著的改进，采用了 桶级锁（bucket-level locking）和 CAS 操作，放弃了分段锁的做法，改为直接使用 volatile 和 CAS 来保证并发性能。

Java 8 之后的设计改进：

  • 移除了分段锁：分段锁被移除，改为一个大的锁保护整个哈希表，使用更多的细粒度同步。
  • 桶级锁：每个桶（bucket）都可以通过 synchronized 或其他机制来独立加锁，减少冲突。
  • 使用 CAS 操作：通过 Compare-And-Swap 操作来保证更新操作的原子性，减少了使用锁的必要。
  • 使用 Node 链表和红黑树：哈希表中的桶不再是简单的链表，而是根据链表长度的不同，自动转换为红黑树（当链表长度超过阈值时），提高查找效率。

3. 结构和核心原理

3.1 数据结构

ConcurrentHashMap 内部数据结构主要由一个 数组（Segment[] 或 Node[]）组成，每个位置可以存放一个桶（bucket），每个桶是一个链表或红黑树。每个桶存储了一个或多个键值对。

  • 数组：数组是哈希表的基础存储结构，用来存储键值对的桶。
  • 桶：每个桶是一个链表或红黑树。链表在冲突不多时使用，而当冲突过多（即桶内元素较多）时，会自动转换为红黑树，提高查找效率。

3.2 锁机制

ConcurrentHashMap 使用了以下几种锁机制来保证线程安全：

  1. CAS（Compare-And-Swap）：对于一些操作（如 putIfAbsent），ConcurrentHashMap 使用了 CAS 操作来保证原子性。CAS 是一种无锁操作，通过比较内存中的值是否等于期望值，如果相等就替换成新值，从而避免了使用传统锁的性能问题。
  2. 分段锁/桶级锁：Java 8 后，ConcurrentHashMap 采用了桶级锁的方式，不再使用全局的锁，而是使用桶级别的同步来保证每个桶的线程安全。
  • 如果多个线程访问同一个桶（比如在链表或红黑树中查找元素），那么会对该桶加锁。
  • 对于不同的桶，ConcurrentHashMap 允许并发操作。
  1. 同步与 volatile 变量：通过 volatile 关键字保证可见性，volatile 关键字可以确保变量的值在多个线程之间正确同步，避免发生不可预测的行为。

3.3 Node 链表与红黑树

  • 链表：当每个桶中的元素比较少时，ConcurrentHashMap 使用链表存储。对于每个桶，哈希冲突的元素会组成一个链表，进行遍历。
  • 红黑树：当桶中的链表长度超过一定阈值（默认是 8），链表会转换成红黑树。红黑树的查找时间复杂度是 O(log n)，比链表的 O(n) 快。

3.4 哈希冲突的处理

ConcurrentHashMap 通过 链表 和 红黑树 处理哈希冲突：

  • 如果同一个桶内有多个元素发生哈希冲突，ConcurrentHashMap 会使用链表存储这些元素。
  • 当链表过长时，ConcurrentHashMap 会将其转化为红黑树，以提高查找效率。

3.5 扩容机制

  • 扩容条件：当 ConcurrentHashMap 中的元素数目超过了当前容量的 75% 时，会触发扩容操作。扩容时，哈希表的容量会翻倍，并且重新计算所有元素的哈希位置。
    这个过程是线程安全的，通过锁定整个 ConcurrentHashMap 来进行扩容，确保扩容时没有线程正在修改表。

4. 并发操作的优化

ConcurrentHashMap 通过以下几种方式优化并发操作：

  1. 多线程读写：在没有修改结构的情况下，多个线程可以并发地读取 ConcurrentHashMap 中的元素。
  2. 细粒度锁：通过将哈希表分成多个桶，减少了锁的竞争，提高了并发性。每个桶可以单独加锁，不会影响其他桶的操作。
  3. 原子操作：ConcurrentHashMap 提供了很多原子操作（如 putIfAbsent()、remove()、replace() 等），这些操作都能保证在多线程环境下的线程安全。

5. ConcurrentHashMap 的常见操作

  1. putIfAbsent(K key, V value)：
  • 如果 key 不存在，则将 key-value 插入 map 中。否则，不做任何操作。
  • 使用 CAS 操作保证原子性。
  1. computeIfAbsent(K key, Function<? super K, ? extends V> mappingFunction)：
  • 如果 key 不存在，则通过给定的 mappingFunction 计算 value 并插入。否则返回已有的 value。
  1. remove(Object key, Object value)：
  • 如果指定的 key 存在且其对应的 value 与提供的 value 匹配，则从 map 中移除该 key-value 对。
  1. replace(K key, V oldValue, V newValue)：
  • 如果 key 存在且对应的 value 是 oldValue，则替换成 newValue。

6. 总结

ConcurrentHashMap 的核心原理在于通过细粒度的锁（桶级锁或分段锁）和 CAS 操作来保证多线程环境下的线程安全，同时尽量减少锁的竞争，以提高性能。此外，它通过链表和红黑树的方式来处理哈希冲突，使用扩容机制来处理大量元素的情况。这些设计使得 ConcurrentHashMap 在高并发场景下表现出色，并且具备较高的性能。