# 什么是跳表？

### 一：什么是跳表

$O(N)$

class Node<E extends Comparable<E>> {
public E e;
public Node<E>[] next;

public Node(int level) {
next = new Node[level];
}

@Override
public String toString() {
StringBuilder sb = new StringBuilder();
sb.append("{ e : " + e + " , level : " + next.length + " }");
return sb.toString();
}
}

private int generateRandomLevel() {
int level = 1;
for (int i = 1; i < MAX_LEVEL; i++) {
if (random.nextInt() % 2 == 1) {
level++;
}
}
return level;
}

### 二：在跳表中查询元素

public boolean contains(E e) {
for (int i = maxLevel - 1; i >= 0; i--) {
while (cur.next[i] != null && cur.next[i].e.compareTo(e) < 0) {
cur = cur.next[i];
}
if (cur.next[i] != null && cur.next[i].e.equals(e)) {
return true;
}
}
return false;
}

### 三：在跳表中插入和删除元素

#### 在跳表中插入元素

Java 代码实现如下：

/**
* @param e 向跳表中添加一个元素 e
*/
if (contains(e)) {
}

int level = generateRandomLevel();
// 更新当前跳表的 maxLevel
if (level > maxLevel) {
maxLevel = level;
}
Node<E> newNode = new Node<>(level);
newNode.e = e;

for (int i = maxLevel - 1; i >= 0; i--) {
while (cur.next[i] != null && cur.next[i].e.compareTo(e) < 0) {
cur = cur.next[i];
}
if (level > i) {
if (cur.next[i] == null) {
cur.next[i] = newNode;
} else {
Node next = cur.next[i];
cur.next[i] = newNode;
newNode.next[i] = next;
}
}
}

size++;
}

#### 在跳表中删除元素

Java 代码实现如下：

/**
* @param e 从跳表中删除元素 e
*/
public void remove(E e) {
if (!contains(e)) {
throw new IllegalArgumentException("Remove Failed! There is no such element: " + e + " in SkipList.");
}
Node<E>[] update = new Node[maxLevel];
for (int i = maxLevel - 1; i >= 0; i--) {
while (cur.next[i] != null && cur.next[i].e.compareTo(e) < 0) {
cur = cur.next[i];
}
update[i] = cur;
}
if (cur.next[0] != null && cur.next[0].e.equals(e)) {
for (int i = maxLevel - 1; i >= 0; i--) {
if (update[i].next[i] != null && update[i].next[i].e.equals(e)) {
update[i].next[i] = update[i].next[i].next[i];
}
}
// 更新当前跳表的 maxLevel
while (maxLevel > 1 && head.next[maxLevel] == null) {
maxLevel--;
}
}
size--;
}

### 四：跳表的复杂度分析

Skip Lists: A Probabilistic Alternative to Balanced Trees

$n$

$n/2$

，第二级索引的节点个数大约就是

$n/4$

，第三级索引的节点个数大约就是

$n/8$

$k$

$n/2^k$

$h$

$n/(2^h) = 2$

$h=log2^n - 1$

$m$

$O(mlogn)$

$m$

$O(logN)$

，这个查找的时间复杂度和二分查找的原理是一样的。同理，添加，删除一个元素的时间复杂度也是

$O(logN)$

$O(logN)$

。在这里，我们就不给出详细的证明了，大家可以查看我给出的资料自行研究。

### 五：跳表的性能测试

private static Array<Integer> generateRandomArray() {
Array<Integer> array = new Array<>();
Random random = new Random();
for (int i = 0; i < 100000; i++) {
}
return array;
}
private static double testSkipList(SkipList<Integer> skipList, Array<Integer> array) {
long startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
skipList.contains(array.get(i));
}
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
long startTime = System.nanoTime();
for (int i = 0; i < 100000; i++) {
}
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
@Test
void SkipListPerformanceTest() {
SkipList<Integer> skipList = new SkipList<>();
for (int i = 0; i < 10000; i++) {
}
Array<Integer> array = generateRandomArray();
double time1 = testSkipList(skipList,array);

System.out.println("SkipList contains : " + time1 + " s");
System.out.println("LinkedList contains : " + time2 + " s");
}

SkipList contains : 0.057014315 s

### 六：为什么 Redis 要使用跳表来实现有序集合，而不是红黑树

• 插入一个数据
• 删除一个数据
• 查找一个数据
• 按照区间查找数据（比如查找值在 [100,356] 之间的数据）
• 迭代输出有序序列

$O(logn)$