Skip List（跳表）是一种能高效实现插入、删除、查找的内存数据结构。常用来对标 AVL tree 或红黑树等二叉查找树。与红黑树以及其他的二分查找树相比，跳跃表的优势在于实现简单，而且在并发场景下加锁粒度更小，从而可以实现更高的并发性。因此在一些热门项目中，如 Redis、LevelDB、HBase 都把跳跃表作为一种维护有序数据集合的基础数据结构。JDK 中也内置了基于 Skip List 实现的并发容器 ConcurrentSkipListMap 和 ConcurrentSkipListSet。

基本思想

对于一个有序链表，如果要搜索一个数，需要从头到尾比较每个元素是否匹配，直到找到匹配的数为止，即时间复杂度是 $O(n)$。同理，插入或删除一个数并保持链表有序，需要先找到合适的插入或删除位置，再执行插入或删除，总计也是 $O(n)$ 的时间。

如果链表在查找的时候，能够避免依次查找元素，那么查找复杂度将降低。而跳跃表就是利用这一思想，在链表之上额外存储了一些节点的索引信息，达到避免依次查找元素的目的，从而将查询复杂度优化为 $O(\log{}n)$。将查询复杂度优化之后，自然也优化了插入和删除的复杂度。

我们新创建一个链表，它包含的元素为前一个链表的偶数个元素。这样在搜索一个元素时，我们先在上层链表进行搜索，当元素未找到时再到下层链表中搜索。我们以搜索数字 19 为例，先在上层中搜索，到达节点 17 时发现下一个节点为 21，已经大于 19，于是转到下一层搜索，找到的目标数字 19。

我们知道上层的节点数目为 $n/2$，因此，有了这层索引，我们搜索的时间复杂度降为了：$O(n/2)$。同理，我们可以不断地增加层数，来减少搜索的时间。

一般地，如果有 k 层，我们需要的搜索次数会小于 $\lceil \frac{n}{2^k} \rceil + k$，这样当层数 k 增加到 $\lceil \log_{2} n \rceil$ 时，搜索的时间复杂度就变成了 $O(\log{}n)$。其实这背后的原理和二叉搜索树或二分查找很类似，通过索引来跳过大量的节点，从而提高搜索效率。

定义

• 跳跃表由多条分层的链表组成。
• 每条链表中的元素都是有序的。
• 每条链表都有两个元素：+∞（正无穷大）和-∞（负无穷大），分别表示链表的头部和尾部。
• 上层链表元素集合是下层链表元素集合的子集。
• 从上到下，上层链表元素集合是下层链表元素集合的子集。
• 跳跃表的高度定义为水平链表的层数。

操作

查找

• 以左上角元素为起点。
• 如果当前节点的后继节点的值小于等于待查询值，则沿着这条链表向后查询，否则，切换到当前节点的下一层链表。
• 继续查询，直到找到待查询值或者当前节点为空。

删除

• 先搜索得到该节点，把节点和对应的所有索引节点全部删除。
• 搜索过程中可以记录下路径，表面删除索引层节点时重复搜索。

插入

• 上面的示例中简单设置了上层节点和下层节点的个数是 $1:2 $，以此决定跳表的高度。

• 在实际使用中，为了便于实现，采用随机算法决定每个节点的索引层数。

• 伪代码如下：

  randomLevel()
      lvl := 1
      -- random() that returns a random value in [0...1)
      while random() < p and lvl < MaxLevel do
          lvl := lvl + 1
      return lvl

• 上面的伪代码相当于抛硬币，如果是正面则层数加一，直到抛出反面为止。其中的 $MaxLevel$ 是防止如果运气太好，层数就会太高，而太高的层数往往并不会提供额外的性能，一般 $MaxLevel=log_{1/p}{n}$， $p=1/4$ 或者 $1/2$。

性能分析

在最坏的情况下，所有节点都没有创建索引，时间复杂度为 $O(n)$。但在平均情况下，搜索的时间复杂度却是 $O(\log{}n)$。一些严格的证明会涉及到比较复杂的概率统计学知识，以下只做简单说明。

• 一个节点落在第 $k$ 层的概率为 $p^{k-1}$。

• 一个最底层链表有 $n$ 个元素的跳跃表，总共元素个数为 $\underset{k=1}{Σ} n×p^{k-1}$，其中 $k$ 为跳跃表的高度。

  一个元素落在第 $k$ 层概率为 $p^{k-1}$，则第 $k$ 层插入的元素个数为 $n×p^{k-1}$，所有 $k$ 相加得到上述公式。当 $p≤ \frac{1}{2}$时，上述公式小于 $O(2n)$，所以空间复杂度为 $O(n)$。

• 跳跃表的高度为 $O(\log{}n)$。

• 跳跃表的查询时间复杂度为 $O(\log{}n)$。

  为了计算搜索的时间复杂度，我们可以将查找的过程倒过来，从搜索最后的节点开始，一直向左或向上，直到最顶层。如下图，在路径上的每一点，都可能有两种情况：

  1. 节点有上一层的节点，向上。这种情况出现的概率是 $p$。
  2. 节点没有上一层的节点，向左。出现的概率是 $1-p$。

  于是，设 C(k) 为反向搜索爬到第 k 层的平均路径长度，则有：

  C(0) = 0
  C(k) = p * (情况1) + (1-p) * (情况2)

  将两种情况也用 C 代入，有：

  C(k) = p*(1 + C(k–1)) + (1–p)*(1 + C(k))
  C(k) = C(k–1) + 1/p
  C(k) = k/p

  我们知道跳表的最大层数为 $O(\log{}n)$，因此，搜索的复杂度 $O(\log{}n)/p=O(\log{}n)$。

参考资料

跳表──没听过但很犀利的数据结构

HBase原理与实践

Java并发容器之SkipList