前言跳表是面试中经常被问到的一种数据结构。它用于许多中间件和语言。我们熟悉RedisSkipList。而且在很多面试场景中，可能会被问到，偶尔也会被要求手写（跳表可能会手写，红黑树是不可能的），不，让大家还原一个场景：不过大家不要慌，遇到蘑菇头这样的面试官不要害怕，因为看完这篇文章（心满意足），再也不用像熊猫一样尴尬了。对于一个数据结构或算法，听过名字，了解基本原理，了解执行过程，能够手写的人数，表现出甩手的趋势。因为很多数据结构和算法的核心原理可能很简单，但是理解执行过程需要动脑筋去思考和理解，但是如果能写出来，就得一步步去设计和实现。实际写出来可能要花很长时间，而且可能需要大量的研究。本文前面介绍了跳表，后面详细介绍了跳表的设计和实现。要了解跳表，这篇文章真的够了。快速了解跳表跳表（简称跳表）是美国计算机科学家WilliamPugh于1989年发明的。他在论文《Skip lists: a probabilistic alternative to balanced trees》中详细介绍了跳表的数据结构和插入、删除等操作。跳表（SkipList，全称SkipList）是一种用于快速搜索和查找有序元素序列的数据结构。SkipList是一种随机数据结构，本质上是一个有序链表，可以进行二分查找。跳表是在原来有序链表的基础上增加多级索引，通过索引实现快速查找。跳表不仅可以提高查找性能，还可以提高插入和删除操作的性能。在性能上与红黑树和AVL树不相上下，但是跳表的原理很简单，其实现也比红黑树简单很多。这里可以看到一些关键词：链表（有序链表）、索引、二分查找。想必你心中已经有了一个大概的印象，但你可能还不知道这个“跳转链表”到底有多屌，甚至还有点疑惑：这跟随机化有什么关系？你很快就会得到答案！回顾链表，我们知道链表和时序表（数组）通常是相爱相杀，成对出现，各有优缺点。链表的优点是插入和删除效率更高。痛点是查询很慢！每一个查询都是一个复杂度为O(n)的操作，链表估计气得想哭。这是一个有头节点的链表（头节点相当于一个固定的表项，不存储有意义的值）。每次搜索都需要一个一个枚举，相当慢。我们能不能稍微优化一下，让它跳一点呢？答案是肯定的。我们知道许多算法和数据结构以空间换取时间。我们在上面加了一层索引，让一些节点可以直接定位到上层，这样链表的查询时间几乎减少了一半。链表虽然没有什么开心的感觉，但是收起了哭脸。这样，在查询某个节点时，会先从上层快速定位到该节点的一个范围。如果找到特定范围，则搜索成本很小。当然在表的结构设计上会加入向下索引。（指针）用于查找和确定底层节点。平均查找速度平均为O(n/2)。但是当节点数量很多的时候，还是很慢。我们都知道二分查找每次可以将查找范围压缩一半。如果有序链表也能这样往上跳就完美了。没错，跳链可以让链表拥有接近二分查找效率的数据结构。原理还是在里面加上几层索引，优化搜索速度。从上图可以看出，通过这样的数据结构查找有序链表的性能几乎可以提高一倍。就是在上面维护这么多层索引。首先在最高层索引上查找比当前查找元素小的最后一个位置，然后跳转到二级索引继续查找，直到最底层。这时，它离搜索元素很近了。元素的位置（如果搜索元素存在）。由于可以根据索引一次跳过多个元素，因此跳过搜索的搜索速度变得更快。对于一个理想的跳表，每个上层的索引节点数是下层索引节点数的1/2。那么如果n个节点增加节点数（1/2+1/4+...）这个结构真的存在吗？大概率是不存在的，因为作为一个链表，少不了一些增删改查的操作。删除和插入可能会改变整个结构，所以以上是理想的结构。插入时是否加上层索引是个概率题（1>查看??上面跳表的增删改查，了解跳表是什么，那这里就说一下增删改的过程，修改和检查跳表，为了方便实现跳表过程中的操作，我们将跳表的头节点（head）的key设置为int的最小值（必须满足左小的）right比较大），对于每个节点的设置，设置到SkipNode类中，为了防止初学者混淆next是down还是right，直接设置right和down指针。classSkipNode{intkey;Tvalue;SkipNoderight,down;//指向右下方向的指针publicSkipNode(intkey,Tvalue){this.key=key;this.value=value;}}skip的结构和初始化table也很重要，它的主要参数和初始化方法是：publicclassSkipList{SkipNodeheadNode;//头节点，entryinhighLevel;//当前跳表索引级别Randomrandom;//用来抛币finalintMAX_LEVEL=32;//最大层SkipList(){random=newRandom();headNode=newSkipNode(Integer.MIN_VALUE,null);highLevel=0;}//其他方法}在很多查询操作中，链表也可能是这样连接的，仅以某个元素或键作为排序标准。所以有可能链表内部有一些值。但是，无论是修改还是查询，其实都是一种查找键号（key）的操作。而且查找过程也很简单，设置一个临时节点team=head。当team不为null时，流程大致如下：(1)从team节点开始，如果当前节点的key等于查询的key，则返回当前节点（如果是a修改操作，向下修改值即可）。(2)如果keys不相等，右边为null，那么证明只能向下（结果可能出现右下方向），此时team=team.down(3)如果keys不相等，右边不为null，右边节点key小于要查询的key。那么就意味着同层也可以往右走。此时team=team.right(4)（否则）如果key不相等，且右边不为null，且右节点key大于要查询的key。那么就是说，如果有结果，就是这个索引和下一个索引之间，此时team=team.down。最后会按照这一步返回正确的节点或者null（表示没有找到）。比如查询上图中的12个节点，首先从head开始，发现右边不为空，且7<12，则往右走；第二步右边为空，往下走；第三步是节点7的右侧，10<12继续向右；第四步，右边10为空，向下；第五步，12的右边小于等于右边。第6步Start找到相等的返回节点end。而这段代码也非常简单：publicSkipNodesearch(intkey){SkipNodeteam=headNode;while(team!=null){if(team.key==key){returnteam;}elseif(team.right==null)//右边没了，只能往下{team=team.down;}elseif(team.right.key>key)//需要往下找{team=team.down;}else//右侧较小，右侧{team=team.right;}}returnnull;}删除操作删除操作比查询复杂一点，但比插入简单。删除需要改变链表的结构，所以需要处理节点之间的连接。对于删除操作，需要注意以下几点：(1)删除当前节点与该节点前后的节点有关(2)删除当前层节点后，该节点的下一层key也会被删除，直到结束底层根据这两点分析：如果找到了当前节点，如何找到上一个节点？这不能再穿越了！有些使用四个方向（上、下、左、右）的指针来找到左节点。是可以的，不过这里可以特殊处理一下，不是直接对节点进行判断和操作，而是先找到要删除的节点的左节点。删除可以通过这个节点完成，然后这个节点直接往下找下一层要删除的左边节点。设置一个临时节点team=head，当team不为null时，具体循环过程为：（1）如果team右边为null，则team=team.down（之所以敢直接判断这个是因为左边有一个头节点在左边，不用担心特殊情况）(2)如果队右边不为null，并且右边的key等于key要删除，则先删除节点，再往下teamteam=team.down删除下层节点。(3)如果队右边不为null，且右边key小于要删除的key，则队为右team=team.right。(4)如果team右侧不为null，且右侧的key大于要删除的key，则team往下走team=team.down，继续在中查找被删除的节点下层。比如上图中删除10个节点，首先team=head从team开始，7<10往右走（team=team.right后省略）；第二步右边为空，只能往下走；第三部分右边10删除当前层的10个节点，继续寻找下一层的10个节点；第四步向右8<10；第五步向右10，删除节点，队伍下山。如果team为null，表示删除完成，退出循环。实现删除操作的代码如下：publicvoiddelete(intkey)//删除不需要考虑层数{SkipNodeteam=headNode;while(team!=null){if(team.right==null){//右边没了，说明这一层找到了，如果没有team=team.down;}elseif(team.right.key==key)//找到节点，右边是要到的节点被删除{team.right=team.right.right;//删除右侧节点team=team.down;//继续往下查找删除}elseif(team.right.key>key)//右侧已经不行了，down{team=team.down;}else{//节点还在右边team=team.right;}}}插入操作插入操作是实现起来最麻烦的，也是最需要考虑的。回头查询，不需要移动索引；回过头来看删除，如果索引的每一层都有一个删除就足够了。但是插入是不同的。插入需要考虑是否插入索引，插入多少层等等。由于需要插入和删除，我们当然不能维护一个完全理想的索引结构，因为它的成本太高了。但是我们采用随机的方式来决定是否往上层插入索引。即生成一个[0-1]的随机数，小于0.5则向上插入索引。插入完成后，再次使用随机数判断是否向上插入索引。如果幸运的话，这个值可能是一个多级索引。如果运气不好，只能插入最底层（这是100%插入）。但是，索引不能不限制高度。我们一般设置最高的指标值。如果大于这个值，我们就不会继续添加索引。让我们一步步分析如何去做。过程是（1）首先，通过上面的查找方式找到要插入的左节点。如果插入，则必须插入最底层，所以通过链表插入节点（需要考虑是否是尾节点）(2)插入本层后，需要考虑是否插入了上一层。首先，判断当前指数水平。如果大于最大值则停止（例如已经达到最高索引级别）。否则，设置一个1/2概率的随机数向上插入一层索引（因为理想状态是每2向上建立一个索引节点）。(3)继续(2)的操作，直到概率退出或者索引层数大于最大索引层数。往上插的时候，其实有很重要的细节需要考虑。首先，如何找到上层要插入的节点？实现方法可能不同。如果有向左和向上的指针，就可以从向左和向上找到上层要插入的节点，但是如果只有向右和向下的指针，我们也可以机灵一点。借助于在查询期间记录下降节点。因为降序节点的逆序就是需要插入的节点，最底层也不例外（因为没有匹配值，所以会降为null结束循环）。这里我使用栈数据结构进行存储，当然也可以使用List。下图是插入示意图。其次，如果这一层是当前最高层的索引，需要继续建索引怎么办？首先，跳表一开始肯定是没有索引的，然后慢慢添加节点，有一级二级索引。但是，如果这个节点添加的指标突破了当前的顶层，怎么办？这个时候我们需要注意，需要改变跳表的表头，新建一个ListNode节点作为新的表头，将其向下指向旧的表头，并将这个表头节点加入栈中（也是这个node就是下一次要插入的节点），比如上面9个节点运气好建了一层节点，就会这样。插入到上层时，注意所有节点必须是新创建（复制）的。除了右指向下，别忘了当下指向上一个节点时，可以使用一个临时节点作为前驱节点。如果层数超过了当前的顶层，则需要改变头节点（entry）。这部分的更多细节在代码注释中解释。详细代码为：publicvoidadd(SkipNodenode){intkey=node.key;SkipNodefindNode=search(key);if(findNode!=null)//如果有这个key的节点{findNode.value=node.value;return;}Stackstack=newStack();//存储向下的节点，这些节点可能会插入到右边.while(team!=null){//执行查找操作if(team.right==null)//右边没有了，只能往下走{stack.add(team);//记录已经被过的节点downteam=team.down;}elseif(team.right.key>key)//需要向下寻找{stack.add(team);//记录下节点team=team.down;}else//totheright{team=team.right;}}intlevel=1;//当前层数，从第一层开始添加（必须添加第一层，先添加再判断）SkipNodedownNode=null;//保留前导node(即Down点，初始为null)while(!stack.isEmpty()){//在这一层插入nodeteam=stack.pop();//抛出左边待插入的节点SkipNodenodeTeam=newSkipNode(node.key,node.value);//需要重新创建节点nodeTeam.down=downNode;//处理垂直方向downNode=nodeTeam;//下次使用时标记一个新节点/右侧为null表示在最后插入n两个nodeTeam.right=team.right;team.right=nodeTeam;}//考虑是否需要上去if(level>MAX_LEVEL)//已经达到最高等级break;doublenum=random.nextDouble();//[0-1]随机数if(num>0.5)//倒霉的endbreak;level++;if(level>highLevel)//高于当前最大高度但仍需在允许范围内改变头节点range{highLevel=level;//需要创建一个新节点SkipNodehighHeadNode=newSkipNode(Integer.MIN_VALUE,null);highHeadNode.down=headNode;headNode=highHeadNode;//改变headstack.add(headNode);//下次再抛头}}}小结至此，跳表的完整分析就结束了。当然你可能会看到不同类型的跳表的实现，有的是用数组来表示上下层的关系。也是可以的，不过本文只定义了右下方向的链表。对跳转列表的更纯粹的解释。对于跳表和跳表的同类拳头产品：红黑树，为什么Redis的有序集（zset）要用跳表？什么？因为跳表除了查找、插入和维护之外，和红黑树的效率几乎一样。是一个可以确定范围区间的链表，区间问题在树上查询可能不是那么方便。以及JDK中的跳表ConcurrentSkipListSet和ConcurrentSkipListMap。有兴趣的也可以查看源码。对于学习来说，完整的代码非常重要。这里我把完整的代码贴出来，自己拿。importjava.util.Random;importjava.util.Stack;classSkipNode{intkey;Tvalue;SkipNoderight,down;//左、右、上、下四个方向的指针publicSkipNode(intkey,Tvalue){this.key=key;this.value=value;}}publicclassSkipList{SkipNodeheadNode;//头节点，入口inthighLevel;//层数Randomrandom;//用于抛币finalintMAX_LEVEL=32;//最大层SkipList(){random=newRandom();headNode=newSkipNode(Integer.MIN_VALUE,null);highLevel=0;}publicSkipNodesearch(intkey){SkipNodeteam=headNode;while(team!=null){if(team.key==key){returnteam;}elseif(team.right==null)//右边没有了，只能往下{team=team.down;}elseif(team.right.key>key)//需要往下走find{team=team.down;}else//右边比较小的向右{team=team.right;}}returnnull;}publicvoiddelete(intkey)//删除不需要考虑层数{SkipNodeteam=headNode;while(team!=null){if(team.right==null){//右侧没了，说明that找到这一层，如果没有，只能下拉team=team.down;}elseif(team.right.key==key)//找到节点，右边要删除node{team.right=team.right.right;//删除右边的节点team=team.down;//继续往下找删除}elseif(team.right.key>key)//右边没有longerpossible,down{team=team.down;}else{//节点还在右边team=team.right;}}}publicvoidadd(SkipNodenode){intkey=node.key;SkipNodefindNode=search(key);if(findNode!=null)//如果有这个key的节点{findNode.value=node.value;return;}Stackstack=newStack();//存储向下的节点，这些节点可能会插入到右边while(team!=null){//执行查找操作if(team.right==null)//右边没有了，只能往下走{stack.add(team);//记录已经被过的节点downteam=team.down;}elseif(team.right.key>key)//需要向下寻找{stack.add(team);//记录下节点team=team.down;}else//totheright{team=team.right;}}intlevel=1;//当前层数，从第一层开始添加（必须添加第一层，先添加再判断）SkipNodedownNode=null;//保留前导node(即Down点，初始为null)while(!stack.isEmpty()){//在这一层插入nodeteam=stack.pop();//抛出左边待插入的节点SkipNodenodeTeam=newSkipNode(node.key,node.value);//需要重新创建节点nodeTeam.down=downNode;//处理垂直方向downNode=nodeTeam;//下次使用时标记一个新节点/右侧为null表示在最后插入n两个nodeTeam.right=team.right;team.right=nodeTeam;}//考虑是否需要上去if(level>MAX_LEVEL)//已经达到最高等级break;doublenum=random.nextDouble();//[0-1]随机数if(num>0.5)//倒霉的endbreak;level++;if(level>highLevel)//高于当前最大高度但仍需在允许范围内改变头节点range{highLevel=level;//需要创建一个新节点SkipNodehighHeadNode=newSkipNode(Integer.MIN_VALUE,null);highHeadNode.down=headNode;headNode=highHeadNode;//改变headstack.add(headNode);//下次抛头}}}publicvoidprintList(){SkipNodeteamNode=headNode;intindex=1;SkipNodelast=teamNode;while(last.down!=null){last=last.down;}while(teamNode!=null){SkipNodenumNode=teamNode.right;SkipNodenumLast=last.right;System.out.printf("%-8s","head->");while(enumLast!=null&&enumNode!=null){if(enumLast.key==enumNode.key){System.out.printf("%-5s",enumLast.key+"->");enumLast=enumLast.right;enumNode=enumNode.right;}else{enumLast=enumLast.right;System.out.printf("%-5s","");}}teamNode=teamNode.down;index++;System.out.println();}}publicstaticvoidmain(String[]args){SkipListlist=newSkipList();for(inti=1;i<20;i++){list.add(newSkipNode(i,666));}list.printList();list.delete(4);list.delete(8);list.printList();}}测试一下，发现跳表相当完美（吹牛）
