图示
在跳表中，第0层为原始的链表。第1层为第1级索引，第2层为第2级索引…层数越高，该层的节点越少。
在跳表中进行查找时，从最高层开始查找。比如如果我们需要查找10这个元素，就会经过以下路线：第二层的1->第一层的1->第一层的4->第一层的7->第一层的9->原始链表的9->原始链表的10。
由于从最高层（节点最少）的层开始查找，因此当数据较多时，相比普通的线性查找，跳表的查找可以快速缩小查找范围（有点类似于二分，但不完全是）。查找得时间复杂度是O(logn)。
代码实现
上图是一个单链表，为了便于删除，下面的代码是用双链表实现的。注释写得比较详细了。
import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;
/**
* 跳表
* 跳表有0，1，2，3......29层，一共有30层
* 第0层为原始的双链表
* 第1层为第1级索引
* 第2层为第2级索引
* ......
* 层数越往上，该层的节点越少
*/
public class SkipListMultiSet {
/**
* 跳表的节点。forward[i]代表节点在第i层的下一个节点是什么
* prevs[i]代表节点在第i层的上一个节点是什么
*/
static class Node {
Integer num;
int cnt;
Node[] forwards = new Node[TIER_NUM];
Node[] prevs = new Node[TIER_NUM];
public Node(Integer num, int cnt) {
this.num = num;
this.cnt = cnt;
}
@Override
public String toString() {
return "{" +
"num=" + num +
", cnt=" + cnt +
'}';
}
}
//写死跳表三十层
private static final int TIER_NUM = 30;
//跳表的哑头节点。
private final Node head = new Node(null, 0);
//跳表的哑尾节点
private final Node tail = new Node(null, 0);
public SkipListMultiSet() {
//哑头节点和哑尾节点互相指向
for (int i = 0; i < head.forwards.length; i++) {
head.forwards[i] = tail;
tail.prevs[i] = head;
}
}
/**
* 查找target的数是否在跳表中
*
* @param target 要查找的数
* @return 如果存在，返回true，否则返回False
*/
public boolean search(int target) {
Node targetNode = this.findNode(target);
return targetNode != null && targetNode.cnt > 0;
}
/**
* 将num添加到跳表
*
* @param num 要添加的元素
*/
public void add(int num) {
//先看看num的节点是否在链表中，如果是的话直接把cnt加一
Node targetNode = findNode(num);
if (targetNode != null) {
targetNode.cnt++;
return;
}
//每一层插入在哪个节点后面？
Node[] nodeListToInsertAfter = getNodeListToInsertAfter(num);
Node newNode = new Node(num, 1);
//在底层插入
insertAfter(newNode, nodeListToInsertAfter[0], 0);
//逐层向上插入。
for (int i = 1; i < nodeListToInsertAfter.length; i++) {
//从第1层不停的向上插入。每一次的概率都是0.5，如果有一次决定不插入，就停止整个过程
double d = Math.random();
if (d < 0.5) {
if (nodeListToInsertAfter[i].forwards[i] == newNode) {//由于这里nodeListToInsertAfter就是向下查找时的路径，因此可能有垂直向下的路径，要避免重复插入
continue;
}
insertAfter(newNode, nodeListToInsertAfter[i], i);
} else {
break;
}
}
}
/**
* 把newNode插在anchor的后面
*
* @param newNode 要插入的新节点
* @param anchor 在anchor节点后面插入
*/
public void insertAfter(Node newNode, Node anchor, int tier) {
Node originalAnchorNext = anchor.forwards[tier];
anchor.forwards[tier] = newNode;
newNode.forwards[tier] = originalAnchorNext;
originalAnchorNext.prevs[tier] = newNode;
newNode.prevs[tier] = anchor;
}
/**
* 【调用前提】跳表的数据结构中不含num这个节点
* 要在跳表的数据结构中插入num这个节点，这个函数可以返回一个数组返回数组nodeListToInsertAfter，表示在每一层上，在哪个节点后插入。
*
* @param num 要插入的数字
* @return 返回数组nodeListToInsertAfter[i]表示在第i层的这个节点后面插入。比如在第5层上，就在nodeListToInsertAfter[i]后面插入
*/
private Node[] getNodeListToInsertAfter(int num) {
Node[] nodeToInsertAfter = new Node[TIER_NUM];
//从顶层向下遍历
int tier = TIER_NUM - 1;
Node ptr = head;
//遍历的过程和findNode类似。
while (tier >= 0) {
Node next = ptr.forwards[tier];
if (next == tail && tier == 0) {//如果到了第0层的末尾，则第0层应该在ptr后面插入，并break
nodeToInsertAfter[tier] = ptr;
break;
} else if (next == tail) {//遍历到了非0层的末尾，应该在ptr后面插入，并下降一层
nodeToInsertAfter[tier] = ptr;
tier--;
} else if (next.num < num) {//如果下一个节点比要插入的数字小，则要插入的位置应该在这一层的更后面
ptr = next;
} else if (next.num > num) {//如果下一个节点比要插入的数字大，则在这一层上，应该在ptr后面插入。同时下降一层
nodeToInsertAfter[tier] = ptr;
tier--;
} else if (next.num == num) {
nodeToInsertAfter[tier] = next;
tier--;
}
}
return nodeToInsertAfter;
}
/**
* 从跳表中删除num
*
* @param num 要删除的数字
* @return 如果跳表原来存在num，删除后返回true。如果跳表中不存在num，就返回false。
*/
public boolean erase(int num) {
//寻找是否存在num的节点。
Node targetNode = findNode(num);
if (targetNode == null) {
return false;
} else {
if (targetNode.cnt > 0) {//先将cnt减1，如果cnt变为0，就从数据结构中移除掉这个节点
targetNode.cnt--;
if (targetNode.cnt == 0) {
removeThisNode(targetNode);
}
return true;
} else {
return false;
}
}
}
/**
* 将anchor的节点在所有层的索引当中删除
*
* @param anchor 要删除的节点
*/
private void removeThisNode(Node anchor) {
for (int tier = 0; tier < TIER_NUM; tier++) {
Node preAnchor = anchor.prevs[tier];
Node postAnchor = anchor.forwards[tier];
if (preAnchor != null && postAnchor != null) {
preAnchor.forwards[tier] = postAnchor;
postAnchor.prevs[tier] = preAnchor;
}
}
}
/**
* 找到内部值为num的节点。如果找不到，返回null
*
* @param num 要查找的数
* @return 如果存在值为num的节点，就返回它，否则就返回null
*/
private Node findNode(int num) {
//从最高层，也就是节点最少的层开始找
int tier = TIER_NUM - 1;
Node ptr = head;
while (tier >= 0) {
Node next = ptr.forwards[tier];
if (next == tail && tier == 0) {//如果已经到了底层的最尾，说明找不到
return null;
} else if (next == tail) {//如果到了最尾部但不是底层，就向下一层
tier--;
} else if (next.num < num) {//如果下一个节点小于num，说明要找的节点应该还在这一层的后面
ptr = next;
} else if (next.num > num) {//如果下一个节点大于num，说明要找的节点夹在ptr和next之间，但不在这一层。于是向下一层找
tier--;
} else if (next.num == num) {//找到了！
return next;
}
}
return null;
}
/**
* 按层输出跳表
*
* @return 按层输出跳表的表示
*/
@Override
public String toString() {
StringBuilder builder = new StringBuilder();
int tier = TIER_NUM - 1;
while (tier >= 0) {
List<Node> li = new ArrayList<>();
Node ptr = head;
while (ptr != null) {
li.add(ptr);
ptr = ptr.forwards[tier];
}
String line = li.stream().map(Object::toString).collect(Collectors.joining("<->"));
builder.append(line);
builder.append("\n");
tier--;
}
return builder.toString();
}
}