跳表核心原理

在实际的面试中，几乎不会让你手写跳表的实现代码，但可能会问你跳表的基本原理及复杂度分析，所以本站需要讲解这种数据结构。

本文处在基础章节，不会具体讲解跳表的实现细节，只介绍跳表的核心原理。初学者学习本文，知道有这么一种数据结构，了解它的基本原理和时间复杂度即可。具体的代码实现将放到数据结构设计章节。

在 链表基础 中我们说到，在单链表中增删查改指定索引的元素所需的时间复杂度是 $O(N)$。

其实，如果拿到了待操作的链表节点，操作几次指针就能完成删除、修改、插入操作，时间复杂度是 $O(1)$。

时间主要消耗在查询操作，因为通过索引查询对应的节点，只能从头结点开始，逐个遍历到目标节点，然后才做删除、修改、插入操作。

那么，我们是否可以通过一些优化方式，让链表支持快速的查找操作呢？

有一种方式是借助键值映射，用 $O(1)$ 的事件直接拿到目标节点，避免了遍历查找的时间消耗，这个思路在后面的 哈希链表（LinkedHashMap） 中会详细介绍。

另一种方式，这就是本文介绍的跳表（Skip List），利用空间换时间的思想，用额外的空间记录额外的信息，增删查改的时间复杂度都能优化到 $O(\log N)$。

跳表核心原理

我们就以查询指定索引的元素为例，来看看跳表是如何优化单链表的。

一条普通的单链表长这样：

index  0  1  2  3  4  5  6  7  8  9
node   a->b->c->d->e->f->g->h->i->j

如果我们想查询索引为 7 的元素是什么，只能从索引 0 头结点开始往后遍历，直到遍历到索引 7，找到目标节点 h。

而跳表则是这样的：

indexLevel   0-----------------------8-----10
indexLevel   0-----------4-----------8-----10
indexLevel   0-----2-----4-----6-----8-----10
indexLevel   0--1--2--3--4--5--6--7--8--9--10
nodeLevel    a->b->c->d->e->f->g->h->i->j->k

跳表相当于在原链表的基础上，增加了多层索引，每向上一层，索引节点的数量减少一半，索引的间隔变为 2 倍，所以索引的高度是 $\log N$。

此时，如果我们想查询索引为 7 的元素，可以从最高层索引开始一层一层地往下找：

首先最高层的第一个索引区间是 [0, 8]，可以确定索引 7 在这个区间内，所以从下一层的节点 0 开始搜索；

第二层从节点 0 开始，索引区间 [0, 4] 不包含索引 7，继续往右移动到节点 4，索引区间 [4, 8] 包含索引 7，所以从下一层的节点 4 开始搜索；

第三层从节点 4 开始，索引区间 [4, 6] 不包含索引 7，继续往右移动到节点 6，索引区间 [6, 8] 包含索引 7，所以从下一层的节点 6 开始搜索；

第四层从节点 6 开始，索引区间 [6, 7] 包含索引 7，最终找到目标节点 h。

这个搜索过程中，会经过 $\log N$ 层索引，在每层索引中移动的次数不会超过 2 次（因为上层索引区间在下一层被分为两半），所以跳表的查询时间复杂度是 $O(\log N)$。

总结

上面这个简化的例子应该能让你对跳表的核心原理有个直观的认识，跳表是典型的空间换时间设计思路，额外维护多层索引，增加空间复杂度，降低增删查改的时间复杂度。

跳表的具体实现还是有一些复杂，而且和上面的简化示例有一些不同，下面补充几点：

1、上面的例子只展示了查询操作，但跳表肯定得支持插入和删除操作，这就涉及到索引层中节点的动态调整，你需要保证每一层的索引区间尽可能二分，这样才能保证索引层的高度为 $\log N$，否则时间复杂度就会退化。

2、不仅仅是查找索引对应的节点，跳表还可以运用到更通用的场景，比如说有序键值对的存储和查找。实际上，跳表的使用场景和后面我们会学习到的二叉搜索树非常类似，只不过跳表的代码实现相较于自平衡二叉搜索树要简单很多。

关于跳表的具体实现，我会更新到数据结构的设计章节，敬请期待。