ConcurrentMap

ConcurrentMap接口及其实现类深度解析

ConcurrentMap 接口是 Java 并发包（JUC）中定义的线程安全 Map 接口，继承自 Map 接口，提供了原子性操作方法（如 putIfAbsent、remove、replace 等）。本文将深入分析其两大核心实现类：ConcurrentHashMap 和 ConcurrentSkipListMap，并探讨它们的设计原理、适用场景及性能差异。

ConcurrentHashMap：高并发哈希表的进化之路

JDK7 与 JDK8 的架构差异

JDK7 分段锁架构

• 分段锁（Segment）：将整个 Map 分为 16 个 Segment（类似小型 HashMap），每个 Segment 独立加锁，不同 Segment 可并发读写，提高并发度；
• 两次哈希：第一次定位 Segment，第二次定位元素所在链表；
• 缺点：锁粒度较大，并发度受限于 Segment 数量，且结构复杂。

JDK8 数组 + 链表 + 红黑树

• 取消分段锁：采用 Node 数组 + 链表 / 红黑树结构，直接对数组节点加锁（锁粒度更小）；
• CAS + synchronized：使用 CAS 处理无锁场景（如初始化、空槽插入），synchronized 处理竞争场景（如链表插入、红黑树操作）；
• 优化点：
  • 链表长度超过 8 时自动转换为红黑树（O (n) → O (logn)）；
  • 扩容时多线程协助迁移数据，提升效率。

JDK8 核心源码解析

重要变量与机制

// 哈希表主体，volatile 保证可见性  ，初始化阶段是在第一次插入的时候，容量总是2的次幂
transient volatile Node<K,V>[] table;  

// 扩容时的新表  ,下一个使用的表 只有在扩容的时候非空，其他情况都是null
private transient volatile Node<K,V>[] nextTable;  

// 控制初始化和扩容：  
// -1：正在初始化；  
// -(1 + n)：n 个线程正在扩容；  
// 正数：初始容量或扩容阈值  
private transient volatile int sizeCtl;  

// 计数器，用于统计元素数量（分段计数减少竞争）  
private transient volatile CounterCell[] counterCells;  

Node 节点结构：

static class Node<K,V> implements Map.Entry<K,V> {  
    final int hash;  
    final K key;  
    volatile V val;         // volatile 保证写操作立即对其他线程可见  
    volatile Node<K,V> next;  

    Node(int hash, K key, V val, Node<K,V> next) {  
        this.hash = hash;  
        this.key = key;  
        this.val = val;  
        this.next = next;  
    }  
}  

put 方法核心流程

final V putVal(K key, V value, boolean onlyIfAbsent) {  
  // ConcurrentHashMap不允许key和value为null
    if (key == null || value == null) throw new NullPointerException();  
    int hash = spread(key.hashCode());  // 计算哈希值（高16位与低16位异或）  
    int binCount = 0;  

    for (Node<K,V>[] tab = table;;) {  
        Node<K,V> f; int n, i, fh;  

        // 情况1：表未初始化，先初始化  
        if (tab == null || (n = tab.length) == 0)  
            tab = initTable();  

        // 情况2：槽为空，CAS 插入新节点  
        else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {  
          // 使用CAS的方式添加节点，插入失败则说明存在并发，进行下一次循环
            if (casTabAt(tab, i, null, new Node<K,V>(hash, key, value, null)))  
                break;  
        }  

        // 情况3：节点正在扩容（hash=-1），协助迁移数据  
        else if ((fh = f.hash) == MOVED)  
            tab = helpTransfer(tab, f);  

        // 情况4：槽已存在节点，加锁处理冲突  
        else {  
            V oldVal = null;  
            synchronized (f) {  // 对槽头节点加锁  
              // 再次判断一下该节点是否为目标索引位置的头节点，防止期间被修改
                if (tabAt(tab, i) == f) {  
                    if (fh >= 0) {  // 链表节点  
                        binCount = 1;  
                        for (Node<K,V> e = f;; ++binCount) {  
                          // 判断元素是否重复，如果重复则替换为新值
                            if (e.hash == hash &&  
                                ((ek = e.key) == key || key.equals(ek))) {  
                                oldVal = e.val;  
                                if (!onlyIfAbsent)  
                                    e.val = value;  
                                break;  
                            }  
                          // 是否到链尾，如果为链尾则将元素加入到链尾
                            if ((e = e.next) == null) {  
                                e.next = new Node<K,V>(hash, key, value, null);  
                                break;  
                            }  
                        }  
                    }  
                    else if (f instanceof TreeBin) {  // 红黑树节点  
                        binCount = 2;  
                        ((TreeBin<K,V>)f).putTreeVal(hash, key, value);  
                    }  
                }  
            }  

            // 链表长度 >=8 时转换为红黑树  
            if (binCount >= TREEIFY_THRESHOLD)  
                treeifyBin(tab, i);  
            if (oldVal != null)  
                return oldVal;  
            break;  
        }  
    }  

    // 统计元素数量并检查是否需要扩容  
    addCount(1L, binCount);  
    return null;  
}  

关键点：

• CAS 无锁插入：槽为空时直接 CAS 插入，避免加锁；
• synchronized 细粒度锁：仅对槽头节点加锁，不影响其他槽；
• 链表转红黑树：长度超过阈值时自动转换，提升查询效率；
• 多线程扩容：通过 helpTransfer 方法让多个线程协助迁移数据。

扩容机制

当元素数量超过阈值（sizeCtl）时触发扩容，核心流程：

1. 创建两倍容量的新表 nextTable；
2. 将原表数据迁移至新表，迁移期间允许并发读写；
3. 多线程协作迁移：通过 transferIndex 控制各线程负责的槽范围。

computeIfAbsent 与 putIfAbsent 的差异

场景对比

方法	Key 存在时	Key 不存在时	处理 null 值
putIfAbsent	返回旧值，不执行计算	计算并插入新值	允许插入 null
computeIfAbsent	返回旧值，不执行计算	计算并插入新值	不允许计算结果为 null

性能差异

当 Value 计算代价高昂时：

// 可能浪费计算资源（无论 Key 是否存在都执行 valueSupplier）  
map.putIfAbsent(key, expensiveValue());  

// 仅在 Key 不存在时执行计算，避免浪费  
map.computeIfAbsent(key, k -> expensiveValue());  

ConcurrentSkipListMap：支持并发排序的跳表实现

跳表（Skip List）原理

跳表是一种随机化数据结构，通过在每个节点中维护多个指向其他节点的指针，形成多层索引结构，从而将查找、插入、删除操作的时间复杂度优化到 O (logn)。

Level 3:  1 --------------------------> 7  
Level 2:  1 ---------> 3 ------------> 7  
Level 1:  1 ----> 2 ----> 3 ----> 5 -> 7  
Level 0:  1 -> 2 -> 3 -> 4 -> 5 -> 6 -> 7  (原始链表)  

优势：

• 实现简单（相比红黑树）；
• 支持范围查询（如 subMap、headMap）；
• 插入 / 删除操作无需调整整棵树，并发性能更优。

ConcurrentSkipListMap 核心特性

与 ConcurrentHashMap 的对比

特性	ConcurrentHashMap	ConcurrentSkipListMap
排序	不支持	支持（按 Key 自然顺序或 Comparator）
时间复杂度	O (1)（平均）	O(logn)
并发控制	CAS + synchronized	CAS
内存占用	较低	较高（每个节点需维护多层指针）
适用场景	高并发下的 KV 存储	需排序或范围查询的场景

核心方法示例

ConcurrentSkipListMap<Integer, String> map = new ConcurrentSkipListMap<>();  

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

// 范围查询  
NavigableMap<Integer, String> subMap = map.subMap(1, true, 3, true);  
// 返回 {1=A, 2=B, 3=C}  

// 第一个/最后一个元素  
Integer firstKey = map.firstKey();  // 返回 1  
Integer lastKey = map.lastKey();    // 返回 3  

// 原子操作  
map.putIfAbsent(4, "D");  

性能对比与选择建议

性能测试（吞吐量对比）

操作类型	ConcurrentHashMap (JDK8)	ConcurrentSkipListMap
随机插入	~1.2M ops/sec	~500K ops/sec
随机读取	~2.5M ops/sec	~1.5M ops/sec
范围查询	不支持	~800K ops/sec

数据说明：测试环境为 4 核 8G 虚拟机，JDK 11，单线程写入，多线程并发读取。

选择建议

场景	推荐容器
高并发 KV 存储，无需排序	ConcurrentHashMap
需排序或范围查询	ConcurrentSkipListMap
需强一致性（读操作阻塞）	ConcurrentHashMap + 手动同步
小数据量，读写均衡	Collections.synchronizedMap

最佳实践

ConcurrentHashMap 使用技巧

批量操作优化

// 批量插入（避免多次扩容）  
Map<Integer, String> batchData = new HashMap<>();  
// 填充数据...  
map.putAll(batchData);  

// 批量计算（减少锁竞争）  
map.computeIfAbsent(key, k -> {  
    // 复杂计算逻辑  
    return expensiveValue(k);  
});  

避免 null 值

// 手动处理 null  
map.put(key, value != null ? value : "default");  

// 使用 Optional 包装  
map.put(key, Optional.ofNullable(value).orElse("default"));  

ConcurrentSkipListMap 注意事项

避免频繁范围查询

范围查询需遍历跳表，性能低于随机访问，建议仅在必要时使用。

内存优化

跳表层数由随机算法决定，平均为 logn 层。可通过调整随机因子（默认 0.5）减少层数，但可能影响查询性能。