ConcurrentSkipListMap（跳表）

发表于： 2023-06-04 分类于： java

字数： 1824 阅读：≈ 4分钟浏览：

Map的比较

ConcurrentSkipListMap和TreeMap，都是有序的哈希表。

线程安全机制不同，TreeMap非线程安全，ConcurrentSkipListMap线程安全。
TreeMap是通过红黑树实现，ConcurrentSkipListMap通过跳表实现。
ConcurrentHashMap 存取速度高于ConcurrentSkipListMap，但是ConcurrentSkipListMap 支持更高的并发。
TreeMap没有对应的并发类，因为红黑树在插入删除时要旋转子树，那么使用并发方法很难做到让多个线程同时旋转子树而不需要加锁。红黑树本身就已经非常复杂了，要把它改写为并发数据结构难度太大了。

跳表（SkipList），插入、删除、搜索和替换（替换实际上并入了put方法）只是在操作多个单向链表（包括一个节点链表和最多31个索引链表），因此可以使用无锁算法。

所以只有TreeMap，没有其并发实现，但是却有跳表实现的ConcurrentSkipListMap。

使用空间换时间的算法，是先大步查找确定范围，再逐渐缩小迫近。

跳表是一种允许在有序队列中进行快速查找的数据结构，其插入、删除、查找的时间复杂度均为O(logN)，这一点与TreeMap类似。

本质是一条单向链表，其中按照顺序存储了节点，并为每个节点按照一定的概率生成了多级索引，下层的索引必定包含上层索引。

数据结构：跳表是多层链表，更简单；红黑树是平衡有序的二叉树，更复杂。
具备更好的并发优势。红黑树在插入时可能涉及到整棵树的 rebalance，而 SkipList 可以仅在某个局部进行操作，要锁定的节点更少，从而实现更好的并发性能。

利用了：volatile关键字、Unsafe的CAS方法、自旋锁等并发技巧，实现了无锁算法，获得了更加优秀的并发性能。

由于多个线程可以同时对映射表进行操作，所以size需要遍历整个链表才能返回元素个数。

对于删除这种较为危险的操作，ConcurrentSkipListMap 会使用标记的方式，先阻止其他线程对待删除节点的进一步操作，再对该节点进行删除，从而降低删除的危险性。通过标记的方式，也可以让其他线程在操作时帮助进行删除，避免阻塞其他操作，进一步提升写性能。

悲观锁就是一种避免冲突的办法，我们同一时间只允许一个线程进入 put() 等方法，比如使用 Java 的 synchronized 关键字。

这种锁总是假设最坏的情况，认为每次自己拿数据的时候别人都会修改，所以共享资源每次只允许一个线程使用，这样会影响跳表的性能。

可以使用读写锁来改善并发读的性能（比如 Java 的 ReentrantReadWriteLock），这种锁允许多个线程同时进行读操作，但在并发读写的情况下，读写操作还是会被其他的写操作阻塞。

ConcurrentSkipListMap 的核心是 CAS 操作。

原因：跳表这种数据结构在写入时修改存在一定的局部性。不同于红黑树等树状结构在插入时的平衡操作可能涉及整个树，跳表在插入或删除时只涉及一小部分的指针变动

假设：两个节点在插入时对彼此没有影响，在这种情况下，跳表是可以并发进行写入的。

当它在试图修改某个节点的指针时，会使用局部变量保存该指针的原始状态，并利用 CAS 操作进行修改，如果修改失败，则使用 for 循环进行重试。

现代 CPU 几乎都提供了指令来实现，称为 CAS（Compare And Swap 或 Compare And Set）。

CAS 操作是原子的，因此 CAS 是一种常见的实现乐观锁的方法。

由于乐观锁并没有阻塞线程的执行，只是进行了冲突检测，因此在不存在冲突的情况下可以实现多个节点的并发写入，让跳表拥有更好的写入性能。

整体来看，CAS 操作相比互斥锁开销较低，并且能推动开发者更细粒度地对临界区进行控制，减少对其他线程的阻塞，但由于它使用 for 循环进行重试操作，有可能占用一定的 CPU 资源。

因此 CAS 操作更适用于使用多核 CPU，并且临界区较小（并发操作共享变量的事件较短）的场景。

因为CAS等无锁实现，所以 LevelDB、RockDB 以及 Pebble 等高性能键值对存储引擎都采用 SkipList 来作为自己的内存数据结构。

Redis使用跳跃表作为有序集合(zset)键的底层实现之一。

如果一个有序集合包含的元素数量比较多，又或者有序集合中元素的成员是比较长的字符串时，Redis就会使用跳跃表来作为有序集合键的底层实现。