【数据结构与算法】系列四十 - 跳表

发表于 | 分类于
| 字数统计 2.5k 字 | 阅读时长 10 分钟

一个有序链表搜索、添加、删除的平均时间复杂度是多少？$O(n)$

能否利用二分搜索优化有序链表，将搜索、添加、删除的平均时间复杂度降低至 $O(logn)$？

由于链表没有像数组那样的高效随机访问（时间复杂度：$O(1)$），所以不能像有序数组那样直接进行二分搜索优化。

那有没有其他办法让有序链表搜索、添加、删除的平均时间复杂度降低至 $O(logn)$？使用跳表。

一、跳表

跳表（SkipList），又叫做跳跃表、跳跃列表，在有序链表的基础上增加了“跳跃”的功能。由William Pugh于1990年发布，设计的初衷是为了取代平衡树（比如AVL树、红黑树）。

Redis中的SortedSet、LevelDB中的MemTable都用到了跳表，Redis、LevelDB都是著名的Key-Value数据库。

对比平衡树，跳表的实现和维护会更加简单，而且跳表的搜索、删除、添加的平均时间复杂度是 $O(logn)$。

1.1. 使用跳表优化链表

普通链表查找元素需要一级一级往下找。

链表基础上增加中转跳跃，即部分节点有多个指向，如下图中的节点6、9、17、21、26，一个节点可以指向多个下一级节点。

如下图，查找节点19的顺序是：

  • first -> 6 -> 9 -> 17
  • 此时发现17的第一个指向是21（比19大）
  • 继续往下找17的下一个指向
  • 发现指向的刚好是要找的节点19

如果继续增加层数，指向的节点个数也会增加，相应的搜索速度也会更快。

是不是层数越多，搜索速度越快？不是的，实验数据显示，层数最多是32层。

注意点：

  1. 节点存储的是key-value，和TreeMap有点类似，key必须具备可比性。

  2. 首节点的层数肯定是和链表中节点层数最高的一样，但由于无法确定层数是多少，所以首节点的层数就使用默认最大层数32层。

  3. 如果确定了首节点层数，如何遍历呢？因为是从上往下进行遍历（思考：为什么不从0开始遍历？），所以需要确定有效层数是多少，最终从有效层数最高层开始遍历。

1.2. 搜索

  1. 从顶层链表的首元素开始，从左往右搜索，直至找到一个大于或等于目标的元素，或者到达当前层链表的尾部；
  2. 如果该元素等于目标元素，则表明该元素已被找到；
  3. 如果该元素大于目标元素或已到达链表的尾部，则退回到当前层的前一个元素，然后转入下一层进行搜索。
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
public class SkipList<K, V> {
  // 最大层数
  private static final int MAX_LEVEL = 32;
  // 随机概率（0.25是模仿Redis的做法）
  private static final double P = 0.25;
  // 节点个数
  private int size;
  // 自定义比较器
  private Comparator<K> comparator;
  // 有效层数
  private int level;
  // 首节点，不存放任何K-V，只有nexts指向
  private Node<K, V> first;

  public SkipList(Comparator<K> comparator) {
    this.comparator = comparator;
    // 首节点使用最高层
    first = new Node<>(null, null, MAX_LEVEL);
  }

  public SkipList() {
    this(null);
  }

  // 链表大小（节点个数）
  public int size() {
    return size;
  }

  // 链表是否为空
  public boolean isEmpty() {
    return size == 0;
  }

  // 获取节点value
  public V get(K key) {
    keyCheck(key);
    // 从首节点的最高层开始搜索
    Node<K, V> node = first;
    for (int i = level - 1; i >= 0; i--) {
      int cmp = -1;
      // 如果目标节点key > 指向的节点key，就让指向的节点继续往下搜索
      while (node.nexts[i] != null 
          && (cmp = compare(key, node.nexts[i].key)) > 0) {
        node = node.nexts[i];
      }
      // 代码执行到这里一定是：目标节点key ≤ 指向的节点key，即cmp ≤ 0
      // cmp == 0 代表找到目标（目标key和指向的节点key相等）
      if (cmp == 0) return node.nexts[i].value;
      // cmp < 0 代表node的当前层没有找到目标，需要继续往node的下一层继续查找
    }
    return null;
  }

  // key非空检查
  private void keyCheck(K key) {
    if (key == null) {
      throw new IllegalArgumentException("key must not be null.");
    }
  }

  // 比较
  private int compare(K k1, K k2) {
    return comparator != null 
        ? comparator.compare(k1, k2)
        : ((Comparable<K>)k1).compareTo(k2);
  }

  // 节点
  private static class Node<K, V> {
    K key;
    V value;
    Node<K, V>[] nexts; // 指向下一级的节点列表
    public Node(K key, V value, int level) {
      this.key = key;
      this.value = value;
      nexts = new Node[level];
    }
  }
}

1.3. 添加

添加元素最大的疑问就是如何确定层数？其实层数是随机决定的（不超过最大层数限制），只不过这个随机范围是有限制的。虽然是随机的，但是经过大量数据验证表明它的效率是最高的。

添加的步骤：

  1. 如果节点指向的节点key比目标key小，就在沿着指向的节点往下找；
  2. 如果节点指向的节点key等于目标key，直接更新指向的节点值即可；
  3. 如果节点指向的节点key比目标key大，就在当前节点的层级往下找，并且记录这个节点以及在哪一层；
  4. 直到所有层数遍历结束，开始添加新的节点。
    • 新节点的前驱（哪些节点指向这个新节点）就是第3步记录的节点；
    • 新节点的后继（新节点的nexts指向）就是第3步记录的节点所指向的节点；
    • 如果新节点的层数比跳表当前的层数高（有效层），直接让首节点的超出层级指向新节点。
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
// 添加（更新）节点
public V put(K key, V value) {
  // 非空检查
  keyCheck(key);
  
  // 按层依次寻找key
  Node<K, V> node = first;
  Node<K, V>[] prevs = new Node[level];
  for (int i = level - 1; i >= 0; i--) {
    int cmp = -1;
    while (node.nexts[i] != null 
        && (cmp = compare(key, node.nexts[i].key)) > 0) {
      node = node.nexts[i];
    }
    if (cmp == 0) { // 如果节点是存在的，就把节点的值更新一下
      V oldV = node.nexts[i].value;
      node.nexts[i].value = value;
      return oldV;
    }
    /*
     node当前层的指向节点key比传入的key大（node.nexts[i].key > key），
     而node又比传入的key小，所以把当前node记录下来，当做新建节点的前驱节点
     */
    prevs[i] = node;
  }
  
  // 代码执行到这意味着没有找到key对应的节点，所以需要新建节点。

  // 新节点的层数
  int newLevel = randomLevel();
  // 添加新节点
  Node<K, V> newNode = new Node<>(key, value, newLevel);
  // 设置前驱和后继
  for (int i = 0; i < newLevel; i++) {
    if (i >= level) { // 超出有效层level部分用首节点对应层级直接指向新节点
      first.nexts[i] = newNode;
    } else {
      newNode.nexts[i] = prevs[i].nexts[i];
      prevs[i].nexts[i] = newNode;
    }
  }
  
  // 节点数量增加
  size++;
  
  // 计算跳表的最终层数
  level = Math.max(level, newLevel);
  
  return null;
}

// 随机层数
private int randomLevel() {
  int level = 1;
  while (Math.random() < P && level < MAX_LEVEL) {
    level++;
  }
  return level;
}

1.4. 删除

删除和添加有点类似，都要找出前驱节点。主要就是让被删除节点的前驱节点指向被删除节点的指向节点。需要注意的是删除一个元素后，整个跳表的层数可能会降低。

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
// 移除节点
public V remove(K key) {
  keyCheck(key);
  
  Node<K, V> node = first;
  Node<K, V>[] prevs = new Node[level];
  boolean exist = false;
  for (int i = level - 1; i >= 0; i--) {
    int cmp = -1;
    while (node.nexts[i] != null 
        && (cmp = compare(key, node.nexts[i].key)) > 0) {
      node = node.nexts[i];
    }
    prevs[i] = node;
    if (cmp == 0) exist = true;
  }
  if (!exist) return null;
  
  // 代码执行到这里，node一定是被删除节点的第0层前驱节点，对应的也是node的第0层
  // 需要被删除的节点
  Node<K, V> removedNode = node.nexts[0];
  
  // 数量减少
  size--;
  
  // 设置后继
  for (int i = 0; i < removedNode.nexts.length; i++) {
    prevs[i].nexts[i] = removedNode.nexts[i];
  }
  
  // 更新跳表的层数，主要是计算首节点非空层数
  int newLevel = level;
  while (--newLevel >= 0 && first.nexts[newLevel] == null) {
    level = newLevel;
  }
  
  return removedNode.value;
}

1.5. 层数

跳表是按层构造的，底层是一个普通的有序链表，高层相当于是低层的“快速通道”。

在第 $i$ 层中的元素按某个固定的概率 $p$（通常为$\frac{1}{2}$ 或 $\frac{1}{4}$）出现在第 $i + 1$ 层中，产生越高的层数，概率越低。

  • 元素层数恰好等于 $1$ 的概率为 $1 ; – ; p$
  • 元素层数大于等于 $2$ 的概率为 $p$，而元素层数恰好等于 $2$ 的概率为 $p * (1 ; – ; p)$
  • 元素层数大于等于 $3$ 的概率为 $p^2$，而元素层数恰好等于 $3$ 的概率为 $p^2 * (1 ; – ; p)$
  • 元素层数大于等于 $4$ 的概率为 $p^3$，而元素层数恰好等于 $4$ 的概率为 $p^3 * (1 ; – ; p)$
  • ……
  • 一个元素的平均层数是 $\frac{1}{1 ; – ; p}$

公式推导：
$$
1 * (1 - p) + 2p(1 - p) + 3p^2(1 - p) + 4p^2(1 - p) + … = (1 - p)\sum_{k = 1}^{+\infty}kp^{k - 1} = (1 - p)\frac{1}{(1 - p)^2} = \frac{1}{1 - p}
$$

  • 当 $p = \frac{1}{2}$ 时，每个元素所包含的平均指针数量是 $2$
  • 当 $p = \frac{1}{4}$ 时，每个元素所包含的平均指针数量是 $1.33$

从这也可以看出来，跳表相比TreeMap比较省内存（红黑树节点需要key, value, left, right, parent等指针，而跳表节点只需要key, value, nexts等指针）。

1.6. 复杂度分析

每一层的元素数量

  • 第 $1$ 层链表固定有 $n$ 个元素
  • 第 $2$ 层链表平均有 $n * p$ 个元素
  • 第 $3$ 层链表平均有 $n * p^2$ 个元素
  • 第 $k$ 层链表平均有 $n * p^k$ 个元素
  • ……

另外，最高层的层数是 $log_{\frac{1}{p}}n$，平均有 $\frac{1}{p}$ 个元素。在搜索时，每一层链表的预期查找步数最多是 $\frac{1}{p}$，所以总的查找步数是 $\frac{1}{p}*log_{\frac{1}{p}}n = – \frac {log_{p}{n}}{p}$，时间复杂度是 $O(logn)$。