JS实现跳表：插入删除全解析

跳表是一种高效的有序数据结构，通过多层级链表和随机化层级设计，在JavaScript中实现了平均O(logN)的查找、插入和删除性能，媲美平衡二叉树。其核心优势在于实现简单、并发性能好，且缓存友好，特别适用于Redis有序集合等需要高效操作有序数据的场景。本文将深入探讨跳表的JavaScript实现，重点讲解插入和删除操作，包括节点结构、随机层级生成、update数组的使用以及头节点的处理等关键技术细节，助你避开常见“坑”，充分发挥跳表的优势，提升系统性能。

跳表通过多层级链表和随机化层级设计，在平均情况下实现O(logN)的查找、插入和删除性能，其核心优势在于实现简单、并发性能好、缓存友好，且适用于有序数据的高效操作，常见于Redis有序集合等场景。

跳表（Skip List）在JavaScript中实现，本质上是构建一个多层级的链表结构。它的核心思想是通过概率性地在不同层级维护有序的链表，从而在平均情况下实现对数时间复杂度的查找、插入和删除操作，性能上可以媲美平衡二叉搜索树，但在实现上却简单得多。它的插入和删除操作都依赖于先找到元素的位置，然后像操作普通链表一样调整指针，只不过这个过程需要在多个层级上同步进行。

解决方案

实现跳表，我们首先需要一个节点（Node）结构，它包含值、以及一个指向多层下一个节点的数组（next）。然后是跳表类本身，它管理着头节点、最大层级以及一个随机层级生成器。

class SkipListNode {
    constructor(value, level) {
        this.value = value;
        // next是一个数组，存储指向不同层级下一个节点的引用
        this.next = new Array(level + 1).fill(null);
    }
}

class SkipList {
    constructor(maxLevel = 16, probability = 0.5) {
        this.maxLevel = maxLevel; // 跳表的最大层级
        this.probability = probability; // 决定节点层级的概率因子
        this.level = 0; // 当前跳表的最高层级
        // 头节点，其值通常为null或-Infinity，用于简化边界处理
        this.head = new SkipListNode(null, maxLevel); 
    }

    // 随机生成新节点的层级
    // 这是一个核心机制，决定了跳表的性能
    randomLevel() {
        let lvl = 0;
        while (Math.random() < this.probability && lvl < this.maxLevel) {
            lvl++;
        }
        return lvl;
    }

    // 插入操作
    insert(value) {
        // update数组用来存储每一层需要更新的节点
        // update[i] 表示在第i层，新节点应该插入到update[i]的后面
        const update = new Array(this.maxLevel + 1).fill(null);
        let current = this.head;

        // 从最高层开始向下查找，找到插入位置
        for (let i = this.level; i >= 0; i--) {
            while (current.next[i] && current.next[i].value < value) {
                current = current.next[i];
            }
            update[i] = current; // 记录下当前层的前一个节点
        }

        // 如果值已经存在，通常选择不插入或更新，这里选择不插入
        if (current.next[0] && current.next[0].value === value) {
            // console.log(`Value ${value} already exists.`);
            return false;
        }

        // 确定新节点的层级
        const newLevel = this.randomLevel();

        // 如果新节点的层级高于当前跳表的最高层级，需要更新head的next指针
        // 并且update数组中超出当前level的部分，其前驱节点就是head
        if (newLevel > this.level) {
            for (let i = this.level + 1; i <= newLevel; i++) {
                update[i] = this.head;
            }
            this.level = newLevel; // 更新跳表的最高层级
        }

        // 创建新节点
        const newNode = new SkipListNode(value, newLevel);

        // 调整指针，将新节点插入到相应的位置
        for (let i = 0; i <= newLevel; i++) {
            newNode.next[i] = update[i].next[i];
            update[i].next[i] = newNode;
        }
        return true;
    }

    // 删除操作
    delete(value) {
        const update = new Array(this.maxLevel + 1).fill(null);
        let current = this.head;

        // 从最高层开始向下查找，找到要删除的节点
        for (let i = this.level; i >= 0; i--) {
            while (current.next[i] && current.next[i].value < value) {
                current = current.next[i];
            }
            update[i] = current; // 记录下当前层的前一个节点
        }

        // 检查要删除的节点是否存在
        current = current.next[0];
        if (!current || current.value !== value) {
            // console.log(`Value ${value} not found.`);
            return false;
        }

        // 调整指针，跳过要删除的节点
        for (let i = 0; i <= this.level; i++) {
            // 如果update[i]的下一个节点是要删除的节点，就跳过它
            if (update[i].next[i] === current) {
                update[i].next[i] = current.next[i];
            }
        }

        // 删除后，检查是否需要降低跳表的最高层级
        // 从最高层开始检查，如果head的next指针指向null，说明该层已空
        while (this.level > 0 && this.head.next[this.level] === null) {
            this.level--;
        }
        return true;
    }

    // 查找操作（通常也会实现，但这里不作为重点）
    search(value) {
        let current = this.head;
        for (let i = this.level; i >= 0; i--) {
            while (current.next[i] && current.next[i].value < value) {
                current = current.next[i];
            }
        }
        current = current.next[0];
        return current && current.value === value;
    }

    // 打印跳表（辅助调试）
    print() {
        console.log("Skip List:");
        for (let i = this.level; i >= 0; i--) {
            let current = this.head.next[i];
            let levelStr = `Level ${i}: Head -> `;
            while (current) {
                levelStr += `${current.value} -> `;
                current = current.next[i];
            }
            levelStr += "NULL";
            console.log(levelStr);
        }
    }
}

// 示例用法：
// const skipList = new SkipList();
// skipList.insert(3);
// skipList.insert(6);
// skipList.insert(7);
// skipList.insert(9);
// skipList.insert(12);
// skipList.insert(1);
// skipList.print();
// console.log("Searching for 7:", skipList.search(7)); // true
// console.log("Searching for 5:", skipList.search(5)); // false
// skipList.delete(7);
// skipList.print();
// console.log("Searching for 7 after deletion:", skipList.search(7)); // false
// skipList.delete(1);
// skipList.print();
// skipList.delete(100); // Value 100 not found.

跳表为什么能比平衡树更快？它的核心优势在哪里？

对我来说，跳表最吸引人的地方，是它在实现复杂度和性能之间的那种微妙平衡。我们都知道，平衡二叉搜索树（比如红黑树、AVL树）在理论上提供了严格的O(logN)性能保证，但它们的实现，尤其是插入和删除后的“旋转”和“着色”操作，那真的是相当烧脑，调试起来更是痛苦。相较之下，跳表的核心优势就在于它的概率性结构和实现上的简洁性。

首先，实现难度大大降低。跳表不需要复杂的平衡算法。插入时，你只需要通过一个简单的随机函数来决定新节点的层级，然后像操作链表一样插入；删除时也类似，找到节点后直接调整指针即可。这种“简单粗暴”的方式，在工程实践中意味着更少的bug、更快的开发周期。我个人就觉得，与其花大量时间去搞懂红黑树的各种旋转规则，不如用跳表，效率上差不太多，但省心太多了。

其次，并发性能上的潜在优势。在多线程或并发环境下，跳表在某些操作上表现得比平衡树更好。因为它的结构是多层链表，在进行插入或删除时，往往只需要锁定少量相关的节点，而不是像平衡树那样可能需要对整个子树进行复杂的全局性调整。这种局部性锁定的特性，使得跳表在并发数据结构的设计中非常受欢迎，比如Redis的Sorted Set就是基于跳表实现的。

此外，缓存友好性也是一个不容忽视的优点。跳表的节点在内存中通常是连续的，或者至少比二叉树的节点分布更线性。这有助于CPU缓存的命中率，因为处理器在访问数据时，往往会预取相邻的数据。虽然这不总是绝对的优势，但在某些场景下，它确实能带来实际的性能提升。平衡树的节点可能散落在内存的各个角落，导致更多的缓存未命中。

最后，虽然是概率性的，但跳表在平均情况下的性能是非常可靠的O(logN)。只要随机函数足够好，你几乎可以总是获得与平衡树相媲美的性能。这种“足够好”的随机性，对于大多数应用场景来说已经足够了。

在实际项目中，跳表有哪些常见的应用场景？

跳表虽然不如哈希表或平衡树那么“家喻户晓”，但在一些特定领域，它可是实实在在的“幕后英雄”。它简洁高效的特性，让它在需要有序数据且对插入/删除性能有较高要求的场景下，显得格外有用。

最典型的应用，莫过于数据库索引。比如，大名鼎鼎的Redis，它的有序集合（Sorted Set）就是通过跳表来实现的。有序集合需要支持快速地按分数范围查询、添加、删除元素，并且能按序遍历。跳表完美契合了这些需求：查找、插入、删除都是对数时间复杂度，同时还能高效地进行范围查询（因为数据在每一层都是有序的）。这比使用哈希表（无法保持顺序）或单纯的链表（查找慢）要高效得多。

除了数据库，并发数据结构也是跳表大展拳脚的地方。正如前面提到的，跳表的局部性锁定优势，使得它非常适合构建无锁（lock-free）或读写锁（read-write lock）优化的并发数据结构。在高性能计算、高并发服务中，如果需要一个有序的集合，并且要处理大量的并发读写请求，跳表会是一个非常好的选择。它能够减少线程间的竞争，提高系统的吞吐量。

再往深一点看，一些网络路由表的实现也可能借鉴跳表的思想。路由表需要快速查找IP地址对应的下一跳，并且路由规则可能会动态添加或删除。跳表的多层级结构和高效的查找能力，使其在处理这种有序查找和更新的场景时具有优势。

甚至在一些内存管理或垃圾回收算法中，如果需要维护一个有序的空闲内存块列表，跳表也可以用来高效地管理这些内存块，以便快速分配和回收。

总结来说，只要你的项目需要一个能够快速查找、插入、删除，并且数据需要保持有序的数据结构，同时你又希望实现起来相对简单，或者对并发性能有较高要求，那么跳表就非常值得考虑。它不像那些“万金油”的数据结构，但它在自己的“舒适区”里，表现是相当出色的。

实现跳表时，有哪些常见的“坑”或者需要特别注意的技术细节？

实现跳表，虽然整体上比平衡树简单，但它也有一些自己的“脾气”和需要注意的细节，不然一不小心就会踩坑。我自己在写的时候，就遇到过一些小问题，值得拿出来聊聊。

首先，随机层级生成器的质量至关重要。跳表的性能在很大程度上依赖于这个随机性。如果你的随机函数不够“随机”，或者概率因子设置不合理，可能会导致跳表退化成普通链表（所有节点都在第一层），或者层级过高（浪费内存）。通常我们用Math.random() < probability来决定是否增加层级，这个probability（通常是0.5）需要根据实际情况和经验来设置。如果这个概率太低，节点层级普遍不高，跳表会比较“扁”，查找性能可能受影响；如果太高，节点层级普遍很高，虽然查找快，但内存开销会变大。

其次，update 数组的正确使用是插入和删除操作的关键。这个数组在查找过程中，记录了每一层需要更新的“前驱节点”。在插入时，新节点要插入到update[i]和update[i].next[i]之间；在删除时，update[i].next[i]需要跳过被删除的节点，直接指向被删除节点的下一个节点。如果这里处理不当，比如数组索引越界，或者指针链断裂，整个跳表就可能崩溃。尤其是在新节点的层级高于当前跳表最高层级时，update数组中超出原level的部分，其前驱节点都应该是head，这个细节很容易被忽略。

还有一个小点，就是头节点（head）的处理。我通常会给头节点一个null或-Infinity的值，并且它的层级设置为maxLevel。这样做的好处是，头节点总是在所有元素的“前面”，并且它的next数组总是有足够的空间来容纳指向最高层级节点的指针。这样可以避免在处理边界情况时写出很多额外的判断逻辑，代码会显得更简洁。

最后，删除操作后最高层级的维护。当你删除一个节点后，如果这个节点恰好是某个层级的唯一节点，或者它被删除后导致最高层级变得空荡荡（head.next[this.level]变成了null），那么你需要适时地降低跳表的this.level。这虽然不是性能上的大问题，但可以避免跳表维持过高的空层级，节省一点内存，也让结构看起来更“紧凑”。不处理这个，跳表也能正常工作，但从“工程美学”上讲，稍微有些不完美。

这些细节，看似微不足道，但在实际编码中，它们往往是导致bug或者让代码变得晦涩难懂的罪魁祸首。理解并正确处理它们，才能真正发挥跳表的优势。

本篇关于《JS实现跳表：插入删除全解析》的介绍就到此结束啦，但是学无止境，想要了解学习更多关于文章的相关知识，请关注golang学习网公众号！