数据结构：跳表

本文主要总结下自己学习跳表时的一些笔记，主要包含跳表的由来、时空复杂度、增删改查和具体应用四个方面。

二分查找的数据结构是数组，利用数组随机访问查找的时间复杂度是 O(logn)。如果数据结构是链表，可以达到这样的速度吗？答案是可以的，只是需要对链表进行改造，改造之后的结构就是跳表（又名跳跃表），是一种动态数据结构，可以支持快速的插入、删除、查找、按范围查找，功能类似于红黑树，Redis 中的有序集合使用的就是跳表（后文会说）。

从图中可以看到， 跳跃表主要由以下部分构成：

• 表头（head）：负责维护跳表的节点指针
• 跳表节点：保存着元素值，以及多个层。
• 层：保存着指向其它元素的指针。高层的指针越过的元七墨博客素数量大于等于低层的指针，为了提高查找的效率，程序总是从高层先开始访问，然后随着元素值范围的缩小，慢慢降低层次。
• 表尾：全部由 NULL 组成，表示跳表的末尾。

其实，上面的介绍一般会在算法相关的课程中引入，不过跳表真正是由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出， 跳表以有序的方式在层次化的链表中保存元素， 效率和平衡树媲美 -> 查找、删除、添加等操作都可以在对数期望时间下完成， 并且比起平衡树来说， 跳表的实现要简单直观得多。

跳表（skiplist）是对链表这种数据结构进行了升维操作，由原来的一维升级成二维，这样一来，占用的空间也变多了，这就是所谓的空间换时间的操作。

• 时间复杂度

我们知道单链表查询的时间复杂度为 O(n)，而插入、删除操作需要先找到对应的位置，所以插入、删除的时间复杂度也是 O(n)。

那么，跳表的时间复杂度是多少呢？

如果按照标准的跳表（每两个元素向上提取一个元素）来看的话，每一级索引减少 k/2 个元素（k 为其下面一级索引的个数），那么整个跳表的高度就是 logn。学习过平衡二叉树的同学都知道，它的时间复杂度与树的高度成正比，即 O(logn)。所以，跳表的时间复杂度也是 O(logn)。（这里不一步步推倒了，只要记住，查询时每次减少一半的元素的时间复杂度都是O(logn)，如二叉树的查找、二分法查找、归并排序、快速排序）

• 空间复杂度

还是以标准的跳表来分析，每两个元素向上提取一个元素，那么，最后额外需要的空间就是：

n/言七墨2 + (n/2)^2 + (n/2)^3 + … + 8 + 4 + 2 = n – 2

所以，跳表的空间复杂度是 O(n)。

• 查找元素

跳表允许快速查询一个有序连续元素的数据链表，它的平均查找和插入时间复杂度都是 O(logn)，优于普通队列的 O(n)。快速查询是通过维护一个多层次的链表，且上层链表中的元素是下层链表元素的子集。一开始时，算法在最稀疏的层次进行搜索，直至需要查找的元素在该层两个相邻的元素中间，这时，算法将跳转到下一个层次，重复刚才的搜索，直到找到需要查找的元素为止。跳过元素的方法可以是随机性选择或确定性选择，其中前者更为常见。

• 插入或 更新元素

由于跳表数据结构整体上是有序的，所以在插入时，需要首先查找到合适的位置，然后就是修改指针（和链表中操作类似），然后更新跳表的 level 变量。（更新同理，先找到要更新的元素，更新元素内容，并维护被更新节点的指针域和 level 变量）

• 删除元素

和插入是相同的，首先需要查找待删除的节点，如果找到了该节点的话，那么只需要更新指针域和 level 变量。

首先来对比下跳表和红黑树：

跳表会经常被用来跟平衡树，尤其是红黑树来比较，这是因为跳表和红黑树能做的事几乎相同。

• 跳表比红黑树更容易实七墨博客现
• 跳表占用的存储空间比红黑树大，但也大不了多少
• 查询效率而言，红黑树更稳定，但绝大多数情况下区别不大
• 跳表数据存放是紧凑的，也就是顺序递增的，这样就非常适合范围查找，红黑树的范围查找就不怎么样了

像 Redis 中的 ZSet 数据结构是用跳表来实现的，而 JDK 中的 TreeMap 使用红黑树来实现的。

好了，主要说下跳表的具体应用：

Redis 的 ZSet 结构同时包含一个字典和一个跳表，字典保存着从 member 到 score 的映射，跳表将指向有序集的score值和member域的指针作为元素， 并以score值为索引， 对有序集元素进行排序，这两种结构通过指针共享相同元素的 member 和 score，不会浪费额外内存。

举个例子， 以下代码创建了一个带有 3 个元素的有序集：

redis> ZADD s 6 x 10 y 15 z
(integer) 3
redis> ZRANGE s 0 -1 WITHSCORES
1) "x"
2) "6"
3) "y"
4) "10"
5) "z"
6) "15"

在底层实现中， Redis 为x、y和z三个member分别创建了三个字符串， 值分别为doubl言七墨e类型的6、10和15， 然后用跳表将这些指针有序地保存起来， 形成这样一个跳跃表：

在上图中我们直接将member和score值包含在表节点中， 但是在实际的定义中， 因为跳表要和字典分享member和score值， 所以跳跃表只保存指向member和score的指针。

• https://cyningsun.github.io/06-18-2018/skiplist.html
• https://redisbook.readthedocs.io/en/latest/internal-datastruct/skiplist.html
• https://blog.51cto.com言七墨/14267003/2377507