# 问题

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

# 标准答案

ConcurrentSkipListMapTreeMap 都是 有序 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
1
2
3

当查询 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");
    
    1
    2
    3
  • 有序数据存储(如字典、统计信息)
  • 需要 NavigableMap 方法(如 higherKey()floorKey()

# ✅ ConcurrentSkipListMap 适用场景

  • 高并发数据排序查询(如 订单系统、排行榜):
    ConcurrentSkipListMap<Long, String> map = new ConcurrentSkipListMap<>();
    map.put(1000L, "order1");
    map.put(2000L, "order2");
    
    1
    2
    3
  • 范围查询(如 subMap(),适用于 缓存超时管理
    // 查询 1000ms ~ 5000ms 之间的订单
    map.subMap(1000L, true, 5000L, true);
    
    1
    2
  • 高并发读取场景(如 时间序列数据存储

# 深入追问

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

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

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

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

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

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

# 相关面试题

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