Java高手的30k之路｜面试宝典｜精通跳表SkipList

跳表 Skip List

跳表（Skip List）是一种数据结构，它在有序链表的基础上，通过增加多级索引来提高查找、插入和删除操作的效率。

跳表的平均时间复杂度为 O(log n)，与平衡树（如红黑树、AVL树）相当，但实现起来更为简单。

跳表的结构

跳表由多层链表组成，每一层都是一个有序链表。底层（第0层）是一个完整的有序链表。每向上一层，链表中的节点数量减少，且上一层的节点都是下一层节点的子集。

示例图解

下面是一个简单的跳表结构的图示：

Level 3:  [Header] ------------------------> [8] ------------------------> [null]

Level 2:  [Header] --------------> [4] ------------------------> [8] -----> [null]

Level 1:  [Header] --> [2] ------> [4] --> [5] --> [7] -------> [8] -----> [10] -----> [null]

Level 0:  [Header] -> [1] -> [2] -> [3] -> [4] -> [5] -> [6] -> [7] -> [8] -> [9] -> [10] -> [null]

解释

1. 节点结构：每个节点包含多个指向不同层的前进指针。例如，节点 [4] 在第0层、第1层和第2层都有指针，但在第3层没有指针。

2. 查找操作：

   • 查找元素 7：从最高层开始，顺着指针找到最接近且不超过 7 的元素。在图示中，首先从 Header 走到 4，然后从 4 走到 5，再从 5 走到第1层的 7。
   • 查找路径：Header -> 4 (Level 2) -> 5 (Level 1) -> 7 (Level 1)。

3. 插入操作：

   • 插入元素时，先找到该元素在每一层的插入位置，然后根据随机数决定该元素的高度，并插入到相应的层中。

4. 删除操作：

   • 删除元素时，先找到该元素在每一层的位置，然后将其从每一层中删除。假设要删除 7，就需要从第0层、第1层中删除节点 7。

节点层数的选择标准

跳表的每一层节点都是上一层节点的子集，通常通过随机化策略来决定哪些节点会出现在更高层。具体来说，当插入一个新节点时，通过随机算法来决定这个节点的高度。每一层节点的选择标准是独立的，通常使用几何分布或类似的随机分布。

在 Java 中实现跳表时，常用的方式是通过一个随机函数来决定节点的层数。在经典的 SkipList 实现中，每一个节点的高度由一个随机函数生成，这个随机函数会在每一层上有一定概率（通常是 0.5）决定是否将节点提升到更高一层。

示例：Java 中跳表的实现

以下是一个完整的 Java 跳表实现示例，展示了如何使用随机化策略来决定节点的高度，并维护多级链表：

import java.util.Random;

class SkipListNode {
    int value;
    SkipListNode[] forward;

    public SkipListNode(int value, int level) {
        this.value = value;
        this.forward = new SkipListNode[level + 1];
    }
}

public class SkipList {
    private static final int MAX_LEVEL = 16;
    private final SkipListNode header = new SkipListNode(-1, MAX_LEVEL);
    private int level = 0;
    private final Random random = new Random();

    // 插入方法
    public void insert(int value) {
        SkipListNode[] update = new SkipListNode[MAX_LEVEL + 1];
        SkipListNode current = header;

        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value < value) {
                current = current.forward[i];
            }
            update[i] = current;
        }

        int nodeLevel = randomLevel();
        if (nodeLevel > level) {
            for (int i = level + 1; i <= nodeLevel; i++) {
                update[i] = header;
            }
            level = nodeLevel;
        }

        SkipListNode newNode = new SkipListNode(value, nodeLevel);
        for (int i = 0; i <= nodeLevel; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }

    // 查找方法
    public boolean search(int value) {
        SkipListNode current = header;
        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value < value) {
                current = current.forward[i];
            }
        }
        current = current.forward[0];
        return current != null && current.value == value;
    }

    // 删除方法
    public void delete(int value) {
        SkipListNode[] update = new SkipListNode[MAX_LEVEL + 1];
        SkipListNode current = header;

        for (int i = level; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value < value) {
                current = current.forward[i];
            }
            update[i] = current;
        }

        current = current.forward[0];
        if (current != null && current.value == value) {
            for (int i = 0; i <= level; i++) {
                if (update[i].forward[i] != current) break;
                update[i].forward[i] = current.forward[i];
            }

            while (level > 0 && header.forward[level] == null) {
                level--;
            }
        }
    }

    // 随机层数生成方法
    private int randomLevel() {
        int lvl = 0;
        while (lvl < MAX_LEVEL && random.nextInt(2) == 0) {
            lvl++;
        }
        return lvl;
    }

    public static void main(String[] args) {
        SkipList skipList = new SkipList();
        skipList.insert(3);
        skipList.insert(6);
        skipList.insert(7);
        skipList.insert(9);
        skipList.insert(12);
        skipList.insert(19);

        System.out.println(skipList.search(6));  // true
        System.out.println(skipList.search(15)); // false

        skipList.delete(6);
        System.out.println(skipList.search(6));  // false
    }
}

解释

1. 节点类 (SkipListNode)：每个节点包含一个值和一个指针数组，指向每一层的下一个节点。

2. 插入方法 (insert)：

   • 使用 update 数组记录在每一层插入新节点的位置。
   • 从最高层开始，找到需要插入的位置。
   • 调用 randomLevel 方法随机生成节点的高度。
   • 如果生成的节点高度比当前跳表的高度大，更新跳表的高度。
   • 插入新节点，并更新相关的指针。

3. 查找方法 (search)：

   • 从最高层开始，逐层查找目标值。
   • 如果找到则返回 true，否则返回 false。

4. 删除方法 (delete)：

   • 使用 update 数组记录在每一层删除节点的位置。
   • 从最高层开始，找到需要删除的位置。
   • 删除节点，并更新相关的指针。
   • 如果某一层为空，减少跳表的高度。

5. 随机层数生成方法 (randomLevel)：

   • 随机生成一个节点的高度，使用几何分布，概率为 0.5。

关键点

• 随机层数生成：通过 randomLevel 方法来决定新节点的高度，使用 nextInt(2) 模拟掷硬币的概率，层数越高，节点数量越少。
• 多级链表：使用多层链表来加速查找、插入和删除操作，平均时间复杂度为 O(log n)。
• 更新指针：插入和删除操作需要更新多层链表的指针。

跳表的优点

1. 高效：查找、插入和删除的时间复杂度平均为 (O(\log n))。
2. 简单：相对于平衡树，跳表实现起来更为简单。
3. 灵活：通过调整层数和概率，可以在空间和时间复杂度之间进行权衡。

跳表实现时为什么选择随机算法决定level

跳表选择随机算法决定节点的层级（level），而不是平均分布，主要基于以下几个考虑：

1. 平衡性和性能：随机算法可以在一定程度上保证跳表的平衡性。通过随机确定每个节点的层级，可以避免节点集中在某一层，从而保持跳表在不同层次上的均衡分布。这种均衡性有助于提高搜索、插入和删除操作的性能，因为在平衡的情况下，操作的时间复杂度更稳定。

2. 避免确定性结构：如果使用平均分布，每个节点的层级可能会逐渐递增或递减，导致跳表的结构不够随机化。这种确定性结构可能会在特定操作序列下导致性能的不稳定性或者退化。

3. 简单性和效率：随机算法相对于确定性分布更加简单且高效。随机生成节点层级只需要简单的随机数生成器，而不需要复杂的计算或者存储结构，这在实现和维护上都更加方便。

4. 概率均衡：虽然是随机的，但在实践中，随机算法可以通过调整概率分布来控制节点层级的期望分布。比如，可以调整随机算法的概率参数，以达到期望的分布特性，如更倾向于生成较低层次的节点，或者在特定场景下生成更高层次的节点。

跳表选择随机算法决定节点层级，是为了在保持操作效率和简单性的同时，保持跳表结构的均衡性和性能稳定性。这种随机化的设计使得跳表在实际应用中能够更好地应对不同数据分布和操作序列的挑战。

高层节点的值在低层一定会出现吗

不完全对。跳表中的节点分布并不是高层的节点会出现在每一个低层，而是每个节点在更高的层次上都有可能存在。