目录

跳表

转载:理论整理总结—跳表

基本介绍

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

https://gitee.com/lienhui68/picStore/raw/master/null/20200808185819.png

那怎么来提⾼查找效率呢?如果像图中那样,对链表建⽴⼀级 “索引”,查找起来是不是就会更快⼀些呢?每两个结点提取⼀个结点到上⼀级,我们把抽出来的那⼀级叫作索引或索引层。

https://gitee.com/lienhui68/picStore/raw/master/null/20200808185852.png

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

跟前⾯建⽴第⼀级索引的⽅式相似,我们在第⼀级索引的基础之上,每两个结点就抽出⼀个结点到第⼆级索引。现在我们再来查找 16,只需要遍历 6 个结点了,需要遍历的结点数量⼜减少了。

https://gitee.com/lienhui68/picStore/raw/master/null/20200808185959.png

我举的例⼦数据量不⼤,所以即便加了两级索引,查找效率的提升也并不明显。为了让你能真切地感受索引提升查询效率。我画了⼀个包含 64 个结点的链表,按照前⾯讲的这种思路,建⽴了五级索引。

https://gitee.com/lienhui68/picStore/raw/master/null/20200808190034.png

这种链表加多级索引的结构,就是跳表

时间复杂度

我们知道,在⼀个单链表中查询某个数据的时间复杂度是 O (n)。那在⼀个具有多级索引的跳表中,查询某个数据的时间复杂度是多少呢?

按照我们刚才讲的,每两个结点会抽出⼀个结点作为上⼀级索引的结点,那第⼀级索引的结点个数⼤约就是 n/2,第⼆级索引的结点个数⼤约就是 n/4,第三级索引的结点个数⼤约就是 n/8,依次类推,也就是说,第 k 级索引的结点个数是第 k-1 级索引的结点个数的 1/2,那第 k 级索引结点的个数就是 $n/2^k$。

假设索引有 h 级,最⾼级的索引有 2 个结点。通过上⾯的公式,我们可以得到 $n/2^h$=2,从⽽求得 $h=log_2n-1$。如果包含原始链表这⼀层,整个跳表的⾼度就是 $log_2n$。我们在跳表中查询某个数据的时候,如果每⼀层都要遍历 m 个结点,那在跳表中查询⼀个数据的时间复杂度就是 O (m*logn)。

假设我们要查找的数据是 x,在第 k 级索引中,我们遍历到 y 结点之后,发现 x ⼤于 y,⼩于后⾯的结点 z,所以我们通过 y 的 down 指针,从第 k 级索引下降到第 k-1 级索引。在第 k-1 级索引中,y 和 z 之间只有 3 个结点(包含 y 和 z),所以,我们在 K-1 级索引中最多只需要遍历 3 个结点,依次类推,每⼀级索引都最多只需要遍历 3 个结点。

https://gitee.com/lienhui68/picStore/raw/master/null/20200808190454.png

通过上⾯的分析,我们得到 m=3,所以在跳表中查询任意数据的时间复杂度就是 O (logn)。这个查找的时间复杂度跟⼆分查找是⼀样的。换句话说,我们其实是基于单链表实现了⼆分查找。

空间复杂度

假设原始链表⼤⼩为 n,那第⼀级索引⼤约有 n/2 个结点,第⼆级索引⼤约有 n/4 个结点,以此类推,每上升⼀级就减少⼀半,直到剩下 2 个结点。如果我们把每层索引的结点数写出来,就是⼀个等⽐数列。

https://gitee.com/lienhui68/picStore/raw/master/null/20200808190530.png

这⼏级索引的结点总和就是 n/2+n/4+n/8…+8+4+2=n-2。所以,跳表的空间复杂度是 O (n)。

高效的动态插入和删除

跳表这个动态数据结构,不仅⽀持查找操作,还⽀持动态的插⼊、删除操作,⽽且插⼊、删除操作的时间复杂度也是 O (logn)。

在单链表中,⼀旦定位好要插⼊的位置,插⼊结点的时间复杂度是很低的,就是 O (1)。但是,这⾥为了保证原始链表中数据的有序性,我们需要先找到要插⼊的位置,这个查找操作就会⽐较耗时。 对于纯粹的单链表,需要遍历每个结点,来找到插⼊的位置。但是,对于跳表来说,我们讲过查找某个结点的的时间复杂度是 O (logn),所以这⾥查找某个数据应该插⼊的位置,⽅法也是类似的,时间复杂度也是 O (logn)。

https://gitee.com/lienhui68/picStore/raw/master/null/20200808190634.png

Redis中的有序集合

Redis 中的有序集合是通过跳表来实现的,严格点讲,其实还⽤到了散列表。

Redis 中的有序集合⽀持的核⼼操作主要有下⾯这⼏个:

插⼊⼀个数据;删除⼀个数据;查找⼀个数据;按照区间查找数据(⽐如查找值在 [100, 356] 之间的数据);迭代输出有序序列。

其中,插⼊、删除、查找以及迭代输出有序序列这⼏个操作,红⿊树也可以完成,时间复杂度跟跳表是⼀样的。但是,按照区间来查找数据这个操作,红⿊树的效率没有跳表⾼。 对于按照区间查找数据这个操作,跳表可以做到 O (logn) 的时间复杂度定位区间的起点,然后在原始链表中顺序往后遍历就可以了。

当然,Redis 之所以⽤跳表来实现有序集合,还有其他原因,⽐如,跳表更容易代码实现。虽然跳表的实现也不简单,但⽐起红⿊树来说还是好懂、好写多了,⽽简单就意味着可读性好,不容易出错。还有,跳表更加灵活,它可以通过改变索引构建策略,有效平衡执⾏效率和内存消耗。