有序集合（Ordered Set）

MrHe··3 min read

解法一：无脑数组/链表，先跑起来再说

拿到一个需求，别总想着一步到位整个最优解。先用最简单、最暴力的方法实现，保证功能正确，这是基本盘。

对于“有序集合”，最先蹦到我脑子里的就是两种基本结构：

  1. 有序数组：用 ArrayList 维护一个有序列表。

  2. 有序链表：用 LinkedList 维护一个有序链表。

我们来分析一下这两兄弟的性能。假设集合里已经有 N 个元素了。

对于有序数组：

  • 查找 (Search)：太爽了，天生支持二分查找，时间复杂度 O(logN)。

  • 插入 (Add)：这就拉了。你得先用二分查找 O(logN) 找到插入位置，然后把这个位置后面的所有元素都往后挪一位，这个移动操作是 O(N) 的。所以整体是 O(N)。

  • 删除 (Remove)：同理，先 O(logN) 找到元素，然后把后面的元素往前挪，整体也是 O(N)。

对于有序链表：

  • 查找 (Search)：链表没法二分，只能从头结点一个一个往后捋，平均时间复杂度 O(N)。

  • 插入 (Add)：也得先找到插入位置，这个过程是 O(N)。找到位置后，改个指针就行，操作本身是 O(1)，但整体还是 O(N)。

  • 删除 (Remove)_：和插入一样，找到它 O(N)，干掉它 O(1)，整体 O(N)。

小结一下：数组查得快，但增删是硬伤；链表增删的瞬间操作快，但定位太慢。两者都有 O(N) 的瓶颈，数据量一大，肯定超时。

这个解法在面试时可以作为开胃菜，展示你考虑问题的全面性，但如果就此打住，那这轮基本就凉了。

解法二：升维打击，用“空间”换“时间”——跳表 (Skip List)

既然 O(N) 的瓶颈在于查找，那我们就得想办法加速查找。链表的查找慢，是因为它是一维的，我们只能一步一步挪。那能不能给它升个维，加一些“快速通道”呢？

你想啊，我们坐地铁，除了站站都停的普通线，还有只停大站的快线。我要是从北京的“天通苑”到“西单”，如果坐普通线得停十几二十站。但如果我能先坐快线几站到“东单”，再换普通线坐一两站到“西单”，是不是就快多了？

这个“快线”思想，就是跳表 (Skip List) 的精髓。

我们可以在原始的有序链表（下图中的第 0 层）之上，再加一层链表（第 1 层）。第 1 层的节点，是从第 0 层里“随机”抽出来的。比如，每隔一个节点，就把它提拔到第 1 层。

Level 1:  1 ----------------> 9 ----------------> 21
            |                 |                   |
Level 0:  1 ----> 4 ----> 9 ----> 12 ----> 17 ----> 21

现在我要查找 17。

  1. 我先在最高层（Level 1）的快线上走。从头结点出发，下一个是 9，比 17 小，继续走。

  2. 9 的下一个是 21，比 17 大了！说明 17 肯定在 9 和 21 之间。

  3. 于是我从 9 这个节点，“下沉”到下一层（Level 0）。

  4. 在 Level 0，我从 9 开始往后走。下一个是 12，比 17 小，继续。下一个是 17，找到了！

你看，我没必要从 1 开始遍历整个底层链表，通过上层的“快速通道”，我直接跳过了 4。

如果数据量更大，一层“快线”还不够爽，那我就加更多的层！比如第 2 层是从第 1 层里抽，第 3 层从第 2 层里抽......越往上，节点越稀疏，跨度越大。

跳表示意图

这就是一个多层的跳表结构。查找过程永远是从最高层的头结点开始，向右查找，如果右边的节点值大于目标值，或者右边没节点了，就“下沉”一层继续向右查找。整个路径就像是在一个立体交通网里不断向右、向下移动，直到找到目标。

关键问题：新节点该加几层？

这是跳表最巧妙的地方——随机！

当我们插入一个新节点时，我们通过抛硬币的方式来决定这个节点要不要被“提拔”到上一层。比如，抛一次硬币，如果是正面，就提拔，然后继续为上一层抛硬币，直到抛出反面或者达到最高层为止。

这种纯随机的方式，在概率上保证了整个跳表的高度维持在 logN 级别，也保证了每一层的节点数量大概是下一层的一半。正因为如此，跳表的查找、插入、删除操作的平均时间复杂度都是 O(logN)，性能媲美平衡二叉搜索树（比如红黑树）！

而且，相比红黑树复杂无比的左旋、右旋、变色等平衡操作，跳表的插入和删除只需要修改前后节点的指针，逻辑清晰简单，代码写起来也更容易。

下面是一个极简的Java实现，帮你理解核心逻辑：

// 跳表节点
class Node {
    Integer value;
    Node[] forward; // 存放指向各层下一个节点的指针

    public Node(Integer value, int level) {
        this.value = value;
        this.forward = new Node[level];
    }
}

// 跳表实现
class SkipList {
    private static final float P = 0.5f; // 随机因子
    private static final int MAX_LEVEL = 16; // 最大层数

    private int level; // 当前跳表的有效层数
    private Node head; // 头结点，不存数据

    public SkipList() {
        this.level = 0;
        this.head = new Node(null, MAX_LEVEL);
    }

    // 随机生成新节点的层数
    private int randomLevel() {
        int lv = 1;
        while (Math.random() < P && lv < MAX_LEVEL) {
            lv++;
        }
        return lv;
    }

    public boolean search(int target) {
        Node current = this.head;
        // 从最高层开始往下找
        for (int i = level - 1; i >= 0; i--) {
            while (current.forward[i] != null && current.forward[i].value < target) {
                current = current.forward[i];
            }
        }
        // 来到第0层，判断下一个节点是不是目标
        current = current.forward[0];
        return current != null && current.value == target;
    }

    public void add(int num) {
        // update数组记录了新节点在每一层的前驱节点
        Node[] update = new Node[MAX_LEVEL];
        for (int i = 0; i < MAX_LEVEL; i++) {
            update[i] = head;
        }

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

        // 生成新节点的随机层数
        int newLevel = randomLevel();
        // 如果新节点的层数比当前跳表还高，更新跳表层数，并填充update数组
        if (newLevel > level) {
            level = newLevel;
        }

        Node newNode = new Node(num, newLevel);
        // 逐层插入新节点
        for (int i = 0; i < newLevel; i++) {
            newNode.forward[i] = update[i].forward[i];
            update[i].forward[i] = newNode;
        }
    }

    // 删除逻辑和添加类似，先找到每一层的前驱，然后修改指针
    // 这里就不放代码了，思路是一样的
}

这个解法，有思路，有实现，有复杂度分析，面试到这儿，已经很不错了。

解法三：站在巨人的肩膀上，聊聊 JDK 的实现

面试官除了想看你的动手能力，也想了解你的知识广度。在实际工作中，我们很少会自己手写一个跳表，而是直接用现成的。那么，Java 里有没有官方的有序集合实现呢？

当然有！

  1. java.util.TreeSet：

    • 底层实现：红黑树 (TreeMap)。

    • 特点：经典的平衡二叉搜索树实现，能保证增、删、查都是严格的 O(logN) 时间复杂度。元素不允许重复，且会自动排序。

    • 适用场景：绝大多数单线程场景下的有序集合需求，用它就完事了，稳定、高效。

  2. java.util.concurrent.ConcurrentSkipListSet：

    • 底层实现：跳表 (ConcurrentSkipListMap)。

    • 特点：这才是我们今天的主角！JDK 专门为并发场景设计的有序集合。跳表结构天然适合并发操作，它的节点修改只涉及局部的前后指针，不像红黑树那样一次旋转可能要锁定大半个树。ConcurrentSkipListSet 通过 CAS (Compare-And-Swap) 操作实现了非阻塞的、线程安全的增删查，性能极高。

    • 适用场景：高并发环境下需要一个有序的集合。比如实时排行榜、需要排序的分布式任务队列等。

所以，当面试官问你如何实现有序集合时，你可以这么回答：

  • 第一层（基础方案）：可以先用有序数组或链表实现，分析其 O(N) 的性能瓶颈。

  • 第二层（进阶方案）：为了突破 O(N) 瓶颈，可以引入跳表结构。详细阐述跳表的原理，如何通过分层索引和随机化来实现 O(logN) 的期望复杂度，并且可以手写出核心代码。

  • 第三层（架构视野）：在实际应用中，我们会优先选择 JDK 提供的成熟实现。在单线程环境下，使用基于红黑树的 TreeSet；在并发环境下，为了追求更高的性能和伸缩性，会选择基于跳表的 ConcurrentSkipListSet，并解释为什么跳表更适合并发（锁粒度小，易于实现无锁操作）。

总结

从最朴实的数组/链表，到巧妙的跳表，再到工业级的 TreeSet 和 ConcurrentSkipListSet，我们看到了一条清晰的思维进阶路线。

  • 暴力解 -> 发现瓶颈 -> 针对性优化 -> 形成高级数据结构
  • #ordered-set