跳表数据结构的发明者William Pugh在1990年的论文《Skip Lists: A Probabilistic Alternative to Balanced Trees》中首次提出了跳表的概念和设计。跳表是一种基于链表的数据结构，通过添加多层索引来加速查找操作，相比于平衡树等其他数据结构，跳表具有简单、高效的特点；在插入、删除、查找元素的时间复杂度跟红黑树都是一样量级的，时间复杂度都是O(logn)。
1、本质：有序链表之上添加索引
下图是一个简单的有序单链表，单链表的特性就是每个元素存放下一个元素的指针（或引用）。即：通过第一个元素可以找到第二个元素，通过第二个元素可以找到第三个元素，依次类推，直到找到最后一个元素。
如果我们想快速找到上图链表中的 5这个元素，只能从头开始遍历链表，直到找到我们需要找的元素。查找路径：0、1、2、3、4、5。这样的查找效率很低，平均时间复杂度很高O(n)。那有没有办法提高链表的查找速度呢？如下图所示，我们从链表中每两个元素抽出来，加一级索引level1，level0为原始链表。
查找路径优先从level1的head开始，向右直到遇到大于当前查找值，也就是到节点4时发现下一个节点值为6，大于当前查找值5，于是跳转到level0的节点4，再继续查找下一节点，找到5后搜索结束；查找路径：level1的0（后续简写成1 - 0）、1 - 2、1 - 4、0 - 4、0 - 5；
从一层索引下，平均时间复杂度降为O(n/2)；但是这仅是一层索引的情况，在多层索引的情况下时间复杂度如何呢？
假设跳表的元素个数为n，每个节点的层级都是随机分布的，平均来说，每个节点的上层节点数是下层的一半。这样，最底层level 0有n个节点的索引，level 1有n/2个索引，level 2有n/4个索引，以此类推。最高级索引 h 满足 1= n/2^h，即 h = log2n；
整个查找过程类似二分查找。我们从最高层开始，如果当前节点的下一个节点值大于目标值，我们就转到当前层的下一层继续查找；如果当前节点的下一个节点值小于或等于目标值，我们就在当前层向右移动。这样平均每一层我们只需要遍历1次节点（向右或向下），所以在每一层的时间复杂度是O(1)。
因为跳表的高度是logn，所以查找操作的总时间复杂度是O(logn) * O(1) = O(logn)。
2、 实际的数据结构
上面讲的是跳表从有序单链表演化的数据结构，但在实际编码中跳表的结构是这样的
class Node<T> {
String key;
T value;
Node<T>[] forwards;
public Node(int level, T value, String key) {
this.value = value;
this.key = key;
forwards = new Node[level];
}
}
- 每个节点node存放data(本例是map，存放key、value)和指针数组forward
- forward指针数组指向当层level的下一节点，如node1的forward[2]指向level 2层的下一节点node2，而forward[3]指向level 3层的下一节点node3
- 遍历从head的forward[n-1]开始，遍历方向为向右，向上（算法上一般讲向下，是指level层数意义上的；我这里取向上是指物理地址空间意义上的，方便图文对应）
- 每层节点数是下层的一半， 即level 0有全部n个节点，level 1有n/2个节点，leve l2有n/4个节点
- 索引结构的高度是log n，整个跳表的空间复杂度可以近似地看作是O(n + log n)；但在实际应用中，存储的节点数n较小，通常将其简化为O(n)
3、查找
以下以查找元素5为例，详细描述查找过程
- 从head的forward[n-1]开始，指向node3
- node3的value为3，小于查找值5，跳转node3
- node3的forward[n-1]指向空，无法向右；向上跳转forward[n-2]
- node3的forward[n-2]指向node6，node6的value为6，大于5，无法向右；向上跳转forward[n-3]
- node3的forward[n-3]指向node6，node6的value为6，大于5，无法向右；向上跳转直至forward[4]
- node3的forward[4]指向node4，node4的value为4，小于5，向右跳转至node4
- node4的forward[4]指向node6，node6的value为6，大于5，无法向右；向上跳转直至forward[3]
- node4的forward[3]指向node5，node5的value为5，等于查找值5，查找结束
public T get(String key) {
Node<T> current = head;
for (int i = level - 1; i >= 0; i--) {
while (current.forwards[i] != null && current.forwards[i].key.compareTo(key) < 0) {
current = current.forwards[i];
}
}
current = current.forwards[0];
if (current != null && current.key.equals(key)) {
return current.value;
} else {
return null;
}
}
在最坏情况下，查找操作可能需要遍历整个跳表，导致时间复杂度变为O(n)。平均情况下的时间复杂度是O(log n)。
4、插入
在查找中我们没有讲到整个索引表是如何构建出来，所以在插入中我们重点讲一下如何构建整个跳表的节点和索引的。
4.1、如何保证level h层的索引数1= n/2^h
要保证level 0有n个节点的索引，level 1有n/2个索引，level 2有n/4个索引, level 3有n/4个索引...
我们可以通过randomLevel函数来实现这个分布；randomLevel() 随机生成 1~MAX_LEVEL 之间的数（MAX_LEVEL表示索引的最高层数），当randomLevel返回1，表示当前node只有一层索引（level 0层），概率为100%(返回值>=1的概率为100%)；当randomLevel返回2，表示当前node有2层索引（level 1层），概率为1/2；当randomLevel返回3，表示当前node有3层索引（level 2层），概率为1/4；所以在大量数据插入时，node节点按这个概率去生成forward数组，整个表基本会满足这个分布，代码如下：
private final Random rand = new Random();
private final double P = 0.5;
private final int MAX_LEVEL = 16;
private int randomLevel() {
int newLevel = 1;
while (rand.nextDouble() < P && newLevel < MAX_LEVEL) {
newLevel++;
}
return newLevel;
}
4.2插入节点和更新索引
-
本处以插入node4为例，假设randomlevel生成的索引层数为5层，插入前表结构如下
插入前.png -
寻找到合适的插入位置，查找算法同步骤3，找到node3
寻找插入位置 -
查找过程中，记录需要更新索引的左侧update节点，本例中是node3的forward[0] ~ forward[4]（下图红框选中节点）
记录左侧待更新索引节点.png -
更新索引，将node4的forward[0] ~ forward[4]指向原node3的forward[0] ~ forward[4]所指向的节点；然后将node3的forward[0] ~ forward[4]指向插入的node4；
更新索引 插入流程结束，平均时间复杂度为O(log n)。
5、删除
删除与插入一样，需要对索引进行更新，本处以删除node1为例
-
查找删除节点的前一节点，本例为node0；同时记录需要更新索引的左侧update节点（下图红框选中节点）
查找待删除节点的前面一个节点 -
更新索引，将update数组的forwards指向node1的forwards
更新索引 - 删除流程结束，平均时间复杂度为O(log n)。
public void remove(String key) {
Node<T>[] update = new Node[level];
Node<T> current = head;
for (int i = level; i >= 0; i--) {
while (current.forwards[i] != null && current.forwards[i].key.compareTo(key) < 0) {
current = current.forwards[i];
}
update[i] = current;
}
current = current.forwards[0];
if (current != null && current.key.equals(key)) {
for (int i = 0; i <= level; i++) {
if (update[i].forwards[i] != current) {
break;
}
update[i].forwards[i] = current.forwards[i];
}
while (level > 0 && head.forwards[level] == null) {
level--;
}
nodeCount--;
}
}
总结
- 跳表是一个接近二分查找的有序链表
- 跳表中最核心的就是搜索，不管是在插入，更新，删除还是查找中，都要先搜索
- 跳表在插入node时，通过随机数确定node中层数的
- 跳表相对于红黑树，优势是相对容易实现，和范围查找方便
