Java中如何通过ConcurrentSkipListMap实现有序并发Map

ConcurrentSkipListMap是Java中基于跳跃表实现的线程安全有序Map，支持高并发下O(log n)时间复杂度的插入、删除和查找操作，1. 它实现了SortedMap和ConcurrentMap接口，2. 默认按自然顺序排序键，也可通过Comparator自定义排序规则，3. 遍历时Entry按键排序且不抛出ConcurrentModificationException，4. 提供putIfAbsent、remove、replace等原子操作，适用于多线程环境下的有序数据访问场景，但不支持null键或值。

在Java中，ConcurrentSkipListMap 是一个支持高并发、线程安全且能保持键有序的Map实现。它基于跳跃表（Skip List）结构，适用于需要按自然顺序或自定义顺序排序键的并发场景。

1. 什么是 ConcurrentSkipListMap？

ConcurrentSkipListMap 是 java.util.concurrent 包中的一个类，实现了 SortedMap 和 ConcurrentMap 接口。与 ConcurrentHashMap 不同的是，它不仅线程安全，还能保证键的有序性——默认按自然顺序排序，也可以传入 Comparator 自定义排序规则。

它的主要优势在于：

• 支持并发读写操作，性能优于加锁的同步Map
• 所有操作（插入、删除、查找）平均时间复杂度为 O(log n)
• 遍历时返回的Entry是按键排序的
• 适用于高并发下需要有序访问的场景

2. 基本使用方式

创建和使用 ConcurrentSkipListMap 非常简单，可以直接实例化：

ConcurrentSkipListMap map = new ConcurrentSkipListMap<>();
map.put("apple", 1);
map.put("banana", 2);
map.put("cherry", 3);

// 输出时会按字母顺序排列
map.forEach((k, v) -> System.out.println(k + ": " + v));
// 输出：
// apple: 1
// banana: 2
// cherry: 3

3. 自定义排序规则

如果希望键按照特定顺序排列，可以在构造函数中传入 Comparator：

// 按字符串长度排序
ConcurrentSkipListMap map = new ConcurrentSkipListMap<>(
    (a, b) -> Integer.compare(a.length(), b.length())
);
map.put("hi", 1);
map.put("hello", 2);
map.put("hey", 3);

map.forEach((k, v) -> System.out.println(k + ": " + v));
// 输出：
// hi: 1
// hey: 3
// hello: 2

4. 并发环境下的安全操作

ConcurrentSkipListMap 所有方法都是线程安全的，多个线程可同时进行读写：

• putIfAbsent(key, value)：仅当键不存在时才插入
• remove(key, value)：条件删除
• replace(key, oldVal, newVal)：原子替换
• 支持并发迭代，不会抛出 ConcurrentModificationException

示例：多线程环境下安全更新计数器

ConcurrentSkipListMap counter = new ConcurrentSkipListMap<>();

Runnable task = () -> {
    for (int i = 0; i < 1000; i++) {
        counter.compute(i % 10 == 0 ? "even" : "odd", 
            (k, v) -> v == null ? 1L : v + 1);
    }
};

// 启动多个线程
Thread t1 = new Thread(task);
Thread t2 = new Thread(task);
t1.start(); t2.start();
t1.join(); t2.join();

System.out.println(counter); // {even=200, odd=1800}