转自 公众号 【彤哥说源码】
1 前言
何为跳表？
跳表是一个随机化的数据结构，实际上就是一种可以进行二分查找的有序列表。跳表在原来的有序列表上面增加了多级索引，通过索引来实现快速查找。
跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。
2 跳表详解
2.1 有序列表
在上面的有序列表中，查找3,7等元素，只能从头开始遍历链表，直到查找到元素为止。
链表是有序的，但是不能使用二分查找（数组是可以实现二分查找的），那么如何实现有序列表的二分查找？
——答案是肯定的，跳表。
2.2 跳表的演进
将一些节点从有序链表中提取出来，缓存一级索引，就组成了下面的结构：
如果现在查找元素17是怎样的过程呢？
只要从一级索引往后遍历即可，只需要经过1、6、15、17这几个元素就可以找到17了。
那么，如何查找11这个元素呢？
从一级索引的1开始，向右到6，再向右发现是15，比11大，此路不通，回退，从6往下走，再从下面的6往右走，到7，再到11。
同样地，一级索引也可以往上再提取一层，组成二级索引，如下：
这时候我们再查找17这个元素呢？
只需要经过6、15、17这几个元素就可以找到17了。
这基本上就是跳表的核心思想了，其实这也是一个“空间换时间”的算法，通过向上提取索引增加了查找的效率。
2.3 跳表的插入
如何向跳表中插入元素呢？
比如，要向上面这个跳表添加一个元素8。
首先，随机选择该元素8要占据的索引层数，如果level=2，找到元素8在这两层的前置节点，
比如元素8在第一层的前置节点就是7，在第二层的前置节点就是6，接着就是链表的插入元素操作，比较简单。
2.4 跳表的删除
如何删除元素呢？
首先，找到各层中包含元素x的节点，然后，使用标准的链表删除元素的方法删除就可以。
比如删除17这个元素，找到元素17的前置节点为15，将所有15的next节点指向null即可。
3 标准化的跳表
举的例子是完全随机的跳表，那么，如果我们每两个元素提取一个元素作为上一级的索引会怎么样呢？
这种结构特别像平衡二叉树，如下
可以看见，上一级元素的个数是下一级的一半，这样每次减少一半，就很接近平衡二叉树了。
4.计算时间复杂度
单链表查询的时间复杂度为O(n)，而插入、删除操作需要先找到对应的位置，所以插入、删除的时间复杂度也是O(n)。
跳表的时间复杂度是多少？
如果按照标准的跳表来看的话，每一级索引减少k/2个元素（k为其下面一级索引的个数），那么整个跳表的高度就是(log n)。
对于平衡二叉树而言，它的时间复杂度与树的高度成正比，即O(log n)。
所以，这里跳表的时间复杂度也是O(log n)。（这里不一步步推倒了，只要记住，查询时每次减少一半的元素的时间复杂度都是O(log n)，比如二叉树的查找、二分法查找、归并排序、快速排序）
5.计算空间复杂度
我们还是以标准的跳表来分析，每两个元素向上提取一个元素，那么，最后额外需要的空间就是：
n/2 + n/(2^2) + n/(2^3) + ... + 8 + 4 + 2 = n - 2
所以，跳表的空间复杂度是O(n)。
6.总结
（1）跳表是可以实现二分查找的有序链表；
（2）每个元素插入时随机生成它的level；
（3）最低层包含所有的元素；
（4）如果一个元素出现在level(x)，那么它肯定出现在x以下的level中；
（5）每个索引节点包含两个指针，一个向下，一个向右；
（6）跳表查询、插入、删除的时间复杂度为O(log n)，与平衡二叉树接近
面试问题：
- 为什么Redis选择使用跳表而不是红黑树来实现有序集合？
答案：
Redis中sorted set支持的操作有
<1> 插入元素 <2> 删除元素 <3> 查找元素 <4> 有序输出所有元素 <5> 查找区间内所有元素
其中，前4项红黑树都可以完成，且时间复杂度与跳表一致。
但是，最后一项，红黑树的效率就没有跳表高了。
在跳表中，要查找区间的元素，我们只要定位到两个区间端点在最低层级的位置，然后按顺序遍历元素就可以了，非常高效。
而红黑树只能定位到端点后，再从首位置开始每次都要查找后继节点，相对来说是比较耗时的。
此外，跳表实现起来很容易且易读，红黑树实现起来相对困难，所以Redis选择使用跳表来实现有序集合。
网友评论