Java里的ConcurrentSkipListMap是什么？基于跳表实现的可排序并发Map详解

在Java并发容器家族中，ConcurrentHashMap无疑是最常用的选择，但它有一个天然的局限：不保证键的遍历顺序。当你需要一个线程安全且按key排序的Map时，ConcurrentSkipListMap就是标准答案。它是JDK在1.6版本引入的并发容器，底层基于跳表（Skip List）实现，同时实现了NavigableMap接口，支持丰富的导航操作。本文将从原理、对比和实践三个层面，把这个容器彻底讲清楚。

跳表原理：为什么不用红黑树也能做到O(log n)

跳表是由William Pugh在1990年提出的一种概率性数据结构，核心思想是用空间换时间。单链表查找需要从头遍历，复杂度是O(n)，而跳表在链表之上建立了多层索引：最底层是完整的有序链表，上层索引逐层抽取部分节点，每个节点以随机概率决定自己要出现在第几层。

查找时从最高层出发，如果当前节点的下一个节点比目标小，就继续向右走；否则下降一层继续找。这样每一层都能跳过大约一半的节点，整体查找次数期望值为O(log n)，与平衡树的性能相当。下图是一个简化的跳表示意：假设要查找key为35的节点，从第3层开始，依次经过20（下降）、30（下降），最终在最底层定位到35，全程只比较了3次。

第3层:  head ------------------------------> 50
第2层:  head --------> 30 --------------------> 50
第1层:  head --> 20 --> 30 --> 40 --------> 50
第0层:  head -> 10 -> 20 -> 30 -> 35 -> 40 -> 50

相比红黑树，跳表最大的优势在于实现简单且天然适合并发。红黑树在插入删除时可能引发大范围的结构调整，需要全局加锁或复杂的锁方案；而跳表的插入和删除只影响相邻节点，可以通过CAS操作完成无锁化的层级连接。这正是Doug Lea选择跳表作为ConcurrentSkipListMap底层结构的原因。随机层数的生成也很简单，通常使用抛硬币的方式，代码大致如下：

// 判断节点应该插入到多少层，每层以1/4概率晋升
private int randomLevel() {
    int level = 0;
    while (rnd.nextInt() >= 0 && level < MAX_LEVEL) {
        level++;  // 概率性增加层数
    }
    return level;
}

与ConcurrentHashMap的对比：选型前必须搞清楚

两者的定位完全不同。ConcurrentHashMap基于哈希表实现，通过CAS加synchronized锁住桶头节点，写入吞吐量极高，查找是O(1)级别；ConcurrentSkipListMap基于跳表，写入和查找都是O(log n)，还包含维护多层索引的额外开销。在纯粹的无序读写场景下，ConcurrentSkipListMap的性能通常只有ConcurrentHashMap的三分之一到一半左右。

但顺序性是它不可替代的价值。跳表本身有序，遍历时按键的自然顺序（或构造时传入的Comparator顺序）输出，支持firstKey、lastKey、floorKey、ceilingKey、headMap、tailMap、subMap等导航方法，这些在哈希结构上无从谈起。此外，ConcurrentSkipListMap的size方法需要遍历统计，复杂度是O(n)且不是常量时间，迭代器是弱一致性的，反映创建时刻之后的写入，但不会抛出ConcurrentModificationException。

选型可以简单总结为一句话：不需要顺序、追求极致吞吐，用ConcurrentHashMap；需要有序遍历、范围查询、排名类操作，用ConcurrentSkipListMap。与之配套的还有ConcurrentSkipListSet，本质上是对ConcurrentSkipListMap的包装，行为等价于线程安全的TreeSet。

实战用法：导航操作与并发遍历示例

先看基础用法。下面的代码演示了构造、排序遍历以及几个典型的导航方法。注意当key是自定义类型时，必须保证其compareTo方法与equals语义一致，否则容器内部状态可能出现混乱。

ConcurrentSkipListMap<Integer, String> map = new ConcurrentSkipListMap<>();
map.put(30, "三十");
map.put(10, "十");
map.put(20, "二十");

// 遍历结果按键升序输出：10、20、30
for (Map.Entry<Integer, String> entry : map.entrySet()) {
    System.out.println(entry.getKey() + " = " + entry.getValue());
}

System.out.println(map.firstKey());    // 10，最小的键
System.out.println(map.lastKey());     // 30，最大的键
System.out.println(map.floorKey(25));  // 20，小于等于25的最大键
System.out.println(map.ceilingKey(25)); // 30，大于等于25的最小键

范围查询是跳表结构的强项。headMap(K toKey)返回小于toKey的视图，tailMap(K fromKey)返回大于等于fromKey的视图，subMap则取闭开区间。这些方法返回的是原map的视图而非拷贝，视图上的修改会直接影响原容器，开销极小。

ConcurrentSkipListMap<Integer, String> map = new ConcurrentSkipListMap<>();
for (int i = 1; i <= 100; i++) {
    map.put(i, "value-" + i);
}

// 范围查询：取[20, 50)区间的数据，视图操作无需拷贝
NavigableMap<Integer, String> sub = map.subMap(20, true, 50, false);
sub.forEach((k, v) -> System.out.println(k + " -> " + v));

// 逆序视图，倒序遍历整个map
for (Integer k : map.descendingKeySet()) {
    // 从100到1依次输出
}

在多线程环境下使用时，可以直接放心地并发读写，无需任何外部同步。一个常见的应用场景是实时排行榜：多个线程并发更新分数，展示线程按分数倒序取出前N名。通过构造时传入倒序Comparator，配合headMap就能高效实现。

// 用跳表实现简单的并发排行榜，按分数从高到低排列
ConcurrentSkipListMap<Long, String> rank = new ConcurrentSkipListMap<>(Comparator.reverseOrder());

// 并发写入分数（key为分数，value为用户名）
new Thread(() -> rank.put(95L, "alice")).start();
new Thread(() -> rank.put(88L, "bob")).start();
new Thread(() -> rank.put(92L, "carol")).start();

// 取前两名：由于是倒序，最小的key就是榜首之后的边界
NavigableMap<Long, String> top = rank.headMap(90L, true);
top.forEach((score, user) -> System.out.println(user + ": " + score));

使用时的注意事项

第一，性能敏感场景要掂量索引开销。每次插入都要生成随机层数、维护索引链，高并发写入下CAS重试也可能带来竞争，官方文档也明确指出它是排序场景下的选择而非通用首选。第二，size和isEmpty不是O(1)，跨方法组合调用（比如先判断size再get）在并发下没有原子性保证，需要原子语义时应使用putIfAbsent、compute、merge这类复合方法。

第三，key必须可比较且比较逻辑稳定。要么实现Comparable接口，要么构造时提供Comparator，比较过程中如果依赖可变字段，会导致节点定位错误甚至数据丢失。第四，null约束很严格：key和value都不允许为null，传入null会直接抛出NullPointerException，这一点比HashMap严格得多，迁移旧代码时要特别留意。

总结一下，ConcurrentSkipListMap用概率性的跳表结构换来了与TreeMap等价的有序语义，同时通过CAS实现了无锁并发。理解它，不仅能解决有序并发这一类具体问题，更能体会到数据结构设计在并发编程中的权衡艺术。

ConcurrentSkipListMap跳表并发Map修改时间：2026-08-31 18:00:40