问题

12. ConcurrentSkipListMap 是如何保证线程安全的？相比 ConcurrentHashMap 有哪些优势？

标准答案

ConcurrentSkipListMap 通过 跳表（SkipList）+ 无锁 CAS + 自旋重试 机制实现线程安全，支持高效的并发读写操作。相比于 ConcurrentHashMap，ConcurrentSkipListMap 支持 Key 有序存储，适用于范围查询、排序、Top K 查询等场景，而 ConcurrentHashMap 仅适用于高吞吐的 Key-Value 读写，并不保证有序性。

答案解析

1. ConcurrentSkipListMap 的底层实现

ConcurrentSkipListMap 基于跳表（SkipList），底层是 多级索引 + 有序链表 结构：

• 数据结构：多层索引，最底层是 有序单链表，高层是索引层，帮助快速查找。
• 并发控制：采用 CAS（无锁操作）+ 自旋重试 进行插入、删除，避免全局锁，提高吞吐量。

跳表的结构如下：

Level 3:    ----> 10 ------------> 50 ------------------> 90
Level 2:    ----> 10 ------> 30 --> 50 ------> 70 ------> 90
Level 1:    ----> 10 -> 20 -> 30 -> 40 -> 50 -> 60 -> 70 -> 80 -> 90

🔹 每一层都是一个有序链表，上层是下层的索引，查询时可跳过大量数据，提高查找速度。
🔹 最底层 维护所有数据，插入时 随机决定 是否在更高层建立索引。

---

2. 并发安全的实现

ConcurrentSkipListMap 采用 CAS（Compare-And-Swap）+ 自旋 来保证线程安全，避免锁竞争：

1. 插入（put）

   • 先通过 索引层 快速定位插入点；
   • 采用 CAS 将新节点插入到 底层链表，如果失败，则重试；
   • 根据 随机概率 决定是否在更高层索引插入该节点。

2. 删除（remove）

   • 先通过 索引层 定位目标节点；
   • 采用 CAS 将目标节点从底层链表移除；
   • 清理无效的索引层，保持索引结构紧凑。

3. 查询（get）

   • 先通过 索引层 快速跳跃查找目标 key；
   • 再进入底层链表，找到最精确的 key-value。

由于所有操作都基于 CAS + 链表操作，避免了同步锁（如 synchronized），极大提高并发性能。

---

3. ConcurrentSkipListMap VS ConcurrentHashMap

特性	ConcurrentSkipListMap	ConcurrentHashMap
数据结构	跳表（SkipList）	数组 + 链表 + 红黑树
线程安全机制	CAS + 自旋	分段锁（JDK 1.7）→ CAS + 链表/红黑树（JDK 1.8）
Key 是否有序	✅ 有序（自然排序或 Comparator）	❌ 无序
查询效率	O(log n)	O(1)
插入/删除效率	O(log n)	O(1)
适用场景	范围查询、排序、Top K 查询	高并发 Hash 读写
内存占用	较高（维护索引层）	较低

4. 适用场景

✅ 适合 ConcurrentSkipListMap 的场景

1. 需要有序 Key 存储：如 排行榜、时间序列数据存储（按时间排序）；
2. 范围查询（Range Query）：如 subMap(fromKey, toKey)，适合区间查询；
3. Top K 查询：如查找最大/最小 N 个元素；
4. 消息队列（Kafka-like）：消息按照时间戳排序，按时间批量消费。

❌ 不适合的场景

1. 高吞吐 Hash 读写：如果不关心顺序，ConcurrentHashMap 读写性能更高；
2. 极端高并发场景：由于 O(log n) 查询效率，性能比 ConcurrentHashMap 略低。

---

深入追问

🔹 为什么 ConcurrentSkipListMap 采用跳表而不是红黑树？
🔹 CAS 自旋会导致 CPU 高负载，如何优化？
🔹 ConcurrentSkipListMap 如何在高并发场景下保持索引层稳定？

---

相关面试题

• ConcurrentSkipListMap 与 TreeMap 的本质区别？
• 跳表相比于红黑树有哪些优势？
• ConcurrentSkipListMap 如何实现无锁并发？
• ConcurrentSkipListMap 适用于哪些业务场景？