跳表原理及Go实现跳表

1. 什么是跳表？

跳跃表（skiplist）是一种随机化的数据，由 William Pugh 在论文《Skip lists: a probabilistic alternative to balanced trees》中提出，跳跃表以有序的方式在层次化的链表中保存元素，效率和平衡树媲美 —— 查找、删除、添加等操作都可以在对数期望时间下完成，并且比起平衡树来说，跳跃表的实现要简单直观得多。

跳表（Skip list） 实际上就是在链表的基础上改造生成的。

跳表是一种各方面性能都比较优秀的动态数据结构，可以支持快速的插入、删除、查找操作，写起来也不复杂，甚至可以替代红黑树。

跳表是一个动态数据结构，可以支持快速地插入、删除、查找操作，写起来也不怎么复杂，甚至可以替代红黑树。跳表的空间复杂度是 O(n)，时间复杂度是 O(logn)。

对于一个有序的单链表来说，如果想要查找一个数据也只能从头到尾遍历链表。为了提高查询的效率，我们可以借助索引，即对链表构建一级索引，比如把每两个链表节点中较小的那个节点提取为一级索引节点（对于 key value 的值来说，可以只保留 key 值），一级索引节点也可以采用同样的方式提取为二级索引节点，如图所示，即为跳表的结构。

从图中可以看到，跳跃表主要由以下部分构成：

表头（head）：负责维护跳跃表的节点指针。
跳跃表节点：保存着元素值，以及多个层。
层：保存着指向其他元素的指针。高层的指针越过的元素数量大于等于低层的指针，为了提高查找的效率，程序总是从高层先开始访问，然后随着元素值范围的缩小，慢慢降低层次。
表尾：全部由 NULL 组成，表示跳跃表的末尾。

Redis 中的有序集合就是用跳表来实现的。那 Redis 为什么会选择用跳表来实现有序集合呢？

2. 为什么需要跳表？

链表

对于单链表来说，我们查找某个数据，只能从头到尾遍历链表，此时时间复杂度是 ○(n)。

首先，我们在心里思考一个问题：排序单链表的查找时间复杂度能否比好呢？

对于一个已经排好序的单链表来说，想要查询其中的一个数据，也只能从头开始遍历链表，不能跳过节点（skip nodes）查找，这样效率很低，时间复杂度为。

平衡二叉搜索树（AVL 树）

如上图所示，对于平衡二叉搜索树（AVL 树），在与根进行一次比较后，我们跳过了几乎一半的节点。

数组

对于排序的数组，我们可以随机访问，并且可以对数组应用二分查找法。

跳表

单链表即使存储的数据有序，若搜索某数据，也只能从头到尾遍历，搜索效率很低，平均时间复杂度是O(n)。

下图是一个简单的有序单链表，单链表的特性就是每个元素存放下一个元素的引用。即：通过第一个元素可以找到第二个元素，通过第二个元素可以找到第三个元素，依次类推，直到找到最后一个元素。

原始链表如下所示：

现在我们有个场景，想快速找到上图链表中的 10 这个元素，只能从头开始遍历链表，直到找到我们需要找的元素。查找路径：1、3、4、5、7、8、9、10。这样的查找效率很低，平均时间复杂度很高O(n)。

那我们是不是可以对排序单链表进行增强（比如像二分查找一样）来提高查找速度呢？那就是 跳表（Skip List）。

如何提高查询效率？

那怎么来提高查找效率呢？如果像图中那样，对链表建立一级“索引”，查找起来是不是就会更快一些呢？每两个结点提取一个结点到上一级，我们把抽出来的那一级叫作索引或索引层。图中的 down 表示 down 指针，指向下一级结点

比如要搜索16：

先遍历索引层，当遍历到索引层的13时，发现下一个结点是17，说明目标结点位于这俩结点中间
然后通过down指针，下降到原始链表层，继续遍历
此时只需再遍历2个结点，即可找到16！

原先单链表结构需遍历10个结点，现在只需遍历7个结点即可。可见，加一层索引，所需遍历的结点个数就减少了，搜索效率提升。

还可以再提高查询效率吗？

若再加层索引，搜索效率是不是更高？于是每两个结点再抽出一个结点到第二级索引。现在搜索16，只需遍历6个结点了！

随着索引层数的递增，会使查询效率提高的非常明显。

这里数据量不大，可能你也没感觉到搜索效率ROI高吗。

那数据量就变大一点，现有一64结点链表，给它建立五级的索引。

原来没有索引时，单链表搜索62需遍历62个结点！

现在呢？只需遍历11个！所以你现在能体会到了，当链表长度n很大时，建立索引后，搜索性能显著提升。

如下图所示，假如有序单链表现在有1万个元素，分别是 0~9999。现在我们建了很多级索引，最高级的索引，就两个元素 0、5000，次高级索引四个元素 0、2500、5000、7500，依次类推，当我们查找 7890 这个元素时，查找路径为 0、5000、7500 … 7890，通过最高级索引直接跳过了5000个元素，次高层索引直接跳过了2500个元素，从而使得链表能够实现二分查找。由此可以看出，当元素数量较多时，索引提高的效率比较大，近似于二分查找。

综上所述，跳表是一个值有序的链表建立多级索引之后的一种数据结构，通过上述的查找方式，我们可以看到类似于二叉查找树的查找方式，所以说跳表查找类似于链表的“二分查找”算法，本质上是以空间换时间。

小结

实现简单。
区间查找快。跳表可以做到O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。
并发环境优势。红黑树在插入和删除的时候可能需要做一些rebalance的操作，这样的操作可能会涉及到整个树的其他部分，而skiplist的操作显然更加局部性一些，需要锁住的节点更少，因此在这样的情况下性能好一些。

3. 跳表的操作

查询

时间复杂度

单链表查询的时间复杂度是 O(n)，那么针对一个具有多级索引的跳表，查询某个数据的时间复杂度是多少呢？能否提高查询的效率呢？

既然跳表可以提升链表查找元素的效率，那查找一个元素的时间复杂度到底是多少呢？查找元素的过程是从最高级索引开始，一层一层遍历最后下沉到原始链表。所以，时间复杂度 = 索引的高度 * 每层索引遍历元素的个数。

假设链表中有 n 个节点，我们假设每两个节点抽出一个节点作为上一级的索引节点，那么第一级的索引节点个数是 n/2，第二级的索引节点个数是 n/2^2。依次类推，第 k 级的索引节点个数是 n/2^k。假设索引层最高有 h 级，而最高层的索引节点有 2 个节点，那么得到 $h = log_2 n - 1$ ，加上原始链表这一层，一共有
$log_2 n$ 层。

我们在跳表中查询某个数据的时候，如果每一层都要编译 m 个，那么跳表一个数据的时间复杂度就是 O(mlogn)。由于我们是每两个节点抽出一个节点，而且最高层也只有两个节点，所以每一层最多比较 3 个节点。比如我们要查找的数据是 x，当在第 k 级索引层遍历到 y 节点之后，发现 x 大于 y 但是小于 y 后面的 z 节点，那么则通过 y 的down 指针从 k 级索引下降到 k-1 级索引，而在 k-1 级索引中最多只需要遍历 3 个节点即可。

因此，在跳表中查询数据的时间复杂度是 O(logn)，这个时间复杂度和二分查找是一样的。不过，这种查询效率的提升，提前是建立了很多级索引，使用了空间换时间的设计思路。

空间复杂度

假设原始链表大小为 n，那第一级链表有 n/2 个节点，第二季索引有 n/4 个节点，最顶层有 2 个节点。那么总共需要的索引节点个数就是

n/2 + n/4 + ... + 2 = n - 2

因此，跳表总的空间复杂度还是 O(n)，也就说使用跳表查询数据时，需要额外 n 个节点的存储空间。虽然空间复杂度还是没变，但是使用的额外空间还是有点多的。那么，可以采用以下方法来尽可能的降低索引占用的空间复杂度：可以多几个节点抽取成一个节点，比如每 3 个节点或者 5 个节点抽取成一个节点。虽然这样子空间复杂度还是 O(n)，但实际上所需的索引节点数量少了好多。

实际的软件开发中，原始链表中存储的有可能是很大的对象，而索引节点只需要存储关键值和几个指针，并不需要存储对象，这个时候，索引节点所占用的额外空间相比大对象来说其实很小，可以忽略不计。
举个例子：我们现在需要用跳表来给所有学生建索引，学生有很多属性：学号、姓名、性别、身份证号、年龄、家庭住址、身高、体重等。学生的各种属性只需要在原始链表中存储一份即可，我们只需要用学生的学号（int 类型的数据）建立索引，所以索引相对原始数据而言，占用的空间可以忽略。

插入

在跳表中插入一个数据，只需O(logn)时间复杂度。

在单链表中，假如定位到了要插入的位置，那么插入节点这个操作的时间复杂度很低，为 O(1)。但是要定位到插入的位置的时间复杂度是 O(n)，比如原始链表中数据有序，那么需要遍历链表才能找到要插入的位置。

对于跳表来说，由于查找某个节点的时间复杂度是 O(logn)，而插入实际上就是链表中的插入，因此插入操作的时间复杂度也就是 O(logn)。

如下图所示，假如一直往原始列表中添加数据，但是不更新索引，就可能出现两个索引节点之间数据非常多的情况，极端情况，跳表退化为单链表，从而使得查找效率从 O(logn) 退化为 O(n)。

那这种问题该怎么解决呢？

我们需要在插入数据的时候，索引节点也需要相应的增加、或者重建索引，来避免查找效率的退化。那我们该如何去维护这个索引呢？

比较容易理解的做法就是完全重建索引，我们每次插入数据后，都把这个跳表的索引删掉全部重建，重建索引的时间复杂度是多少呢？因为索引的空间复杂度是 O(n)，即：索引节点的个数是 O(n) 级别，每次完全重新建一个 O(n) 级别的索引，时间复杂度也是 O(n) 。造成的后果是：为了维护索引，导致每次插入数据的时间复杂度变成了 O(n)。

详细的方式会在下文的索引更新讲到。

删除

删除操作也是类似的，但是如果这个节点在索引中也有出现的话，除了要删除原始链表中的节点之外，还要删除索引中的。由于删除节点需要前驱节点，因此使用双向链表的话，可以很方便的删除一个节点。

综上，删除操作的时间复杂度也可以做到 O(logn)。

索引更新

当我们不停地往跳表中插入数据而不更新索引节点的话，那么 2 个索引节点之间的数据可能会非常的多。极端情况下，跳表可能会退化为单链表。

因此，作为一种动态数据结构，我们需要某种手段来维护索引与原始链表大小之间的平衡，也就是说如果链表中的节点变多了，索引节点也相应地增加一些，避免查找、插入、删除的性能下降。

对于平衡二叉树来说，比如红黑树、AVL，它们是通过左右旋的方式来保持左右子树的平衡。

往跳表插入数据时，可以选择同时将这个数据插入到部分索引层中。

那如何选择加入哪些索引层呢？

那有没有其他效率比较高的方式来维护索引呢？

假如跳表每一层的晋升概率是 1/2，最理想的索引就是在原始链表中每隔一个元素抽取一个元素做为一级索引。换种说法，我们在原始链表中随机的选 n/2 个元素做为一级索引是不是也能通过索引提高查找的效率呢？

当然可以了，因为一般随机选的元素相对来说都是比较均匀的。

如下图所示，随机选择了n/2 个元素做为一级索引，虽然不是每隔一个元素抽取一个，但是对于查找效率来讲，影响不大，比如我们想找元素 16，仍然可以通过一级索引，使得遍历路径较少了将近一半。如果抽取的一级索引的元素恰好是前一半的元素 1、3、4、5、7、8，那么查找效率确实没有提升，但是这样的概率太小了。

我们可以认为：当原始链表中元素数量足够大，且抽取足够随机的话，我们得到的索引是均匀的。我们要清楚设计良好的数据结构都是为了应对大数据量的场景，如果原始链表只有 5 个元素，那么依次遍历 5 个元素也没有关系，因为数据量太少了。所以，我们可以维护一个这样的索引：随机选 n/2 个元素做为一级索引、随机选 n/4 个元素做为二级索引、随机选 n/8 个元素做为三级索引，依次类推，一直到最顶层索引。这里每层索引的元素个数已经确定，且每层索引元素选取的足够随机，所以可以通过索引来提升跳表的查找效率。

那代码该如何实现，才能使跳表满足上述这个样子呢？

可以在每次新插入元素的时候，尽量让该元素有 1/2 的几率建立一级索引、1/4 的几率建立二级索引、1/8 的几率建立三级索引，以此类推，就能满足我们上面的条件。现在我们就需要一个概率算法帮我们把控这个 1/2、1/4、1/8 … ，当每次有数据要插入时，先通过概率算法告诉我们这个元素需要插入到几级索引中，然后开始维护索引并把数据插入到原始链表中。

跳表通过随机函数的方式来维护这种平衡性。当我们往跳表中插入数据的时候，我们通过一个随机函数，来决定将这个在哪几层索引层中添加。比如随机函数生成了值 k，那么我们就在第一级到第 k 级这 k 级索引中添加相应的索引节点。

下面开始讲解这个概率算法代码如何实现。

所以，通过 randomLevel() 方法，我们可以控制整个跳表各级索引中元素的个数。重点来了：randomLevel() 方法返回 2 的时候会建立一级索引，我们想要一级索引中元素个数占原始数据的 1/2，但是 randomLevel() 方法返回 2 的概率为 1/4，那是不是有矛盾呢？明明说好的 1/2，结果一级索引元素个数怎么变成了原始链表的 1/4？我们先看下图，应该就明白了。

假设我们在插入元素 6 的时候，randomLevel() 方法返回 1，则我们不会为 6 建立索引。插入 7 的时候，randomLevel() 方法返回3 ，所以我们需要为元素 7 建立二级索引。这里我们发现了一个特点：当建立二级索引的时候，同时也会建立一级索引；当建立三级索引时，同时也会建立一级、二级索引。所以，一级索引中元素的个数等于 [ 原始链表元素个数 ] * _[ randomLevel() 方法返回值 > 1 的概率 ]_。因为 randomLevel() 方法返回值 > 1就会建索引，凡是建索引，无论几级索引必然有一级索引，所以一级索引中元素个数占原始数据个数的比率为 randomLevel() 方法返回值 > 1 的概率。

那 randomLevel() 方法返回值 > 1 的概率是多少呢？

因为 randomLevel() 方法随机生成 1~MAX_LEVEL 的数字，且 randomLevel() 方法返回值 1 的概率为 1/2，则 randomLevel() 方法返回值 > 1 的概率为 1 - 1/2 = 1/2。即通过上述流程实现了一级索引中元素个数占原始数据个数的 1/2。

同理，当 randomLevel() 方法返回值 > 2 时，会建立二级或二级以上索引，都会在二级索引中增加元素，因此二级索引中元素个数占原始数据的比率为 randomLevel() 方法返回值 > 2 的概率。 randomLevel() 方法返回值 > 2 的概率为 1 减去 randomLevel() = 1 或 =2 的概率，即 1 - 1/2 - 1/4 = 1/4。OK，达到了我们设计的目标：二级索引中元素个数占原始数据的 1/4。

以此类推，可以得出，遵守以下两个条件：

randomLevel() 方法，随机生成 1~MAX_LEVEL 之间的数（MAX_LEVEL表示索引的最高层数），且有 1/2的概率返回 1、1/4的概率返回 2、1/8的概率返回 3 …
randomLevel() 方法返回 1 不建索引、返回2建一级索引、返回 3 建二级索引、返回 4 建三级索引 …

就可以满足我们想要的结果，即：一级索引中元素个数应该占原始数据的 1/2，二级索引中元素个数占原始数据的 1/4，三级索引中元素个数占原始数据的 1/8 ，依次类推，一直到最顶层索引。

但是问题又来了，怎么设计这么一个 randomLevel() 方法呢？

代码如下：

// 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ：
//        1/2 的概率返回 1
//        1/4 的概率返回 2
//        1/8 的概率返回 3 以此类推
private int randomLevel() {
  int level = 1;
  // 当 level < MAX_LEVEL，且随机数小于设定的晋升概率时，level + 1
  while (Math.random() < SKIPLIST_P && level < MAX_LEVEL)
    level += 1;
  return level;
}

上述代码可以实现我们的功能，而且，我们的案例中晋升概率 SKIPLIST_P 设置的 1/2，即：每两个结点抽出一个结点作为上一级索引的结点。如果我们想节省空间利用率，可以适当的降低代码中的 SKIPLIST_P，从而减少索引元素个数，Redis 的 zset 中 SKIPLIST_P 设定的 0.25。下图所示，是Redis t_zset.c 中 zslRandomLevel 函数的实现：

Redis 源码中 (random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF) 在功能上等价于我代码中的 Math.random() < SKIPLIST_P ，只不过 Redis 作者 antirez 使用位运算来提高浮点数比较的效率。

整体思路大家应该明白了，那插入数据时维护索引的时间复杂度是多少呢？**元素插入到单链表的时间复杂度为 O(1)**，我们索引的高度最多为 logn，当插入一个元素 x 时，最坏的情况就是元素 x 需要插入到每层索引中，所以插入数据到各层索引中，最坏时间复杂度是 O(logn)。

过程大概理解了，再通过一个例子描述一下跳表插入数据的全流程。现在我们要插入数据 6 到跳表中，首先 randomLevel() 返回 3，表示需要建二级索引，即：一级索引和二级索引需要增加元素 6。该跳表目前最高三级索引，首先找到三级索引的 1，发现 6 比 1大比 13小，所以，从 1 下沉到二级索引。

下沉到二级索引后，发现 6 比 1 大比 7 小，此时需要在二级索引中 1 和 7 之间加一个元素6 ，并从元素 1 继续下沉到一级索引。

下沉到一级索引后，发现 6 比 1 大比 4 大，所以往后查找，发现 6 比 4 大比 7 小，此时需要在一级索引中 4 和 7 之间加一个元素 6 ，并把二级索引的 6 指向一级索引的 6，最后，从元素 4 继续下沉到原始链表。

下沉到原始链表后，就比较简单了，发现 4、5 比 6小，7比6大，所以将6插入到 5 和 7 之间即可，整个插入过程结束。

整个插入过程的路径与查找元素路径类似，每层索引中插入元素的时间复杂度 O(1)，所以整个插入的时间复杂度是 O(logn)。

跳表的优缺点

作为快速查找的数据结构，跳表常用来和红黑树做比较，列一下跳表和红黑树的优缺点吧

跳表的优点：
1. 跳表实现起来相对简单。红黑树的定义和左旋右旋操作，确实复杂。
2. 区间查找方便。在跳表中找到一个节点后，就可以通过前后指针找到相邻的元素。红黑树则需要通过父节点，子节点去寻找，相对麻烦。
红黑树的优点
1. 内存占用小，只需要3个指针就可以（左子树，右子树，父节点）而跳表有一个向后的指针，每一层都有一个向前的指针
2. 红黑树的查找稳定，红黑树有着严格的定义，每次插入和删除数据都会通过左旋右旋来平衡树的结构，通过红黑树查找有着稳定的查找时间O(logn) ，为啥跳表是不稳定的，看到跳表是怎样确定层数的就明白了

4. 跳表的应用

适用场景：节点插入和删除操作比较少，查询频次较多的情况。

使用跳表的产品：

Lucene, elasticSearch
Redis：Redis sorted set的内部使用 HashMap 和跳表(SkipList)来保证数据的存储和有序，HashMap 里放的是成员到 score 的映射，而跳跃表里存放的是所有的成员，排序依据是 HashMap 里存的 score ，使用跳表的结构可以获得比较高的查找效率，并且在实现上比较简单。
HBase MemStore 内部数据存储

Redis 中的有序集合就是用跳表来实现的，另外还用到了散列表。为什么使用跳表而不是红黑树实现呢？最主要的是跳表它支持区间查找。

Redis 中的有序集合支持的核心操作中主要有：

插入、删除、查找一个数据；
按照区间查找数据（比如查找值在 [100, 356] 之间的数据）
迭代输出有序序列

其中插入、删除、查找操作，红黑树也可以很快完成，时间复杂度也是 O(logn)。但是按照区间来查找数据这个操作，红黑树的效率没有跳表高。跳表可以做到 O(logn) 的时间复杂度定位区间的起点，然后在原始链表中顺序往后遍历就可以了。

除了性能，还有其它原因：

代码实现比红黑树好懂、好写多了，因为简单就代表可读性好，不易出错
跳表更灵活，可通过改变索引构建策略，有效平衡执行效率和内存消耗

5. Java实现跳表

跳表实现的主要难度在于插入(add)算法。只要把add方法搞明白之后，一切都迎刃而解了。

关于跳表的插入，一张图即可描述出来，

数据结构的定义

每个节点由一个关键字 key 和一个前向数组 forwards[] 组成，该数组存储指向不同层的节点的指针。i 层的节点的前向数组保存了从第 0 层到第 i 层前向节点的指针。

跳表的节点

public class SkipListNode<T> {

    // 节点key
    int key;
    // 节点value
    T value;
    // 节点在不同层的下一个节点
    SkipListNode[] forwards;

    public static final int HEAD_KEY = Integer.MIN_VALUE; // 负无穷
    public static final int  TAIL_KEY = Integer.MAX_VALUE; // 正无穷

    public SkipListNode(int key, T value, int size) {
        this.key = key;
        this.value = value;
        this.forwards = new SkipListNode[size];
    }

}

跳表的结构

表中的元素使用结点来表示，结点的层数在它被插入时随机计算决定（与表中已有结点数目无关）。

一个i层的结点有i个前向指针（java中使用结点对象数组forward来表示），索引为从1到i。用MaxLevel来记录跳表的最大层数。

跳表的层数为当前所有结点中的最大层数（如果list为空，则层数为1）。

列表头header拥有从1到MaxLevel的前向指针：

public class SkipList<T> {

    // 最大层数
    private static final int DEFAULT_MAX_LEVEL = 32;
    // 随机层数概率，也就是随机出的层数，在 第1层以上(不包括第一层)的概率，层数不超过maxLevel，层数的起始号为1
    private static final double DEFAULT_P_FACTOR = 0.25;
    // 生成randomLevel用到的概率值
    private double P;
    // 最高层数
    private int maxLevel;
    // 当前层数
    private int currentLevel;
    // 表头
    private SkipListNode<T> head;
    // 表尾
    private SkipListNode<T> tail;
    // 节点总数
    private int size;

    public SkipList() {
        this(DEFAULT_P_FACTOR, DEFAULT_MAX_LEVEL);
    }

    public SkipList(double probability, int maxLevel) {
        this.P = probability;
        this.maxLevel = maxLevel;
        clear();
    }

    /*
     * 清空跳跃表
     */
    public void clear() {
        head = new SkipListNode<T>(SkipListNode.HEAD_KEY, null, maxLevel);
        tail = new SkipListNode<T>(SkipListNode.TAIL_KEY, null, maxLevel);

        currentLevel = 1;
        for (int i = head.forwards.length - 1; i >= 0; i--) {
            head.forwards[i] = tail;
        }
    }
}

查找

跳表的查找操纵非常类似于在跳表插入操作中搜索插入元素的位置的方法。基本的想法是：

下一个节点的关键字 key 小于查找的关键字，则我们在同一层上继续前进查找。
下一个节点的关键字 key 大于查找的关键字，则我们将指向当前节点i的指针存储在 update[i] 处，并向下移动一层，继续搜索。

在最底层（第 0 层），如果最右边元素的前向元素的值等于搜索关键字的值，则我们找到了关键字，否则未找到。

如图所示，查找关键字 17 ，红色的路线表示查找路径，其中的蓝色箭头表示最右边元素 12 的前向指针，该指针的值 17 与查找的关键字 key 相等，返回值为 key 的结点。

查找的实现代码相当简单了：

/*
    * 查找
    */
   public SkipListNode<T> search(int searchKey) {
       SkipListNode cur = head;

       //从最高层开始找,外层循环，遍历向下的指针
       for (int i = currentLevel - 1; i >= 0; i--) {
           //内层循环，遍历向右的指针,找到每一层最后一个小于searchKey的位置
           while (cur.forwards[i] != null && cur.forwards[i].key < searchKey) {
               cur = cur.forwards[i];
           }
       }
       cur = cur.forwards[0];
       //判断原始链表对于的值是否等于 value，如果找到了，返回这个Node
       if (cur.key == searchKey) {
           return cur;
       } else {
           return null;
       }
   }

插入

若key不存在，则插入该key与对应的value；若key存在，则更新value。

如果待插入的结点的层数高于跳表的当前层数currentLevel，则更新currentLevel。

选择待插入结点的层数randomLevel：

randomLevel只依赖于跳表的最高层数和概率值p。

// 理论来讲，一级索引中元素个数应该占原始数据的 50%，二级索引中元素个数占 25%，三级索引12.5% ，一直到最顶层。
   // 因为这里每一层的晋升概率是 50%。对于每一个新插入的节点，都需要调用 randomLevel 生成一个合理的层数。
   // 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ：
   //        50%的概率返回 1
   //        25%的概率返回 2
   //      12.5%的概率返回 3 ...
   private int randomLevel() {
       int level = 1;
       while (Math.random() < P && level < maxLevel) {
           level++;
       }
       return level;
   }

我们将从列表的最高层开始，将当前节点的下一个节点的 key 与要插入的 key 进行比较。基本思想是：

如果下一个节点的 key 小于要插入的 key ，则我们在同一层上继续前进查找。
如果下一个节点的 key 大于要插入的 key ，则我们将指向当前节点 i 的指针存储在 update[i] 处，并向下移动一层，继续搜索。

在第 0 层，我们一定会找到一个位置来插入给定的 key 。

以下是插入操作的代码：

/*
    * 插入：插入的时候就维护了索引，每次经过对应的层级的时候就插入对应的索引，直到到达原链表
    */
   public void add(int key, T value) {

       // 创建 update 数组并初始化
       SkipListNode<T>[] updates = new SkipListNode[maxLevel];
       SkipListNode<T> cur = head;

       for (int i = currentLevel - 1; i >= 0; i--) {
           while (cur.forwards[i] != null && cur.forwards[i].key < key) {
               cur = cur.forwards[i];
           }
           // cur.key < key <= cur.forward[i].key
           updates[i] = cur;  // update[i]就是i层级下newNode应该插入的位置，即a的位置
       }

       cur = cur.forwards[0];

       if (cur.key == key) {
           // key存在，则更新value
           cur.value = value;
       } else {
           int level = randomLevel();

           // 如果待插入的结点的层数高于跳表的当前层数currentLevel，则更新currentLevel
           if (currentLevel < level) {
               for (int i = currentLevel; i < level; i++) {
                   updates[i] = head;
               }
               currentLevel = level;
           }

           SkipListNode<T> newNode = new SkipListNode<>(key, value, level);

           // 开始在每层对应的位置插入newNode ，原本指针指向 a -> b
           for (int i = 0; i < level; i++) {
               // 修改该层链表指向为 newNode.next -> a.next
               newNode.forwards[i] = updates[i].forwards[i];
               // 修改该层链表指向为 a.next -> newNode
               updates[i].forwards[i] = newNode;
           }
       }

   }

在这里，update[i] 表示插入值为 key 的节点时，第 i 层需要修改的节点为 p，也就是位于查找路径上的节点。考虑以下示例，我们想要在其中插入值 17，设随机层数为 randomLevel() == 2 ，update[] 函数就包含两个元素，update[1] 存储的是 key 为 9 的结点的地址，**update[0]** 存储的是值为 12 的结点的地址，当插入值 17 之后，**9** 和 12 的前向结点就变成了 17 ，而 17 的前向结点就变成了**9** 和 12 原始的前向结 25 和 19 。

删除

在删除元素 key 之前，使用上述查找方法在跳表中定位元素。如果找到了元素，就像我们在单链表中所做的那样，重新排列指针以删除列表中的元素。

我们从最底层（第 0 层）开始向上重新排列，直到 update[i] 的下一个元素不是 key 。删除元素后，可能会导致跳表层数 currentLevel 的降低，最后对其进行更新即可。

如上图所示，删除 key = 6 的结点之后，第三层没有了元素(红色虚线箭头)。所以我们将跳表的层数减 1。

代码如下：

/*
     * 删除
     */
    public void delete(int key) {
        SkipListNode<T>[] updates = new SkipListNode[currentLevel];
        SkipListNode<T> cur = head;

        // 查找要删除结点的前序结点并保存至 update[] 中
        // 和添加一样，找到每层要删除的索引的对应的位置
        for (int i = currentLevel - 1; i >= 0; i--) {
            // 内层循环退出的条件是p的下一个节点的值大于等于key，即找到每一层最后一个小于key的位置
            while (cur.forwards[i] != null && cur.forwards[i].key < key) {
                cur = cur.forwards[i];
            }
            // 把cur赋值给update[i]
            updates[i] = cur;
        }

        // if条件确保最下层原始链表存在要删除的该值
        if (cur.forwards[0] != null && cur.forwards[0].key == key) {
            // 从最上层开始删,一直删到原始链表
            for (int i = currentLevel - 1; i >= 0; i--) {
                // 如果update[i]的下一个节点等于key，即 b == key ，则删除该节点
                if (updates[i].forwards[i] != null && updates[i].forwards[i].key == key) {
                    updates[i].forwards[i] = updates[i].forwards[i].forwards[i];
                }
            }
        }

        // 修改该跳表的层高，因为删除了一些索引节点，有可能层高变小
        while (currentLevel > 1 && head.forwards[currentLevel - 1] == tail) {
            currentLevel--;
        }

    }

完整代码

public class SkipList<T> {

    // 最大层数
    private static final int DEFAULT_MAX_LEVEL = 32;
    // 随机层数概率，也就是随机出的层数，在 第1层以上(不包括第一层)的概率，层数不超过maxLevel，层数的起始号为1
    private static final double DEFAULT_P_FACTOR = 0.25;
    // 生成randomLevel用到的概率值
    private double P;
    // 最高层数
    private int maxLevel;
    // 当前层数
    private int currentLevel;
    // 表头
    private SkipListNode<T> head;
    // 表尾
    private SkipListNode<T> tail;
    // 节点总数
    private int size;

    public SkipList() {
        this(DEFAULT_P_FACTOR, DEFAULT_MAX_LEVEL);
    }

    public SkipList(double probability, int maxLevel) {
        this.P = probability;
        this.maxLevel = maxLevel;
        clear();
    }

    /*
     * 清空跳跃表
     */
    public void clear() {
        head = new SkipListNode<T>(SkipListNode.HEAD_KEY, null, maxLevel);
        tail = new SkipListNode<T>(SkipListNode.TAIL_KEY, null, maxLevel);

        currentLevel = 1;
        for (int i = head.forwards.length - 1; i >= 0; i--) {
            head.forwards[i] = tail;
        }
    }


    /*
     * 查找
     */
    public SkipListNode<T> search(int searchKey) {
        SkipListNode cur = head;

        //从最高层开始找,外层循环，遍历向下的指针
        for (int i = currentLevel - 1; i >= 0; i--) {
            //内层循环，遍历向右的指针,找到每一层最后一个小于searchKey的位置
            while (cur.forwards[i] != null && cur.forwards[i].key < searchKey) {
                cur = cur.forwards[i];
            }
        }

        //判断原始链表对于的值是否等于 value，如果找到了，返回这个Node
        if (cur.key == searchKey) {
            return cur;
        } else {
            return null;
        }
    }

    /*
     * 插入：插入的时候就维护了索引，每次经过对应的层级的时候就插入对应的索引，直到到达原链表
     */
    public void add(int key, T value) {

        // 创建 update 数组并初始化
        SkipListNode<T>[] updates = new SkipListNode[maxLevel];
        SkipListNode<T> cur = head;

        for (int i = currentLevel - 1; i >= 0; i--) {
            while (cur.forwards[i] != null && cur.forwards[i].key < key) {
                cur = cur.forwards[i];
            }
            // cur.key < key <= cur.forward[i].key
            updates[i] = cur;  // update[i]就是i层级下newNode应该插入的位置，即a的位置
        }

        cur = cur.forwards[0];

        if (cur.key == key) {
            // key存在，则更新value
            cur.value = value;
        } else {
            int level = randomLevel();

            // 如果待插入的结点的层数高于跳表的当前层数currentLevel，则更新currentLevel
            if (currentLevel < level) {
                for (int i = currentLevel; i < level; i++) {
                    updates[i] = head;
                }
                currentLevel = level;
            }

            SkipListNode<T> newNode = new SkipListNode<>(key, value, level);

            // 开始在每层对应的位置插入newNode ，原本指针指向 a -> b
            for (int i = 0; i < level; i++) {
                // 修改该层链表指向为 newNode.next -> a.next
                newNode.forwards[i] = updates[i].forwards[i];
                // 修改该层链表指向为 a.next -> newNode
                updates[i].forwards[i] = newNode;
            }
        }

    }

    /*
     * 删除
     */
    public void delete(int key) {
        SkipListNode<T>[] updates = new SkipListNode[currentLevel];
        SkipListNode<T> cur = head;

        // 查找要删除结点的前序结点并保存至 update[] 中
        // 和添加一样，找到每层要删除的索引的对应的位置
        for (int i = currentLevel - 1; i >= 0; i--) {
            // 内层循环退出的条件是p的下一个节点的值大于等于key，即找到每一层最后一个小于key的位置
            while (cur.forwards[i] != null && cur.forwards[i].key < key) {
                cur = cur.forwards[i];
            }
            // 把cur赋值给update[i]
            updates[i] = cur;
        }

        // if条件确保最下层原始链表存在要删除的该值
        if (cur.forwards[0] != null && cur.forwards[0].key == key) {
            // 从最上层开始删,一直删到原始链表
            for (int i = currentLevel - 1; i >= 0; i--) {
                // 如果update[i]的下一个节点等于key，即 b == key ，则删除该节点
                if (updates[i].forwards[i] != null && updates[i].forwards[i].key == key) {
                    updates[i].forwards[i] = updates[i].forwards[i].forwards[i];
                }
            }
        }

        // 修改该跳表的层高，因为删除了一些索引节点，有可能层高变小
        while (currentLevel > 1 && head.forwards[currentLevel - 1] == tail) {
            currentLevel--;
        }

    }

    // 理论来讲，一级索引中元素个数应该占原始数据的 50%，二级索引中元素个数占 25%，三级索引12.5% ，一直到最顶层。
    // 因为这里每一层的晋升概率是 50%。对于每一个新插入的节点，都需要调用 randomLevel 生成一个合理的层数。
    // 该 randomLevel 方法会随机生成 1~MAX_LEVEL 之间的数，且 ：
    //        50%的概率返回 1
    //        25%的概率返回 2
    //      12.5%的概率返回 3 ...
    private int randomLevel() {
        int level = 1;
        while (Math.random() < P && level < maxLevel) {
            level++;
        }
        return level;
    }

    public void print() {
        for (int i = currentLevel - 1; i >= 0; i--) {
            SkipListNode<T> curNode = head.forwards[i];
            while (curNode != tail) {
                System.out.print(curNode.key + "->");
                curNode = curNode.forwards[i];
            }
            System.out.println("tail");
        }
    }

    public static void main(String[] args) {
        SkipList<Integer> sl = new SkipList<Integer>();
        sl.add(20, 20);
        sl.add(5, 5);
        sl.add(10, 10);
        sl.add(1, 1);
        sl.add(100, 100);
        sl.add(80, 80);
        sl.add(60, 60);
        sl.add(30, 30);
        System.out.println("add1------------------------------------------------------");
        sl.print();

        sl.delete(20);
        sl.delete(100);
        System.out.println("delete1------------------------------------------------------");
        sl.print();

        sl.add(122, 122);
        sl.add(38, 38);
        System.out.println("add2------------------------------------------------------");
        sl.print();

        sl.add(66, 66);
        sl.add(11, 11);
        sl.add(22, 22);
        sl.add(7, 7);
        sl.add(6, 6);
        sl.add(48, 48);
        sl.add(24, 24);
        System.out.println("add3------------------------------------------------------");
        sl.print();
    }

}

6. Go实现跳表

代码如下：

package skip

import (
	"fmt"
	"math"
	"math/rand"
)

const (
	maxLevel = 32
	r        = 0.25
)

type Node struct {
	key, value int32
	forwards   []*Node
}

type SkipList struct {
	head, tail   *Node
	currentLevel int32
	length       int32
}

func NewNode(key, value, level int32) *Node {
	node := &Node{
		key:      key,
		value:    value,
		forwards: make([]*Node, level),
	}

	for i := 0; i < len(node.forwards); i++ {
		node.forwards[i] = new(Node)
	}
	return node
}

func NewSkipList() *SkipList {
	sl := &SkipList{
		head:         NewNode(math.MinInt32, 0, maxLevel),
		tail:         NewNode(math.MaxInt32, 0, maxLevel),
		currentLevel: 1,
		length:       0,
	}

	for i := len(sl.head.forwards) - 1; i >= 0; i-- {
		sl.head.forwards[i] = sl.tail
	}
	return sl
}

func (sl *SkipList) Search(searchKey int32) *Node {
	cur := sl.head

	for i := sl.currentLevel - 1; i >= 0; i-- {
		for cur.forwards[i] != nil && cur.forwards[i].key < searchKey {
			cur = cur.forwards[i]
		}
	}

	cur = cur.forwards[0]

	if cur.key == searchKey {
		return cur
	} else {
		return nil
	}
}

func (sl *SkipList) Add(addKey, value int32) {
	updates := make([]*Node, maxLevel)
	cur := sl.head

	for i := sl.currentLevel - 1; i >= 0; i-- {
		for cur.forwards[i] != nil && cur.forwards[i].key < addKey {
			cur = cur.forwards[i]
		}
		updates[i] = cur
	}

	cur = cur.forwards[0]

	if cur.key == addKey {
		cur.value = value
	} else {
		level := sl.randomLevel()

		if sl.currentLevel < level {
			for i := sl.currentLevel; i < level; i++ {
				updates[i] = sl.head
			}
			sl.currentLevel = level
		}

		newNode := NewNode(addKey, value, level)

		var i int32
		for i = 0; i < level; i++ {
			newNode.forwards[i] = updates[i].forwards[i]
			updates[i].forwards[i] = newNode
		}

	}

}

func (sl *SkipList) Delete(key int32) {
	updates := make([]*Node, sl.currentLevel)
	cur := sl.head

	for i := sl.currentLevel - 1; i >= 0; i-- {
		for cur.forwards[i] != nil && cur.forwards[i].key < key {
			cur = cur.forwards[i]
		}
		updates[i] = cur
	}

	if cur.forwards[0] != nil && cur.forwards[0].key == key {
		for i := sl.currentLevel - 1; i >= 0; i-- {
			if updates[i].forwards[i] != nil && updates[i].forwards[i].key == key {
				updates[i].forwards[i] = updates[i].forwards[i].forwards[i]
			}
		}
	}

	for sl.currentLevel > 1 && sl.head.forwards[sl.currentLevel-1] == sl.tail {
		sl.currentLevel--
	}

}

func (sl *SkipList) randomLevel() int32 {
	var level int32 = 1
	for sl.currentLevel < maxLevel && rand.Float64() < r {
		level++
	}
	return level
}

func (sl *SkipList) Print() {

	fmt.Println(sl.currentLevel)
	for i := sl.currentLevel - 1; i >= 0; i-- {
		cur := sl.head.forwards[i]
		for cur != sl.tail {
			fmt.Print(cur.key)
			fmt.Print("-->")
			cur = cur.forwards[i]
		}
		fmt.Println("tail")
	}

}

参考感谢
Redis 有序集合使用的跳表到底是什么 (qq.com)
面试官：为何Redis使用跳表而非红黑树实现SortedSet？ (qq.com)
图解：什么是跳表？ (qq.com)
跳表 Golang 实现 (qq.com)
redis源码阅读-跳表分析 (qq.com)
带你彻底击溃跳表原理及其Golang实现！（内含图解） (qq.com)
Java手写实现跳表 - 设计跳表 - 力扣（LeetCode） (leetcode-cn.com)
跳表(Probabilistic Alternative to Balanced Trees) - 设计跳表 - 力扣（LeetCode） (leetcode-cn.com)
ByteDance高频题 - 设计跳表 - 力扣（LeetCode） (leetcode-cn.com)
Skip List–跳表（全网最详细的跳表文章没有之一） - 简书 (jianshu.com)