SkipList

SkipList 译为跳跃列表，常简称跳表，是一种用于快速查找的数据结构，由美国计算机科学家 William Pugh（威廉·普） 于 1990 年在论文 Skip lists: A probabilistic alternative to balanced trees 中提出。发明者认为，跳跃列表是在很多应用中有可能替代平衡树而作为实现方法的一种数据结构。跳跃列表的算法有同平衡树一样的渐进的预期时间边界，并且更简单、更快速和使用更少的空间。由于时间复杂度与红黑树相当，且实现简单，两者常常被相互比较。它不像红黑树需要复杂的再平衡，有利于并发操作。

java.util.concurrent 包下有一个 ConcurrentSkipListMap 类，它实现了并发版本的 SkipList，提供了平均 log(n) 时间复杂度的数据查找，添加和删除操作，并且可以被多线程并发访问。Redis 的有序集合也使用了跳跃列表，本文参考其源码提供一个简单的 Java 版本实现。

核心原理

如上图所示，要插入 17 时，从头节点最高层开始遍历链表，当找到最后一个小于 17 的节点时，沿层级数组下降，遍历下层链表。重复上述过程，直到找到大于 17 的节点，在它之前插入数据。如果遍历最底层的原始链表，则需经过 5 个节点，现在只需 3 个。查找和删除也是如此，理解起来比红黑树简单很多。详细分析参考文末资料。

复杂度分析

空间复杂度

假设总节点数为 n，每 2 个节点间构建一个索引，少于 2 个节点的层无意义，则

层次	节点数
top	$$2$$
...	$$...$$
k	$$\frac{n}{2^{k}}$$
...	$$...$$
2	$$\frac{n}{2^{2}}$$
1	$$\frac{n}{2}$$
0	$$n$$

$$\frac{n}{2^{top}} = 2$$

$$n=2^{top+1}$$

$$top + 1=\log_{2}{n}$$

$$top=\log_{2}{n} - 1$$

加上最后一层，则总层数为 \(\log_{2}{n}\)。1 ~ top 层需要占用额外空间，节点数总和为

$$2 + 4 + ... + 2^{\log_{2}{n} - 1}$$

$$= 2 \times (2^{\log_{2}{n} - 1} - 1)$$

$$= 2^{\log_{2}{n}} - 2$$

$$= n-2$$

所以跳表的空间复杂度为 O(n)。

时间复杂度

插入和删除依赖查找，调整指针的时间复杂度为 O(1)。如果像上面那样建立最密索引，每层只需一次比较，因为层数为 \(\log_{2}{n}\)，所以最好时间复杂度为 O(logn)。不建立索引退化为链表，时间复杂度 O(n)。

运行效果

Size of list: 10
|L6| -------------------------------------------------------------------------> |97| -> |NULL|
|L5| -> |10| -------------------------> |62| ---------------------------------> |97| -> |NULL|
|L4| -> |10| -> |24| ---------> |61| -> |62| -> |63| -----------------> |86| -> |97| -> |NULL|
|L3| -> |10| -> |24| ---------> |61| -> |62| -> |63| -----------------> |86| -> |97| -> |NULL|
|L2| -> |10| -> |24| ---------> |61| -> |62| -> |63| -> |65| ---------> |86| -> |97| -> |NULL|
|L1| -> |10| -> |24| -> |29| -> |61| -> |62| -> |63| -> |65| -> |76| -> |86| -> |97| -> |NULL|
|L0| -> |10| -> |24| -> |29| -> |61| -> |62| -> |63| -> |65| -> |76| -> |86| -> |97| -> |NULL|

Insertion of 88 succeeded? true
Insertion of 55 succeeded? true
Insertion of 11 succeeded? true
Insertion of 11 again succeeded? false

Size of list: 13
|L6| -------------------------------------------------------------------------------------------------> |97| -> |NULL|
|L5| -> |10| -----------------------------------------> |62| ---------------------------------> |88| -> |97| -> |NULL|
|L4| -> |10| ---------> |24| -----------------> |61| -> |62| -> |63| -----------------> |86| -> |88| -> |97| -> |NULL|
|L3| -> |10| -> |11| -> |24| -----------------> |61| -> |62| -> |63| -----------------> |86| -> |88| -> |97| -> |NULL|
|L2| -> |10| -> |11| -> |24| -----------------> |61| -> |62| -> |63| -> |65| ---------> |86| -> |88| -> |97| -> |NULL|
|L1| -> |10| -> |11| -> |24| -> |29| -> |55| -> |61| -> |62| -> |63| -> |65| -> |76| -> |86| -> |88| -> |97| -> |NULL|
|L0| -> |10| -> |11| -> |24| -> |29| -> |55| -> |61| -> |62| -> |63| -> |65| -> |76| -> |86| -> |88| -> |97| -> |NULL|

Deletion of 88 succeeded? true
Deletion of 55 succeeded? true
Deletion of 11 succeeded? true
Deletion of 11 again succeeded? false

Size of list: 10
|L6| -------------------------------------------------------------------------> |97| -> |NULL|
|L5| -> |10| -------------------------> |62| ---------------------------------> |97| -> |NULL|
|L4| -> |10| -> |24| ---------> |61| -> |62| -> |63| -----------------> |86| -> |97| -> |NULL|
|L3| -> |10| -> |24| ---------> |61| -> |62| -> |63| -----------------> |86| -> |97| -> |NULL|
|L2| -> |10| -> |24| ---------> |61| -> |62| -> |63| -> |65| ---------> |86| -> |97| -> |NULL|
|L1| -> |10| -> |24| -> |29| -> |61| -> |62| -> |63| -> |65| -> |76| -> |86| -> |97| -> |NULL|
|L0| -> |10| -> |24| -> |29| -> |61| -> |62| -> |63| -> |65| -> |76| -> |86| -> |97| -> |NULL|

Process finished with exit code 0

源码实现

package com.logi.ds;

public class Main {

    public static void main(String[] args) {
        SkipList<Integer> list = new SkipList<>(7);

        for (int i = 0; i < 10; i++) {
            // [10, 100)
            int item = (int) (Math.random() * 90) + 10;
            list.insert(item);
        }
        list.print();

        System.out.printf("\nInsertion of 88 succeeded? %s\n", list.insert(88));
        System.out.printf("Insertion of 55 succeeded? %s\n", list.insert(55));
        System.out.printf("Insertion of 11 succeeded? %s\n", list.insert(11));
        System.out.printf("Insertion of 11 again succeeded? %s\n\n", list.insert(11));
        list.print();

        System.out.printf("\nDeletion of 88 succeeded? %s\n", list.delete(88));
        System.out.printf("Deletion of 55 succeeded? %s\n", list.delete(55));
        System.out.printf("Deletion of 11 succeeded? %s\n", list.delete(11));
        System.out.printf("Deletion of 11 again succeeded? %s\n\n", list.delete(11));
        list.print();
    }
}

package com.logi.ds;

/**
 * @author LOGI
 * @version 1.0
 * @date 2021/7/2 17:12
 */
public class SkipList<E extends Comparable<? super E>> {

    private final static class Node<S> {
        private final static class Level<T> {
            Node<T> forward; // 层后继
            int span;        // 层跨度

            public Level(Node<T> forward, int span) {
                this.forward = forward;
                this.span = span;
            }
        }

        S item;            // 数据
        Node<S> backward;  // 前驱
        Level<S>[] levels; // 层级数组

        public Node(S item, int level) {
            this.item = item;
            this.levels = new Level[level];
        }
    }

    private static final int DEFAULT_LEVEL = 6;

    private final Node<E> header; // 表头
    private Node<E> tail;         // 表尾
    private final int maxLevel;   // 最大层级
    private long size;            // 总节点数

    public SkipList() {
        this(DEFAULT_LEVEL);
    }

    public SkipList(int maxLevel) {
        this.maxLevel = maxLevel;
        header = tail = new Node<>(null, maxLevel);
        for (int i = 0; i < maxLevel; i++) {
            header.levels[i] = new Node.Level<>(null, 0);
        }
    }

    /**
     * 查找并返回某一层小于 elem 的最后一个节点
     *
     * @param start 起始搜寻节点
     * @param level 当前层级
     * @param elem  比较数据
     * @return 找到的节点
     */
    private Node<E> getLevelPrev(Node<E> start, int level, E elem) {
        while (start.levels[level].forward != null &&
                start.levels[level].forward.item.compareTo(elem) < 0) {
            start = start.levels[level].forward;
        }
        return start;
    }

    /**
     * 查找并返回包含指定数据的节点
     *
     * @param elem 待查数据
     * @return 未找到返回 null，否则返回数据所在节点
     */
    private Node<E> getNode(E elem) {
        Node<E> prev = header;
        for (int i = maxLevel - 1; i >= 0; i--) {
            // 获得当前层级的前驱
            prev = getLevelPrev(prev, i, elem);

            // 确保存在后继
            if (prev.levels[i] == null) continue;

            Node<E> node = prev.levels[i].forward;
            if (node != null && node.item.equals(elem)) {
                return node;
            }
        }
        return null;
    }


    /**
     * 生成并返回一个随机层级
     *
     * @return [1, maxLevel] 之间的随机数
     */
    private int getRandomLevel() {
        return (int) Math.ceil(Math.random() * (maxLevel - 1)) + 1;
    }

    /**
     * 查找数据
     *
     * @param elem 待查数据
     * @return 找到返回 true，否则返回 false
     */
    public boolean contains(E elem) {
        return getNode(elem) != null;
    }

    /**
     * 插入数据
     *
     * @param elem 待插数据
     * @return 如果数据已存在返回 false，否则返回 true
     */
    public boolean insert(E elem) {
        if (contains(elem)) return false;

        int level = getRandomLevel();
        Node<E> newNode = new Node<>(elem, level);

        Node<E> prev = header;
        for (int i = level - 1; i >= 0; i--) {
            // 获得当前层级的前驱
            prev = getLevelPrev(prev, i, elem);

            Node.Level<E> prevLevel = prev.levels[i];
            Node<E> next = prevLevel.forward;

            // 更新后继的前驱或尾节点，并设置新节点的前驱
            if (i == 0) {
                if (next != null) {
                    next.backward = newNode;
                } else {
                    tail = newNode;
                }
                newNode.backward = prev;
            }

            // 增加后继们的跨度
            while (next != null) {
                next.levels[i].span++;
                next = next.levels[i].forward;
            }

            // 设置新节点的后继和跨度
            newNode.levels[i] = new Node.Level<>(prevLevel.forward, prevLevel.span + 1);
            // 更新前驱的后继
            prevLevel.forward = newNode;
        }

        size++;
        return true;
    }

    /**
     * 删除数据
     *
     * @param elem 待删数据
     * @return 如果数据不存在返回 false，否则返回 true
     */
    public boolean delete(E elem) {
        Node<E> node = getNode(elem);
        if (node == null) return false;

        Node<E> prev = header;
        for (int i = node.levels.length - 1; i >= 0; i--) {
            // 获得当前层级的前驱
            prev = getLevelPrev(prev, i, elem);

            Node<E> next = node.levels[i].forward;

            // 更新前驱的后继
            prev.levels[i].forward = next;

            // 更新后继的前驱或尾节点
            if (i == 0) {
                if (next != null) {
                    next.backward = prev;
                } else {
                    tail = prev;
                }
            }

            // 减小后继们的跨度
            while (next != null) {
                next.levels[i].span--;
                next = next.levels[i].forward;
            }
        }

        size--;
        return true;
    }

    public void print() {
        int maxItemLength = size == 0 ? 0 : tail.item.toString().length();
        String format = "-> |%" + maxItemLength + "s| ";
        String gap = "------" + "-".repeat(maxItemLength);

        System.out.printf("Size of list: %d\n", size);
        for (int i = maxLevel - 1; i >= 0; i--) {
            Node<E> node = header;

            int nextSpan = 1;
            if (node.levels[i].forward != null) {
                nextSpan = node.levels[i].forward.levels[i].span;
            }

            System.out.printf("|L%d| ", i);
            while (node.levels[i].forward != null) {
                node = node.levels[i].forward;

                while (nextSpan++ < node.levels[0].span) {
                    System.out.print(gap);
                }

                System.out.printf(format, node.item);
            }

            for (int j = nextSpan; j <= tail.levels[0].span; j++) {
                System.out.print(gap);
            }
            System.out.println("-> |NULL|");
        }
    }
}

参考资料

• 跳跃列表 - 维基百科
• 跳跃表的实现 - Redis 设计与实现
• 跳表 - 知乎
• SkipList 的原理与实现 - 知乎
• 深入理解跳跃链表 - 掘金