数据结构与算法—跳表 agile Posted on Jul 13 2023 数据结构与算法 ## 跳表 ### 前言 跳表是面试常问的一种数据结构，它在很多中间件和语言中得到应用，我们熟知的就有Redis跳表。并且在面试的很多场景可能会问到，偶尔还会让你手写试一试(跳表可能会让手写，红黑树是不可能的)，这不，给大伙复原一个场景：  但你别慌，遇到蘑菇头这种面试官也别怕，因为你看到这篇文章了(得意😏)，不用像熊猫那样窘迫。 对于一个数据结构或算法，人群数量从听过名称、了解基本原理、清楚执行流程、能够手写 呈抖降的趋势。因为很多数据结构与算法其核心原理可能简单，但清楚其执行流程就需要动脑子去思考想明白，但是如果能够把它写出来，那就要自己一步步去设计和实现。可能要花很久才能真正写出来，并且还可能要查阅大量的资料。 而本文在前面进行介绍跳表，后面部分详细介绍跳表的设计和实现，搞懂跳表，这一篇真的就够了。 ### 快速了解跳表 跳跃表(简称跳表)由美国计算机科学家***William Pugh发明于1989年***。他在论文《Skip lists: a probabilistic alternative to balanced trees》中详细介绍了跳表的数据结构和插入删除等操作。 > 跳表(SkipList，全称跳跃表)是用于有序元素序列快速搜索查找的一个数据结构，跳表是一个随机化的数据结构，实质就是一种可以进行二分查找的有序链表。跳表在原有的有序链表上面增加了多级索引，通过索引来实现快速查找。跳表不仅能提高搜索性能，同时也可以提高插入和删除操作的性能。它在性能上和红黑树，AVL树不相上下，但是跳表的原理非常简单，实现也比红黑树简单很多。 在这里你可以看到一些关键词：链表(**有序链表**)、索引、二分查找。想必你的脑海中已经有了一个初略的印象，不过你可能还是不清楚这个"会跳的链表"有多diao，甚至还可能会产生一点疑虑：跟随机化有什么关系？你在下文中很快就能得到答案！ 回顾链表，我们知道链表和顺序表(数组)通常都是相爱相杀，成对出现，各有优劣。而链表的优势就是更高效的插入、删除。**痛点就是查询很慢很慢**！每次查询都是一种O(n)复杂度的操作，链表估计自己都气的想哭了😢。  这是一个带头结点的链表(头结点相当于一个固定的入口，不存储有意义的值)，每次查找都需要一个个枚举，相当的慢，我们能不能稍微优化一下，让它稍微跳一跳呢？答案是可以的，我们知道很多算法和数据结构**以空间换时间**，我们在上面加一层索引，让部分节点在上层能够直接定位到，这样链表的查询时间近乎减少一半，链表自己虽然没有开心起来，但收起了它想哭的脸。  这样，在查询某个节点的时候，首先会从上一层快速定位节点所在的一个范围，如果找到具体范围向下然后查找代价很小，当然在表的结构设计上会增加一个向下的索引(指针)用来查找确定底层节点。平均查找速度平均为O(n/2)。但是当节点数量很大的时候，它依旧很慢很慢。我们都知道二分查找是每次都能折半的去压缩查找范围，要是有序链表也能这么跳起来那就太完美了。没错**跳表就能让链表拥有近乎的接近二分查找的效率的一种数据结构**，其原理依然是给上面加若干层索引，优化查找速度。  通过上图你可以看到，通过这样的一个数据结构对有序链表进行查找都能近乎二分的性能。就是在上面维护那么多层的索引，首先在最高级索引上查找最后一个小于当前查找元素的位置，然后再跳到次高级索引继续查找，直到跳到最底层为止，这时候以及十分接近要查找的元素的位置了(如果查找元素存在的话)。由于根据索引可以一次跳过多个元素，所以跳查找的查找速度也就变快了。 对于理想的跳表，每向上一层索引节点数量都是下一层的1/2.那么如果n个节点增加的节点数量(1/2+1/4+…)<n。并且层数较低，对查找效果影响不大。但是对于这么一个结构，你可能会疑惑，这样完美的结构真的存在吗？大概率不存在的，因为作为一个链表，少不了增删该查的一些操作。而删除和插入可能会改变整个结构，所以上面的这些都是理想的结构，在插入的时候是否添加上层索引是个概率问题(1/2的概率)，在后面会具体讲解。 ### 跳表的增删改查 上面稍微了解了跳表是个啥，那么在这里就给大家谈谈跳表的增删改查过程。在实现本跳表的过程为了便于操作，我们将跳表的头结点(head)的key设为int的最小值(一定满足左小右大方便比较)。 对于每个节点的设置，设置成SkipNode类，为了防止初学者将next向下还是向右搞混，直接设置right，down两个指针。 ```java class SkipNode<T> { int key; T value; SkipNode right,down;//右下个方向的指针 public SkipNode (int key,T value) { this.key=key; this.value=value; } } ``` 跳表的结构和初始化也很重要，其主要参数和初始化方法为： ```java public class SkipList <T> { SkipNode headNode;//头节点，入口 int highLevel;//当前跳表索引层数 Random random;// 用于投掷硬币 final int MAX_LEVEL = 32;//最大的层 SkipList(){ random=new Random(); headNode=new SkipNode(Integer.MIN_VALUE,null); highLevel=0; } //其他方法 } ``` #### 查询操作 很多时候链表也可能这样相连仅仅是某个元素或者key作为有序的标准。所以有可能链表内部存在一些value。不过修改和查询其实都是一个操作，找到关键数字(key)。并且查找的流程也很简单，设置一个临时节点team=head。当**team不为null**其流程大致如下： (1) 从team节点出发，**如果当前节点的key与查询的key相等**，那么返回当前节点(如果是修改操作那么一直向下进行修改值即可)。 (2) 如果key不相等，且**右侧为null**，那么证明只能向下(结果可能出现在下右方向)，此时team=team.down (3) 如果key不相等，且右侧不为null，且**右侧节点key小于待查询的key**。那么说明同级还可向右，此时team=team.right (4)（否则的情况）如果key不相等，且右侧不为null，且**右侧节点key大于待查询的key** 。那么说明如果有结果的话就在这个索引和下个索引之间，此时team=team.down。 最终将按照这个步骤返回正确的节点或者null(说明没查到)。  例如上图查询12节点，首先第一步从head出发发现右侧不为空，且7<12,向右；第二步右侧为null向下；第三步节点7的右侧10<12继续向右；第四步10右侧为null向下；第五步右侧12小于等于向右。第六步起始发现相等返回节点结束。 而这块的代码也非常容易： ```java public SkipNode search(int key) { SkipNode team=headNode; while (team!=null) { if(team.key==key) { return team; } else if(team.right==null)//右侧没有了，只能下降 { team=team.down; } else if(team.right.key>key)//需要下降去寻找 { team=team.down; } else //右侧比较小向右 { team=team.right; } } return null; } ``` #### 删除操作 删除操作比起查询稍微复杂一丢丢，但是比插入简单。删除需要改变链表结构所以需要处理好节点之间的联系。对于删除操作你需要谨记以下几点： (1)删除当前节点和这个节点的前后节点都有关系 (2)删除当前层节点之后，下一层该key的节点也要删除，一直删除到最底层 根据这两点分析一下：如果找到当前节点了，**它的前面一个节点怎么查找呢**？这个总不能在遍历一遍吧！有的使用四个方向的指针(上下左右)用来找到左侧节点。是可以的，但是这里可以**特殊处理一下** ，不直接判断和操作节点，先找到**待删除节点的左侧节点**。通过这个节点即可完成删除，然后这个节点直接向下去找下一层待删除的左侧节点。设置一个临时节点team=head，**当team不为null**具体循环流程为： (1)如果**team右侧为null**，那么team=team.down(之所以敢直接这么判断是因为左侧有头结点在左侧，不用担心特殊情况) (2)如果team右侧不 为null，并且**右侧的key等于待删除的key**，那么先删除节点，再team向下team=team.down为了删除下层节点。 (3)如果team右侧不 为null，并且**右侧key小于待删除的key**，那么team向右team=team.right。 (4)如果team右侧不 为null，并且**右侧key大于待删除的key**，那么team向下team=team.down，在下层继续查找删除节点。  例如上图删除10节点，首先team=head从team出发，7<10向右(team=team.right后面省略)；第二步右侧为null只能向下；第三部右侧为10在当前层删除10节点然后向下继续查找下一层10节点；第四步8<10向右；第五步右侧为10删除该节点并且team向下。team为null说明删除完毕退出循环。 当然删除之后还要重新计算高度(防止高度下降了)。 删除操作实现的代码如下： ```java public void delete(int key)//删除不需要考虑层数 { SkipNode team=headNode; while (team!=null) { if (team.right == null) {//右侧没有了，说明这一层找到，没有只能下降 team=team.down; } else if(team.right.key==key)//找到节点，右侧即为待删除节点 { team.right=team.right.right;//删除右侧节点 team=team.down;//向下继续查找删除 } else if(team.right.key>key)//右侧已经不可能了，向下 { team=team.down; } else { //节点还在右侧 team=team.right; } } // 重新计算层高 while (headNode.right == null) { headNode= headNode.down; hightLevel--; } } ``` #### 插入操作 插入操作在实现起来是最麻烦的，需要的考虑的东西最多。回顾查询，不需要动索引；回顾删除，每层索引如果有删除就是了。但是插入不一样了，**插入需要考虑是否插入索引，插入几层**等问题。由于需要插入删除所以我们肯定无法维护一个完全理想的索引结构，因为它耗费的代价太高。但我们使用**随机化**的方法去判断是否向上层插入索引。即产生一个[0-1]的随机数如果小于0.5就向上插入索引，插入完毕后再次使用随机数判断是否向上插入索引。运气好这个值可能是多层索引，运气不好只插入最底层(这是100%插入的)。但是索引也不能不限制高度，我们一般会设置索引最高值如果大于这个值就不往上继续添加索引了。 我们一步步剖析该怎么做，其流程为 (1)首先通过上面查找的方式，找到**待插入的左节点**。插入的话最底层肯定是需要插入的，所以通过链表插入节点(需要考虑是否为末尾节点) (2)插入完这一层，需要考虑上一层是否插入，首先判断当前索引层级，如果大于最大值那么就停止(比如已经到最高索引层了)。否则设置一个随机数1/2的概率向上插入一层索引(因为理想状态下的就是每2个向上建一个索引节点)。 (3)继续(2)的操作，直到概率退出或者索引层数大于最大索引层。 在**具体向上插入**的时候，实质上还有非常重要的细节需要考虑。首先**如何找到上层的待插入节点** ？ 这个各个实现方法可能不同，如果有左、上指向的指针那么可以向左向上找到上层需要插入的节点，但是如果只有右指向和下指向的我们也可以**巧妙的借助查询过程中记录下降的节点**。因为曾经下降的节点倒序就是需要插入的节点，最底层也不例外(因为没有匹配值会下降为null结束循环)。在这里我使用**栈**这个数据结构进行存储，当然使用List也可以。下图就是给了一个插入示意图。  其次如果该层是目前的**最高层索引**，需要**继续向上建立索引**应该怎么办？ 首先跳表最初肯定是没索引的，然后慢慢添加节点才有一层、二层索引，但是如果这个节点添加的索引突破当前最高层，该怎么办呢？ 这时候**需要注意**了，跳表的head需要改变了，新建一个ListNode节点作为新的head，将它的down指向老head，将这个head节点加入栈中(也就是这个节点作为下次后面要插入的节点)，就比如上面的9节点如果运气够好在往上建立一层节点，会是这样的。  插入上层的时候注意所有节点要新建(拷贝)，除了right的指向down的指向也不能忘记，down指向上一个节点可以用一个临时节点作为前驱节点。如果层数突破当前最高层，头head节点(入口)需要改变。 这部分更多的细节在代码中注释解释了，详细代码为： ```java public void add(SkipNode node) { int key=node.key; SkipNode findNode=search(key); if(findNode!=null)//如果存在这个key的节点 { findNode.value=node.value; return; } Stack<SkipNode>stack=new Stack<SkipNode>();//存储向下的节点，这些节点可能在右侧插入节点 SkipNode team=headNode;//查找待插入的节点 找到最底层的哪个节点。 while (team!=null) {//进行查找操作 if(team.right==null)//右侧没有了，只能下降 { stack.add(team);//将曾经向下的节点记录一下 team=team.down; } else if(team.right.key>key)//需要下降去寻找 { stack.add(team);//将曾经向下的节点记录一下 team=team.down; } else //向右 { team=team.right; } } int level=1;//当前层数，从第一层添加(第一层必须添加，先添加再判断) SkipNode downNode=null;//保持前驱节点(即down的指向，初始为null) while (!stack.isEmpty()) { //在该层插入node team=stack.pop();//抛出待插入的左侧节点 SkipNode nodeTeam=new SkipNode(node.key, node.value);//节点需要重新创建 nodeTeam.down=downNode;//处理竖方向 downNode=nodeTeam;//标记新的节点下次使用 if(team.right==null) {//右侧为null 说明插入在末尾 team.right=nodeTeam; } //水平方向处理 else {//右侧还有节点，插入在两者之间 nodeTeam.right=team.right; team.right=nodeTeam; } //考虑是否需要向上 if(level>MAX_LEVEL)//已经到达最高级的节点啦 break; double num=random.nextDouble();//[0-1]随机数 if(num>0.5)//运气不好结束 break; level++; if(level>highLevel)//比当前最大高度要高但是依然在允许范围内 需要改变head节点 { highLevel=level; //需要创建一个新的节点 SkipNode highHeadNode=new SkipNode(Integer.MIN_VALUE, null); highHeadNode.down=headNode; headNode=highHeadNode;//改变head stack.add(headNode);//下次抛出head } } } ``` ### 总结 对于上面，跳表完整分析就结束啦，当然，你可能看到不同品种跳表的实现，还有的用数组方式表示上下层的关系这样也可以，但本文只定义right和down两个方向的链表更纯正化的讲解跳表。 对于跳表以及跳表的同类竞争产品：红黑树，为啥Redis的有序集合(zset) 使用跳表呢？因为跳表除了查找插入维护和红黑树有着差不多的效率，它是个链表，能确定范围区间，而区间问题在树上可能就没那么方便查询啦。而JDK中**跳跃表ConcurrentSkipListSet和ConcurrentSkipListMap。** 有兴趣的也可以查阅一下源码。 对于学习，完整的代码是非常重要的，这里我把完整代码贴出来，需要的自取。 ```java import java.util.Random; import java.util.Stack; class SkipNode<T> { int key; T value; SkipNode right,down;//左右上下四个方向的指针 public SkipNode (int key,T value) { this.key=key; this.value=value; } } public class SkipList <T> { SkipNode headNode;//头节点，入口 int highLevel;//层数 Random random;// 用于投掷硬币 final int MAX_LEVEL = 32;//最大的层 SkipList(){ random=new Random(); headNode=new SkipNode(Integer.MIN_VALUE,null); highLevel=0; } public SkipNode search(int key) { SkipNode team=headNode; while (team!=null) { if(team.key==key) { return team; } else if(team.right==null)//右侧没有了，只能下降 { team=team.down; } else if(team.right.key>key)//需要下降去寻找 { team=team.down; } else //右侧比较小向右 { team=team.right; } } return null; } public void delete(int key)//删除不需要考虑层数 { SkipNode team=headNode; while (team!=null) { if (team.right == null) {//右侧没有了，说明这一层找到，没有只能下降 team=team.down; } else if(team.right.key==key)//找到节点，右侧即为待删除节点 { team.right=team.right.right;//删除右侧节点 team=team.down;//向下继续查找删除 } else if(team.right.key>key)//右侧已经不可能了，向下 { team=team.down; } else { //节点还在右侧 team=team.right; } } // 重新计算层高 while (headNode.right == null) { headNode= headNode.down; highLevel--; } } public void add(SkipNode node) { int key=node.key; SkipNode findNode=search(key); if(findNode!=null)//如果存在这个key的节点 { findNode.value=node.value; return; } Stack<SkipNode>stack=new Stack<SkipNode>();//存储向下的节点，这些节点可能在右侧插入节点 SkipNode team=headNode;//查找待插入的节点 找到最底层的哪个节点。 while (team!=null) {//进行查找操作 if(team.right==null)//右侧没有了，只能下降 { stack.add(team);//将曾经向下的节点记录一下 team=team.down; } else if(team.right.key>key)//需要下降去寻找 { stack.add(team);//将曾经向下的节点记录一下 team=team.down; } else //向右 { team=team.right; } } int level=1;//当前层数，从第一层添加(第一层必须添加，先添加再判断) SkipNode downNode=null;//保持前驱节点(即down的指向，初始为null) while (!stack.isEmpty()) { //在该层插入node team=stack.pop();//抛出待插入的左侧节点 SkipNode nodeTeam=new SkipNode(node.key, node.value);//节点需要重新创建 nodeTeam.down=downNode;//处理竖方向 downNode=nodeTeam;//标记新的节点下次使用 if(team.right==null) {//右侧为null 说明插入在末尾 team.right=nodeTeam; } //水平方向处理 else {//右侧还有节点，插入在两者之间 nodeTeam.right=team.right; team.right=nodeTeam; } //考虑是否需要向上 if(level>MAX_LEVEL)//已经到达最高级的节点啦 break; double num=random.nextDouble();//[0-1]随机数 if(num>0.5)//运气不好结束 break; level++; if(level>highLevel)//比当前最大高度要高但是依然在允许范围内 需要改变head节点 { highLevel=level; //需要创建一个新的节点 SkipNode highHeadNode=new SkipNode(Integer.MIN_VALUE, null); highHeadNode.down=headNode; headNode=highHeadNode;//改变head stack.add(headNode);//下次抛出head } } } public void printList() { SkipNode teamNode=headNode; int index=1; SkipNode last=teamNode; while (last.down!=null){ last=last.down; } while (teamNode!=null) { SkipNode enumNode=teamNode.right; SkipNode enumLast=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(); } } public static void main(String[] args) { SkipList<Integer>list=new SkipList<Integer>(); for(int i=1;i<20;i++) { list.add(new SkipNode(i,666)); } list.printList(); list.delete(4); list.delete(8); list.printList(); } } //作者：bigsai ``` 进行测试一下可以发现跳表还是挺完美的(自夸一下)。  数据结构与算法—拓扑排序 数据结构与算法—图论之dfs、bfs(深度优先搜索、宽度优先搜索)