Redis 源码分析跳跃表（skiplist）_redis skiplist源码

跳跃表特点
1、按照 score 来排序，如果 score 相等，那么则按照 ele 来排序。

2、平均查询时间复杂度 O(logn)。

跳跃表实现
跳跃表是由 server.h/zskiplistNode 和 server.h/zskiplist 两个结构定义其中

zskiplistNode 结构用于订阅跳跃表的节点，而 zskiplist 结构用于保存跳跃表相关的信息，比如节点的数量，以及想表头节点和表尾节点的指针等

跳跃表实现 server.h/zskiplistNode 结构定义：

/* ZSETs use a specialized version of Skiplists */
typedef struct zskiplistNode {
    //数据
    sds ele;
    //分值
    double score;
    //后退指针
    struct zskiplistNode *backward;
    //层
    struct zskiplistLevel {
        //前进指针
        struct zskiplistNode *forward;
        //跨度
        unsigned long span;
    } level[];
} zskiplistNode;
​
复制代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

zskiplist 结构定义如下：

typedef struct zskiplist {
    //头节点和尾节点
    struct zskiplistNode *header, *tail;
    //表中节点的数量
    unsigned long length;
    //表中层数最大的节点层数
    int level;
} zskiplist;
复制代码
1
2
3
4
5
6
7
8
9

以 zskiplist 为基础的数据结构图如下：

运用场景
跳跃表是有序集合（zset）的底层实现之一
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;
复制代码
设计跳表
力扣题目（1206）:
不使用任何库函数，设计一个 跳表 。

跳表 是在 O(log(n)) 时间内完成增加、删除、搜索操作的数据结构。跳表相比于树堆与红黑树，其功能与性能相当，并且跳表的代码长度相较下更短，其设计思想与链表相似。

例如，一个跳表包含 [30, 40, 50, 60, 70, 90] ，然后增加 80、45 到跳表中，以下图的方式操作：

Artyom Kalinin [CC BY-SA 3.0], via Wikimedia Commons

跳表中有很多层，每一层是一个短的链表。在第一层的作用下，增加、删除和搜索操作的时间复杂度不超过 O(n)。跳表的每一个操作的平均时间复杂度是 O(log(n))，空间复杂度是 O(n)。

了解更多 : https://en.wikipedia.org/wiki/Skip_list

在本题中，你的设计应该要包含这些函数：

bool search(int target) : 返回target是否存在于跳表中。
void add(int num): 插入一个元素到跳表。
bool erase(int num): 在跳表中删除一个值，如果 num 不存在，直接返回false. 如果存在多个 num ，删除其中任意一个即可。
注意，跳表中可能存在多个相同的值，你的代码需要处理这种情况。

示例 1:

输入

["Skiplist", "add", "add", "add", "search", "add", "search", "erase", "erase", "search"]
[[], [1], [2], [3], [0], [4], [1], [0], [1], [1]]
1
2

输出

[null, null, null, null, false, null, true, false, true, false]
1

解释

Skiplist skiplist = new Skiplist();
skiplist.add(1);
skiplist.add(2);
skiplist.add(3);
skiplist.search(0);   // 返回 false
skiplist.add(4);
skiplist.search(1);   // 返回 true
skiplist.erase(0);    // 返回 false，0 不在跳表中
skiplist.erase(1);    // 返回 true
skiplist.search(1);   // 返回 false，1 已被擦除
复制代码
1
2
3
4
5
6
7
8
9
10
11

提示:

0 <= num, target <= 2 * 104
1

调用search,add, erase 操作次数不大于 5 * 104
解题代码
下面是参考 redis 的 skiplist 的实现。代码如下：

public class Skiplist {
    private static final float SKIPLIST_P = 0.5f;
    private static final int MAX_LEVEL = 16;
    
    // 头节点
    Node head;

    // 节点对象
    class Node {
        int val;
        Node bw;   // 后退指针
        Node[] fw; // 前进指针
​
        // 构造函数
        public Node(int val) {
            this.val = val;
            fw = new Node[randomLevel()];
        }
​
        public Node(int val, int size) {
            this.val = val;
            fw = new Node[size + 1];
        }

        // 生成随机 level
        public int randomLevel() {
            int level = 1;
            while (Math.random() < SKIPLIST_P && level < MAX_LEVEL) {
                level++;
            }
            return level;
        }
    }
​
    // 生成默认的头节点
    public Skiplist() {
        head = new Node(-1, MAX_LEVEL);
    }

    // 查询
    public boolean search(int target) {
        Node p = searchNode(target);
        boolean b = p.val == target;
        //System.out.println(b);
        return b;
    }
    
    // 添加
    public void add(int num) {
        Node p = searchNode(num);
        Node n = new Node(num);
        n.bw = p;
        for (int i = 0; i < n.fw.length; i++) {
            Node f = p;
            while (f.bw != null && f.fw.length < i + 1) {
                f = f.bw;
            }
            if (i == 0 && f.fw[i] != null) {
                f.fw[i].bw = n;
            }
            n.fw[i] = f.fw[i];
            f.fw[i] = n;
        }
    }
    
    // 移除
    public boolean erase(int num) {
        if (isEmpty()) {
            //System.out.println(false);
            return false;
        }
        Node p = searchNode(num);
        if (p.val != num) {
            //System.out.println(false);
            return false;
        }
        for (int i = 0; i < p.fw.length; i++) {
            Node f = p.bw;
            while (f.bw != null && f.fw.length < i + 1) {
                f = f.bw;
            }
            if (i == 0 && f.fw[i].fw[i] != null) {
                f.fw[i].fw[i].bw = f;
            }
            f.fw[i] = f.fw[i].fw[i];
        }
        //System.out.println(true);
        return true;
    }
    
    // 查询节点
    private Node searchNode(int target) {
        if (isEmpty()) {
            return head;
        }
        Node p = head;
        for (int i = MAX_LEVEL; i >= 0; i--) {
            while (p.fw[i] != null && p.fw[i].val <= target) {
                p = p.fw[i];
            }
        }
        return p;
    }
    
    // 是否为空
    private boolean isEmpty() {
        return head.fw[0] == null;
    }
}
复制代码
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

执行示例（执行结果）：

最后
如果你觉得此文对你有一丁点帮助，点个赞。或者可以加入我的开发交流群：1025263163相互学习，我们会有专业的技术答疑解惑

如果你觉得这篇文章对你有点用的话，麻烦请给我们的开源项目点点star:http://github.crmeb.net/u/defu不胜感激 ！

PHP学习手册：https://doc.crmeb.com
技术交流论坛：https://q.crmeb.com