一、前言
跳表（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(); } } } |
