数据结构之跳表

左手的ㄟ右手 2022-10-07 05:46 117阅读 0赞

# 跳表 #

**本文参考资料为极客时间专栏[数据结构与算法之美][Link 1]**

### 文章目录 ###

*  跳表
 *   *  一、什么是跳表
     *  二、跳表的基本特点
     *  三、高效的动态插入和删除
     *   *  1. 插入
         *  2. 删除
     *  四、索引动态更新
     *  五、为什么Redis要用跳表来实现有序集合？
     *  六、总结

## 一、什么是跳表 ##

对于一个单链表来讲，即便链表中存储的数据是有序的，如果想要在其中查找某个数据，也只能从头到尾遍历链表。这样查找效率就会很低，时间复杂度会很高，是 O(n)，如下图所示：

![image-20210612195552784][]

如果每两个结点提取一个结点到上一级，对链表建立一级“索引”，查找起来就会更快一些，把抽出来的那一级叫做索引或索引层。如下图所示（图中的 down 表示 down 指针，指向下一级结点）：

![image-20210612195729677][]

如果现在要查找某个结点，比如 16。可以先在索引层遍历，当遍历到索引层中值为 13 的结点时，发现下一个结点是 17，那要查找的结点 16 肯定就在这两个结点之间。然后通过索引层结点的 down 指针，下降到原始链表这一层，继续遍历。这个时候，只需要再遍历 2 个结点，就可以找到值等于 16 的这个结点了。这样，原来如果要查找 16，需要遍历 10 个结点，现在只需要遍历 7 个结点，可以发现，效率有所提高。

继续使用这个例子，在第一级索引的基础之上，继续每两个结点抽出一个结点到第二级索引。现在再来查找 16，只需要遍历 6 个结点，需要遍历的结点数量又减少了，效率更高了，如下图所示：

![image-20210612200000350][]

从这个例子可以看出，加了索引之后，查找一个结点的效率提高了很多。

上述讲的这种链表加多级索引的结构，就是跳表，是一种空间换时间的数据结构。

## 二、跳表的基本特点 ##

如果链表有n个节点：

*  第 k 级索引结点的个数是 n/(2^k)
 *  跳表的高度是log2n（以2为底）
    
     *  假设索引有 k 级，最高级的索引有 2 个结点。通过上面的公式，可以得到 n/(2^k)=2，从而求得 h=log2n-1。如果包含原始链表这一层，整个跳表的高度就是 log2n。
 *  时间复杂度是O(logn)
 *  空间复杂度是n/2+n/4+n/8…+8+4+2=n-2，也就是O(n)
    
     *  在实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了

## 三、高效的动态插入和删除 ##

### 1. 插入 ###

对于单链表来说，插入一个节点的时候，只要找到插入位置，插入操作的时间复杂度就为 O(1)，所以时间主要耗费在了查找的过程。

对于跳表，查找的时间复杂度为O(logn)，所以跳表插入节点的时间复杂度是 O(logn)

### 2. 删除 ###

对于跳表来说，删除节点的时间复杂度也是O(logn)。

如果这个结点在索引中也有出现，除了要删除原始链表中的结点，还要删除索引中的。

因为单链表中的删除操作需要拿到要删除结点的前驱结点，然后通过指针操作完成删除。所以在查找要删除的结点的时候，一定要获取前驱结点。当然，如果用的是双向链表，就不需要考虑这个问题了。

## 四、索引动态更新 ##

当不停的往跳表中插入数据时，如果不更新索引，就有可能出现某 2 个索引结点之间数据非常多的情况。极端情况下，跳表还会退化成单链表，如下图所示：

![image-20210614175117852][]

作为一种动态数据结构，需要通过某种手段来维护索引与原始链表大小之间的平衡，也就是说，如果链表中结点多了，索引结点就相应地增加一些，跳表是通过随机函数来维护平衡性的。

当向跳表中插入数据的时候，可以选择同时将这个数据插入到部分索引层中，通过一个随机函数，来决定将这个结点插入到哪些索引中，比如随机函数生成了值 K，那就将这个结点添加到从第一级到第 K 级这 K 级个索引中，如下图所示：

![image-20210614180935706][]

## 五、为什么Redis要用跳表来实现有序集合？ ##

Redis 中的有序集合支持的核心操作主要有下面这几个：

*  插入一个数据
 *  删除一个数据
 *  查找一个数据
 *  按照区间查找数据（比如查找值在 \[100, 356\] 之间的数据）
 *  迭代输出有序序列

其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表是一样的。但是，按照区间来查找数据这个操作，红黑树的效率没有跳表高。

对于按照区间查找数据这个操作，跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了，这样做非常高效。

## 六、总结 ##

*  跳表使用空间换时间的设计思路，通过构建多级索引来提高查询效率，实现了基于链表的 “二分查找”（上面每一层链表的节点个数是下面一层的节点个数的一半）。跳表是一种动态数据结构，支持快速地插入、删除、查找操作，时间复杂度都是 O(logn)
 *  跳表的空间复杂度是 O(n)

[Link 1]: https://time.geekbang.org/column/intro/126
[image-20210612195552784]: /images/20221005/361b07cf78f748ea961c9d2a7b09133c.png
[image-20210612195729677]: /images/20221005/91b05d00dc2a421dbfdadc6437d772fc.png
[image-20210612200000350]: /images/20221005/a68440b1787a47949dbf16c9d1c769d1.png
[image-20210614175117852]: /images/20221005/4836693a7eea435089e813a6b77d26cc.png
[image-20210614180935706]: /images/20221005/51821642a1bf4d32b67d9b7b2dacf2bb.png