本文转载自微信公众号《潜行前行》，作者cscw。转载本文请联系SneakUp公众号。什么是跳表？开发中经常用到的平衡数据结构有B数、红黑数、AVL数。但是如果让你去实现其中的一个，实现起来既困难又费时。跳转链表是一种基于链表数组的快速查找数据结构。目前用于开源软件Redis和LevelDB。其效率可与红黑树和AVL树媲美。跳转列表结构publicclassSkipList{//跳转列表的头尾privateSkipListNodehead;//跳转列表包含的元素的长度privateintlength;//跳转列表的历史最大层数publicintmaxLevel;publicSecureRandomrandom;privatestaticfinalintMAX_LEVEL=31;publicSkipList(){//初始化头尾节点及其关系head=newSkipListNode<>(SkipListNode.HEAD_SCORE,null,MAX_LEVEL);//初始化size,Layer,随机长度=0;maxLevel=0;//层数从零开始计算random=newSecureRandom();}...header:指向跳表的头节点当前跳表号length：链表的元素长度。跳转链表中节点的组成：前节点、后节点、score值（map的key值）、存储对象值publicclassSkipListNode{//跳转链表中排序的score值publicdoublescore;publicTvalue;publicintlevel;//前后节点publicSkipListNodenext,pre;//上下节点组成的层publicSkipListNode[]levelNode;privateSkipListNode(doublescore,intlevel){this.score=score;this.level=level;}publicSkipListNode(doublescore,Tvalue,intlevel){this.score=score;this.value=value;this.level=level;this.levelNode=newSkipListNode[level+1];//初始化SkipListNode和各层的nodefor(inti=级别；i>0；--i){levelNode[i]=newSkipListNode(score,level);levelNode[i].levelNode=levelNode;}this.levelNode[0]=this;}@OverridepublicStringtoString(){return"Node[score="+score+",value="+value+"]";}}跳转列表就是用空间换取时间。我实现的跳转列表节点包括一个levelNode成员属性，也就是节点层。跳转链表实现快速访问的关键点是它通常访问一个数组，我们按顺序遍历，跳转链表比数组链表效率更高，因为它使用节点层存储多级索引形成一个稀疏索引，所以需要更多的内存空间跳表有多快？如果一个链表有n个节点，每提取两个节点建立一个索引，那么第一层索引的节点数约为n/2，第二层索引的节点数约为n/4，以此类推，第m层索引的节点数约为n/(2^m)。访问数据时，可以从m层索引开始查询，定位到m-1层索引数据。而m-1大约是m层的1/2。也就是说，最优时间复杂度是O(log/N)最坏情况。在实际实现中，每一层索引并不能根据数据量每次对折实现一层索引。因此，作为折衷，每一层的索引都是用全量数据随机构建的。也就是说，最坏情况的时间复杂度是O(N)，但是最优的时间复杂度常量查询是从遍历最高层级maxLevel的索引m开始的。按照以下步骤查找与该分数相等或最接近的左节点1：如果同级索引的下一个节点分数小于查询分数，则跳到下一个节点。cur=next2：如果next为空。或者下一个节点分数大于查询分数。然后跳到下一层m-1索引，循环2循环1、2步直到访问节点得分与查询得分一致，或者索引级别为0//SkipListprivateSkipListNodefindNearestNode(doublescore){intcurLevel=最大等级；SkipListNodecur=head.levelNode[curLevel];SkipListNodenext=cur.next;//得分与当前节点相同或下一个为nullwhile(score!=cur.score&&curLevel>0){//1向右下一次遍历if(next!=null&&score>=next.levelNode[0].score){cur=next;}next=cur.levelNode[curLevel].next;//向下遍历第2次layersminus1while((next==null||score0){next=cur.levelNode[--curLevel].next;}}//底层节点。returncur.levelNode[0];}publicSkipListNodeget(doublescore){//返回skiplist的最底层，最接近这个score的nodeSkipListNodep=findNearestNode(score);//score为同理，返回这个nodereturnp.score==score?p:null;}Insert如果score存在，则替换该值。如果分数对应的节点不存在，则使用随机索引级别（值0~31）。然后依赖节点属性levelNode将index从0添加到level层//SkipListpublicTput(doublescore,Tvalue){//首先得到节点SkipListNodep=findNearestNode(score);if(p.score==score){//在跳转表中，只有最底层的节点才有真正的值，只需修改最底层的值Told=p.value;p.value=value;returnold;}//nowNode是新创建的最底层节点。索引层数0到31intnodeLevel=(int)Math.round(random.nextDouble()*32);SkipListNodenowNode=newSkipListNode(score,value,nodeLevel);//初始化每一层并连接每层前后Intlevel=0；while(nodeLevel>=p.level){for(;level<=p.level;level++){insertNodeHorizo??ntally(p.levelNode[level],nowNode.levelNode[level]);}p=p.pre;}//此时p的层数大于nowNode的层数才进入循环for(;level<=nodeLevel;level++){insertNodeHorizo??ntally(p.levelNode[level],nowNode.levelNode[level]);}this.length++;if(this.maxLevelpre,SkipListNodenow){//首先考虑nownow.next=pre.next;now.pre=pre;//再次考虑pre的下一个节点if(pre.next!=null){pre.next.pre=now;}//最后考虑prepre.next=now;}删除并使用get方法找到元素，然后释放节点属性levelNode前后各层索引的引用关系。//SkipListpublicTremove(doublescore){//在最下面找到这个key对应的节点SkipListNodenow=get(score);if(now==null){returnnull;}SkipListNodecurNode,next;//释放各层索引中节点属性levelNode的引用关系for(inti=0;i<=now.level;i++){curNode=now.levelNode[i];next=curNode.next;if(next!=null){next.pre=curNode.pre;}curNode.pre.next=curNode.next;}this.length--;//更新大小，返回旧值returnnow.value;}使用示例publicstaticvoidmain(String[]args){SkipListlist=newSkipList<>();list.printSkipList();list.put(1,"csc");list.printSkipList();list.put(3,"lwl");list.printSkipList();list.put(2,"helloworld!");list.printSkipList();System.out.println(list.get(2));System.out.println(list.get(4));list.remove(2);list.printSkipList();}欢迎参考redis文章针对文中错误的设计跳表（skiplist，skipList）总结与实现-java版[1]数据结构与算法-跳表[2]
