深入浅出跳跃表

跳跃表的引入

我们知道，普通单链表查询一个元素的时间复杂度为 O(n)，即使该单链表是有序的，我们也不能通过 2 分的方式缩减时间复杂度。

如上图，我们要查询元素为 55 的结点，必须从头结点，循环遍历到最后一个节点，不算-INF(负无穷)一共查询 8 次。那么用什么办法能够用更少的次数访问 55 呢？最直观的，当然是新开辟一条捷径去访问 55。

如上图，我们要查询元素为 55 的结点，只需要在 L2 层查找 4 次即可。在这个结构中，查询结点为 46 的元素将耗费最多的查询次数 5 次。即先在 L2 查询 46，查询 4 次后找到元素 55，因为链表是有序的，46 一定在 55 的左边，所以 L2 层没有元素 46。然后我们退回到元素 37，到它的下一层即 L1 层继续搜索 46。非常幸运，我们只需要再查询 1 次就能找到 46。这样一共耗费 5 次查询。

那么，如何才能更快的搜寻 55 呢？有了上面的经验，我们就很容易想到，再开辟一条捷径。

如上图，我们搜索 55 只需要 2 次查找即可。这个结构中，查询元素 46 仍然是最耗时的，需要查询 5 次。即首先在 L3 层查找 2 次，然后在 L2 层查找 2 次，最后在 L1 层查找 1 次，共 5 次。很显然，这种思想和 2 分非常相似，那么我们最后的结构图就应该如下图。

我们可以看到，最耗时的访问 46 需要 6 次查询。即 L4 访问 55，L3 访问 21、55，L2 访问 37、55，L1 访问 46。我们直觉上认为，这样的结构会让查询有序链表的某个元素更快。那么究竟算法复杂度是多少呢？

如果有 n 个元素，因为是 2 分，所以层数就应该是 log n 层 (本文所有 log 都是以 2 为底)，再加上自身的 1 层。以上图为例，如果是 4 个元素，那么分层为 L3 和 L4，再加上本身的 L2，一共 3 层；如果是 8 个元素，那么就是 3+1 层。最耗时间的查询自然是访问所有层数，耗时 logn+logn，即 2logn。为什么是 2 倍的 logn 呢？我们以上图中的 46 为例，查询到 46 要访问所有的分层，每个分层都要访问 2 个元素，中间元素和最后一个元素。所以时间复杂度为 O(logn)。

至此为止，我们引入了最理想的跳跃表，但是如果想要在上图中插入或者删除一个元素呢？比如我们要插入一个元素 22、23、24……，自然在 L1 层，我们将这些元素插入在元素 21 后，那么 L2 层，L3 层呢？我们是不是要考虑插入后怎样调整连接，才能维持这个理想的跳跃表结构。我们知道，平衡二叉树的调整是一件令人头痛的事情，左旋右旋左右旋……一般人还真记不住，而调整一个理想的跳跃表将是一个比调整平衡二叉树还复杂的操作。幸运的是，我们并不需要通过复杂的操作调整连接来维护这样完美的跳跃表。有一种基于概率统计的插入算法，也能得到时间复杂度为 O(logn)的查询效率，这种跳跃表才是我们真正要实现的。

容易实现的跳跃表

容易实现的跳跃表，它允许简单的插入和删除元素，并提供 O(logn)的查询时间复杂度，以下我们简称为跳跃表。

先讨论插入，我们先看理想的跳跃表结构，L2 层的元素个数是 L1 层元素个数的 1/2，L3 层的元素个数是 L2 层的元素个数的 1/2，以此类推。从这里，我们可以想到，只要在插入时尽量保证上一层的元素个数是下一层元素的 1/2，我们的跳跃表就能成为理想的跳跃表。那么怎么样才能在插入时保证上一层元素个数是下一层元素个数的 1/2 呢？很简单，抛硬币就能解决了！假设元素 X 要插入跳跃表，很显然，L1 层肯定要插入 X。那么 L2 层要不要插入 X 呢？我们希望上层元素个数是下层元素个数的 1/2，所以我们有 1/2 的概率希望 X 插入 L2 层，那么抛一下硬币吧，正面就插入，反面就不插入。那么 L3 到底要不要插入 X 呢？相对于 L2 层，我们还是希望 1/2 的概率插入，那么继续抛硬币吧！以此类推，元素 X 插入第 n 层的概率是(1/2)的 n 次。这样，我们能在跳跃表中插入一个元素了。

在此还是以上图为例：跳跃表的初试状态如下图，表中没有一个元素：

如果我们要插入元素 2，首先是在底部插入元素 2，如下图：

然后我们抛硬币，结果是正面，那么我们要将 2 插入到 L2 层，如下图

继续抛硬币，结果是反面，那么元素 2 的插入操作就停止了，插入后的表结构就是上图所示。接下来，我们插入元素 33，跟元素 2 的插入一样，现在 L1 层插入 33，如下图：

然后抛硬币，结果是反面，那么元素 33 的插入操作就结束了，插入后的表结构就是上图所示。接下来，我们插入元素 55，首先在 L1 插入 55，插入后如下图：

然后抛硬币，结果是正面，那么 L2 层需要插入 55，如下图：

继续抛硬币，结果又是正面，那么 L3 层需要插入 55，如下图：

继续抛硬币，结果又是正面，那么要在 L4 插入 55，结果如下图：

继续抛硬币，结果是反面，那么 55 的插入结束，表结构就如上图所示。

以此类推，我们插入剩余的元素。当然因为规模小，结果很可能不是一个理想的跳跃表。但是如果元素个数 n 的规模很大，学过概率论的同学都知道，最终的表结构肯定非常接近于理想跳跃表。

当然，这样的分析在感性上是很直接的，但是时间复杂度的证明实在复杂，在此我就不深究了，感兴趣的可以去看关于跳跃表的 paper。

再讨论删除，删除操作没什么讲的，直接删除元素，然后调整一下删除元素后的指针即可。跟普通的链表删除操作完全一样。

总结

显而易见，跳表的查询，删除，插入速度都很高，唯一不足的大家应该也都发现了，占用空间要多一点
想进一步深入了解，推荐 2 篇不错的文章。

Java 实现跳跃表
C 实现跳跃表