数据结构与算法--跳表
跳表 = 链表 + 多级索引
跳表使用空间换时间的设计思路，通过构建多级索引来提高查询的效率，实现了基于链表的“二分查找”。跳表是一种动态数据结构，支持快读的插入、删除、查找操作，时间复杂度都是O(logn)。
跳表跳表的空间复杂度是O(n)。跳表的实现非常灵活，可以通过改变索引构建策略，有效平衡执行效率和内存消耗。跳表的代码比起红黑树来说，要简单、易读。
链表加多级索引的结构，就是跳表。
对于一个单链表，即便链表中存储的数据是有序的，如果要查找某个数据，也只能从头到尾遍历，时间复杂度是O(n)。
对于链表建立一级“索引”，没两个结点提取一个结点到上一级，把抽出来的那一级叫做索引或索引层。图中的 down表示down指针，指向下一级结点。
这样就可以先在索引层遍历，然后通过索引层结点的down指针，下降到原始链表这一层，继续遍历。
比如要查找16，当在索引层遍历到13时，发现索引层下一个结点是17大于目标16，则可从13的down指针下降到原始链表继续遍历。这样只需要再遍历2个结点，就可以找到值等于16的这个结点了。原来查找16，需要遍历10个结点，加入一层索引后只需要遍历7个结点。
加上一层索引之后，查找一个结点需要遍历的结点个数减少了，查找效率提高了。继续再加一级索引，在第一级索引的基础之上，每两个结点就抽出一个结点到第二级索引。现在再查找16，只需要遍历6个结点了，需要遍历的结点数量又减少了。
下图是一个包含64个结点的链表，建立五级索引。
在五级索引的作用下，查找62只需要遍历11个结点。当链表的长度n比较大时，比如1000、10000的时候，在构建多级索引之后，查找效率的提升就会非常明显。
跳表的时间复杂度
一个链表里有n个结点，每两个结点会抽出一个结点作为上一级索引的结点，那第一级索引的结点个数大约就是n / 2，第二级索引的结点个数大约就是n / 4，第三级索引的结点个数大约就是n / 8，依此类推，也就是说，第k级索引的结点个数就是第k - 1级索引的结点个数的1 / 2，那第k级索引结点的个数就是n / (2 ^ k)。
假设索引有h级，最高级的索引有2个结点，则n / (2 ^ h) = 2，即h = logn - 1。加上原始链表这一层，整个跳表的高度就是logn。在跳表中查询某个数据的时候，如果每一层都要遍历m个结点，那在跳表中查询一个数据的时间复杂度就是O(m * logn)。
按照每两个结点提取一个结点到上一级建立索引这种数据结构，每一级索引都最多只需要遍历3个结点，那么m = 3。
假设要查找的数据是x，在第k级索引中遍历到y结点之后，发现x大于y，小于后面的结点z，所以通过y的down指针，从第k级索引下降到第k - 1级索引。在第k - 1级索引中，y和z之间只有3个结点（包含y和z），所以在k - 1级索引中最多只需要遍历3个结点，依此类推，每一级索引都最多只需要遍历3个结点。
所以在跳表中查询任意数据的时间复杂度就是O(logn)。
跳表的空间复杂度分析
假设原始链表大小为n，那第一级索引大约有n / 2个结点，第二级索引大约有n / 4个结点，以此类推，每上升一级就减少一半，直到剩下2个结点。每层索引的结点数为：
n / 2, n / 4, n / 8, ..., 8, 4, 2
这几级索引的结点总和就是 n / 2 + n / 4 + n / 8 + ... + 8 + 4 + 2 = n - 2。所以跳表的空间复杂度是O(n)。
将包含n个结点的单链表构造成跳表，需要额外再用接近n个结点的存储空间。
如果每三个结点或五个结点，抽一个结点到上级索引：
那第一级索引需要大约n / 3个结点，第二级索引需要大约n / 9个结点。每往上一级，索引结点个数都除以3。为了方便计算，假设最高一级的索引结点个数是1。每3个结点抽一个，每层索引的结点数为：
n / 3, n / 9, n / 27, ..., 9, 3, 1
总的索引结点个数为n / 3 + n / 9 + n / 27 + ...+ 9 + 3 + 1 = n / 2。空间复杂度依然是O(n)，但比每两个结点抽一个结点的索引构建方法，减少了一半的索引结点存储空间。
在实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引结点只需要存储关键值和几个指针，并不需要存储对象，所以当对象比索引结点大很多时，那索引占用的额外空间就可以忽略了。
跳表动态的插入和删除
跳表插入、删除操作的时间复杂度是O(logn)。
对于删除操作，如果这个结点在索引中也有出现，删除原始链表中的结点之后还要删除对应的索引。
查找要删除的结点的时候，一定要获取前驱结点。（双向链表不需要考虑这个问题）
跳表索引动态更新
不停地往跳表中插入数据时，如果不更新索引，就有可能出现某2个索引结点之间数据非常多的情况。极端情况下，跳表还会退化成单链表。
作为一种动态数据结构，需要某种手段来维护索引与原始链表大小之间的平衡：
如果链表中结点多了，索引结点就相应地增加一些，避免复杂度退化，以及查找、插入、删除操作性能下降。
往跳表中插入数据的时候，可以同时将这个数据插入到部分索引层中。通过一个随机函数，来决定将这个结点插入到哪几级索引中，比如随机函数生成了值k，就将这个结点添加到第一级到第k级索引中。
Redis用跳表实现有序集合
Redis中的有序集合是通过跳表来实现的，严格点讲，其实还用到了散列表。
Redis中的有序集合支持的核心操作主要有：
- 插入一个数据；
- 删除一个数据；
- 查找一个数据；
- 按照区间查找数据；
- 迭代输出有序序列。
其中，插入、删除、查找以及迭代输出有序序列这几个操作，红黑树也可以完成，时间复杂度跟跳表一样的。但是，按区间来查找数据这个操作，红黑树的效率没有跳表高。
对于按照区间查找数据这个操作，跳表可以做到O(logn)的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了，这样做非常高效。
跳表相对红黑树而言代码更容易实现，简单就意味着可读性好，不容易出错。还有，跳表更加灵活，它可以通过改变索引构建策略，有效平衡执行效率和内存消耗。
跳表的简易代码实现
public class SkipList {
private static final float SKIPLIST_P = 0.5f;
private static final int MAX_LEVEL = 16;
private int levelCount = 1;
private Node cls = new Node(); // 带头链表
public Node find(int value) {
Node p = cls;
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] = cls;
}
// record every level largest value which smaller than insert value in update[]
Node p = cls;
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 hight
if (levelCount < level) levelCount = level;
}
public void delete(int value) {
Node[] update = new Node[levelCount];
Node p = cls;
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];
}
}
}
while (levelCount>1&&cls.forwards[levelCount]==null){
levelCount--;
}
}
// 理论来讲，一级索引中元素个数应该占原始数据的 50%，二级索引中元素个数占 25%，三级索引12.5% ，一直到最顶层。
// 因为这里每一层的晋升概率是 50%。对于每一个新插入的节点，都需要调用 randomLevel 生成一个合理的层数。
// 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ：
// 50%的概率返回 1
// 25%的概率返回 2
// 12.5%的概率返回 3 ...
private int randomLevel() {
int level = 1;
while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)
level += 1;
return level;
}
public void printAll() {
Node p = cls;
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();
}
}
}
