一、前言
跳表（Skip List）这种数据结构在一般的数据结构书籍和算法书籍里都不怎么涉及----至少我大学数据结构课程没有讲这种结构。但是跳表确实是一种性能比较优秀的动态数据结构，并且Redis中的有序集合（Sorted Set）就是用跳表实现的。本文先大致了解一下跳表。
二、跳表
1、引出
对于一组有序数据，我们想要在其中查找某个数，如果数据使用数组存储，显然二分法是再适合不过了，但是如果数据是用链表存储的呢？难道我们用从头遍历吗？这样时间复杂度会达到O（n）级别，相比二分法O（logn）级别简直天壤地别。那么如何提高效率呢？
链表的查找时间复杂度算法为1/n(1+2+3+…+n)=O(n),数据出现的位置从第一个到最后一个的概率均为1/n,但是查询时间分别是1，2，，，n，所以平均时间复杂度为O（n）。
2、跳表
我用图片形式来理解跳表。
![]()
如下图，对初始链表做一层“索引”，每两个节点提取一个节点到上一层，然后用down指针连接到下一层。
![]()
现在我们查询16这个节点。从第一级索引开始，找到13，并且下一个为17，显然16在这两个节点之间，利用down指针下降一层，这次我们遍历2次即可。利用索引后，遍历了5+2=7次，而原始链表需要10次，这里加一层索引遍历次数减少了，效率提高了一点，但还不够，我们继续往上添加索引层。
![]()
这里我不再算了，结果是6次，效率又提高了！
那么这种链表加多级索引就是跳表的结构了。
3、链表查询的时间复杂度是多少？
①假设链表有N个节点，按图所示依次往上级添加索引，第一级有N/2个节点，第二级有N/4个节点。。。。
那么第k级索引有N/(2^k)个节点。
②假设索引有h级，最高级有2个节点。就有N/(2^h)=2--->h=log2N-1(以2为底N的对数)。加上原始链表，那么高度就是log2N了。
③查询时，如果每层都遍历m次（最高级最多遍历2次，其他级最多遍历m次）那么复杂度就是O（mlgN）（在大O表示法里，logaN级别的复杂度等于lnN复杂度,去掉m就是O（logn）级别了），我们求一下m的值。
![]()
在第k级时，我们遍历到了y和z，查询值介于两者之间，通过down指针，到达第k-1级，而这一级y和z之间最多有3个节点，那么m就等于3了。
综上跳表的查询时间复杂度就是O（logn）了。
4、跳表的耗费空间吗？
这个问题就很简单了，空间复杂度就是每层节点和，即n/2+n/4+...+4+2=n-2,空间复杂度就是O（n）了。
当然了这里也可以扩大索引间隔，减少一点索引空间，但是我们还是按照上面的求时间复杂度方法，得到的结果仍是O（logn）。实际应用中，向来是比较乐意用空间换时间的，所以这种做法的意义并不大，因为时间复杂度还是没变！
并且这里我们使用整数作为例子来讲得，软件开发中，链表存的可能是一个很大的对象，索引只需要记录关键字和一些指针，那么额外的空间和原数据相比完全可以忽略！
5、高效的动态插入和删除
我想汉字没有图片表达的清楚，所以还是用图片来表述！
![]()
时间复杂度仍是O（logn）。我们说单链表插入复杂度为O(1)，但是这是指插入动作，并不包含查找插入点所耗的时间，加上查找时间O（n），跳表效率还是高一点！
删除要麻烦一点，因为删除的节点要是在索引中，我们还得更新索引，更新索引就得找到前驱节点，当然双链表可以不用考虑了！
6、索引动态更新
考虑这样一种情况
![]()
更极端的可以退化成单链表，所以索引的动态更新是必要的！
AVL树是通过左右旋转保持平衡性，而跳表是通过随机函数生成一个值K，然后将节点添加到第一级到第K级索引中。
![]()
关于这个随机函数，我没有做深入研究（水平有限，然后有兴趣可以参考redis中关于有序集合的跳表实现）
三、Redis为什么选择跳表？
严格讲Redis还用到了散列表，但是本文讲的是跳表，所以暂时忽略！
在Redis开发手册中，有序集合支持的操作有
- 插入一个数据
- 删除一个数据
- 查找一个数据
- 迭代输出有序序列
- 按照区间查找数据
前面可以用其他数据结构完成----比如红黑树，但是最后一个显然用跳表去定位起点（然后逐条输出）更好实现！再者跳表的代码虽然很难但是比起红黑树相对起来要好实现。
但是。。。。。。。红黑树有现成的实现，直接拿来用，而跳表却需要自己实现。。。。。。。
四、简单的跳表实现代码
代码由王争老师完成
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
|
package skiplist;
import java.util.Random;
/**
* 跳表的一种实现方法。
* 跳表中存储的是正整数，并且存储的是不重复的。
*
* Author：ZHENG
*/
public class SkipList {
private static final int MAX_LEVEL = 16;
private int levelCount = 1;
private Node head = new Node(); // 带头链表
private Random r = new Random();
public Node find(int value) {
Node p = head;
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
}
if (p.forwards[0] != null && p.forwards[0].data == value) {
return p.forwards[0];
} else {
return null;
}
}
public void insert(int value) {
int level = randomLevel();
Node newNode = new Node();
newNode.data = value;
newNode.maxLevel = level;
Node update[] = new Node[level];
for (int i = 0; i < level; ++i) {
update[i] = head;
}
// record every level largest value which smaller than insert value in update[]
Node p = head;
for (int i = level - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
update[i] = p;// use update save node in search path
}
// in search path node next node become new node forwords(next)for (int i = 0; i < level; ++i) {
newNode.forwards[i] = update[i].forwards[i];
update[i].forwards[i] = newNode;
}
// update node hightif (levelCount < level) levelCount = level;
}
public void delete(int value) {
Node[] update = new Node[levelCount];
Node p = head;
for (int i = levelCount - 1; i >= 0; --i) {
while (p.forwards[i] != null && p.forwards[i].data < value) {
p = p.forwards[i];
}
update[i] = p;
}
if (p.forwards[0] != null && p.forwards[0].data == value) {
for (int i = levelCount - 1; i >= 0; --i) {
if (update[i].forwards[i] != null && update[i].forwards[i].data == value) {
update[i].forwards[i] = update[i].forwards[i].forwards[i];
}
}
}
}
// 随机 level 次，如果是奇数层数 +1，防止伪随机private int randomLevel() {
int level = 1;
for (int i = 1; i < MAX_LEVEL; ++i) {
if (r.nextInt() % 2 == 1) {
level++;
}
}
return level;
}
public void printAll() {
Node p = head;
while (p.forwards[0] != null) {
System.out.print(p.forwards[0] + " ");
p = p.forwards[0];
}
System.out.println();
}
public class Node {
private int data = -1;
private Node forwards[] = new Node[MAX_LEVEL];
private int maxLevel = 0;
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
builder.append("{ data: ");
builder.append(data);
builder.append("; levels: ");
builder.append(maxLevel);
builder.append(" }");
return builder.toString();
}
}
} |
