Mofan
返回

高级数据结构之跳表

发表于 更新于
浏览量： --

文章目录

0%

封面画师：Nengoro(ネんごろぅ)     封面ID：74015476

本文参考视频：小马哥教育(SEEMYGO) 2019 年 恋上数据结构与算法（第二季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

辅助学习网址：数据结构和算法动态可视化     Data Structure Visualizations

0. 需求分析

一个 有序 链表的搜索、添加、删除的平均时间复杂度是 O(n)O(n)。

看到 有序 两个字，能否利用二分搜索优化有序链表，使其搜索、添加、删除的平均时间复杂度降低至 O(logn)O(logn)？

链表不具备像数组那样的高效随机访问特性，因此不能像有序数组那样直接使用二分搜索。

那有没有其他办法让 有序 链表的搜索、添加、删除的平均时间复杂度降低至 O(logn)O(logn) 呢？

可以使用 跳表 （SkipList）。

1. 跳表

1.1 基本概念

跳表（SkipList），又叫做跳跃表、跳跃列表，是在有序链表的基础上增加了「跳跃」的功能。由 William Pugh 于 1990 年发布，设计的初衷是为了取代平衡树（比如红黑树）。

Redis 中的 SortedSet、LevelDB 中的 MemTable 都用到了跳表，Redis、LevelDB 都是著名的 Key-Value 数据库。

与平衡树相比：

徒手写一个红黑树行吗？难吗？😩

不行！难！😖

徒手写一个跳表呢？🤔

这还真行。🤪

1.2 使用跳表优化有序链表

现有一如下图所示的 升序 链表：

一个升序链表

假设需要判断该链表中是否存在元素 19，按照以前的做法，肯定是从首节点开始遍历，查看第一个大于等于 19 的元素是否是 19，如果是表示元素 19 在该列表中存在，反之不存在。这个过程的时间复杂度是 O(n)O(n)。

原链表是升序的，如何利用这个特性来降低时间复杂度呢？

可以在原链表的基础上新增一层，比如：

有序链表增加一层

然后在搜索目标元素时，可以先在最上层进行遍历，将目标元素锁定到一个区间里，之后在这个区间里用较低层的线路继续遍历，重复以上操作，直到找到目标元素或确定目标元素不存在：

有序链表增加一层后的查找

那其实还可以继续增加几层？比如：

有序链表增加至四层

可以是可以，但肯定有一个平衡点，不能一味地增加下去，否则最终的效率可能还不如直接遍历。

那这个平衡点是什么？

先按下不表，这会在后续跳表的实现中讲解。

2. 代码实现

2.1 代码骨架

Redis、LevelDB 都是著名的 Key-Value 数据库，它们的具体实现都用到了跳表，因此在实现跳表时，不妨也将其设计成 K-V 型，即：

/**
 * @author mofan
 * @date 2022/12/4 17:24
 */
public class SkipList<K, V> {
    // ...
}

在跳表中每个位置存放的元素是一个 K-V 对象，因此需要有一个内部类来定义这个结构。

观察下述跳表的结构：

有序链表增加至四层

有些节点除了存放具体的值，还存放了多个指向其他节点的指针。因此这个内部类可以这样设计：

private static class Node<K, V> {
    K key;
    V value;
    Node<K, V>[] nextNodes;

    @SuppressWarnings("unchecked")
    private Node(K key, V value, int level) {
        this.key = key;
        this.value = value;
        nextNodes = (Node<K, V>[]) new Node[level];
    }
}

跳表中的元素是有序的，因此需要用户添加的 Key 具有可比较性，可以在创建跳表时就传入比较器 Comparator，也可以是添加的 Key 本就实现了 Comparable 接口，本身就具有可比较性。

Key 具有可比较性的另一层含义是：添加的 key 不能是 null。

/**
 * @author mofan
 * @date 2022/12/4 17:24
 */
public class SkipList<K, V> {
    private int size;
    private Comparator<K> comparator;

    public SkipList(Comparator<K> comparator) {
        this.comparator = comparator;
    }

    public SkipList() {
        this(null);
    }

    public int size() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    public V put(K key, V value) {
        this.keyCheck(key);
        return null;
    }

    public V get(K key) {
        this.keyCheck(key);
        return null;
    }

    public V remove(K key) {
        this.keyCheck(key);
        return null;
    }

    private void keyCheck(K key) {
        if (key == null) {
            throw new IllegalArgumentException("key must not be null");
        }
    }

    @SuppressWarnings("unchecked")
    private int compare(K k1, K k2) {
        return comparator != null
                ? comparator.compare(k1, k2)
                : ((Comparable<K>) k1).compareTo(k2);
    }
}

继续观察跳表结构：

有序链表增加至四层

跳表的首节点没有存放用户添加的信息，是一个不存放任何 K-V 的虚拟节点，既然如此，在构造跳表时就可以将首节点构造出来，但这又有一个问题：首节点的 nextNodes 数组应该初始化成多少长度的呢？

在 Redis 中使用的跳表对层数有限制，最多有 32 层，这里的实现可以借鉴一下。

在构造首节点时，可以将其的 nextNodes 数组长度初始化为 32，在实际使用过程中，某些层次可能不会被使用，真正使用的层次数应该是跳表中真正存放元素的节点的最高层数。

在使用首节点进行遍历时，每次都从最顶层开始？

实际使用过程中，跳表的真实层数往往没有这么多，为了更好地确定跳表的真实层数，可以使用一个成员变量来记录首节点的有效层数。

最终得到的代码骨架如下：

/**
 * @author mofan
 * @date 2022/12/4 17:24
 */
public class SkipList<K, V> {
    /**
     * 跳表的最高层数，参考 Redis
     */
    private static final int MAX_LEVEL = 32;
    private int size;
    private Comparator<K> comparator;
    /**
     * 有效层数
     */
    private int level;
    /**
     * 不存放任何 K-V 的虚拟节点作为首节点
     */
    private Node<K, V> first;

    @SuppressWarnings({"unchecked"})
    public SkipList(Comparator<K> comparator) {
        this.comparator = comparator;
        this.first = new Node<>();
        this.first.nextNodes = (Node<K, V>[]) new Node[MAX_LEVEL];
    }

    public SkipList() {
        this(null);
    }

    public int size() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    public V put(K key, V value) {
        this.keyCheck(key);
        return null;
    }

    public V get(K key) {
        this.keyCheck(key);
        return null;
    }

    public V remove(K key) {
        this.keyCheck(key);
        return null;
    }

    private void keyCheck(K key) {
        if (key == null) {
            throw new IllegalArgumentException("key must not be null");
        }
    }

    @SuppressWarnings("unchecked")
    private int compare(K k1, K k2) {
        return comparator != null
                ? comparator.compare(k1, k2)
                : ((Comparable<K>) k1).compareTo(k2);
    }

    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V>[] nextNodes;

        @SuppressWarnings("unchecked")
        private Node(K key, V value, int level) {
            this.key = key;
            this.value = value;
            nextNodes = (Node<K, V>[]) new Node[level];
        }
    }
}

可以看到 put()、get() 和 remove() 都不是有效的实现，接下来将对它们一一进行实现。

在【1.2 使用跳表优化有序链表】中对跳表的搜索有所了解，可以先来实现搜索。

2.2 搜索元素

搜索的步骤可以用以下三步概括：

  1. 从顶层链表的首元素开始，从左往右搜索，直至找到一个大于或等于目标的元素，或者到达当前层链表的尾部；
  2. 如果该元素等于目标元素，表明该元素已被找到；
  3. 如果该元素大于目标元素或已到达链表的尾部，则退回至当前层的前一个元素，然后转入下一层进行搜索。重复上述步骤，直到找到目标元素或确定目标元素不存在于当前跳表。
public V get(K key) {
    this.keyCheck(key);

    Node<K, V> node = first;
    for (int i = level - 1; i >= 0; i--) {
        int cmp = -1;
        while (node.nextNodes[i] != null 
               && (cmp = compare(key, node.nextNodes[i].key)) > 0) {
            node = node.nextNodes[i];
        }
        if (cmp == 0) return node.nextNodes[i].value;
    }

    return null;
}

nextNode != null 的作用：下一个节点是 null 时，表示无法在当前层确定目标元素所处的范围，需要前往下一层进行搜索。

(cmp = compare(key, nextNode.key)) > 0：比较目标节点与当前节点指向的下一个节点的大小，并将比较结果赋值给 cmp，如果目标节点较大，进入循环体，移动节点位置，当前节点指向下一个节点，直到目标节点小于等于当前节点指向的下一个节点。

2.3 添加元素

在跳表中添加元素有两个要点：

  1. 找到新增节点的位置
  2. 计算新增节点的层数，并设置前驱节点和后继节点

位置的确定很简单，与搜索元素无异。

那怎么确定新增节点的层数呢？

层数是 随机 的。就像抛硬币一样，假设抛到正面就加一层，直到抛到反面或达到最高层数。暂且不管这样的做法靠不靠谱，先实现再说。😶

可以提供一个私有方法用来计算新增节点的层数，参考 Redis，四分之一的概率增加一层：

private static final double P = 0.25;

private int randomLevel() {
    int level = 1;
    // 四分之一的概率增加层次，最高 32
    while (Math.random() < P && level < MAX_LEVEL) {
        level++;
    }
    return level;
}

在确定新增节点的位置时，可能出现两种情况：

  1. 添加的 Key 在当前跳表中 已存在
  2. 添加的 Key 在当前跳表中 不存在

第一种情况当作特殊情况，直接使用 新值覆盖旧值 即可。

如果是第二种情况，那么需要：

以添加元素 17 为例：

在跳表中添加17

假设添加的 Key 在当前跳表中不存在，在确定节点的位置时， 跳表的遍历会不断从高层次下降，直到最下面一层。

由上图可知，每次层次下降时，那个位置的节点即为新增节点的前序节点，而新增节点的后继节点就是这些前序节点原本的后继节点。可以在确定新增节点的位置时，就将这些前序节点保存下来，方便后续使用。

还有一种特殊情况需要处理：计算出的新增节点的层数比当前跳表的有效层数还要大。

在超出的层次中，让首节点作为新增节点的前序节点，后继节点无需处理，它们本就指向 null。

也是因为这种情况的存在，因此还需要重新计算下当前跳表的有效层数。

因为成功添加了元素，最后别忘了让跳表的长度 size 自增一。

@SuppressWarnings("unchecked")
public V put(K key, V value) {
    this.keyCheck(key);

    Node<K, V> node = first;
    // 添加节点的前驱节点
    Node<K, V>[] pres = (Node<K, V>[]) new Node[level];
    for (int i = level - 1; i >= 0; i--) {
        int cmp = -1;
        while (node.nextNodes[i] != null && (cmp = compare(key, node.nextNodes[i].key)) > 0) {
            node = node.nextNodes[i];
        }
        // 添加的节点存在，新值覆盖旧值
        if (cmp == 0) {
            V oldV = node.nextNodes[i].value;
            node.nextNodes[i].value = value;
            return oldV;
        }
        // 保留前驱节点
        pres[i] = node;
    }

    // 新节点的层数
    int newLevel = randomLevel();
    // 添加的新节点
    Node<K, V> newNode = new Node<>(key, value, newLevel);
    // 设置新节点的前驱与后继
    for (int i = 0; i < newLevel; i++) {
        // 新节点的层数比当前跳表的有效层数还要高
        if (i >= this.level) {
            // 首节点成为新节点的前驱
            first.nextNodes[i] = newNode;
        } else {
            // 添加节点的后继为其前驱节点原本的后继节点
            newNode.nextNodes[i] = pres[i].nextNodes[i];
            // 设置前驱节点
            pres[i].nextNodes[i] = newNode;
        }
    }
    // 计算新的有效层数
    this.level = Math.max(this.level, newLevel);
    size++;
    return null;
}

2.4 删除元素

在跳表中删除元素有两个要点：

  1. 找到删除节点的位置
  2. 设置某些节点新的后继节点，重新计算跳表的有效层数

位置的搜索不在赘述，前文已经出现过两次了，但是一搜索到目标元素就停止搜索吗？

假设被删除的元素在跳表中存在，并且包含被删除元素的节点有至少两层。元素的搜索是从高层次链表向低层次链表进行搜索的，一个至少有两层的节点至少有两个前驱节点，如果一搜索到元素就停止搜索，那么只能确定一个前驱节点的位置，处于低层次链表的前驱节点无法被确定，导致目标节点被删除后，跳表的结构遭到破坏。

因此，在搜索目标节点的位置时，必须从有效层数开始搜索，直到最底层链表。假定这样的一次搜索称为一次「删除时搜索」。

被删除节点的层数可能与当前跳表的有效层数一样，也可能有且仅有一层，只有当完成一次「删除时搜索」后，才能确定被删除节点是否存在。

假设被删除节点存在于当前跳表中，在进行一次「删除时搜索」时，需要将被删除节点的前序节点保存下来，在后续重新设置这些节点的后继节点。

由于被删除节点的层数可能是当前跳表中层数最多的节点，也就是说当前跳表的有效层数等于被删除节点的层数，当该节点被删除时，需要重新设置跳表的有效层数。以首节点为目标，从原有效层数出发，依次判断首节点的后继节点是否为 null，如果为 null，则需要使当前跳表的有效层数减一，直到首节点的后继节点不为 null。

因为成功删除了节点，最后别忘了让跳表的长度 size 自减一。

@SuppressWarnings("unchecked")
public V remove(K key) {
    this.keyCheck(key);

    Node<K, V> node = first;
    // 添加节点的前驱节点
    Node<K, V>[] pres = (Node<K, V>[]) new Node[level];
    boolean exist = false;
    for (int i = level - 1; i >= 0; i--) {
        int cmp = -1;
        while (node.nextNodes[i] != null && (cmp = compare(key, node.nextNodes[i].key)) > 0) {
            node = node.nextNodes[i];
        }
        if (cmp == 0) exist = true;
        pres[i] = node;
    }
    // 被删除的节点不存在，直接返回
    if (!exist) return null;
    // 需要被删除的节点
    Node<K, V> removeNode = node.nextNodes[0];

    // 设置后继
    for (int i = 0; i < removeNode.nextNodes.length; i++) {
        pres[i].nextNodes[i] = removeNode.nextNodes[i];
    }
    // 更新跳表的层数
    int newLevel = this.level;
    while (--newLevel >= 0 && first.nextNodes[newLevel] == null) {
        this.level = newLevel;
    }
    // 数量减少
    this.size--;
    return removeNode.value;
}

2.5 完整代码

/**
 * @author mofan
 * @date 2022/12/4 17:24
 */
public class SkipList<K, V> {
    /**
     * 跳表的最高层数，参考 Redis
     */
    private static final int MAX_LEVEL = 32;
    private static final double P = 0.25;
    private int size;
    private Comparator<K> comparator;
    /**
     * 有效层数
     */
    private int level;
    /**
     * 不存放任何 K-V 的虚拟节点作为首节点
     */
    private Node<K, V> first;

    @SuppressWarnings({"unchecked"})
    public SkipList(Comparator<K> comparator) {
        this.comparator = comparator;
        this.first = new Node<>(null, null, MAX_LEVEL);
    }

    public SkipList() {
        this(null);
    }

    public int size() {
        return this.size;
    }

    public boolean isEmpty() {
        return this.size == 0;
    }

    @SuppressWarnings("unchecked")
    public V put(K key, V value) {
        this.keyCheck(key);

        Node<K, V> node = first;
        // 添加节点的前驱节点
        Node<K, V>[] pres = (Node<K, V>[]) new Node[level];
        for (int i = level - 1; i >= 0; i--) {
            int cmp = -1;
            while (node.nextNodes[i] != null && (cmp = compare(key, node.nextNodes[i].key)) > 0) {
                node = node.nextNodes[i];
            }
            // 添加的节点存在，新值覆盖旧值
            if (cmp == 0) {
                V oldV = node.nextNodes[i].value;
                node.nextNodes[i].value = value;
                return oldV;
            }
            // 保留前驱节点
            pres[i] = node;
        }

        // 新节点的层数
        int newLevel = randomLevel();
        // 添加的新节点
        Node<K, V> newNode = new Node<>(key, value, newLevel);
        // 设置新节点的前驱与后继
        for (int i = 0; i < newLevel; i++) {
            // 新节点的层数比当前跳表的有效层数还要高
            if (i >= this.level) {
                // 首节点成为新节点的前驱
                first.nextNodes[i] = newNode;
            } else {
                // 添加节点的后继为其前驱节点原本的后继节点
                newNode.nextNodes[i] = pres[i].nextNodes[i];
                // 设置前驱节点
                pres[i].nextNodes[i] = newNode;
            }
        }
        // 计算新的有效层数
        this.level = Math.max(this.level, newLevel);
        size++;
        return null;
    }

    public V get(K key) {
        this.keyCheck(key);

        Node<K, V> node = first;
        for (int i = level - 1; i >= 0; i--) {
            int cmp = -1;
            while (node.nextNodes[i] != null && (cmp = compare(key, node.nextNodes[i].key)) > 0) {
                node = node.nextNodes[i];
            }
            if (cmp == 0) return node.nextNodes[i].value;
        }

        return null;
    }

    @SuppressWarnings("unchecked")
    public V remove(K key) {
        this.keyCheck(key);

        Node<K, V> node = first;
        // 添加节点的前驱节点
        Node<K, V>[] pres = (Node<K, V>[]) new Node[level];
        boolean exist = false;
        for (int i = level - 1; i >= 0; i--) {
            int cmp = -1;
            while (node.nextNodes[i] != null && (cmp = compare(key, node.nextNodes[i].key)) > 0) {
                node = node.nextNodes[i];
            }
            if (cmp == 0) exist = true;
            pres[i] = node;
        }
        // 被删除的节点不存在，直接返回
        if (!exist) return null;
        // 需要被删除的节点
        Node<K, V> removeNode = node.nextNodes[0];

        // 设置后继
        for (int i = 0; i < removeNode.nextNodes.length; i++) {
            pres[i].nextNodes[i] = removeNode.nextNodes[i];
        }
        // 更新跳表的层数
        int newLevel = this.level;
        while (--newLevel >= 0 && first.nextNodes[newLevel] == null) {
            this.level = newLevel;
        }
        // 数量减少
        this.size--;
        return removeNode.value;
    }


    private int randomLevel() {
        int level = 1;
        // 四分之一的概率增加层次，最高层次 32
        while (Math.random() < P && level < MAX_LEVEL) {
            level++;
        }
        return level;
    }

    private void keyCheck(K key) {
        if (key == null) {
            throw new IllegalArgumentException("key must not be null");
        }
    }

    @SuppressWarnings("unchecked")
    private int compare(K k1, K k2) {
        return comparator != null
                ? comparator.compare(k1, k2)
                : ((Comparable<K>) k1).compareTo(k2);
    }

    private static class Node<K, V> {
        K key;
        V value;
        Node<K, V>[] nextNodes;

        @SuppressWarnings("unchecked")
        private Node(K key, V value, int level) {
            this.key = key;
            this.value = value;
            nextNodes = (Node<K, V>[]) new Node[level];
        }

        @Override
        public String toString() {
            return key + ":" + value + "_" + nextNodes.length;
        }
    }

    @Override
    public String toString() {
        StringBuilder sb = new StringBuilder();
        sb.append("一共").append(level).append("层").append("\n");
        for (int i = level - 1; i >= 0; i--) {
            Node<K, V> node = first;
            while (node.nextNodes[i] != null) {
                sb.append(node.nextNodes[i]);
                sb.append("\t");
                node = node.nextNodes[i];
            }
            sb.append("\n");
        }
        return sb.toString();
    }
}

2.6 测试代码

/**
 * @author mofan
 * @date 2022/12/5 22:26
 */
public class Main {
    public static void main(String[] args) {
        SkipList<Integer, Integer> list =new SkipList<>();
        test(list, 30, 10);
    }

    private static void test(SkipList<Integer, Integer> list, int count, int delta) {
        for (int i = 0; i < count; i++) {
            list.put(i, i + delta);
        }
        System.out.println(list);
        for (int i = 0; i < count; i++) {
            check(list.get(i) == i + delta);
        }
        check(list.size() == count);

        for (int i = 0; i < count; i++) {
            check(list.remove(i) == i + delta);
        }
        check(list.size() == 0);
    }

    private static void check(boolean condition) {
        try {
            if (!condition) {
                throw new Exception("测试未通过");
            }
        } catch (Exception e) {
            // do nothing
        }
    }

}

2.7 跳表的层数

跳表是按层构造的，底层是一个普通的有序链表，高层相当于是低层的「快速通道」。

在第 ii 层中的元素按某个固定的概率 pp（通常为 12\frac{1}{2} 或 14\frac{1}{4}）出现在第 i+1i + 1 层中，层次越高，拥有的节点越少。

每个元素的层数恰好等于 11 的概率为 1 – p1 \ – \ p；

元素层数大于等于 22 的概率为 pp，而元素层数恰好等于 22 的概率为 p×(1 – p)p \times (1 \ – \ p)；

元素层数大于等于 33 的概率为 p2p^2，而元素层数恰好等于 33 的概率为 p2×(1 – p)p^2 \times (1 \ – \ p)；

元素层数大于等于 44 的概率为 p3p^3，而元素层数恰好等于 44 的概率为 p3×(1 – p)p^3 \times (1 \ – \ p)；

简单解析

一个元素有 pp 的概率出现在更上面一层，因此一个元素不增加层数的概率为 1−p1 - p。

根据上述描可知，每个元素的层数恰好等于 11 的概率就是该元素不会增加层数的概率，即 1−p1 - p；

当元素的层数来到 22 层时，那么来到 22 层的概率是 pp。如果对层数的增加不做要求，也就是恰好等于 22 层或大于 22 层都可以，简而言之，无论增不增加层数都行，那么此时的概率为 p×1=pp \times 1 = p；如果要求元素的层数恰好等于 22 层，即要求元素不再增加层数，那么此时的概率为 p×(1−p)p \times (1 - p)。

当元素的层数来到 33 层时，那么来到 33 层的概率是 p×p=p2p \times p = p^2。如果对层数的增加不做要求，也就是恰好等于 33 层或大于 33 层都可以，简而言之，无论增不增加层数都行，那么此时的概率为 p2×1=p2p^2 \times 1 = p^2；如果要求元素的层数恰好等于 33 层，即要求元素不再增加层数，那么此时的概率为 p2×(1−p)p^2 \times (1 - p)。

元素的平均层数

元素的平均层数 LL 就是下述概率分布的期望 E(L)E(L)：

层数1234…k
恰好等于对应层数的概率1−p1 - pp(1−p)p(1 - p)p2(1−p)p^2(1 - p)p3(1−p)p^3(1 - p)…pk−1(1−p)p^{k - 1}(1 - p)
E(L)=1×(1−p)+2p(1−p)+3p2(1−p)+4p3(1−p)+...+kpk−1(1−p)=(1−p)∑k=1+∞kpk−1=(1−p)⋅1(1−p)2=11−p\begin{aligned} E(L) & = 1 \times (1 - p) + 2p(1 - p) + 3p^2(1 - p) + 4p^3(1 - p) + ... + kp^{k - 1}(1 - p)\\ & = (1 - p)\sum_{k = 1}^{+\infty}kp^{k - 1} \\ & = (1 - p) \cdot \frac{1}{(1 - p)^2} \\ & = \frac{1}{1 - p} \\ \end{aligned}

当 p=12p = \frac{1}{2} 时，每个元素所包含的平均指针数量是 22；

当 p=14p = \frac{1}{4} 时，每个元素所包含的平均指针数量是 1.331.33。Redis 与本文选取的 pp 就是 14\frac{1}{4}，在这种情况下，显然比红黑树更加省内存，因为红黑树每个元素至少包含三个指针（left、right、parent）。

2.8 复杂度分析

参考链接：LeetCode 1206：设计跳表-官方题解

空间复杂度

每个元素的平均层数是 11−p\frac{1}{1 - p}，那么总的空间复杂度为：

O(n×E(L))=O(n×11−p)=O(n)O(n \times E(L)) = O(n \times \frac{1}{1 - p}) = O(n)

时间复杂度

每一层的元素数量：

在含有 nn 个节点的跳表中，最大层数 L(n)L(n) 包含的元素个数期望为 1p\frac{1}{p}。那么有：

n×pk−1=1pn×pk=1k=logp1n\begin{aligned} &n \times p^{k - 1} = \frac{1}{p} \\ \\ &n \times p^k = 1 \\ \\ &k = log_p\frac{1}{n} \end{aligned}

因此，当前最大层数期望 L(n)=logp1nL(n) = log_p\frac{1}{n}。

假设跳表中的元素是 升序 排序的，回忆下搜索目标元素 xx 的过程：当搜索到第 ii 层时，如果当前元素 小于 目标元素 xx，那么继续在当前层向后（向右）搜索，直到下一节点 大于等于 目标元素 xx；如果当前元素 大于 目标元素 xx，则前往下一层进行搜索；重复这些操作，直到找到目标元素 xx。

假设目标元素 xx 的层数为 1，如果要搜索到目标元素，需要一直向下搜索到第一层。

再假设从最高层 L(n)L(n) 的第一个节点搜索到第一层的目标节点 xx 的路径为 SS。现在将路径 SS 反过来，从下向上看，即从目标节点 xx 回到最高层 L(n)L(n) 的第一个节点。

以前文中添加元素 17 的示例图举例，相当于从元素 12 回到最高层的第一个节点：

在跳表中添加17

现有一个结论：如果元素 xx 在第 ii 层中出现，那么它一定会在第 i−1i - 1 层中出现。

目标元素 xx 从第一层回到最高层的过程中，会判断当前元素是否在上一层出现，如果出现，则向上一层，直到当前元素的最大层数，然后再向前（向左）到达元素 yy，判断元素 yy 是否在上一层出现，重复这些步骤，直到回到最高层 L(n)L(n) 的第一个节点。

对处于第 ii 层的元素 xx 来说，此时不知道 xx 的最大层数和 xx 左侧元素的最大层数，只知道元素 xx 的最大层数至少是 ii。如果元素 xx 的最大层数大于 ii，后续需要向上一层，这样的概率是 pp；如果元素 xx 的最大层数等于 ii，后续需要向前（向左）移动一步，这样的概率是 p−1p - 1。

令 C(i)C(i) 表示在一个无限长度的跳表中向上移动 ii 层需要走过的平均路径长度（期望），那么：

C(0)=0C(i)=(1−p)(1+C(i))+p(1+C(i−1))\begin{aligned} C(0) &= 0 \\ \\ C(i) &= (1 - p)(1 + C(i)) + p(1 + C(i - 1)) \end{aligned}

是否向上移动有两种情况：

  1. 不向上移动，而是向左移动一步，概率为 1−p1 - p。路径加一，但还有 C(i)C(i) 步需要移动，因为需要移动的层数没有减少；
  2. 向上移动，概率为 pp。路径加一，由于需要移动的层数减少一，因此还有 C(i−1)C(i - 1) 步需要移动。

对公式进行化简：

C(i)=1+C(i)−p−pC(i)+p+pC(i−1)pC(i)=1+pC(i−1)C(i)=1p+C(i−1)C(i)=ip\begin{aligned} C(i) &= 1 + C(i) - p - pC(i) + p + pC(i - 1) \\ \\ pC(i) &= 1 + pC(i - 1) \\ \\ C(i) &= \frac{1}{p} + C(i - 1) \\ \\ C(i) &= \frac{i}{p} \end{aligned}

在含有 nn 个元素的跳表中，从第一层回到最高层 L(n)L(n) 需要走过的最长路径长度是 L(n)−1p\frac{L(n) - 1}{p}。

到达最高层 L(n)L(n) 后，还需要向前（向左）走，最高层 L(n)L(n) 中元素最多为 1p\frac{1}{p} 个，都取最坏情况，那么总搜索代价为：

L(n)−1p+1p=log1pn−1p+1p=log1pnp\frac{L(n) - 1}{p} + \frac{1}{p} = \frac{log_\frac{1}{p}n - 1}{p} + \frac{1}{p} = \frac{log_\frac{1}{p}n}{p}

pp 是常数，故跳表中搜索元素的时间复杂度是 O(logn)O(logn)。

跳表中元素的添加与删除也会进行元素搜索，因此在跳表中添加元素、删除元素的时间复杂度都是 O(logn)O(logn)。

2.9 LeetCode - 1206

class Skiplist {
    private static final BiConsumer<Integer, Node> EMPTY_CONSUMER = (i, node) -> {
    };
    private static final int MAX_LEVEL = 32;
    private static final double SKIP_LIST_P = 0.25;
    /**
     * 虚拟头节点
     */
    private final Node virtualHead;
    /**
     * 最高层数
     */
    private int maxLevel;

    public Skiplist() {
        this.virtualHead = new Node(-1, MAX_LEVEL);
        this.maxLevel = 0;
    }

    public boolean search(int target) {
        Node cur = lower(target, EMPTY_CONSUMER);
        /*
         * 已经在最底下一层，并且当前 cur 一定严格小于 target
         * 那么 cur 的下一个元素就很有可能是 target
         */
        cur = cur.next[0];
        // 当前元素的值是否等于 target
        return cur != null && cur.val == target;
    }

    public void add(int num) {
        // 存放每一层中，最小的、大于 num 的元素
        Node[] lowers = new Node[MAX_LEVEL];
        Arrays.fill(lowers, virtualHead);
        lower(num, (i, node) -> lowers[i] = node);
        int randomLevel = randomLevel();
        // 更新最高的层数
        this.maxLevel = Math.max(this.maxLevel, randomLevel);
        Node newNode = new Node(num, randomLevel);
        // 将 num 插入进跳表
        for (int i = 0; i < randomLevel; i++) {
            newNode.next[i] = lowers[i].next[i];
            lowers[i].next[i] = newNode;
        }
    }

    public boolean erase(int num) {
        Node[] lowers = new Node[MAX_LEVEL];
        Node cur = lower(num, (i, node) -> lowers[i] = node);
        cur = cur.next[0];
        // 判断在最下面一层中是否存在 num，如果不存在，就证明没有 num
        if (cur == null || cur.val != num) {
            return false;
        }
        for (int i = 0; i < maxLevel; i++) {
            if (lowers[i].next[i] != cur) {
                break;
            }
            // 删除 num，将 num 前一个元素的 next 指向 num 的下一个元素
            lowers[i].next[i] = cur.next[i];
        }
        // 有可能最上层只有一个元素，缩短层数
        while (maxLevel > 1 && virtualHead.next[maxLevel - 1] == null) {
            maxLevel--;
        }
        return true;
    }

    /**
     * 找到最下面一层最大的、严格小于 num 的元素，也就是可能的、num 的前一个元素
     */
    private Node lower(int num, BiConsumer<Integer, Node> consumer) {
        Node cur = this.virtualHead;
        for (int i = maxLevel - 1; i >= 0; i--) {
            while (cur.next[i] != null && cur.next[i].val < num) {
                cur = cur.next[i];
            }
            // 处理每一层中最大的、严格小于 num 的元素
            consumer.accept(i, cur);
        }
        return cur;
    }

    /**
     * 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且
     * 1/2 的概率返回 2
     * 1/4 的概率返回 3
     * 1/8 的概率返回 4 以此类推
     */
    private int randomLevel() {
        int level = 1;
        while (Math.random() < SKIP_LIST_P && level < MAX_LEVEL) {
            level++;
        }
        return level;
    }
}

class Node {
    /**
     * 当前节点储存的值
     */
    int val;
    /**
     * 在某一层的下个节点。
     * 比如当前共有 3 层，那么 next 里共有 3 个元素，存放在每层的下一个元素
     */
    Node[] next;

    public Node(int val, int level) {
        this.val = val;
        this.next = new Node[level];
    }
}
如果这篇文章对你有帮助，可以通过
支付宝
支付宝
微信
微信
请我喝杯 Coffee ☕
上一篇
高级数据结构之B+树
下一篇
高级数据结构之布隆过滤器