跳表

   数据结构与算法 / 数据结构 26 分钟读完 (大约3916个字)0次访问

跳表

一、什么是跳表？

跳表，又叫做跳跃表、跳跃列表。

  • 是一种对有序链式线性表的优化
  • 在原始链表的基础上添加了多级索引链表
  • 分为多层，从下往上分别是原始链表、一级索引、二级索引…
  • 搜索时从上往下，实现了类似“二分查找”的功能

它的结构大概是这样的：

1
2
3
4
5
6
7
8
 ___                                 ___
| 1 | ----------------------------> | 5 |                -- 二级索引
  |                                   |
 ___               ___               ___
| 1 | ----------> | 3 | ----------> | 5 |                -- 一级索引
  |                 |                 |
 ___      ___      ___      ___      ___      ___
| 1 | -> | 2 | -> | 3 | -> | 4 | -> | 5 | -> | 6 |       -- 原始链表

跳表就是对有序链表的一种优化，通过添加多级索引来提升性能。

跳表本质上是一种利用空间来换时间的数据结构。

二、为什么要用跳表？

2.1 引入背景

对于链表来说，查找某个值，只能通过遍历的方式实现，时间复杂度是 O(n)。

即使链表是有序的，依旧也只能是从头到尾遍历，完全没有用到数据的有序性。

1
2
 ___      ___      ___      ___      ___      ___
| 1 | -> | 2 | -> | 3 | -> | 4 | -> | 5 | -> | 6 |

在这种情况下，有没有办法用到链表的有序性？

  • 给链表建立索引，方便快速定位数据的区间范围

比如说，链表的每2个节点就提取出一个索引节点：

1
2
3
4
5
 ___               ___               ___
| 1 | ----------> | 3 | ----------> | 5 |                -- 索引
  |                 |                 |
 ___      ___      ___      ___      ___      ___
| 1 | -> | 2 | -> | 3 | -> | 4 | -> | 5 | -> | 6 |       -- 原始链表

通过索引先快速定位到区间 [1, 3]、[3, 5] 以及 [5, +]，缩小范围，再小范围遍历搜索。

比如说，查找数值 4：

  1. 首先在索引层遍历判断，发现 4 是在区间 [3, 5] 内的
  2. 然后找到了原始链表的 3，再从 3 开始往右遍历，直到找到 4

4 的搜索链路就是：1 -> 3 -> 4，这定位速度就比遍历快多了。

有时候建第一层索引后，遍历范围还是很大（第一层索引的节点数量是 n/2）。

这个时候还可以再往上多建几层索引：

1
2
3
4
5
6
7
8
 ___                                 ___
| 1 | ----------------------------> | 5 |                -- 二级索引
  |                                   |
 ___               ___               ___
| 1 | ----------> | 3 | ----------> | 5 |                -- 一级索引
  |                 |                 |
 ___      ___      ___      ___      ___      ___
| 1 | -> | 2 | -> | 3 | -> | 4 | -> | 5 | -> | 6 |       -- 原始链表

这种在原始链表上建多层索引，实现快速查找的数据结构，就是跳表。

2.2 算法分析

原始有序链表的算法复杂度是：

  • 搜索：时间 O(n)，空间 O(1)
  • 删除：时间 O(n)，空间 O(1)
  • 插入：时间 O(n)，空间 O(1)

跳表的算法复杂度如何呢？以 2 个节点 1 个索引的跳表为例。

1）空间复杂度

跳表的多层索引，从下往上数的话，节点数量分别是：

1
n/2, n/4, n/8, ..., 2

总共是 n/2 + n/4 + ... + 2 = n - 2，也就是说：

  • 跳表结构本身的空间复杂度是 O(n)

2）时间复杂度

根据上面的结构，跳表的层级数量很容易知道：

  • 跳表的索引层级数量是 logn

链表的插入和删除，实际上是依赖于搜索，所以只要分析搜索的时间复杂度即可。

因为每 2 个节点对应 1 个索引节点，所以每一层的搜索节点数量不会超过 3。

比如上一层索引确定了区间 [3, 5]，那么往下一层搜索，搜索只能是 3,4,5。

因此跳表的时间复杂度，依赖于每层遍历的节点数量：

  • 搜索：时间 O(m * logn)
  • 删除：时间 O(m * logn)
  • 插入：时间 O(m * logn)

其中 m 是每层最多遍历的节点数量。

跳表将原始链表的时间复杂度从 O(n) 提升到了 O(logn) 级别。

当然，这是利用空间换时间才得到的，空间消耗变多了。

三、跳表如何实现？

跳表的实现方式可以分为2种：

  • 数组实现：由一个数组实现，数组内部包含多层索引指针
  • 链表实现：有多条链表实现，每条链表一层索引

它们的区别只在于底层存储不同，对外是一致的。

下面以链表实现为例，说明跳表的实现。

3.1 跳表的定义

3.1.1 结构定义

为了减少代码中的判空，采用了一个哨兵头节点，所以实际的跳表结构是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
head
 ___
|   | ---------------------------------------------------------> null
  |
 ___      ___                                 ___
|   | -> | 1 | ----------------------------> | 5 | ------------> null
  |        |                                   |
 ___      ___               ___               ___
|   | -> | 1 | ----------> | 3 | ----------> | 5 | ------------> null
  |        |                 |                 |
 ___      ___      ___      ___      ___      ___      ___
|   | -> | 1 | -> | 2 | -> | 3 | -> | 4 | -> | 5 | -> | 6 | ---> null

顶层的 head 节点单独一层，并且这一层只有它一个非空节点。

3.1.2 接口定义

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
public interface SkipList<T extends Comparable<T>> {

    /**
     * 搜索指定值是否存在
     *
     * @param value 指定值
     * @return true存在/false不存在
     */
    boolean search(T value);

    /**
     * 添加新值
     *
     * @param value 新值
     */
    void add(T value);

    /**
     * 删除指定值
     *
     * @param value 指定值
     * @return true删除成功/false删除失败
     */
    boolean erase(T value);

}

3.1.3 链式跳表的定义

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class LinkedSkipList<T extends Comparable<T>> implements SkipList<T> {

    class Node {
        // 节点值
        T value;
        // 同一层的右侧节点指针
        Node right;
        // 下一层的同值节点指针
        Node down;

        public Node(T value, Node right, Node down) {
            this.value = value;
            this.right = right;
            this.down = down;
        }
    }

}

3.2 跳表的搜索

3.2.1 代码实现

跳表的搜索，就是从顶层的索引开始，一层一层往下找，直到找对对应的节点为止。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean search(T value) {
    Node p = head, q = null;
    // 从上往下一直找，直到最底层的原始链表为止
    while (p != null) {
        // 在当前层遍历搜索，直到找到 value 所在区间
        while (p.right != null && value.compareTo(p.right.value) > 0) {
            p = p.right;
        }
        // 搜索下一层
        q = p;
        p = p.down;
    }
    // 验证节点值是否相等
    return q != null && q.right != null && q.right.value.equals(value);
}

3.2.2 结构示意

搜索过程就类似下面这样（暂时忽略其他线）：

1
2
3
4
5
6
7
8
9
10
11
12
head
 ___
|   |
  |
 ___      ___                                 ___
|   | -> | 1 |                               | 5 |
           |                                    
 ___      ___               ___               ___
|   |    | 1 | ----------> | 3 |             | 5 |
                             |                  
 ___      ___      ___      ___      ___      ___      ___
|   |    | 1 |    | 2 |    | 3 | -> | 4 |    | 5 |    | 6 |

很简单，就是一层一层找符合范围的区间，直到最底层的原始链表。

3.3 跳表的插入

3.3.1 代码实现

插入节点，除了要知道插入点的位置，还要知道上一层跳到下一层的转折节点。

因为插入节点，不仅仅是插入最底层，上面的索引层也需要一起更新。

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
/**
 * 查找指定值的前置路径
 *
 * @param value 指定值
 * @return 前置路径
 */
private List<Node> findProcessors(T value) {
    Deque<Node> stack = new ArrayDeque<>();
    Node p = head;
    // 从上往下一直找，直到最底层的原始链表为止
    while (p != null) {
        // 在当前层遍历搜索，直到找到 value 所在区间
        while (p.right != null && value.compareTo(p.right.value) > 0) {
            p = p.right;
        }
        // 记录上一层节点
        stack.push(p);
        // 搜索下一层
        p = p.down;
    }

    // 路径是倒序摆放的，最接近值 value 的在索引 0 的位置
    List<Node> path = new ArrayList<>(stack.size());
    while (!stack.isEmpty()) {
        path.add(stack.pop());
    }
    return path;
}

查找返回的是目标节点的前置路径：

  • 前置路径是搜索过程中上一层跳到下一层的那个转折节点列表

比如上面搜索 4 时，搜索路径是 1->3->4，那么得到的前置路径就是 [3, 1]。

为什么前置路径是倒序的？

  • 因为插入节点是从下往上插入的，为了方便就倒序返回了

找到前置路径后，就可以准备插入节点了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public void add(T value) {
    List<Node> processors = findProcessors(value);
    int levels = processors.size();

    Node newNode = null;
    boolean insertUp = true;
    for (int i = 0; i < levels && insertUp; i++) {
        Node processor = processors.get(i);
        // 新节点指向下一层的同值节点
        newNode = new Node(value, processor.right, newNode);
        // 在当前层插入新节点
        processor.right = newNode;

        // 是否要继续往上一层插入节点
        insertUp = random.nextDouble() < FACTOR;
    }

    // 更新层级
    if (insertUp) {
        levelUp();
    }
}

3.3.2 结构示意

比如插入前跳表的结构是这样的：

1
2
3
4
5
6
7
8
9
10
11
12
head
 ___
|   | ---------------------------------------------------------> null
  |
 ___      ___                                 ___
|   | -> | 1 | ----------------------------> | 5 | ------------> null
  |        |                                   |
 ___      ___                                 ___
|   | -> | 1 | ----------------------------> | 5 | ------------> null
  |        |                                   |
 ___      ___      ___               ___      ___      ___
|   | -> | 1 | -> | 2 | ----------> | 4 | -> | 5 | -> | 6 | ---> null

此时插入一个 3，插入过程是从下往上的：

1）第一次插入

1
2
3
4
5
6
7
8
9
10
11
12
head
 ___
|   | ---------------------------------------------------------> null
  |
 ___      ___                                 ___
|   | -> | 1 | ----------------------------> | 5 | ------------> null
  |        |                                   |
 ___      ___                                 ___
|   | -> | 1 | ----------------------------> | 5 | ------------> null
  |        |                                   |
 ___      ___      ___      ___      ___      ___      ___
|   | -> | 1 | -> | 2 | -> | 3 | -> | 4 | -> | 5 | -> | 6 | ---> null

2）第二次插入

1
2
3
4
5
6
7
8
9
10
11
12
head
 ___
|   | ---------------------------------------------------------> null
  |
 ___      ___                                 ___
|   | -> | 1 | ----------------------------> | 5 | ------------> null
  |        |                                   |
 ___      ___               ___               ___
|   | -> | 1 | ----------> | 3 | ----------> | 5 | ------------> null
  |        |                 |                 |
 ___      ___      ___      ___      ___      ___      ___
|   | -> | 1 | -> | 2 | -> | 3 | -> | 4 | -> | 5 | -> | 6 | ---> null

至于需要插入多少层，这个是通过随机数控制的。

采用了随机数 random.nextDouble() < FACTOR，来判断要不要往上一层插入节点。

为什么采用随机数？

  • 为了减少算法代码的复杂度
  • 同时又尽量确保跳表的结构平衡

跳表本身代码就比较简单，如果为了维持结构而引入其他复杂算法，显得得不偿失。

随机数就很合适，使用不复杂，而且能大概率保证跳表结构不会严重退化。

3.3.3 提升层级

如果节点被插入到了顶层，这个时候需要提升整个跳表的层级。

比如 3 节点被插入到顶层后，跳表结构变成了这样：

1
2
3
4
5
6
7
8
9
10
11
12
head
 ___                        ___
|   | -------------------> | 3 | ------------------------------> null
  |
 ___      ___               ___               ___
|   | -> | 1 | ----------> | 3 | ----------> | 5 | ------------> null
  |        |                 |                 |
 ___      ___               ___               ___
|   | -> | 1 | ----------> | 3 | ----------> | 5 | ------------> null
  |        |                 |                 |
 ___      ___      ___      ___      ___      ___      ___
|   | -> | 1 | -> | 2 | -> | 3 | -> | 4 | -> | 5 | -> | 6 | ---> null

为了维持跳表头节点在单独一层的结构，就需要提升层级：

1
2
3
4
5
6
7
/**
 * 提升层级
 */
private void levelUp() {
    // 最上层只有一个头节点
    head = new Node(null, null, head);
}

提升层级后，跳表的结构就恢复正常了：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
head
 ___
|   | ---------------------------------------------------------> null
  |
 ___                        ___
|   | -------------------> | 3 | ------------------------------> null
  |
 ___      ___               ___               ___
|   | -> | 1 | ----------> | 3 | ----------> | 5 | ------------> null
  |        |                 |                 |
 ___      ___               ___               ___
|   | -> | 1 | ----------> | 3 | ----------> | 5 | ------------> null
  |        |                 |                 |
 ___      ___      ___      ___      ___      ___      ___
|   | -> | 1 | -> | 2 | -> | 3 | -> | 4 | -> | 5 | -> | 6 | ---> null

3.4 跳表的删除

3.4.1 代码实现

删除和插入过程是一样的，都是先找到前置路径后，再处理节点：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public boolean erase(T value) {
    List<Node> processors = findProcessors(value);

    // 验证删除节点是否存在，没有找到则直接返回
    Node target = processors.get(0).right;
    if (target == null || !value.equals(target.value)) {
        return false;
    }

    // 从下往上，逐层删除指定节点
    for (Node processor : processors) {
        // 指定 value 值的节点在每一层都删完了，就跳出循环
        Node delNode = processor.right;
        if (delNode == null || !delNode.value.equals(value)) {
            break;
        }
        processor.right = delNode.right;
    }

    // 更新层级
    levelDown();

    return true;
}

3.4.2 结构示意

删除也和插入一样，是从下往上的。比如删除 3：

1）第一次删除

1
2
3
4
5
6
7
8
9
10
11
12
head
 ___
|   | ---------------------------------------------------------> null
  |
 ___      ___                                 ___
|   | -> | 1 | ----------------------------> | 5 | ------------> null
  |        |                                   |
 ___      ___               ___               ___
|   | -> | 1 | ----------> | 3 | ----------> | 5 | ------------> null
  |        |                                   |
 ___      ___      ___               ___      ___      ___
|   | -> | 1 | -> | 2 | ----------> | 4 | -> | 5 | -> | 6 | ---> null

2）第二次删除

1
2
3
4
5
6
7
8
9
10
11
12
head
 ___
|   | ---------------------------------------------------------> null
  |
 ___      ___                                 ___
|   | -> | 1 | ----------------------------> | 5 | ------------> null
  |        |                                   |
 ___      ___                                 ___
|   | -> | 1 | ----------------------------> | 5 | ------------> null
  |        |                                   |
 ___      ___      ___               ___      ___      ___
|   | -> | 1 | -> | 2 | ----------> | 4 | -> | 5 | -> | 6 | ---> null

3.4.3 降低层级

删除节点后，有可能导致跳表的上层节点变得比较少，此时需要降低层级。

比如把 1 和 5 都删掉后：

1
2
3
4
5
6
7
8
9
10
11
12
head
 ___
|   | ---------------------------------------------------------> null
  |
 ___                                          
|   | ---------------------------------------------------------> null
  |                                             
 ___                                      
|   | ---------------------------------------------------------> null
  |                                             
 ___               ___               ___               ___
|   | ----------> | 2 | ----------> | 4 | ----------> | 6 | ---> null

上面几层链表都空了，浪费空间，这个时候需要将这些节点很少的层级删除：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
/**
 * 降低层级
 */
private void levelDown() {
    while (head.down != null) {
        // 连续 2 层为空时，才降低层级，因为最上层只有 1 个头节点
        if (head.right != null || head.down.right != null) {
            break;
        }
        Node p = head;
        head = head.down;
        p.down = null;
    }
}

删除后，跳表又恢复成正常的结构了：

1
2
3
4
5
6
head
 ___
|   | ---------------------------------------------------------> null
  |                                             
 ___               ___               ___               ___
|   | ----------> | 2 | ----------> | 4 | ----------> | 6 | ---> null

四、跳表的应用场景

跳表设计的目的，是为了快速查找。所以它比较适合这些场景：

  • 是有序链表，无序链表用不了
  • 多次查询链表，注意是多次，只查一次的话不如直接遍历
  • 较少的插入和删除，虽然跳表的插入删除性能不差，但是其目的不在于此

其实本质上，

  • 跳表就是二分查找的链表实现版本

所以有序数组二分查找适用的场景，基本适用于有序链表的跳表。

参考

https://leetcode.cn/problems/design-skiplist/

https://blog.csdn.net/yjw123456/article/details/105159817/

https://blog.csdn.net/weixin_45480785/article/details/116293416

https://baijiahao.baidu.com/s?id=1710441201075985657&wfr=spider&for=pc

附录

跳表接口

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
/**
 * 跳表接口
 *
 * @author weijiaduo
 * @since 2022/7/28
 */
public interface SkipList<T extends Comparable<T>> {

    /**
     * 搜索指定值是否存在
     *
     * @param value 指定值
     * @return true存在/false不存在
     */
    boolean search(T value);

    /**
     * 添加新值
     *
     * @param value 新值
     */
    void add(T value);

    /**
     * 删除指定值
     *
     * @param value 指定值
     * @return true删除成功/false删除失败
     */
    boolean erase(T value);

}

链表实现

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
/**
 * 跳表（链表）
 *
 * @author weijiaduo
 * @since 2022/7/28
 */
public class LinkedSkipList<T extends Comparable<T>> implements SkipList<T> {

    class Node {
        T value;
        Node right;
        Node down;

        public Node(T value, Node right, Node down) {
            this.value = value;
            this.right = right;
            this.down = down;
        }
    }

    /**
     * 默认最大层级
     */
    static final int DEFAULT_MAX_LEVEL = 32;
    /**
     * 随机因子
     */
    static final double FACTOR = 0.25;

    /**
     * 哨兵头节点
     */
    Node head;
    /**
     * 最大层级
     */
    int maxLevels;
    /**
     * 随机数
     */
    Random random = new Random();

    public LinkedSkipList() {
        this(DEFAULT_MAX_LEVEL);
    }

    public LinkedSkipList(int maxLevels) {
        this.maxLevels = maxLevels;
        this.head = new Node(null, null, null);
    }

    @Override
    public boolean search(T value) {
        Node p = head, q = null;
        // 从上往下一直找，直到最底层的原始链表为止
        while (p != null) {
            // 在当前层遍历，直到找到 value 所在区间
            while (p.right != null && value.compareTo(p.right.value) > 0) {
                p = p.right;
            }
            // 记录上一层的转折点
            q = p;
            // 搜索下一层
            p = p.down;
        }
        return q != null && q.right != null && q.right.value.equals(value);
    }

    @Override
    public void add(T value) {
        List<Node> processors = findProcessors(value);
        int levels = processors.size();

        Node newNode = null;
        boolean insertUp = true;
        for (int i = 0; i < levels && insertUp; i++) {
            Node processor = processors.get(i);
            // 新节点指向下一层的同值节点
            newNode = new Node(value, processor.right, newNode);
            // 在当前层插入新节点
            processor.right = newNode;

            // 是否要继续往上一层插入节点
            insertUp = random.nextDouble() < FACTOR;
        }

        // 更新层级
        if (insertUp) {
            levelUp();
        }
    }

    @Override
    public boolean erase(T value) {
        List<Node> processors = findProcessors(value);

        // 验证删除节点是否存在，没有找到则直接返回
        Node target = processors.get(0).right;
        if (target == null || !value.equals(target.value)) {
            return false;
        }

        // 从下往上，逐层删除指定节点
        for (Node processor : processors) {
            // 指定 value 值的节点在每一层都删完了，就跳出循环
            Node delNode = processor.right;
            if (delNode == null || !delNode.value.equals(value)) {
                break;
            }
            processor.right = delNode.right;
        }

        // 更新层级
        levelDown();

        return true;
    }

    /**
     * 提升层级
     */
    private void levelUp() {
        // 最上层只有一个头节点
        head = new Node(null, null, head);
    }

    /**
     * 降低层级
     */
    private void levelDown() {
        while (head.down != null) {
            // 连续 2 层为空时，才降低层级，因为最上层只有 1 个头节点
            if (head.right != null || head.down.right != null) {
                break;
            }
            Node p = head;
            head = head.down;
            p.down = null;
        }
    }

    /**
     * 查找指定值的前置路径
     *
     * @param value 指定值
     * @return 前置路径
     */
    private List<Node> findProcessors(T value) {
        Deque<Node> stack = new ArrayDeque<>();
        Node p = head;
        // 从上往下一直找，直到最底层的原始链表为止
        while (p != null) {
            // 在当前层遍历，直到找到 value 所在区间
            while (p.right != null && value.compareTo(p.right.value) > 0) {
                p = p.right;
            }
            // 记录上一层的转折点
            stack.push(p);
            // 搜索下一层
            p = p.down;
        }

        // 路径是倒序摆放的，最接近值 value 的在索引 0 的位置
        List<Node> path = new ArrayList<>(stack.size());
        while (!stack.isEmpty()) {
            path.add(stack.pop());
        }
        return path;
    }

}

数组实现

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
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
/**
 * 跳表（数组实现）
 *
 * @author weijiaduo
 * @since 2022/7/27
 */
public class ArraySkipList<T extends Comparable<T>> implements SkipList<T> {

    class Node {
        T value;
        List<Node> forwards;

        Node(T value, int levels) {
            this.value = value;
            forwards = new ArrayList<>(levels);
            for (int i = 0; i < levels; i++) {
                forwards.add(null);
            }
        }
    }

    /**
     * 默认最大层级
     */
    static final int DEFAULT_MAX_LEVEL = 32;
    /**
     * 随机因子
     */
    static final double FACTOR = 0.25;

    /**
     * 哨兵头节点
     */
    Node head;
    /**
     * 当前层级
     */
    int levels = 0;
    /**
     * 最大层级
     */
    int maxLevels;
    /**
     * 随机数
     */
    Random random = new Random();

    public ArraySkipList() {
        this(DEFAULT_MAX_LEVEL);
    }

    public ArraySkipList(int maxLevels) {
        this.maxLevels = maxLevels;
        head = new Node(null, maxLevels);
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean search(T value) {
        Node p = head, q = null;
        // 从上往下一直找，直到最底层的原始链表为止
        for (int i = levels - 1; i >= 0; i--) {
            // 在当前层遍历，直到找到 value 所在区间
            Node right = p.forwards.get(i);
            while (right != null && value.compareTo(right.value) > 0) {
                p = right;
                right = p.forwards.get(i);
            }
            // 记录上一层的转折点
            q = p;
        }
        if (q != null) {
            Node target = q.forwards.get(0);
            return target != null && value.equals(target.value);
        }
        return false;
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public void add(T value) {
        List<Node> processors = findProcessors(value);
        int lv = randomLevel();
        levels = Math.max(levels, lv);
        Node newNode = new Node(value, levels);
        for (int i = 0; i < lv; i++) {
            Node processor = processors.get(i);
            newNode.forwards.set(i, processor.forwards.get(i));
            processor.forwards.set(i, newNode);
        }
    }

    /**
     * {@inheritDoc}
     */
    @Override
    public boolean erase(T value) {
        List<Node> processors = findProcessors(value);
        Node target = processors.get(0).forwards.get(0);
        if (target == null || !value.equals(target.value)) {
            return false;
        }

        // 从下往上，逐层删除指定节点
        for (int i = 0; i < levels; i++) {
            Node processor = processors.get(i);
            Node delNode = processor.forwards.get(i);
            if (delNode == null || delNode != target) {
                break;
            }
            processor.forwards.set(i, delNode.forwards.get(i));
        }

        // 降低层级，最顶层只有头节点时
        for (; levels > 1; levels--) {
            if (head.forwards.get(levels - 1) != null) {
                break;
            }
        }

        return true;
    }

    /**
     * 查找指定值的前置路径
     *
     * @param value 指定值
     * @return 前置路径
     */
    private List<Node> findProcessors(T value) {
        List<Node> path = new ArrayList<>(maxLevels);
        for (int i = 0; i < maxLevels; i++) {
            path.add(head);
        }
        Node p = head;
        for (int i = levels - 1; i >= 0; i--) {
            // 在当前层遍历，直到找到 value 所在区间
            Node right = p.forwards.get(i);
            while (right != null && value.compareTo(right.value) > 0) {
                p = right;
                right = p.forwards.get(i);
            }
            // 记录上一层的转折点
            path.set(i, p);
        }
        return path;
    }

    /**
     * 随机层级
     * <p>
     * 这个随机有点影响时间
     *
     * @return 随即层级
     */
    private int randomLevel() {
        int lv = 1;
        while (lv < maxLevels && random.nextDouble() < FACTOR) {
            lv++;
        }
        return lv;
    }

}

跳表

http://example.com/datastructure/list/skiplist/

作者

jiaduo

发布于

2022-09-18

更新于

2023-04-03

许可协议

 
×