问题

24. ConcurrentSkipListMap 与 TreeMap 的性能对比，适用于哪些场景？

标准答案

ConcurrentSkipListMap 和 TreeMap 都是 有序 Map，但 ConcurrentSkipListMap 适用于 高并发读写 场景，而 TreeMap 更适合 单线程环境。

• ConcurrentSkipListMap（跳表）：基于 跳表（SkipList），读写 O(log n)，支持高并发，多个线程可同时访问。
• TreeMap（红黑树）：基于 红黑树（Red-Black Tree），单线程操作性能优于跳表，但在高并发场景下需要外部同步（如 Collections.synchronizedMap），性能下降。

适用场景：

• 高并发排序查询：如 排行榜、延时队列、缓存过期管理，适合 ConcurrentSkipListMap。
• 单线程范围查询：如 小规模排序存储、离线数据处理，适合 TreeMap。

答案解析

1. ConcurrentSkipListMap 与 TreeMap 的底层结构

TreeMap（红黑树）

TreeMap 采用 红黑树 作为存储结构，具备 自平衡、有序 特性，所有操作的时间复杂度为 O(log n)。

• 插入、删除、查找：O(log n)（红黑树自平衡需要额外旋转操作）。
• 线程安全性：非线程安全，需 Collections.synchronizedSortedMap() 或 ConcurrentHashMap 搭配 CopyOnWriteArrayList。

ConcurrentSkipListMap（跳表）

ConcurrentSkipListMap 采用 跳表（SkipList） 作为存储结构，允许 多线程并发访问，多个线程可以同时读写不同层级的数据，而不会阻塞。

• 插入、删除、查找：O(log n)（通过多级索引优化查询）。
• 线程安全性：内置 CAS + 细粒度锁，支持高并发读写。

数据结构对比

特性	TreeMap（红黑树）	ConcurrentSkipListMap（跳表）
底层结构	红黑树	跳表
插入/删除复杂度	O(log n)（自平衡）	O(log n)（多级索引）
查询复杂度	O(log n)	O(log n)
线程安全	❌ 非线程安全	✅ 线程安全（CAS + 细粒度锁）
并发性能	低（需外部同步）	高（无全局锁，可并发修改）
适用场景	单线程排序存储	高并发范围查询

2. 为什么 ConcurrentSkipListMap 适合高并发？

(1) 跳表的层级索引，提升查询效率

跳表的结构类似于多个层次的链表，高层是对低层数据的索引，查询时可先访问高层索引，减少遍历时间。

Level 3:  ────────────────> [50] ────────────> [100] ────────────> NULL
Level 2:  ─────> [20] ───────────> [50] ────────────> [100] ─────> NULL
Level 1:  [10] ─> [20] ─> [30] ─> [40] ─> [50] ─> [60] ─> [70] ─> [100] ─> NULL

当查询 60 时，不需要遍历整个链表，而是先从 Level 3 查 50，然后直接跳到 Level 1 的 60，比红黑树的 左/右子树搜索更快。

(2) 细粒度锁与 CAS，提升并发性能

• 无全局锁，多个线程可同时操作不同层级的索引，减少锁竞争。
• 写操作采用 CAS（Compare-And-Swap），失败时重试，避免锁开销。
• 部分操作使用 synchronized 保护关键路径，但比 TreeMap 整体同步锁要高效。

(3) ConcurrentSkipListMap 适用于并发排序查询

• 范围查询 (subMap())：支持 O(log n) 查询效率，适合 有序日志、排名系统。
• 动态数据存储：可以高效插入、删除、更新，适用于 缓存超时管理（如 LRU 结合 LinkedHashMap）。
• 无锁遍历：使用 Iterator 进行并发遍历时不会抛出 ConcurrentModificationException，适用于 高吞吐场景。

3. TreeMap 与 ConcurrentSkipListMap 的使用场景

✅ TreeMap 适用场景

• 单线程环境（无并发需求，查询快）：

  TreeMap<Integer, String> treeMap = new TreeMap<>();
  treeMap.put(10, "A");
  treeMap.put(20, "B");
  

• 有序数据存储（如字典、统计信息）
• 需要 NavigableMap 方法（如 higherKey()、floorKey()）

✅ ConcurrentSkipListMap 适用场景

• 高并发数据排序查询（如 订单系统、排行榜）：

  ConcurrentSkipListMap<Long, String> map = new ConcurrentSkipListMap<>();
  map.put(1000L, "order1");
  map.put(2000L, "order2");
  

• 范围查询（如 subMap()），适用于 缓存超时管理：

  // 查询 1000ms ~ 5000ms 之间的订单
  map.subMap(1000L, true, 5000L, true);
  

• 高并发读取场景（如 时间序列数据存储）

深入追问

🔹 1. 为什么 ConcurrentSkipListMap 在高并发下比 TreeMap 更优？

• TreeMap 需要全局锁，并发写入性能差。
• ConcurrentSkipListMap 基于跳表，支持无锁读，并发写入时仅局部锁定。

🔹 2. 为什么 ConcurrentSkipListMap 采用跳表，而不是红黑树？

• 跳表查询复杂度与红黑树相同（O(log n)），但支持无锁读，扩展性更强。
• 红黑树插入/删除涉及旋转，写入时会锁整个结构，影响并发。

🔹 3. 在分布式系统中，跳表有哪些应用？

• Redis 的 ZSET（有序集合）就采用跳表，支持高效范围查询（如 ZRANGE）。
• 时间序列数据库（如 TSDB）使用跳表进行高并发索引。

相关面试题

• 为什么跳表可以替代红黑树？
• ConcurrentSkipListMap 与 ConcurrentHashMap 的区别？
• Redis 为什么使用跳表而不是 AVL 树？
• 如何优化 TreeMap 在高并发下的性能？