一、概述

跳表是一种在各个方面都比较优秀的动态数据结构，可支持快速的插入、删除、查找操作，甚至可以替代红黑树(Red-black Tree) 应用：Redis 中的有序集合(sorted set)是用跳表实现的。

基本思想

结合 链表 和 二分法 的特点，将链表进行加工，创造一个二者的结合体：

链表从头节点到尾节点是有序的可以进行跳跃查找（形如二分法）

例如：我们建立两层索引(第三层和第二层)，若要查找某个结点，比如d。可以先在第三层进行遍历，当遍历的时候，发现结点d在结点a和节点e之间，则通过第三层结点a的指针，下降到第二层，继续遍历==》结点c和节点e之间==》结点c的指针到第一层 ==》继续遍历，找到结点d

当链表的长度 n 比较大时，比如 1000、10000 的时候，在构建索引之后，查找效率的提升就会非常明显。

二、分析

1、时间复杂度分析

如果链表里有 n 个结点，会有多少级索引呢？

每两个结点会抽取一个作为上一级索引的结点，所以第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2，那第 k级索引结点的个数就是 n/(2k)。 ==》 假设索引有 h 级，最高级的索引有 2 个结点。通过上面的公式，我们可以得到 n/(2h)=2，从而求得 h=log₂n-1。如果包含原始链表这一层，整个跳表的高度就是log₂n。 ==》 在跳表中查询某个数据的时候，如果每一层都要遍历 m 个结点，那在跳表中查询一个数据的时间复杂度就是 O(m*logn)。其中 m=3（二分思想） ==》时间复杂度：O(logn)

2、空间复杂度分析

原始链表大小为n，每2个结点抽1个，每层索引的结点数为：

n/2, n/4, n/8, ... , 8 , 4 , 2

结点总和为 n/2 + n/4 + n/8 + … + 8 + 4 + 2 = n - 2 ==》空间复杂度为O(n)

3、变形

每两个结点抽一个结点到上级索引 ==》每三个结点或五个结点，抽一个结点到上级索引

则，第一级索引需要大约 n/3 个结点，第二级索引需要大约 n/9 个结点。每往上一级，索引结点个数都除以 3。通过等比数列求和公式，总的索引结点大约就是 n/3+n/9+… +9+3+1=n/2。 ==》虽然空间复杂度仍为O(n)，但是减少了一半索引结点存储空间

但是实际应用中，不必太在意索引占用的额外空间。

三、操作

1、动态插入和删除

插入、删除操作的时间复杂度为 O(logn)

为了保证原始链表中数据的有序性，需要先找到要插入的位置（时间复杂度为O(logn)），然后执行插入操作。

删除操作：若该结点在索引中也有出现，除了要删除原始链表中的结点外，还要删除索引中的。需要获得要删除结点的前驱结点。

2、索引动态更新

当不停地插入向跳表中插入数据时，如果不更新索引，可能导致某两个索引结点之间的数据非常多的情况 ==》退化为单链表

解决方法：通过随机函数来维护索引与原始链表大小之间的 “平衡性”。也就是说，如果链表中结点多了，索引结点就相应地增加一些，避免复杂度退化，以及查找、插入、删除操作性能下降。

通过随机函数来决定该结点插入到哪一层索引中，比如随机函数生成了 K，则将该结点添加到第一级到第K级这K级索引中。

四、应用

Redis 使用跳表实现有序集合（其实也包括散列表，此处先忽略掉），而非红黑树？

Redis中有序结合支持的核心操作主要是：

插入一个数据；删除一个数据；查找一个数据；按照区间查找数据（eg: 查找值在[155, 296]区间内）==》时间复杂度：O(logn)迭代输出有序序列

跳表更加灵活，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗。