跳跃链表的基本概念初识跳表跳跃列表是一种数据结构，不吹了，快开始品尝这美味的知识吧

跳转链表及其应用是非常热门的问题，深入了解其中的奥秘是非常有益的。让我们停止吹嘘，开始品尝这美味的知识吧！

跳表的基本概念

了解跳过表

跳过列表是一种数据结构。它允许快速查询有序连续元素的链表。跳过列表的平均查找和插入时间复杂度均为 O(log n)，优于普通队列的 O(n)。

跳转表是威廉普发明的，发明人对跳转表的评价：跳转表是一种数据结构，在很多应用中可以替代平衡树作为实现方法。

跳跃列表算法具有与平衡树相同的渐近预期时间界限，并且更简单、更快并且使用更少的空间。

这种数据结构由 William Pugh 发明，并首次出现在他 1990 年的论文“Skip Lists: A Probabilistic Alternative to Balanced Trees”中。

大白在谷歌的skip table上找到了一篇作者的论文。如果有兴趣，强烈推荐下载阅读：

看一下本文的摘要部分：

我们从中得到的信息是：skip table在动态搜索过程中使用了非严格的平衡机制，使得插入和删除更加方便快捷。这种非严格的平衡是基于概率的，而不是平衡树。严格平衡。

说到非严格平衡，首先想到的就是红黑树RbTree，它也是使用非严格平衡来避免像AVL那样调整树结构。我不会在这里展开红黑树。看来skip table也是类似的方式。但它是基于概率的。

动态查找数据结构

所谓动态搜索，就是在搜索过程中进行元素的删除和插入，这对搜索的数据结构提出了一定的挑战，因为每次删除和插入都要对数据结构进行调整以保持顺序。

可用于查找的数据结构示例包括：

下面我们来分析一下各种数据结构在处理动态搜索方面的优缺点吧！

数组结构

数组结构简单，内存连续。可以实现二分查找等基于下标的运算。一直认为数组的杀手锏是下标，连续的内存也带来了问题。

插入和删除时面临整体调整，就像在火车站排队买票一样，线头向前一步，塞子后面的人向后移动。这种整体移动操作在数组结构中性能损失很高，在数据量很大时对连续内存的要求很高。当然，这在大内存机器上可能不是问题。

插入6删除5时数组元素的移动如图：

链表结构

链表的结构也比较简单，但是它不需要内存是连续的，也没有下标来加速非连续性。但是，链表在进行删除和插入时，只影响到插入和删除点前后的元素，影响很小。

但是每次找到一个元素，我都需要遍历。即使我知道一个元素大概在哪里，我也只能一步一步地走过它。如果你看到有优化的空间，那你就很厉害了。说也许几年前，跳过手表是你的发明。

删除元素5，插入元素49时的处理如图：

平衡树

平衡树也是处理动态搜索问题的好手。树一般是基于链表实现的，但是树的节点并不是链表的简单线性关系。会有兄弟姐妹、父亲等节点，并且每一层都有层数限制。，你可以看到这棵树实际上是相当复杂的。

节点需要存储很多信息，每个指针都来回指向，复杂的结构增加了调整平衡的难度，不同情况下左右旋转，所以有这样的工程版AVL就像红黑树，但在实际场景中，中国可能不需要这些兄弟姐妹和父亲，这有点像杀鸡杀猪。

红黑树的节点结构定义：

#define COLOR_RED  0x0
#define COLOR_BLACK 0x1

typedef struct RBNode{
   int key;
   unsigned char color;
   struct RBNode *left;
   struct RBNode *right;
   struct RBNode *parent;
}rb_node_t, *rb_tree_t;

另外，在调整红黑树属性的过程中，插入分为3种情况，删除分为4种情况。仍然很难理解。除非你穿红衬衫黑裤子疯狂暗示面试官，否则被问到的概率还是很高的。没那么大。

三种结构比较

从上面的对比可以看出，数组并没有很好的满足要求分析跳跃列表的时间复杂度，链表在搜索过程中比较笨拙，平衡树有点复杂。我该怎么办？

跳台原型

以上三类结构存在一些问题，所以如果需要变换，可以看到数组和平衡树的一些特性决定了它们不容易变换（数组内存连续性、平衡树节点多指针和层次关系），相反，链表最有可能被转换和优化。

有序列表中的插入和删除相对简单。搜索时不能依赖下标，只能遍历。但是，您知道到达目的地需要走两步，但一次只能走一步。这是痛点。

该图演示了 O(n) 遍历元素 35 并跳过搜索元素 35 的过程：

似乎看到了曙光，那么如何实现跳跃呢？

那就对了！给链表添加索引分析跳跃列表的时间复杂度，让索引告诉我们接下来要跳转到哪里。

看到这里，又让我想起了经典的中间层理论。如果遇到问题，试试加个中间层，说不定就完美解决了。

跳转链表的实现原理

前面说过，可以通过在普通链表中添加索引来解决，但是具体怎么做，有什么难点呢？一步一步分析。

在项目中，跳表索引层数以及节点是否作为索引节点都是非常重要的属性。我稍后会详细讨论。现在我们来看一个简单的场景来说明索引带来的便利。

简单索引

选择每隔一个节点作为索引节点，索引是一层。这种形式虽然在项目中比较规范，但足以说明指标带来的加速。

可以在链表中添加一层指向偶数节点的指针，指向下一个偶数节点，如图：

搜索过程：

添加搜索值为55的节点时，先向上层搜索，从16跳到38，在38的下一跳会到达72，所以继续下一层类似的搜索，找到55。

多级索引

在基于偶数节点增加索引且只有两层的情况下，最高层的节点数为n/2，整体搜索复杂度降低到O(n/2),不要小看这 1/2 的系数，看这里，你会想要将索引层数增加到 k，那么复杂度就会将索引降低到 O(n/2^k)。

索引层的数量不会无休止地增加。它取决于层索引中的节点数。如果该层的索引中的节点数等于2，那么再增加一层是没有意义的。画个图看看：

这很容易理解。如果层中只有一个索引节点，比如4层索引的节点16，则只能向下遍历16，不能向后跳转到第4层的其他节点。因此，当该层的索引节点所在的点数等于2时，就达到了最高的索引级别。在分析跳过列表的复杂性时，此约束很重要。

索引级别和 inode 密度

跳表的复杂度与索引层数和索引节点的稀疏度有很大关系。

从上面我们也可以看出，索引层数等于索引节点数之比。如果跳过链表中的索引节点数量较少，则将接近退化为普通链表。这种情况下，当数据量很大的时候非常明显，看图（蓝色部分表示节点多）：

从图中可以看出，虽然有索引层，但是索引节点的数量相对于总数据来说是比较少的。在这种情况下，search 35 与没有索引的情况相比优势并不明显。

因此，跳表的效率与索引层数和索引节点密度密切相关。当然，索引节点太多意味着没有索引。

太少的 inode 与太多的 inode 一样低效。

复杂性分析

从前面的分析可以看出，跳表的复杂度与索引层数m和索引节点间隙d直接相关。索引节点间隙理解为索引节点被若干节点隔开的出现，反映了对应层的索引节点。的稀疏度，当没有索引节点时，只能遍历，不能跳转。

如何确定最高指标级别m？

如果一个链表有n个节点，如果每两个节点取出来创建一个索引，那么一级索引的节点数为n/2，二级索引的节点数为n/4 ，以此类推 第 m 个索引中的节点数为 n/(2^m)。前面说过，最高层的节点数是2，所以有一个关系：

算上最底层的原始链表，整个跳转链表的高度为h=logn（基数为2)，每层要遍历的节点数为d，那么整体的复杂度过程是：O(d*logn)。

d表示层间节点的稀疏程度，即每2个节点选择索引节点，或者每3个节点选择索引节点，每4个节点选择索引节点……

最密集的情况，d=2，借用知乎一个大佬的文章的图：

但是，索引节点的密度也意味着存储空间的增加。与普通链表相比，跳跃表是一种典型的以空间换时间的数据结构，实现了AVL O(logn)的复杂度。

跳过表的空间存储

以d=2的最密集情况为例，计算skip list中索引节点的总数：2+4+8+…n/8+n/4+n/2=n-2

由比例序列求和公式得到的d=2的跳转表的额外空间为O(n-2).

跳过表的插入和删除

项目中的skip table并没有严格要求索引层节点数遵循2:1的关系，因为这个要求会导致在插入和删除数据时进行调整，代价高昂。

跳过表的每个插入节点在插入时都被选为索引节点。如果是索引节点，层数会随机选择。整个过程是基于概率的，但是在数据量很大的情况下可以很好的使用。解决索引层数和节点数之间的权衡。

下面我们来看看插入和删除的基本操作流程吧！

插入跳转列表元素 17：

链表的插入和删除是结合查找过程完成的。贴一张William Pugh在论文中给出的skip list中插入元素17的过程图（暂时忽略节点17是否作为索引节点和索引层数，后面会详细解释）：

跳过列表元素 1 删除：

与普通链表相比，跳过列表元素的删除增加了索引层的判断。如果节点是非索引节点，则正常处理。如果节点是索引节点，则需要处理索引层节点。

跳过列表的应用

一般来说，讨论搜索问题首先想到的就是平衡树和哈希表，但是跳表的数据结构也很犀利，其性能和实现复杂度与红色不相上下-黑树，甚至某些场景都是由于红黑树。1990年发明，目前广泛应用于各种场景，包括Redis、LevelDB等数据存储引擎，后面会详细介绍。

跳表在Redis中的应用

ZSet 结构包含字典和跳过表。跳过表按分数从小到大存储所有集合元素。字典保存从成员到分数的映射。这两个结构共享相同的 member 元素并通过指针进行评分，因此不会浪费额外的内存。

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

ZSet 中的字典和跳过表布局：

ZSet中skip table的实现细节

随机层的实现原理

跳过表是一种概率数据结构，元素的插入层数是随机分配的。Willam Pugh在论文中描述其计算过程如下：指定节点的最大层数MaxLevel，指定概率p，默认层数lvl为1

生成一个从 0 到 1 的随机数 r，如果 r

重复步骤 2，直到生成的 r > p，其中 lvl 是要插入的层数。

论文中生成随机层的伪代码：

Redis中跳转表的实现基本遵循这个思路，但是有细微的差别。看一下Redis的随机源代码src/z_set.c关于跳转表层数：

/* Returns a random level for the new skiplist node we are going to create.
 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned. */
int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level}

redis.h 中定义了两个宏：

#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */

您可以在以下位置看到时间：

(random()&0xFFFF) < (ZSKIPLIST_P*0xFFFF)

第一次看到这个公式时，我有点惊讶，因为它涉及到位运算。我要研究一下Antirez为什么要用位运算来写成这样？

最初的猜测是random()返回的是一个浮点数[0-1]，于是我在网上找到了一个浮点数转二进制的工具，输入0.5查看结果：

可以看出0.5的32位十六进制转换结果为0x3f000000。如果与 0xFFFF 的 AND 运算结果为 0，则与预期不符。

在我的印象中，C语言的数学库好像没有直接随机函数，所以去Redis源码找，于是下载了3.2版本的代码，没找到random() 的实现，但我找到了。其他几个地方的应用：

看到这里的取模运算，才发现random()是[0-1]的浮点数，但是现在好像是uint32，所以Antirez的公式好理解。

ZSKIPLIST_P*0xFFFF

由于 ZSKIPLIST_P=0.25，相当于将 0xFFFF 右移 2 位为 0x3FFF。假设random()比较均匀，在清除0xFFFF的高16位后，低16位的值落在0x0000-0xFFFF之间，这个同时为真的概率只有1/4，而且更一般地说，为真的概率为 1/ZSKIPLIST_P。

随机层数的实现并不统一。重要的是随机数的生成。LevelDB中跳转表层数的生成代码如下：

template 
int SkipList::randomLevel() {

  static const unsigned int kBranching = 4;
  int height = 1;
  while (height < kMaxLevel && ((::Next(rnd_) % kBranching) == 0)) {
    height++;
  }
  assert(height > 0);
  assert(height <= kMaxLevel);
  return height;
}

uint32_t Next( uint32_t& seed) {
  seed = seed & 0x7fffffffu;

  if (seed == 0 || seed == 2147483647L) { 
    seed = 1;
  }
  static const uint32_t M = 2147483647L;
  static const uint64_t A = 16807;
  uint64_t product = seed * A;
  seed = static_cast((product >> 31) + (product & M));
  if (seed > M) {
    seed -= M;
  }
  return seed;
}

可以看出leveldb使用随机数和kBranching取模。如果值为 0，则添加一个图层。虽然不使用浮点数，但也实现了概率平衡。

跳过列表节点的平均层数

我们可以很容易地看到，节点层数越多，发生的概率越低。无论如何，层数总是满足幂律。数字越大，发生的概率越低。

如果某事发生的频率及其属性之一具有幂关系，则频率可以称为幂律。

幂律的表现是少数事件的发生频率占了发生频率的大部分，而其余事件的大部分仅占整体发生频率的一小部分。

应用于跳表随机层的幂律意味着大部分节点层是黄色部分，只有少数是绿色部分，概率很低。

定量分析如下：

节点层数正好等于K的概率为p^(k-1)(1-p)

所以，如果我们求平均节点层数，那么就变成了求概率分布的期望问题，魂画师大白又上线了：

表中P为概率，V为对应值，给出了所有可能的值和概率，所以可以计算出这个概率分布的期望值。

方括号里的公式其实就是一年级的比例顺序。常用的技术是位错减法和加法。由此可以看出，节点层数的期望值与1-p成反比。

对于 Redis，当 p=0.25 时，预期的节点层数为 1.33。

Redis源码中，有详细的插入删除调整跳表的过程。本文将不展开。代码不难理解。它是用纯 C 编写的，没有太多特殊效果。您可以放心阅读。

概括

本文主要介绍跳表的基本概念和简单原理，以及索引节点级别、时空复杂度等相关部分，不涉及概率平衡和工程实现，取Redis中底层数据结构zset作为一个典型的应用。让我们展开看看跳跃列表的实际应用。

需要注意的是，跳转链表的原理、应用和实现细节也是面试中的热门话题，值得花时间去学习和掌握。