跳表

跳表为解决什么问题而诞生

​ 跳表本质上是一个查找结构，为了解决算法里面的查找问题而诞生。就是根据给定的key快速找到它所在的位置或者value。跳表基于一个有序链表，有序链表的查询时间复杂度是O(n),跳表可以将其优化到O(log n)。跳表经常和平衡树放在一起比较。

跳表的实现

数据结构

跳表是基于有序列表实现的，先看一下有序列表的结构：

在这样一个有序链表中，如果我们要查找某个数据，那么需要从头开始逐个遍历进行比较，直到找到包含数据的那个节点。为了减少遍历次数我们可以给有序链表加一层索引：

增加的一层索引实际上也是一个有序链表，查找数据的时候可以先沿着这个索引进行查找，遇到比待查数据大的节点时在“跳”到原始的节点进行查找。 比如打算查找23,查找的路径就是是沿着下图中标红的指针所指向的方向进行。

在这个查找过程中，由于新增加的索引，我们不再需要与链表中每个节点逐个进行比较了。需要比较的节点数大概只有原来的一半。

利用同样的方式，我们还可以在上层新产生的链表上，继续为每相邻的两个节点增加一个指针，从而产生第三层链表。如下图：

在这个新的三层链表结构上，如果我们还是查找23，那么沿着最上层链表首先要比较的是19，发现23比19大，接下来我们就知道只需要到19的后面去继续查找，从而一下子跳过了19前面的所有节点。可以想象，当链表足够长的时候，这种多层链表的查找方式能让我们跳过很多下层节点，大大加快查找的速度。

层的随机生成

上面讨论的都是一个静态的结构，但是实际中数据不会是静态的，一定是会伴随着增、删、改等操作的。那么一个问题就来了，当新增一个节点的时候这个节点应该出现在第几层索引上，换句话就是如何给他分配层数。跳表采用的是一种随机的方式生产层数，具体如下：

• 每个节点都肯定在第一层链表里面，即每个节点的层数>= 1。

• 如果一个节点有第 i 层指针（即节点在第1~i 层），那么这个节点有第i+1 层指针的概率为p。

• 节点的最大层数不允许超过一个最大值，记为MaxLevel。

这个计算随机层数的伪码如下所示：

randomLevel()
    level := 1
    // random()返回一个[0...1)的随机数
    while random() < p and level < MaxLevel do
        level := level + 1
    return level

复杂度分析

空间复杂度

我们先来计算一下每个节点所包含的平均指针数目（概率期望）。节点包含的指针数目，相当于这个算法在空间上的额外开销(overhead)，可以用来度量空间复杂度。
根据前面randomLevel()的伪码，我们很容易看出，产生越高的节点层数，概率越低。定量的分析如下：

• 节点层数至少为1。而大于1的节点层数，满足一个概率分布。

• 节点层数恰好等于1的概率为1-p。

• 节点层数大于等于2的概率为p，而节点层数恰好等于2的概率为p(1-p)。

• 节点层数大于等于3的概率为p2，而节点层数恰好等于3的概率为p^2*(1-p)。

• 节点层数大于等于4的概率为p3，而节点层数恰好等于4的概率为p^3*(1-p)。

• ……

因此，一个节点的平均层数（也即包含的平均指针数目），计算如下：

$$1*（1-p）+ 2*p（1-p)+ 3*p^2(1-p) = (1-p)\sum\limits_{k=1}^{\infty}kp^{k-1}=(1-p)*1/(1-p)^2 = 1/(1-p)$$

现在很容易计算出：

• 当p=1/2时，每个节点所包含的平均指针数目为2；
• 当p=1/4时，每个节点所包含的平均指针数目为1.33。这也是Redis里的skiplist实现在空间上的开销。

相比有序链表的额外开销是 p/（1-p），复杂度为O(n)

时间复杂度

为了计算查找长度，我们可以将查找过程倒过来看，从右下方第1层上最后到达的那个节点开始，沿着查找路径向左向上回溯，类似于爬楼梯的过程。

现在假设我们从一个层数为i的节点x出发，需要向左向上攀爬k层。这时我们有两种可能：

• 如果节点x有第(i+1)层指针，那么我们需要向上走。这种情况概率为p。

• 如果节点x没有第(i+1)层指针，那么我们需要向左走。这种情况概率为(1-p)。

用C(k)表示向上攀爬k个层级所需要走过的平均查找路径长度（概率期望），那么：

$$\left\{ \begin{aligned} C(0)= 0\\ C(k) = (1-p)*(C(k)+1) + p*(C(k-1)+1) \\ \end{aligned} \right. \Longrightarrow C(k) = C(k-1)/p \Longrightarrow C(k) = k/p (k为总层数-1)$$

下面需要估算k的值，即分析一下当跳表中有n个节点的时候，它的总层数的概率均值是多少。这个问题直观上比较好理解。根据节点的层数随机算法，容易得出：

• 第1层链表固定有n个节点，k = 0；

• 第2层链表平均有n*p个节点，k = 1;

• 第3层链表平均有n*p^2个节点,k = 2；

$$k = \log_p (\frac{1}{n})$$

那么：

$$C(k) = \frac{k}{p} =\frac{\log_p (\frac{1}{n})}{p}$$

所以时间平均复杂度为O(log n)

小结

• 各种搜索结构提高效率的方式都是通过空间换时间得到的。
• 跳表最终形成的结构和搜索树很相似。
• 跳表通过随机的方式来决定新插入节点来决定索引的层数。
• 跳表搜索的时间复杂度是 O(logn)，插入/删除也是，空间复杂度为O(n)

实际应用

• redis 的有序集合
• leveldb