本文转载自微信公众号《JavaKeeper》，作者海星。转载本文请联系JavaKeeper公众号。做过服务端开发的应该都知道Redis的ZSet是使用跳表实现的（当然还有压缩列表和哈希表）。1990年美国大亨WilliamPugh发表的那篇论文我就不说了，直接打开文章，一共两部分。跳过列表如何工作？其实它是在有序链表的基础上发展起来的一个竞争者：跳表（skiplist）针对的是一棵平衡树（AVLTree）优点：是一种可以插入/删除/查找的数据结构。它最大的优点是原理简单，易于实现，易于扩展，效率更高。跳表的基本思路一如既往，用循序渐进的方式带你领略WilliamPugh的用心思考。前提：跳表处理的是一个有序链表，那么我们先来看一个不能再普通的有序链表（一般是双向链表）。如果我们要找某个数，只能遍历链表，一个一个比较。时间复杂度、插入和删除操作是一样的。为了提高查找效率，我们这样在链表上做一个“索引”，我们每隔一个节点取一个数据作为索引节点（或者加一个指针），比如我们要查找31，我们可以直接在索引链表中找到（遍历3次），如果找到16，当你遍历到31时，如果发现比目标节点大，就跳到下一层，然后遍历~（蓝线表示搜索路径）嗯，如果算遍历次数的话，是的，加不加索引需要遍历4次才能找到16。这是因为数据量太小了。如果数据量大，我们还可以多建几层索引。下面4层指标的效果更明显。我们搜索的时间复杂度在原来的基础上增加了几层索引，减少了寻找一个节点需要遍历的节点数，效率提高了很多。Bingo～有没有似曾相识的感觉，像二分查找还是二分查找？fork搜索树，通过索引跳过大量节点，提高搜索效率。这样的多层链表结构就是“跳表”~~改进了多少？推理：如果一个链表有n个节点，如果每两个节点抽取一个节点建立索引，那么一级索引的节点数大约是n/2，二级索引的节点数index约为n/4，依此类推。第m级索引的节点数约为.如果一共有m级索引，第m级的节点数为2，通过我们上面找到的规律，则得到，从而m=-1。如果加上原来的链表，那么整个跳表的高度就是。当我们查询跳表时，如果每一层都需要遍历k个节点，那么最终的时间复杂度为。k的值是多少？根据每两个节点抽取一个基点建立索引的情况，每一层最多需要遍历两个节点，所以k=2。为什么每一层最多遍历两个节点？因为我们每两个节点提取一个节点来建立索引，最高层的索引只有两个节点，然后下一层的索引比上一层的索引在这两个节点之间增加了一个节点，即,上部指标的两个节点的中值。看到这里，是不是想到了二分查找呢？每次我们只需要判断我们要找的值是否在当前节点和下一个节点之间即可。好的。不信你照下图看看能不能在同一层画3条线~~5.既然知道每一层最多可以遍历两个节点，那么跳表查询数据的时间复杂度就是常数2就不用管了，就这样。空间换时间的跳表比链表效率更高，但是跳表需要存储额外的多级索引，所以需要更多的内存空间。跳转表的空间复杂度分析并不难。如果一个链表有n个节点，每抽取两个节点建立一个索引，那么一级索引的节点数约为n/2，二级索引的节点数为n/2大约是n/4，以此类推，第m级索引的节点数大约是n，可以看出这是一个几何序列。这几级索引的节点之和为n/2+n/4+n/8...+8+4+2=n-2，所以跳表的空间复杂度为。其实在软件开发中，我们不必太在意索引占用的额外空间。在讲数据结构和算法的时候，我们习惯性的把要处理的数据看成是整数，但是在实际的软件开发中，原来的链表可能存储的是大对象，索引节点只需要存储key值和几个指针不需要存储对象，所以当对象远大于索引节点时，索引占用的额外空间可以忽略不计。插入数据其实插入数据和查找是一样的，先找到要插入元素的位置，时间复杂度也是，但是有一个问题就是如果我们一直往原列表中添加数据而不更新我们的索引层，会出现两种极端情况索引节点中间数据很多，相当于退化为单链表，查找效率直接变成了跳表索引的动态更新。我们在最上面建立的索引层是下层节点数的1/2，最高层索引的节点数是2，但是如果我们随机插入或者删除原链表的一个节点，这个比例肯定会被破坏。作为一个动态的数据结构，我们需要一些手段来保持索引和原始链表大小的平衡，即如果链表中的节点较多，索引节点会相应增加，以避免复杂度下降.如果重建索引，效率无法保证。如果了解红黑树、AVL树等平衡二叉树，就知道它们是通过左右旋转来维持左右子树的大小平衡的，而跳表是通过随机函数来维持上述“平衡”的.因此，跳表（skiplist）根本不需要1:2。一个节点是否建索引，建多少层索引，可以随意选择。插入节点时通过抛硬币决定。比如我们要插入一个新的节点X，是否要为X建立索引是通过抛硬币来决定的。如果为正则建索引，否则不建。然后把它链接成从第1层到第3层的链表，也就是我们在原来链表的基础上再往上2层添加索引）。事实上，由于我们无法预测跳表的增删操作，因此很难使用有效的算法来保证索引部分始终是统一的。学过概率论的我们都知道，虽然抛硬币不能使指标位置绝对一致，但至少在数量足够大的情况下，可以做到相对一致。删除节点相对容易。如果找到索引层的节点，可以将索引节点和原链表上的节点一一删除。只需删除这一层。其实跳表的思路很好理解，但是不能用在实战中。下面看看实战跳台的实现，差不多了解一下跳台。其实就是一个有几层索引的链表。第0层为原链表，提取部分元素，在第1层形成新的链表，上下层相同元素相连；然后提取第1层的一些元素以形成第2层，依此类推。Leetcode的题目：设计跳表（https://leetcode-cn.com/problems/design-skiplist/）由于是链表结构，首先创建一个NodeclassNode{Integervalue;//节点值Node[]next;//节点在下一个不同层的节点publicNode(Integervalue,intsize){//用size表示当前节点在跳表中索引了多少层，我们先看添加节点。正如我们在上面已经知道的，添加新节点时会随机生成一个层数。看网上大佬的解释。执行插入操作时计算随机数的过程是一个非常关键的过程。的统计特性具有非常重要的影响。这不是服从均匀分布的普通随机数。它的计算过程如下：首先，每个节点都要有一个layer1指针（每个节点都在layer1链表中）。如果一个节点有一个指向第i层的指针（i>=1）（即该节点已经在从第1层到第i层的链表中），那么它有一个指向第（i+1）层指针的概率是页。一个节点的最大层数不允许超过一个最大值，记录为MaxLevel。计算随机层数的代码如下：intrandomLevel()intlevel=1;while(Math.random()
