请描述ConcurrentHashMap的内部数据结构。

参考回答

ConcurrentHashMap 是 Java 中线程安全的高性能 Map 实现，它的内部数据结构和设计目标是为了在多线程环境下高效地实现数据存储和访问。

在 JDK 1.8 及之后，ConcurrentHashMap 的内部数据结构主要包括以下几个部分：

1. 基于数组和链表/红黑树的分段存储机制：
   数据存储在一个 Node<K,V>[] 数组中，每个数组槽位（bucket）使用链表或红黑树存储发生哈希冲突的元素。
2. 分段锁的优化机制：
   通过 CAS（Compare-And-Swap）和 synchronized 锁局部区域，降低线程之间的竞争，允许多线程并发操作。
3. 红黑树优化：
   当哈希冲突导致链表长度超过阈值（默认为 8）时，链表会转换为红黑树，提高查询性能。
4. 扩容机制：
   扩容时，通过分布式迁移机制，减少对整个表的锁定，提高扩容效率。

详细讲解

1. 数据结构核心部分

1.1 Node<K,V>

ConcurrentHashMap 的每个键值对存储在 Node<K,V> 对象中。Node 是一个简单的链表节点，结构如下：

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;      // 键的哈希值
    final K key;         // 键
    volatile V value;    // 值
    volatile Node<K,V> next; // 链表的下一个节点
}

• hash：存储键的哈希值，用于快速查找位置。
• key：存储键。
• value：存储值。
• next：指向链表的下一个节点（用于解决哈希冲突）。

1.2 数组 Node<K,V>[] table

整个 ConcurrentHashMap 使用一个 Node<K,V>[] 数组作为哈希表的底层数据结构。

• 每个数组槽位（bucket）存储一个链表或红黑树的头节点。
• 哈希值通过 hash & (n-1) 定位到数组的某个索引。

例如，table[5] 是数组的第 5 个槽位，可能存储一个链表或红黑树的头节点。

1.3 红黑树节点 TreeNode<K,V>

当链表长度超过阈值（TREEIFY_THRESHOLD = 8）时，链表会转化为红黑树，TreeNode 替代了普通的 Node 节点：

static final class TreeNode<K,V> extends Node<K,V> {
    TreeNode<K,V> parent;  // 父节点
    TreeNode<K,V> left;    // 左子节点
    TreeNode<K,V> right;   // 右子节点
    boolean red;           // 是否为红节点
}

红黑树的引入可以将查询性能从 O(n) 降低到 O(log n)，在高哈希冲突的场景下性能提升显著。

2. 线程安全实现

2.1 CAS 操作

• ConcurrentHashMap 使用 CAS（Compare-And-Swap）操作来保证多线程环境下的高效写操作。
• 例如，插入元素时，ConcurrentHashMap 使用 Unsafe 类中的 compareAndSet 方法尝试无锁更新。

if (U.compareAndSwapObject(tab, i, null, new Node<K,V>(hash, key, value, null))) {
    // 插入成功，无需锁
}

2.2 分段锁

• 在 ConcurrentHashMap 中，某些操作（如链表插入、扩容）需要使用锁机制，但仅锁定当前数组槽位的链表或红黑树，不会影响整个哈希表。
• 使用了 synchronized 关键字，但锁的范围被限制在局部（例如一个链表或树），从而减少锁竞争。

2.3 读写分离

• ConcurrentHashMap 中的读操作通常是无锁的，例如 get() 方法，依赖 volatile 关键字保证数据的可见性。
• 写操作（如 put() 和 remove()）则结合 CAS 和局部锁实现线程安全。

3. 扩容机制

当 ConcurrentHashMap 中元素数量超过扩容阈值（size >= capacity * loadFactor）时，会触发扩容。其扩容机制是并发友好的：

3.1 扩容步骤

1. 创建新表：容量是旧表的两倍。
2. 分布式迁移：
   • 每个线程在插入新元素时，会帮助将旧表中的数据迁移到新表中。
   • 通过一个 ForwardingNode 标记当前桶是否已经迁移。
3. 桶迁移：
   • 如果某个桶是链表，则重新计算每个节点的位置，放入新表中。
   • 如果某个桶是红黑树，则以红黑树的形式迁移到新表中。

3.2 扩容示例

假设当前哈希表容量为 16，负载因子为 0.75，扩容阈值为 16 * 0.75 = 12。当插入第 13 个元素时触发扩容：

• 新表容量为 32。
• 旧表中的数据会被迁移到新表中。

3.3 ForwardingNode

迁移过程中，使用 ForwardingNode 替代旧表中的节点，表示该桶已经迁移完成。

4. 代码示例

以下代码展示了 ConcurrentHashMap 的常见用法以及其线程安全特性：

import java.util.concurrent.ConcurrentHashMap;

public class ConcurrentHashMapExample {
    public static void main(String[] args) {
        // 创建 ConcurrentHashMap
        ConcurrentHashMap<Integer, String> map = new ConcurrentHashMap<>();

        // 插入元素
        map.put(1, "A");
        map.put(2, "B");
        map.put(3, "C");

        // 多线程操作
        Thread t1 = new Thread(() -> {
            map.put(4, "D");
            System.out.println("线程1完成插入: " + map);
        });

        Thread t2 = new Thread(() -> {
            map.put(5, "E");
            System.out.println("线程2完成插入: " + map);
        });

        t1.start();
        t2.start();

        // 等待线程执行完毕
        try {
            t1.join();
            t2.join();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }

        // 打印最终结果
        System.out.println("最终结果: " + map);
    }
}

扩展知识

1. 与 HashMap 的区别

2. 并发性能提升

• 在高并发场景下，ConcurrentHashMap 的性能显著优于传统的 HashTable（其方法使用全表锁）。

总结

• ConcurrentHashMap 使用数组 + 链表/红黑树的数据结构存储元素。
• 通过 CAS 和局部锁实现高效的线程安全。
• 采用分布式迁移机制优化了扩容性能。
• 它是多线程环境下高效的 Map 实现，非常适合高并发场景。

帅地永久会员

打赏 收藏 海报挣佣金 推广链接