这篇“Java跳表方法实例分析”文章的知识点大部分人都不太理解，所以小编给大家总结了以下内容，内容详细，步骤清晰，具有一定的借鉴价值，希望大家阅读完这篇文章能有所收获，下面我们一起来看看这篇“Java跳表方法实例分析”文章吧。

跳跃表是一种随机化数据结构，基于并联的链表，其效率可比拟于二叉查找树(对于大多数操作需要O(log n)平均时间)，并且对并发算法友好。

SkipList(跳表）是一种可以代替平衡树的数据结构，默认是按照Key值升序的。SkipList让已排序的数据分布在多层链表中，以0-1随机数决定一个数据的向上攀升与否，通过“空间来换取时间”的一个算法，在每个节点中增加了向前的指针，在插入、删除、查找时可以忽略一些不可能涉及到的结点，从而提高了效率。

在Java的API中已经有了实现：分别是:

ConcurrentSkipListMap(在功能上对应HashTable、HashMap、TreeMap) ；
ConcurrentSkipListSet(在功能上对应HashSet).
确切来说，SkipList更像Java中的TreeMap，TreeMap基于红黑树（一种自平衡二叉查找树）实现的，时间复杂度平均能达到O(log n)。
HashMap是基于散列表实现的，时间复杂度平均能达到O(1)。ConcurrentSkipListMap是基于跳表实现的，时间复杂度平均能达到O(log n)。

SkipList的性质

(1) 由很多层结构组成，level是通过一定的概率随机产生的。
(2) 每一层都是一个有序的链表，默认是升序
(3) 最底层(Level 1)的链表包含所有元素。
(4) 如果一个元素出现在Level i 的链表中，则它在Level i 之下的链表也都会出现。
(5) 每个节点包含两个指针，一个指向同一链表中的下一个元素，一个指向下面一层的元素。

例子：查找元素 117

(1) 比较 21， 比 21 大，往后面找

(2) 比较 37, 比 37大，比链表最大值小，从 37 的下面一层开始找

(3) 比较 71, 比 71 大，比链表最大值小，从 71 的下面一层开始找

(4) 比较 85， 比 85 大，从后面找

(5) 比较 117， 等于 117， 找到了节点。

/***找到元素val的前一个节点即最高层第一次出现的同一行的前一个元素*/privateNodefindPreNode(intval){Nodefirst=head.getFirst();//从最上层的头节点开始搜索while(first!=null){if(first.data<val&&first.next.data>val){if(first.down==null){break;}first=first.down;//往下搜索}elseif(first.data<val&&first.next.data<val){first=first.next;//往右搜索}elseif(first.data<val&&first.next.data==val){returnfirst;}}returnnull;}三、插入元素

先确定该元素要占据的层数 K（采用丢硬币的方式，这完全是随机的）然后在 Level 1 … Level K 各个层的链表都插入元素。

/***随机获取高度,（相当于抛硬币连续出现正面的次数）*@return*/privateintgetLeavel(){intk=0;while(rd.nextInt(2)==1){k++;}returnk;}

如果 K 大于链表的层数，则要添加新的层。
例子：插入 119， K = 4

从上往下删除

/***向跳表中删除元素，从上往下删除，每次找到所在行的前一个节点*@paramval*@return如果找不到待删除元素则返回false*/booleandelete(intval){NodelindPre=findPreNode(val);//找到待删除元素的最上层的前一个节点if(lindPre==null){returnfalse;}while(true){lindPre.next=lindPre.next.next;lindPre=lindPre.down;//往下遍历，直到最底下一层if(lindPre==null){break;}//跳出循环//找到待删除元素所在行的前一个节点while(lindPre.next.data!=val){lindPre=lindPre.next;}}size--;returntrue;}五、完整代码

packagecom.longstudy.algorithm;importjava.util.LinkedList;importjava.util.Random;/***@anthorlongzx*@create2021052115:20*@Description跳表抽象数据结构**/publicclassSkipList{//使用头插法插入新节点LinkedList<Node>head;//每一行的头结点，相当于跳表的第一列，默认设置为Integer.MIN_VALUELinkedList<Node>tail;//每一行大最后一个节点，相当与跳表的最后一列Integer.MAX_VALUERandomrd;//用于生成随机数数inthight=-1;//当前跳表的层数，hight从0开始,初始值为-1，intsize;//所有的节点数publicSkipList(){this.head=newLinkedList<>();this.tail=newLinkedList<>();this.rd=newRandom();}publicstaticvoidmain(String[]args){SkipListsl=newSkipList();int[]arr=newint[500];for(inti=0;i<500;i++){arr[i]=(int)(Math.random()*600);}sl.arrayToSkipList(arr);sl.showSkipList();System.out.println(sl.find(100));System.out.println(sl.find(50));System.out.println(sl.find(99));System.out.println("清空跳表");sl.clear();sl.showSkipList();}/***节点内部类*/privateclassNode{intdata;//存放数据Nodenext;//指向右边节点Nodedown;//指向下面节点intlevel;//当前所在的层publicNode(){}publicNode(intdata,intlevel){this.data=data;this.level=level;}publicNode(intdata,intlevel,Nodenext,Nodedown){this.data=data;this.level=level;this.next=next;this.down=down;}}/***向跳表中加添加元素*是否考虑重复元素？？？？？？？？？？*@paramval*@return*/booleanadd(intval){intk=getLeavel();//获得层数//层数比当前大的时候，增加新的层if(k>hight){inti=k-hight;for(intj=1;j<=i;j++){//新增头节点和尾节点Nodeh=newNode(Integer.MIN_VALUE,hight+j);if(head.size()>0){h.down=head.getFirst();//往下指}Nodet=newNode(Integer.MAX_VALUE,hight+j);//尾if(tail.size()>0){t.down=tail.getFirst();}h.next=t;//头指向尾tail.addFirst(t);head.addFirst(h);}hight=k;//修改当前的跳表层数}returnaddFromK(val,k);//从第k层添加元素}/***从跳表的第k层新增元素*被add(intval)方法调用**/booleanaddFromK(intval,intk){NodepreNewNode=newNode(val,k);NodepreLine=head.get(hight-k);//获取新增节点所在层的头节点while(preLine!=null){while(preLine.next.data<val){//往右搜索preLine=preLine.next;}preNewNode.next=preLine.next;preLine.next=preNewNode;//如果不是第一层，则建立下一层的新节点if(preNewNode.level>0){NodenewNode=newNode(val,preNewNode.level-1);preNewNode.down=newNode;//往下指向新节点preNewNode=newNode;}//往下层建立新节点preLine=preLine.down;}size++;//跳表中的元素数量加一returntrue;}/***随机获取高度,（相当于抛硬币连续出现正面的次数）*@return*/privateintgetLeavel(){intk=0;while(rd.nextInt(2)==1){k++;}returnk;}/***向跳表中删除元素，从上往下删除，每次找到所在行的前一个节点*@paramval*@return如果找不到待删除元素则返回false*/booleandelete(intval){NodelindPre=findPreNode(val);//找到待删除元素的最上层的前一个节点if(lindPre==null){returnfalse;}while(true){lindPre.next=lindPre.next.next;lindPre=lindPre.down;//往下遍历，直到最底下一层if(lindPre==null){break;}//跳出循环//找到待删除元素所在行的前一个节点while(lindPre.next.data!=val){lindPre=lindPre.next;}}size--;returntrue;}/***销毁跳表中的所有元素*/voidclear(){this.hight=-1;this.size=0;this.head=null;this.tail=null;}/***查找跳表中是否存在该元素*@paramval*@return*/booleanfind(intval){returnfindPreNode(val)!=null;}/***找到元素val的前一个节点即最高层第一次出现的同一行的前一个元素*/privateNodefindPreNode(intval){Nodefirst=head.getFirst();//从最上层的头节点开始搜索while(first!=null){if(first.data<val&&first.next.data>val){if(first.down==null){break;}first=first.down;//往下搜索}elseif(first.data<val&&first.next.data<val){first=first.next;//往右搜索}elseif(first.data<val&&first.next.data==val){returnfirst;}}returnnull;}/***将数组中的元素添加到跳表中*@paramarr*/voidarrayToSkipList(int[]arr){intlen=arr.length;for(inti=0;i<len;i++){add(arr[i]);}}/***从上到下打印跳表的内容*/voidshowSkipList(){System.out.println("元素个数为："+size);//从上往下逐层打印for(inti=0;i<=hight;i++){NodelinFirst=head.get(i);System.out.print("第"+linFirst.level+"层:"+"head->");linFirst=linFirst.next;//跳过第一列的元素while(linFirst!=null){if(linFirst.next!=null){System.out.print(""+linFirst.data+''+"->");//+"height:"+linFirst.level}else{System.out.println("tail");}linFirst=linFirst.next;}System.out.println();}}}

以上就是关于“Java跳表方法实例分析”这篇文章的内容，相信大家都有了一定的了解，希望小编分享的内容对大家有帮助，若想了解更多相关的知识内容，请关注亿速云行业资讯频道。