跳表（Skip List）

一. 跳表的定义

1. 跳表，又叫做跳跃表、跳跃列表，在有序链表的基础上增加了“跳跃”的功能
2. 跳表在原来的有序链表上加上了多级索引，通过索引来快速查找；可以支持快速的删除、插入和查找操作。
3. 跳表实际上是一种增加了前向指针的链表，是一种随机化的数据结构
4. Redis中 的 SortedSet、LevelDB 中的 MemTable 都用到了跳表
5. 对比平衡树, 跳表的实现和维护会更加简单, 跳表的搜索、删除、添加的平均时间复杂度是 O(logn)

二. 跳表的数据结构图型

使用跳表优化链表

• 对于一个单链表来讲，即使链表中存储的数据是有序的，如果我们想要在其中查找某个数据，也只能从头开到尾的遍历，查询效率低，时间复杂度是O(n)。

三. 跳表的搜索

跳表查找任意数据的时间复杂度为O(logn)

1. 从顶层链表的首元素开始，从左往右搜索，直至找到一个大于或等于目标的元素，或者到达当前层链表的尾部
2. 如果该元素等于目标元素，则表明该元素已被找到
3. 如果该元素大于目标元素或已到达链表的尾部，则退回到当前层的前一个元素，然后转入下一层进行搜索

四. 跳表的插入

跳表插入的时间复杂度为：O(logn)，支持高效的动态插入。

五. 跳表的删除

跳表的删除操作时间复杂度为：O(logn)，支持动态的删除。

• 在跳表中删除某个结点时，如果这个结点在索引中也出现了，我们除了要删除原始链表中的结点，还要删除索引中的。因为单链表中的删除操作需要拿到删除结点的前驱结点，然后再通过指针操作完成删除。所以在查找要删除的结点的时候，一定要获取前驱结点（双向链表除外）。因此跳表的删除操作时间复杂度即为O(logn)。

六. 跳表索引动态更新

• 当我们不断地往跳表中插入数据时，我们如果不更新索引，就有可能出现某2个索引节点之间的数据非常多的情况，在极端情况下，跳表还会退化成单链表

跳表是通过随机函数来维护“平衡性”。

• 当我们在跳表中插入数据的时候，我们通过选择同时将这个数据插入到部分索引层中，如何选择索引层，可以通过一个随机函数来决定这个节点插入到哪几级索引中，比如随机生成了k，那么就将这个索引加入到，第一级到第k级索引中。

七. 跳表的性质

1. 跳表由很多层结构组成，level是通过一定的概率随机产生的；
2. 每一层都是一个有序的链表，默认是升序 ；
3. 最底层(Level 1)的链表包含所有元素；
4. 如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现；
5. 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

八.Java实现跳表

import java.util.Random;

/**
 * Copyright (c) 2023,
 * All rights reserved
 * Author: hakusai22@qq.com
 */
public class SkipList {
  // 跳表中存储的是正整数，并且存储的数据是不重复的
  private static final int MAX_LEVEL = 16;    // 结点的个数
  private int levelCount = 1;   // 索引的层级数
  private final Node head = new Node();    // 头结点
  private final Random random = new Random();

  // 查找操作
  public Node find(int value) {
    Node p = head;
    for (int i = levelCount - 1; i >= 0; --i) {
      while (p.next[i] != null && p.next[i].data < value) {
        p = p.next[i];
      }
    }

    if (p.next[0] != null && p.next[0].data == value) {
      return p.next[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] = head;
    }

    Node p = head;
    for (int i = level - 1; i >= 0; --i) {
      while (p.next[i] != null && p.next[i].data < value) {
        p = p.next[i];
      }
      update[i] = p;
    }

    for (int i = 0; i < level; ++i) {
      newNode.next[i] = update[i].next[i];
      update[i].next[i] = newNode;
    }
    if (levelCount < level) {
      levelCount = level;
    }
  }

  // 删除操作
  public void delete(int value) {
    Node[] update = new Node[levelCount];
    Node p = head;
    for (int i = levelCount - 1; i >= 0; --i) {
      while (p.next[i] != null && p.next[i].data < value) {
        p = p.next[i];
      }
      update[i] = p;
    }

    if (p.next[0] != null && p.next[0].data == value) {
      for (int i = levelCount - 1; i >= 0; --i) {
        if (update[i].next[i] != null && update[i].next[i].data == value) {
          update[i].next[i] = update[i].next[i].next[i];
        }
      }
    }
  }

  // 随机函数
  private int randomLevel() {
    int level = 1;
    for (int i = 1; i < MAX_LEVEL; ++i) {
      if (random.nextInt() % 2 == 1) {
        level++;
      }
    }

    return level;
  }

  // Node内部类
  public static class Node {
    private int data = -1;
    private final Node[] next = new Node[MAX_LEVEL];
    private int maxLevel = 0;

    // 重写toString方法
    @Override
    public String toString() {
      return "{data:" +
          data +
          "; levels: " +
          maxLevel +
          " }";
    }
  }

  // 显示跳表中的结点
  public void display() {
    Node p = head;
    while (p.next[0] != null) {
      System.out.println(p.next[0] + " ");
      p = p.next[0];
    }
    System.out.println();
  }

}

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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119

测试自定义跳表

最后总结跳表

• 跳表使用的是空间换时间的思想，通过构建多级索引来提高查询效率，实现基于链表的“二分查找”，跳表是一种动态的数据结构，支持快速的查找、插入和删除操作，时间复杂度是 O(logn)。
• 跳表的空间复杂度是 O(n)，不过跳表可以通过改变索引策略，动态的平衡执行效率和内存消耗。