线性数据结构之跳跃列表（Skip List）详解及其Java实现

[TOC]

#### 一、跳跃列表（Skip List）简介
列表（List）是最基本的数据结构之一。与数组（Array）类似，它们都是相同元素的集合。然后列表的查找效率并不理想，与树形结构（在前面提到了[平衡二叉树](https://www.datalearner.com/blog/1051540458496514)相关的数据结构如[AVL树](https://www.datalearner.com/blog/1051540468259136)和[红黑树](https://www.datalearner.com/blog/1051540540644626)等查找效率都很高，但是需要旋转或者变色的等操作保持自平衡。）相比，列表虽然简单，但是对元素的查找需要比对列表中的每个元素，查找速度较慢。为了兼顾列表的简单易用，并提高查找效率，William Pugh在1990年发表了一篇论文（[Skip lists: a probabilistic alternative to balanced trees](ftp://ftp.cs.umd.edu/pub/skipLists/skiplists.pdf)），提出了跳跃列表（Skip List）数据结构，以空间换时间的方式，构造了一个层次的列表为数据建立索引，以提高列表的查找效率。

具体来说，Skip List是允许在有序的元素序列内快速搜索（量化）的数据结构。 通过维持子序列的链接层次结构，可以实现快速搜索，每个连续的子序列跳过比前一个更少的元素（参见下图）。 搜索从最稀疏的子序列（就是从最上层）开始，直到找到两个连续的元素，一个较小，一个大于或等于搜索的元素。 通过链接层次结构，这两个元素链接到下一个最稀疏子序列的元素，其中继续搜索，直到最后我们在完整序列中搜索。 跳过的元素可以概率地或确定性地选择，前者更常见。

如下图所示，是一个常见的跳跃列表实现情况：

<center>![](https://i.imgur.com/nNjOtfa.png)

</center>

Skip List是按层构建的。底层是普通有序链表。每个较高层充当下面列表的“快速通道”，其中图层$i$中的元素以一定的固定概率$p$出现在图层$i + 1$中，（p的两个常用值是1/2和1/4）。平均而言，每个元素都出现在1/(1-p)的列表中，以及最高的元素（通常是特殊的元素）所有列表中的跳过列表前面的元素。Skip List包含$\log\_{1/p}n$个列表。注意，这里是说的构造的结果，不是构造过程。跳跃列表的构造过程见后面的插入操作。

搜索目标元素从顶部列表中的head元素开始，并水平前进，直到当前元素大于或等于目标。如果当前元素等于目标，则已找到它。如果当前元素大于目标，或者搜索到达链接列表的末尾，则在返回上一个元素并垂直下降到下一个下一个列表后重复该过程。每个链接列表中的预期步数最多为1/p，可以通过从目标向后追踪搜索路径来查看直到到达下一个更高列表中出现的元素或到达当前列表的开头。因此，搜索的总预期成本为：
```math
\frac{\log_{1/p}n}{p}
```

p是一个常量。通过选择p的不同值，可以将搜索成本与存储成本进行交易。

我们通过旋转可以发现跳跃列表与二叉查找树很相似，上图旋转后如下：

<center>![](https://i.imgur.com/DO031ek.png)

</center>

总结一下，跳跃列表的特性如下：
1. 构造跳跃列表的开始就要确定这个表有几层
2. 最下层一般称为第0层，是一个包含所有的元素的有序列表
3. 每一层都是个有序列表，但上层的节点数总是小于下层的节点数
4. 上层列表的每个元素都要在下层出现
5. 不同层之间相同的元素需要通过指针连接
6. 每一层都有个最小值和最大值
7. 在构造跳跃列表的时候，先确定待插入元素的层，然后要在当前层下的所有层新加节点并做连接操作
8. 跳跃表的搜索效率与自平衡二叉查找树一样，但是不需要通过自平衡操作维护，所以实现更加简单

#### 二、跳跃列表的搜索操作
在前面的叙述中，我们把跳跃列表旋转之后就可以使得跳跃列表像一个二叉搜索树，因此，跳跃列表的搜索和二叉查找树的搜索类似。一般最上面的层

以上图搜索30为例。

- 首先从最上面的一层的第一个节点开始，如果待搜索节点大于当前层的当前节点的右节点，那么，沿着这一层继续查找。
- 如果待搜索节点小于当前节点的右节点，则到下一层继续寻找。
- 到了第0层（即最后一层）如果当前节点的右边最近的节点等于待查找元素，则找到了，否则失败。

<center>![](https://i.imgur.com/H5KjvqC.png)

</center>

可以这么理解，上层的节点是下层节点的索引，从最上面节点开始搜索，找到待查节点所属的区域，然后向下层移动，一直到最底层即可。

#### 三、跳跃列表的插入操作
之前也说过，跳跃列表是一个层次结构的有序列表。最底层（第0层）包含了所有的元素，如果某个元素在某一层出现，那么比该层低的所有层中都应当包含这个元素。每个节点要有一个指针，指向下一层包含相同值的节点。所以插入操作要主要是决定是待插入元素在第几层，然后把元素添加到这一层中，并在下面的层里也做相应的操作，并将这些节点连接起来。

一般来说最开始要确定一个Skip List的最大层数，在插入一个节点的时候，首先要以一定的概率确定这个节点在哪一层。确定好之后，也要把这个节点在所有的下层加上，并更新指针即可。删除也是类似的操作。

#### 四、跳跃列表的Java实现

线性数据结构之跳跃列表（Skip List）详解及其Java实现

相关博客

最热博客