SkipList跳表原理

朱雀 2022-02-23 11:42 260阅读 0赞

## **为什么选择跳表** ##

目前经常使用的平衡数据结构有：B树，红黑树，AVL树，Splay Tree, Treep等。想象一下，给你一张草稿纸，一只笔，一个编辑器，你能立即实现一颗红黑树，或者AVL树，出来吗？ 很难吧，这需要时间，要考虑很多细节，要参考一堆算法与数据结构之类的树，还要参考网上的代码，相当麻烦。用跳表吧，跳表是一种随机化的数据结构，目前开源软件 Redis 和 LevelDB 都有用到它，它的效率和红黑树以及 AVL 树不相上下，但跳表的原理相当简单，只要你能熟练操作链表，就能轻松实现一个 SkipList。

## **有序表的搜索** ##

考虑一个有序表：

![20190408091349981.png][]

从该有序表中搜索元素 < 23, 43, 59 > ，需要比较的次数分别为 < 2, 4, 6 >，总共比较的次数为 2 + 4 + 6 = 12 次。有没有优化的算法吗?  链表是有序的，但不能使用二分查找。类似二叉搜索树，我们把一些节点提取出来，作为索引。得到如下结构：

![20190408091449281.png][]

这里我们把 < 14, 34, 50, 72 > 提取出来作为一级索引，这样搜索的时候就可以减少比较次数了。我们还可以再从一级索引提取一些元素出来，作为二级索引，变成如下结构：

![20190408091518865.png][]

这里元素不多，体现不出优势，如果元素足够多，这种索引结构就能体现出优势来了。

这基本上就是跳表的核心思想，其实也是一种通过“空间来换取时间”的一个算法，通过在每个节点中增加了向前的指针，从而提升查找的效率。

## **跳表** ##

下面的结构是就是跳表：

其中 -1 表示 INT\_MIN， 链表的最小值，1 表示 INT\_MAX，链表的最大值。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70][]

跳表具有如下性质：

*  (1) 由很多层结构组成
 *  (2) 每一层都是一个有序的链表
 *  (3) 最底层(Level 1)的链表包含所有元素
 *  (4) 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。
 *  (5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

## **跳表的搜索** ##

![20190408091715493.png][]

例子：查找元素 117

*  (1) 比较 21， 比 21 大，往后面找
 *  (2) 比较 37,   比 37大，比链表最大值小，从 37 的下面一层开始找
 *  (3) 比较 71,  比 71 大，比链表最大值小，从 71 的下面一层开始找
 *  (4) 比较 85， 比 85 大，从后面找
 *  (5) 比较 117， 等于 117， 找到了节点。

## **跳表的插入** ##

先确定该元素要占据的层数 K（采用丢硬币的方式，这完全是随机的）

然后在 Level 1 ... Level K 各个层的链表都插入元素。

例子：插入 119， K = 2

![2019040809185032.png][]

如果 K 大于链表的层数，则要添加新的层。

例子：插入 119， K = 4

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 1][]

## **丢硬币决定** **K** ##

插入元素的时候，**元素所占有的层数完全是随机的**，通过一下随机算法产生：相当与做一次丢硬币的实验，如果遇到正面，继续丢，遇到反面，则停止，用实验中丢硬币的次数 K 作为元素占有的层数。显然随机变量 K 满足参数为 p = 1/2 的几何分布，K 的期望值 E\[K\] = 1/p = 2. 就是说，各个元素的层数，期望值是 2 层。

## **跳表的空间复杂度分析** ##

根据上面的分析，每个元素的期望高度为 2， 一个大小为 n 的跳表，其节点数目的

期望值是 2n。

## **跳表的删除** ##

在各个层中找到包含 x 的节点，使用标准的 delete from list 方法删除该节点。

例子：删除 71

![20190408092223937.png][]

# **ConcurrentSkipListMap** #

我们知道 HashMap 是一种键值对形式的数据存储容器，但是它有一个缺点是，元素内部**无序**。由于它内部根据键的 hash 值取模表容量来得到元素的存储位置，所以整体上说 HashMap 是无序的一种容器。当然，jdk 中也为我们提供了基于红黑树的存储的 **TreeMap 容器**，它的内部元素是有序的，但是由于它内部通过红黑结点的各种变换来维持二叉搜索树的平衡，**相对复杂**，并且在并发环境下碍于 rebalance 操作，性能会受到一定的影响。

ConcurrentSkipListMap提供了一种线程安全的并发访问的排序映射表。内部是SkipList（跳表）结构实现，在理论上能够在O(log(n))时间内完成查找、插入、删除操作。调用ConcurrentSkipListMap的size时，由于多个线程可以同时对映射表进行操作，所以映射表需要遍历整个链表才能返回元素个数，这个操作是个O(log(n))的操作。

参考ConcurrentSkipListMap：[https://blog.csdn.net/qq\_35326718/article/details/78870658][https_blog.csdn.net_qq_35326718_article_details_78870658]

[20190408091349981.png]: /images/20220223/65823e56be5847dfbc9408d0f94f3798.png
[20190408091449281.png]: /images/20220223/7cd1376eb3fe4511978a14168e6ff3ae.png
[20190408091518865.png]: /images/20220223/6f7ed78f7d7b4c5d824cc6a2e5974ff0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70]: /images/20220223/351b9e0523a34399a5464daa0a5bc373.png
[20190408091715493.png]: /images/20220223/981bd59405ba404b8e7fbe25eda88a2f.png
[2019040809185032.png]: /images/20220223/511921017f9f4fbe8d51a245d03cf533.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0ppblhZYW4_size_16_color_FFFFFF_t_70 1]: /images/20220223/147c0dcfee984d04a23d513855081eb2.png
[20190408092223937.png]: /images/20220223/6ff6c8702dc84dc3b1533d513b0f5bf6.png
[https_blog.csdn.net_qq_35326718_article_details_78870658]: https://blog.csdn.net/qq_35326718/article/details/78870658