ConcurrentSkipListSet和ConcurrentSkipListMap分析以及总结Set
ConcurrentSkipListSet和ConcurrentSkipListMap分析以及总结Set
ConcurrentSkipListSet怎么实现线程安全
跳表结构
跳表是一种概率型数据结构，由多个层级的链表组成，每个元素在不同的层中出现的概率是固定的。这种结构使得在平均情况下，插入、删除和查找操作的时间复杂度为 (O(\log n))。
2. 原子操作
ConcurrentSkipListSet 的内部实现依赖于 java.util.concurrent.atomic 包中的原子类，如 AtomicInteger 和 AtomicReference。这允许在并发环境中安全地更新节点和指针。
3. 锁分段技术
跳表的每个节点都有一个前向指针（即指向下一个节点），在进行插入和删除时，ConcurrentSkipListSet 会使用一种锁分段策略。它对每个节点的更新操作仅锁定该节点及其前后节点，而不是整个数据结构。这种局部性减少了锁竞争，提高了并发性能。
4. CAS（Compare-And-Swap）
ConcurrentSkipListSet 在插入和删除元素时，使用 CAS 操作来更新节点的指针。通过原子性地更新指针，避免了传统锁机制所带来的开销。
5. 遍历操作
在遍历时，ConcurrentSkipListSet 允许其他线程对集合进行并发修改。这是通过复制当前状态的快照（snapshot）来实现的，确保遍历的线程能够看到一致的视图。
1. ConcurrentSkipListMap 与 ConcurrentSkipListSet
JDK中包含两个与SkipList相关的数据结构，分别是ConcurrentSkipListSet和ConcurrentSkipListMap，二者均为并发容器，一个是Set实现一个是Map实现。 而ConcurrentSkipListSet内部实际上包含一个ConcurrentSkipListMap，其将元素作为ConcurrentSkipListMap的key存放，所以本质上也以ConcurrentSkipListMap作为底层实现。这里将主要分析ConcurrentSkipListMap的源代码。
2. 与ConcurrentHashMap对比
-
ConcurrentSkipListMap与ConcurrentHashMap都是线程安全的并发容器，可以应用于并发读写场景。
-
ConcurrentHashMap底层基于哈希，ConcurrentSkipListMap底层基于跳表结构，而跳表本身是有序的，所以ConcurrentSkipListMap也是有序的。
3. ConcurrentSkipListMap采用的无锁删除算法
基础的算法基于 HM linked ordered set algorithm (Tim Harris, "A pragmatic implementation of non-blocking linked lists")的变种。它的基本思想是在删除节点时标记待删除结点的下一个结点，来避免并发的插入冲突。作者也提到另一种方案是使用AtomicMarkedReference，但是作者认为AtomicMarkedReference不够高效, 直接使用CAS操作更加高效。
具体在删除时，采用的是类似懒删除的策略，如果一个结点的value为null，则认为它已经被逻辑删除
假设待删除结点为n，b为它的前驱结点，f为它的后继结点
第一步CAS设置n的value为null，此时该结点已经被逻辑删除，插入、查找等操作将会忽略该结点。
第二步CAS设置n的后继结点为一个Marker结点（value指向自己），此时任何操作都不会再其后继续添加结点。
第三步CAS设置n的前驱结点b指向其后继结点f，完成删除。
在这个过程中，如果第一步失败，则会进行重试。第二步或第三步失败也不会影响其他操作，因为该结点value已经被设置成null，其他操作会忽略该结点，相当于该结点已经被删除。并且其他操作内部有帮助删除操作，会检查value已经被设定成null的结点，帮助其完成删除的第二步和第三步。
4. 源码分析
在ConcurrentSkipListMap源代码的基础上，对主要的查询、插入、删除等操作进行分析，并增加了详细的代码注释，帮助理解ConcurrentSkipListMap的源代码。
Set大汇总（横屏观看）
| Set | 有序性 | 线程安全 | 底层实现 | 关键接口 | 特点 |
|---|---|---|---|---|---|
| HashSet | 无 | 否 | HashMap | 无 | 简单 |
| LinkedHashSet | 有 | 否 | LinkedHashMap | 无 | 插入顺序 |
| TreeSet | 有 | 否 | NavigableMap | NavigableSet | 自然顺序 |
| CopyOnWriteArraySet | 有 | 是 | CopyOnWriteArrayList | 无 | 插入顺序，读写分离 |
| ConcurrentSkipListSet | 有 | 是 | ConcurrentSkipListMap | NavigableSet | 自然顺序 |
从中我们可以发现一些规律：
（1）除了HashSet其它Set都是有序的；
（2）实现了NavigableSet或者SortedSet接口的都是自然顺序的；
（3）使用并发安全的集合实现的Set也是并发安全的；
（4）TreeSet虽然不是全部都是使用的TreeMap实现的，但其实都是跟TreeMap相关的（TreeMap的子Map中组合了TreeMap）；
（5）ConcurrentSkipListSet虽然不是全部都是使用的ConcurrentSkipListMap实现的，但其实都是跟ConcurrentSkipListMap相关的（ConcurrentNavigableMap为ConcurrentSkipListMap的具体实现）；