Java ConcurrentSkipListMap 跳表

淩亂°似流年 2021-09-25 03:46 319阅读 0赞

到目前为止，我们在Java世界里看到了两种实现key-value的数据结构：Hash、TreeMap，这两种数据结构各自都有着优缺点。

1.  Hash表：插入、查找最快，为O(1)；如使用链表实现则可实现无锁；数据有序化需要显式的排序操作。
2.  红黑树：插入、查找为O(logn)，但常数项较小；无锁实现的复杂性很高，一般需要加锁；数据天然有序。 然而，这次介绍第三种实现key-value的数据结构：SkipList。SkipList有着不低于红黑树的效率，但是其原理和实现的复杂度要比红黑树简单多了。
3.    TreeMap使用红黑树按照key的顺序（自然顺序、自定义顺序）来使得键值对有序存储*，*但是只能在单线程下安全使用；多线程下想要使键值对按照key的顺序来存储，则需要使用ConcurrentSkipListMap。
    
      ConcurrentSkipListMap的底层是通过跳表来实现的。跳表是一个链表，但是通过使用“跳跃式”查找的方式使得插入、读取数据时复杂度变成了O（logn）。
4.  ConcurrentSkipListMap是线程安全的有序的哈希表，适用于高并发的场景。  
    ConcurrentSkipListMap和[TreeMap][]，它们虽然都是有序的哈希表。但是，第一，它们的线程安全机制不同，TreeMap是非线程安全的，而ConcurrentSkipListMap是线程安全的。第二，ConcurrentSkipListMap是通过跳表实现的，而TreeMap是通过红黑树实现的。

# SkipList #

什么是SkipList？Skip List ，称之为跳表，它是一种可以替代平衡树的数据结构，其数据元素默认按照key值升序，天然有序。Skip list让已排序的数据分布在多层链表中，以0-1随机数决定一个数据的向上攀升与否，通过“空间来换取时间”的一个算法，在每个节点中增加了向前的指针，在插入、删除、查找时可以忽略一些不可能涉及到的结点，从而提高了效率。

我们先看一个简单的链表，如下：

![d90d2de5ca20d66f48d3539e233f0efb.png][]

如果我们需要查询9、21、30，则需要比较次数为3 + 6 + 8 = 17 次，那么有没有优化方案呢？有！我们将该链表中的某些元素提炼出来作为一个比较“索引”，如下：

![1932fb8cb49f047076aca5a1261d5e0a.png][]

我们先与这些索引进行比较来决定下一个元素是往右还是下走，由于存在“索引”的缘故，导致在检索的时候会大大减少比较的次数。当然元素不是很多，很难体现出优势，当元素足够多的时候，这种索引结构就会大显身手。

## SkipList的特性 ##

SkipList具备如下特性：

1.  由很多层结构组成，level是通过一定的概率随机产生的
2.  每一层都是一个有序的链表，默认是升序，也可以根据创建映射时所提供的Comparator进行排序，具体取决于使用的构造方法
3.  最底层(Level 1)的链表包含所有元素
4.  如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现
5.  每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素

我们将上图再做一些扩展就可以变成一个典型的SkipList结构了

![8863aa7099815014a817b6972bc761fb.png][]

## SkipList的查找 ##

SkipListd的查找算法较为简单，对于上面我们我们要查找元素21，其过程如下：

1.  比较3，大于3，往后找（9），
2.  比9大，继续往后找（25），但是比25小，则从9的下一层开始找（16）
3.  16的后面节点依然为25，则继续从16的下一层找
4.  找到21

![117743b0684574612f9cafb40b8f31ee.png][]

红色虚线代表路径。

## SkipList的插入 ##

SkipList的插入操作主要包括：

1.  查找合适的位置。这里需要明确一点就是在确认新节点要占据的层次K时，采用丢硬币的方式，完全随机。如果占据的层次K大于链表的层次，则重新申请新的层，否则插入指定层次
2.  申请新的节点
3.  调整指针

假定我们要插入的元素为23，经过查找可以确认她是位于25前，9、16、21后。当然需要考虑申请的层次K。

如果层次K > 3

需要申请新层次（Level 4）

![5ba3368edcf8fcb726d4a30e3f4499ff.png][]

如果层次 K = 2

直接在Level 2 层插入即可

![a087a404d07075a4afdc3e20ea9e4fc6.png][]

这里会涉及到以个算法：通过丢硬币决定层次K，该算法我们通过后面ConcurrentSkipListMap源码来分析。还有一个需要注意的地方就是，在K层插入元素后，需要确保所有小于K层的层次都应该出现新节点。

## SkipList的删除 ##

删除节点和插入节点思路基本一致：找到节点，删除节点，调整指针。

比如删除节点9，如下：

![4183aef75fa94f89c76f4fe2c6235b04.png][]

# ConcurrentSkipListMap #

通过上面我们知道SkipList采用空间换时间的算法，其插入和查找的效率O(logn)，其效率不低于红黑树，但是其原理和实现的复杂度要比红黑树简单多了。一般来说会操作链表List，就会对SkipList毫无压力。

转自：[https://juejin.cn/post/6844903958499033095][https_juejin.cn_post_6844903958499033095]

[TreeMap]: http://www.cnblogs.com/skywang12345/p/3310928.html
[d90d2de5ca20d66f48d3539e233f0efb.png]: /images/20210923/840b526d0a6442aaaa5a96633aed62f8.png
[1932fb8cb49f047076aca5a1261d5e0a.png]: /images/20210923/d11e60069d43411b9c8a9ae9c6feda39.png
[8863aa7099815014a817b6972bc761fb.png]: /images/20210923/d78ae54de5e4487d87504627d91dba3c.png
[117743b0684574612f9cafb40b8f31ee.png]: /images/20210923/90f6b509313d40c9b95a672cc90f2e28.png
[5ba3368edcf8fcb726d4a30e3f4499ff.png]: /images/20210923/982a77d91620460b9be16df47e3953ba.png
[a087a404d07075a4afdc3e20ea9e4fc6.png]: /images/20210923/e3dc9e35e9e34f40a82c95c852550328.png
[4183aef75fa94f89c76f4fe2c6235b04.png]: /images/20210923/7c0b3fd01a11412abe6dc17100cc87d6.png
[https_juejin.cn_post_6844903958499033095]: https://juejin.cn/post/6844903958499033095