紫夜の博客 HomeArchivesTagsCategories
跳表的研究与实现
|数据结构
字数总计: 2.2k|阅读时长: 8 分钟

跳表的基本原理介绍我是从极客学院王争老师的课程中了解到的，由于其实现相比红黑树简单，并且有与之媲美的性能，便想要实现一下，但纸上得来终觉浅，实际编码过程中遇到了不少的困难，希望本文对大家实现跳表有所帮助。

原理

待补充，可先移步至csdn相关博客，内容和王争老师文章差别不大

实现

本文采用java语言实现，为了让删除的时间复杂度达到O(1),采用了双链表结构，代码地址在我的Github数据结构专栏。

节点数据结构

首先说下节点的数据结构代码

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
/**
 * 用双链表存储
 */
class Node {
    private Integer data;

    private Node[] forwards;

    // 为删除等操作提供O(1)
    private Node[] previous;

    public Node(Integer data, int level) {
        this.data = data;
        // ++level , level层有level+1个后继节点
        forwards = new Node[level];
        previous = new Node[level];
    }

    @Override
    public String toString() {
        return data == null ? "" : String.valueOf(data);
    }

    /**
     * 获取节点在level层的下一个节点
     */
    public Node boyNextDoor(int level) {
        return forwards[level];
    }

    public Node previous(int level) {
        return previous[level];
    }
}

可以看到有两个数组，相信一开始很多人和我一样百思不得解两个数组是干什么的，相信大家见到的跳表差不多是这样的
跳表1
上图红线给出了查找20的路径，一开始我也觉得很好理解，但随即两个问题困扰了我很久

  1. 图中有必要每层都存数据域吗，比如图中的10，为什么有5个？一个数据域+N和前后指针就可以了啊
  2. 向下的箭头怎么表示？ 再来个down指针？

在找跳表相关文章时，看到一位作者引用了跳表的论文，点进去一看有种恍然大悟的感觉，跳表其实应该是这样的
跳表2

于是我又手绘了一张跳表的结构图(省略了前驱指针)，一边画一边思考，发现问题1和问题2解决之后变得很简单
跳表3
最终得到了上面的代码，而forwards正是红色部分表示的后驱指针，这个后驱指针数组的长度完全取决于它所在的层数，但HEAD节点默认初始化为最大层数

可以看到previous和boyNextDoor(手动斜眼)两个方法提供了获取一个节点在x层上获取前驱和后继节点的能力

初始化及成员变量介绍

成员变量如下

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
/**
 * 最高16层
 */
private static int MAX_LEVEL = 16;

/**
 * head节点
 */
private Node head;

/**
 * 元素个数
 */
private int size;

/**
 * 跳表高度, 从1开始算
 */
private int height;

/**
 * 用于随机节点所在层数
 */
private Random random = new Random();

构造函数

1
2
3
4
5
6
7
/**
 * 初始化数据
 */
public SkipList() {
    head = new Node(null, MAX_LEVEL);
    height = 1;
}

公共方法findFirstGreater

在讲解插入，删除，查找之前，先介绍findFirstGreater方法，这是一个简单且重要的公共方法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 *
 * @param data    要查找的数据
 * @param current 查询的起始节点
 * @param level   要查找的层数
 * @return 如果当前节点的下一个节点比data大(不能包含等于)，返回当前节点
 */
private Node findFirstGreater(int data, Node current, int level) {
    Node nextDoor = current.boyNextDoor(level);
    // current在后，nextDoor在前，两个同时往右走， 就像两个快慢指针
    // 只要发现nextDoor比data大，直接返回current
    while (nextDoor != null) {
        // 这个if写到while里也可以
        if (data < nextDoor.data) {
            break;
        }
        // 往前走一个
        current = nextDoor;
        nextDoor = current.boyNextDoor(level); 
    }
    // 当前层没有比data大的，但是下一层可能有
    return current;
}

无论是查找，插入，删除，我们都要找到第一个比data大的节点的前一个节点,假设data=5，链表为 2 3(5) 7, 第一个大于5的是7，则返回3(5)，该值<=5

插入

插入的思路是这样的，首先通过随机函数决定节点有多高，当然最高不超过MAX_LEVEL，这个随机算法直接从redis源码里拿过来的，然后在每一层通过findFirstGreater方法找到第一个比data大的节点的前一个节点，剩下的就是双链表的插入了

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
public void insert(int data) {
	// 先判断是否已经存在
    if (contains(data)) {
        return;
    }

    // 构造节点
    int level = randomLevel();
    Node newNode = new Node(data, level);
    // 必须先赋值，下面开始--了，或者用临时变量保存
    if (level > height) {
        height = level;
    }
    // level-1， 下面的leve都用做forwards数组的下标了
    level--;
    // 从上往下插入
    Node current = head;
    while (level >= 0) {
        // 最关键的一行代码
        current = findFirstGreater(data, head, level);
        // 双链表插入
        Node nextDoor = current.boyNextDoor(level);
        newNode.forwards[level] = nextDoor;
        newNode.previous[level] = current;
        current.forwards[level] = newNode;
        if (nextDoor != null)
            nextDoor.previous[level] = newNode;
        // 体会level-1对findFirstGreater方法影响，是不是达到了节点向下一层的目的？问题2搞定
        level--;
    }
    size++;

}

contains方法

contains的实现很简单，就是调用了查找方法

1
2
3
4
public boolean contains(int data) {
    Node node = find(data);
    return node != null && node.data != null && data == node.data;
}

随机算法

返回1到MAX_LEVEL之间的随机数，符合正态分布

1
2
3
4
5
6
7
8
9
private int randomLevel() {
    // the following implementation is basically as same as Redis ZSET implementation
    // see https://github.com/antirez/redis/blob/4.0/src/t_zset.c
    int newLevel = 1;
    while ((random.nextInt() & 0xFFFF) < (0xFFFF >> 2)) {
        newLevel++;
    }
    return (newLevel < MAX_LEVEL) ? newLevel : MAX_LEVEL;
}

查找

查找就是我们所熟知的跳表查询方法

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * 查找节点
 */
public Node find(int data) {
    Node node = head;
    int level = height - 1;
    // 必须找到最后一层
    while (level >= 0) {
        node = findFirstGreater(data, node, level);
        level--;
    }
    return node;
}

删除

删除相比查找，需要判断findFirstGreater返回的节点值等于data才能删，然后就是简单的双链表删除操作，过程也很简单

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 void remove(int data) {
    if (!contains(data)) {
        return;
    }
    Node current = head;
    int level = height - 1;
    while (level >= 0) {
        current = findFirstGreater(data, current, level);
        if (current != head && current.data == data) {
            // 双链表删除
            Node previous = current.previous(level);
            Node nextDoor = current.boyNextDoor(level);
            System.out.println(previous.data + "-->" + current.data + "-->" + (nextDoor == null ? "" : nextDoor.data));

            previous.forwards[level] = nextDoor;
            if (nextDoor != null) {
                nextDoor.previous[level] = previous;
            }
            size--;
        }
        // 下一层
        level--;
    }
}

打印

说实话最耽误时间的反而是这个打印功能，我希望打印出如下形式，这我心目中这是最直观的，但这就要考虑两个节点间的空格数量，看我的代码会比较复杂，但只要自己沉下心来认真想一下，相信大家都能很快有思路

1
2
3
level 2:         29                                                                                                                                                                                                                               
level 1:         29          57         148                                                                                                         
level 0: 2 13 18 29 48 50 51 57 131 132 148

我的方式不一定适合每个人，遇到两个节点只是简单的从level0遍历，大数据量不适合

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
public void easyPrint() {
    for (int i = height - 1; i >= 0; i--) {
        System.out.print("level " + i + ": ");
        Node current = head.forwards[i];
        Node next = current.boyNextDoor(i);

        StringBuilder builder = new StringBuilder();
        if (current.data != head.forwards[0].data) {
            builder.append(whiteSpaceHelper(current.data));
        }
        builder.append(current.data);
        while (next != null) {
            builder.append(whiteSpaceHelper(current.data, next.data)).append(next.data);
            current = current.boyNextDoor(i);
            next = next.boyNextDoor(i);
        }
        System.out.println(builder.toString());
    }
}

private String whiteSpaceHelper(int pre, int next) {
    Node current = head.boyNextDoor(0);
    while (current != null) {
        if (current.data == pre) {
            break;
        }
        current = current.boyNextDoor(0);
    }
    Node node = current.boyNextDoor(0);
    int count = 0;
    while (node != null) {
        count++;
        if (node.data == next) {
            break;
        }
        count += node.data.toString().length();
        node = node.boyNextDoor(0);
    }
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < count; i++) {
        builder.append(" ");
    }
    return builder.toString();
}

private String whiteSpaceHelper(int next) {
    Node node = head.forwards[0];
    int count = 0;
    while (node != null) {
        if (node.data == next) {
            break;
        }
        count += node.data.toString().length();
        count++;
        node = node.boyNextDoor(0);
    }
    StringBuilder builder = new StringBuilder();
    for (int i = 0; i < count; i++) {
        builder.append(" ");
    }
    return builder.toString();
}

测试用例

依次对跳表的插入，删除，打印查找做测试

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
public static void main(String[] args) {
    SkipList skipList = new SkipList();
    /*skipList.insert(300);
    skipList.insert(54);
    skipList.insert(14);
    skipList.insert(1010);
    skipList.insert(23);
    skipList.insert(8);
    skipList.insert(325);
    skipList.find(325);
    */
    for (int i = 0; i < 100; i++) {
        int number = skipList.random.nextInt(1000);
        skipList.insert(number);
        if (i == 15) {
            skipList.insert(666);
        }
    }
    skipList.easyPrint();
    skipList.remove(666);

    System.out.println("===================split line=================");
    skipList.easyPrint();

    System.out.println(skipList.find(666));
    System.out.println(skipList.find(1024));
}

回顾

纵观跳表的插入，查找，删除操作，只涉及了简单的查找，双链表的增加，删除节点等基本操作，比起红黑树的实现简单太多，但红黑树在java中有jdk实现，跳表却没有，有些遗憾

跳表与红黑树

跳表与红黑树相比有以下特性

  1. 跳表采用的是空间换时间策略，也就是多了两个指针数组，如果对内存空间十分敏感的场景不太适合，即使是redis也是基于大内存+分布式
  2. 跳表和红黑树都有O(logN)的时间复杂度，并且跳表更易于维护
  3. 跳表适合做区间查找，且十分高效
文章作者: 紫夜
文章链接: https://greedypirate.github.io/2022/09/20/跳表的研究与实现/
版权声明: 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议。转载请注明来自 紫夜の博客！
数据结构