数据结构：跳跃表

妖狐艹你老母 2022-09-08 12:54 126阅读 0赞

### 跳跃表 ###

*   *  为什么跳跃表？
     *  有序表的搜索
     *  跳表
     *   *  跳表的搜索
         *  跳表的插入
         *  K值的大小
     *  跳表实现

前一段时间在看`《Redis的设计与实现》`，发现`Redis`中的`ZSet`数据类型就是采用跳跃表实现的（zSkipList）。后来看到`levelDB`中也使用了跳跃表。

另外Skip List是在有序链表的基础上进行了扩展，解决了有序链表结构查找特定值困难的问题，查找特定值的`时间复杂度O(logn)`，他是一种可以代替平衡树的数据结构。

## 为什么跳跃表？ ##

目前经常使用的平衡数据结构有：B树，红黑树，AVL树，Splay Tree, Treep等。

但是上面这些数据结构大部分实现起来非常复杂，维护也不好维护。

比如：

*  `范围查找`的时候，平衡树比skiplist操作要复杂。在平衡树上，我们找到指定范围的小值之后，还需要以`中序遍历的顺序继续寻找`其它不超过大值的节点。而在skiplist上进行范围查找就非常简单，只需要在找到小值之后，对第1层链表进行若干步的遍历就可以实现。
 *  插入的时候：平衡树的插入和删除操作可能引发子树的调整，逻辑复杂。而skiplist的插入和删除只需要修改相邻节点的指针，操作简单又快速。

## 有序表的搜索 ##

考虑一个有序表：

![在这里插入图片描述][451bf861506c43febd411e20ad27e9e6.png]

从该有序表中搜索元素 < 23, 43, 59 > ，需要比较的次数分别为 < 2, 4, 6 >，总共比较的次数

为 2 + 4 + 6 = 12 次。有没有优化的算法吗? 链表是有序的，但不能使用二分查找。类似二叉

搜索树，我们把一些节点提取出来，作为索引。得到如下结构：

![img][]

这里我们把 < 14, 34, 50, 72 > 提取出来作为一级索引，这样搜索的时候就可以减少比较次数了。

我们还可以再从一级索引提取一些元素出来，作为二级索引，变成如下结构：

![img][img 1]

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

## 跳表 ##

下面的结构是就是跳表：

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

![img][img 2]

跳表具有如下性质：

(1) 由很多层结构组成

(2) 每一层都是一个有序的链表

(3) 最底层(Level 1)的链表包含所有元素

(4) 如果一个元素出现在 Level i 的链表中，则它在 Level i 之下的链表也都会出现。

(5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

### 跳表的搜索 ###

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA6JKL6JKL5Y-I6YeN5ZCN_size_23_color_FFFFFF_t_70_g_se_x_16]  
例子：查找元素 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  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA6JKL6JKL5Y-I6YeN5ZCN_size_23_color_FFFFFF_t_70_g_se_x_16 1]

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

例子：插入 119， K = 4

![img][img 3]

### K值的大小 ###

通过跳表的查询可以知道，除了最底层的链表保存了所有的节点，其他层，相当于索引功能。所以如何生成K值，对于查找的效率还是有很大的影响的。所以在实现获取K的方法上，需要多花一点心思。

## 跳表实现 ##

等有空了会用Java实现一个跳跃表，代更。。。。。。

[451bf861506c43febd411e20ad27e9e6.png]: /images/20220829/8e95e0d3fcfe49ea9979404280040a1b.png
[img]: /images/20220829/5883604f0cae428dbf63ef7dc3acaca9.png
[img 1]: /images/20220829/422e4d5affb8471da35624067f9caeeb.png
[img 2]: /images/20220829/671ec07838db456e970f60bc230e9429.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA6JKL6JKL5Y-I6YeN5ZCN_size_23_color_FFFFFF_t_70_g_se_x_16]: /images/20220829/00e4a53f82684a3aae92eb4a95727e90.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_Q1NETiBA6JKL6JKL5Y-I6YeN5ZCN_size_23_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220829/b9bb3ecd17b1426b875d1382bc768987.png
[img 3]: /images/20220829/17888cffc7d346cf873575234831916c.png