# 问题
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
1
2
3
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 在高并发下的性能?