今天小編為大家帶來的是社區作者半夏之沫的文章，在這篇文章中他將帶領大家學習跳表的實現。
讓我們一起來了解吧~
前言
跳表可以達到和紅黑樹一樣的時間複雜度O(logN)，且實現簡單，Redis中的有序集合對象的底層數據結構就使用了跳表。本篇文章將對跳表的實現進行學習。
正文一. 跳表的基礎概念
跳表，即跳躍表（Skip List），是基於並聯的鍊表數據結構，操作效率可以達到O(logN)，對並發友好，跳表的示意圖如下所示。
跳表的特點，可以概括如下。
跳表是多層（level）鍊表結構；
跳表中的每一層都是一個有序鍊表，並且按照元素升序（默認）排列；
跳表中的元素會在哪一層出現是隨機決定的，但是只要元素出現在了第k層，那麼k層以下的鍊表也會出現這個元素；
跳表的底層的鍊表包含所有元素；
跳表頭節點和尾節點不存儲元素，且頭節點和尾節點的層數就是跳表的最大層數；
跳表中的節點包含兩個指針，一個指針指向同層鍊表的後一節點，一個指針指向下層鍊表的同元素節點。
以上圖中的跳表為例，如果要查找元素 71，那麼查找流程如下圖所示。從頂層鍊表的頭節點開始查找，查找到元素71的節點時，一共遍歷了4個節點，但是如果按照傳統鍊表的方式（即從跳表的底層鍊表的頭節點開始向後查找），那麼就需要遍歷7個節點，所以跳表以空間換時間，縮短了操作跳表所需要花費的時間。二. 跳表的節點已知跳表中的節點，需要有指向當前層鍊表後一節點的指針，和指向下層鍊表的同元素節點的指針，所以跳表中的節點，定義如下。
publicclassSkiplistNode{publicintdata;publicSkiplistNodenext;publicSkiplistNodedown;publicintlevel;publicSkiplistNode(intdata,intlevel){this.data=data;this.level=level;}}
上述是跳表中的節點的最簡單的定義方式，存儲的元素 data 為整數，節點之間進行比較時直接比較元素 data 的大小。
三. 跳表的初始化跳表初始化時，將每一層鍊表的頭尾節點創建出來並使用集合將頭尾節點進行存儲，頭尾節點的層數隨機指定，且頭尾節點的層數就代表當前跳表的層數。初始化後，跳表結構如下所示。
publicLinkedList<SkiplistNode>headNodes;publicLinkedList<SkiplistNode>tailNodes;publicintcurLevel;publicRandomrandom;publicSkiplist(){random=newRandom();//headNodes用於存儲每一層的頭節點headNodes=newLinkedList<>();//tailNodes用於存儲每一層的尾節點tailNodes=newLinkedList<>();//初始化跳表時，跳表的層數隨機指定curLevel=getRandomLevel();//指定了跳表的初始的隨機層數後，就需要將每一層的頭節點和尾節點創建出來並構建好關係SkiplistNodehead=newSkiplistNode(Integer.MIN_VALUE,0);SkiplistNodetail=newSkiplistNode(Integer.MAX_VALUE,0);for(inti=0;i<=curLevel;i++){head.next=tail;headNodes.addFirst(head);tailNodes.addFirst(tail);SkiplistNodeheadNew=newSkiplistNode(Integer.MIN_VALUE,head.level+1);SkiplistNodetailNew=newSkiplistNode(Integer.MAX_VALUE,tail.level+1);headNew.down=head;tailNew.down=tail;head=headNew;tail=tailNew;}}四. 跳表的添加方法每一個元素添加到跳表中時，首先需要隨機指定這個元素在跳表中的層數，如果隨機指定的層數大於了跳表的層數，則在將元素添加到跳表中之前，還需要擴大跳表的層數，而擴大跳表的層數就是將頭尾節點的層數擴大。下面給出需要擴大跳表層數的一次添加的過程。
現在要往跳表中添加元素 120，並且隨機指定的層數為 3，大於了當前跳表的層數 2，此時需要先擴大跳表的層數，2如 下圖所示。
將元素 120 插入到跳表中時，從頂層開始，逐層向下插入，如下圖所示。
publicvoidadd(intnum){//獲取本次添加的值的層數intlevel=getRandomLevel();//如果本次添加的值的層數大於當前跳表的層數//則需要在添加當前值前先將跳表層數擴充if(level>curLevel){expanLevel(level-curLevel);}//curNode表示num值在當前層對應的節點SkiplistNodecurNode=newSkiplistNode(num,level);//preNode表示curNode在當前層的前一個節點SkiplistNodepreNode=headNodes.get(curLevel-level);for(inti=0;i<=level;i++){//從當前層的head節點開始向後遍歷，直到找到一個preNode//使得preNode.data<num<=preNode.next.datawhile(preNode.next.data<num){preNode=preNode.next;}//將curNode插入到preNode和preNode.next中間curNode.next=preNode.next;preNode.next=curNode;//如果當前並不是0層，則繼續向下層添加節點if(curNode.level>0){SkiplistNodedownNode=newSkiplistNode(num,curNode.level-1);//curNode指向下一層的節點curNode.down=downNode;//curNode向下移動一層curNode=downNode;}//preNode向下移動一層preNode=preNode.down;}}privatevoidexpanLevel(intexpanCount){SkiplistNodehead=headNodes.getFirst();SkiplistNodetail=tailNodes.getFirst();for(inti=0;i<expanCount;i++){SkiplistNodeheadNew=newSkiplistNode(Integer.MIN_VALUE,head.level+1);SkiplistNodetailNew=newSkiplistNode(Integer.MAX_VALUE,tail.level+1);headNew.down=head;tailNew.down=tail;head=headNew;tail=tailNew;headNodes.addFirst(head);tailNodes.addFirst(tail);}}五. 跳表的搜索方法在跳表中搜索一個元素時，需要從頂層開始，逐層向下搜索。搜索時遵循如下規則。
目標值大於當前節點的後一節點值時，繼續在本層鍊表上向後搜索；
目標值大於當前節點值，小於當前節點的後一節點值時，向下移動一層，從下層鍊表的同節點位置向後搜索；
目標值等於當前節點值，搜索結束。
publicbooleansearch(inttarget){//從頂層開始尋找，curNode表示當前遍歷到的節點SkiplistNodecurNode=headNodes.getFirst();while(curNode!=null){if(curNode.next.data==target){//找到了目標值對應的節點，此時返回truereturntrue;}elseif(curNode.next.data>target){//curNode的後一節點值大於target//說明目標節點在curNode和curNode.next之間//此時需要向下層尋找curNode=curNode.down;}else{//curNode的後一節點值小於target//說明目標節點在curNode的後一節點的後面//此時在本層繼續向後尋找curNode=curNode.next;}}returnfalse;}六. 跳表的刪除方法當在跳表中需要刪除某一個元素時，則需要將這個元素在所有層的節點都刪除，具體的刪除規則如下所示。
首先按照跳表的搜索的方式，搜索待刪除節點，如果能夠搜索到，此時搜索到的待刪除節點位於該節點層數的最高層；
從待刪除節點的最高層往下，將每一層的待刪除節點都刪除掉，刪除方式就是讓待刪除節點的前一節點直接指向待刪除節點的後一節點。
publicbooleanerase(intnum){//刪除節點的遍歷過程與尋找節點的遍歷過程是相同的//不過在刪除節點時如果找到目標節點，則需要執行節點刪除的操作SkiplistNodecurNode=headNodes.getFirst();while(curNode!=null){if(curNode.next.data==num){//preDeleteNode表示待刪除節點的前一節點SkiplistNodepreDeleteNode=curNode;while(true){//刪除當前層的待刪除節點，就是讓待刪除節點的前一節點指向待刪除節點的後一節點preDeleteNode.next=curNode.next.next;//當前層刪除完後，需要繼續刪除下一層的待刪除節點//這裡讓preDeleteNode向下移動一層//向下移動一層後，preDeleteNode就不一定是待刪除節點的前一節點了preDeleteNode=preDeleteNode.down;//如果preDeleteNode為null，說明已經將底層的待刪除節點刪除了//此時就結束刪除流程，並返回trueif(preDeleteNode==null){returntrue;}//preDeleteNode向下移動一層後，需要繼續從當前位置向後遍歷//直到找到一個preDeleteNode，使得preDeleteNode.next的值等於目標值//此時preDeleteNode就又變成了待刪除節點的前一節點while(preDeleteNode.next.data!=num){preDeleteNode=preDeleteNode.next;}}}elseif(curNode.next.data>num){curNode=curNode.down;}else{curNode=curNode.next;}}returnfalse;}七. 跳表完整代碼
publicclassSkiplist{publicLinkedList<SkiplistNode>headNodes;publicLinkedList<SkiplistNode>tailNodes;publicintcurLevel;publicRandomrandom;publicSkiplist(){random=newRandom();//headNodes用於存儲每一層的頭節點headNodes=newLinkedList<>();//tailNodes用於存儲每一層的尾節點tailNodes=newLinkedList<>();//初始化跳表時，跳表的層數隨機指定curLevel=getRandomLevel();//指定了跳表的初始的隨機層數後，就需要將每一層的頭節點和尾節點創建出來並構建好關係SkiplistNodehead=newSkiplistNode(Integer.MIN_VALUE,0);SkiplistNodetail=newSkiplistNode(Integer.MAX_VALUE,0);for(inti=0;i<=curLevel;i++){head.next=tail;headNodes.addFirst(head);tailNodes.addFirst(tail);SkiplistNodeheadNew=newSkiplistNode(Integer.MIN_VALUE,head.level+1);SkiplistNodetailNew=newSkiplistNode(Integer.MAX_VALUE,tail.level+1);headNew.down=head;tailNew.down=tail;head=headNew;tail=tailNew;}}publicbooleansearch(inttarget){//從頂層開始尋找，curNode表示當前遍歷到的節點SkiplistNodecurNode=headNodes.getFirst();while(curNode!=null){if(curNode.next.data==target){//找到了目標值對應的節點，此時返回truereturntrue;}elseif(curNode.next.data>target){//curNode的後一節點值大於target//說明目標節點在curNode和curNode.next之間//此時需要向下層尋找curNode=curNode.down;}else{//curNode的後一節點值小於target//說明目標節點在curNode的後一節點的後面//此時在本層繼續向後尋找curNode=curNode.next;}}returnfalse;}publicvoidadd(intnum){//獲取本次添加的值的層數intlevel=getRandomLevel();//如果本次添加的值的層數大於當前跳表的層數//則需要在添加當前值前先將跳表層數擴充if(level>curLevel){expanLevel(level-curLevel);}//curNode表示num值在當前層對應的節點SkiplistNodecurNode=newSkiplistNode(num,level);//preNode表示curNode在當前層的前一個節點SkiplistNodepreNode=headNodes.get(curLevel-level);for(inti=0;i<=level;i++){//從當前層的head節點開始向後遍歷，直到找到一個preNode//使得preNode.data<num<=preNode.next.datawhile(preNode.next.data<num){preNode=preNode.next;}//將curNode插入到preNode和preNode.next中間curNode.next=preNode.next;preNode.next=curNode;//如果當前並不是0層，則繼續向下層添加節點if(curNode.level>0){SkiplistNodedownNode=newSkiplistNode(num,curNode.level-1);//curNode指向下一層的節點curNode.down=downNode;//curNode向下移動一層curNode=downNode;}//preNode向下移動一層preNode=preNode.down;}}publicbooleanerase(intnum){//刪除節點的遍歷過程與尋找節點的遍歷過程是相同的//不過在刪除節點時如果找到目標節點，則需要執行節點刪除的操作SkiplistNodecurNode=headNodes.getFirst();while(curNode!=null){if(curNode.next.data==num){//preDeleteNode表示待刪除節點的前一節點SkiplistNodepreDeleteNode=curNode;while(true){//刪除當前層的待刪除節點，就是讓待刪除節點的前一節點指向待刪除節點的後一節點preDeleteNode.next=curNode.next.next;//當前層刪除完後，需要繼續刪除下一層的待刪除節點//這裡讓preDeleteNode向下移動一層//向下移動一層後，preDeleteNode就不一定是待刪除節點的前一節點了preDeleteNode=preDeleteNode.down;//如果preDeleteNode為null，說明已經將底層的待刪除節點刪除了//此時就結束刪除流程，並返回trueif(preDeleteNode==null){returntrue;}//preDeleteNode向下移動一層後，需要繼續從當前位置向後遍歷//直到找到一個preDeleteNode，使得preDeleteNode.next的值等於目標值//此時preDeleteNode就又變成了待刪除節點的前一節點while(preDeleteNode.next.data!=num){preDeleteNode=preDeleteNode.next;}}}elseif(curNode.next.data>num){curNode=curNode.down;}else{curNode=curNode.next;}}returnfalse;}privatevoidexpanLevel(intexpanCount){SkiplistNodehead=headNodes.getFirst();SkiplistNodetail=tailNodes.getFirst();for(inti=0;i<expanCount;i++){SkiplistNodeheadNew=newSkiplistNode(Integer.MIN_VALUE,head.level+1);SkiplistNodetailNew=newSkiplistNode(Integer.MAX_VALUE,tail.level+1);headNew.down=head;tailNew.down=tail;head=headNew;tail=tailNew;headNodes.addFirst(head);tailNodes.addFirst(tail);}}privateintgetRandomLevel(){intlevel=0;while(random.nextInt(2)>1){level++;}returnlevel;}}
總結跳表的時間複雜度與AVL樹和紅黑樹相同，可以達到O(logN)，但是AVL樹要維持高度的平衡，紅黑樹要維持高度的近似平衡，這都會導致插入或者刪除節點時的一些時間開銷，所以跳表相較於AVL樹和紅黑樹來說，省去了維持高度的平衡的時間開銷，但是相應的也付出了更多的空間來存儲多個層的節點，所以跳表是用空間換時間的數據結構。
點擊左下角閱讀原文，到SegmentFault 思否社區和文章作者展開更多互動和交流，「公眾號後台」回復「入群」即可加入我們的技術交流群，收穫更多的技術文章~
留言列表