【数据结构与算法】跳表

柔光的暖阳◎ 2022-11-29 00:48 216阅读 0赞

### 一、什么是跳表？ ###

为一个值有序的链表建立多级索引，比如每2个节点提取一个节点到上一级，我们把抽出来的那一级叫做索引或索引层。如下图所示，其中down表示down指针，指向下一级节点。以此类推，对于节点数为n的链表，大约可以建立log2n-1级索引。像这种为链表建立多级索引的数据结构就称为跳表。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]

### 二、跳表的时间复杂度？ ###

1.计算跳表的高度  
如果链表有n个节点，每2个节点抽取抽出一个节点作为上一级索引的节点，那第1级索引的节点个数大约是n/2，第2级索引的节点个数大约是n/4，依次类推，第k级索引的节点个数就是n/(2k)。假设索引有h级别，最高级的索引有2个节点，则有n/(2^h)=2，得出h=log2n-1，包含原始链表这一层，整个跳表的高度就是log2n。  
2.计算跳表的时间复杂度  
假设我们在跳表中查询某个数据的时候，如果每一层都遍历m个节点，那在跳表中查询一个数据的时间复杂度就是O(m\*logn)。那这个m是多少呢？如下图所示，假设我们要查找的数据是x，在第k级索引中，我们遍历到y节点之后，发现x大于y，小于后面的节点z，所以我们通过y的down指针，从第k级下降到第k-1级索引。在第k-1级索引中，y和z之间只有3个节点（包含y和z），所以，我们在k-1级索引中最多只需要遍历3个节点，以此类推，每一级索引都最多只需要遍历3个节点。所以m=3(与间距有关)。因此在跳表中查询某个数据的时间复杂度就是**O(logn)**。![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]

### 三、跳表的空间复杂度及如何优化？ ###

1.计算索引的节点总数  
如果链表有n个节点，每2个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为：n/2，n/4，n/8，…，8，4，2，等比数列求和n-1，所以跳表的**空间复杂度为O(n)。**  
2.如何优化时间复杂度  
如果链表有n个节点，每3或5个节点抽取抽出一个节点作为上一级索引的节点，那每一级索引的节点数分别为（以3为例）：n/3，n/9，n/27，…，27，9，3，1，等比数列求和n/2，所以跳表的空间复杂度为O(n)，和每2个节点抽取一次相比，时间复杂度要低不少呢。

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

跳表本质上就是链表，所以仅插作，插入和删除操时间复杂度就为O(1)，但在实际情况中，要插入或删除某个节点，需要先查找到指定位置，而这个查找操作比较费时，但在跳表中这个查找操作的时间复杂度是**O(logn)**，所以，跳表的插入和删除操作的是时间复杂度也是O(logn)。

### 五、跳表索引动态更新？ ###

当往跳表中插入数据的时候，可以选择同时将这个数据插入到部分索引层中，那么如何选择这个索引层呢？可以通过随机函数来决定将这个节点插入到哪几级索引中，比如随机函数生成了值K，那就可以把这个节点添加到第1级到第K级索引中。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]

### 六、思考 ###

**为什么 Redis 要用跳表来实现有序集合，而不是红黑树？**

1.  Redis 中的有序集合支持的核心操作主要有下面这几个：插入一个数据；删除一个数据；查找一个数据；按照区间查找数据（比如查找值在\[100, 356\]之间的数据）；迭代输出有序序列。  
    其中\*\*，插入、删除、查找以及迭代输出有序序列**这几个操作，红黑树也可以完成，时间复杂度跟跳表是**一样\*\*的。但是，**按照区间来查找数据**这个操作，\*\*红黑树的效率没有跳表高。\*\*对于按照区间查找数据这个操作，跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。
2.  \*\*跳表更容易代码实现。\*\*虽然跳表的实现也不简单，但比起红黑树来说还是好懂、好写多了，而简单就意味着可读性好，不容易出错。
3.  **跳表更加灵活**，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗。

PS：业务开发 红黑树可以直接用 跳表需要自己实现

1.每次插入数据的时候随机产生的level:决定了新节点的层数；  
2.数组update的作用：用以存储新节点所有层数上，各自的前一个节点的信息；  
3.节点内的forwards数组：用以存储该节点所有层的下一个节点的信息；  
4.当所有节点的最大层级变量maxlevel=1的时候，跳表退化成一个普通链表  
[调表实现链接][Link 1]

[笔记整理来源： 王争 数据结构与算法之美][Link 2]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center]: /images/20221124/a2f35793b75644449b34949739b9fc9f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221124/6bfcea8a15df4e13b57d7478a15b2d9b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2RhZG9uZ3d1ZGk_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221124/6c67f74f4f3c4ee9a51ae906f6f7d361.png
[Link 1]: https://github.com/wangzheng0822/algo/blob/master/java/17_skiplist/SkipList2.java
[Link 2]: https://s1.ax1x.com/2020/08/03/aUh2TS.png