[[360331]]

 前言

跳表是面試常問的一種數據結構，它在很多中間件和語言中得到應用，我們熟知的就有Redis跳表。并且在面試的很多場景可能會問到，偶爾還會讓你手寫試一試(跳表可能會讓手寫，紅黑樹是不可能的)，這不，給大伙復原一個場景：

但你別慌，遇到蘑菇頭這種面試官也別怕，因為你看到這篇文章了(得意)，不用像熊貓那樣窘迫。

對于一個數據結構或算法，人群數量從聽過名稱、了解基本原理、清楚執(zhí)行流程、能夠手寫 呈抖降的趨勢。因為很多數據結構與算法其核心原理可能簡單，但清楚其執(zhí)行流程就需要動腦子去思考想明白，但是如果能夠把它寫出來，那就要自己一步步去設計和實現。可能要花很久才能真正寫出來，并且還可能要查閱大量的資料。

而本文在前面進行介紹跳表，后面部分詳細介紹跳表的設計和實現，搞懂跳表，這一篇真的就夠了。

快速了解跳表

跳躍表(簡稱跳表)由美國計算機科學家William Pugh發(fā)明于1989年。他在論文《Skip lists: a probabilistic alternative to balanced trees》中詳細介紹了跳表的數據結構和插入刪除等操作。

• 跳表(SkipList，全稱跳躍表)是用于有序元素序列快速搜索查找的一個數據結構，跳表是一個隨機化的數據結構，實質就是一種可以進行二分查找的有序鏈表。跳表在原有的有序鏈表上面增加了多級索引，通過索引來實現快速查找。跳表不僅能提高搜索性能，同時也可以提高插入和刪除操作的性能。它在性能上和紅黑樹，AVL樹不相上下，但是跳表的原理非常簡單，實現也比紅黑樹簡單很多。

在這里你可以看到一些關鍵詞：鏈表(有序鏈表)、索引、二分查找。想必你的腦海中已經有了一個初略的印象，不過你可能還是不清楚這個"會跳的鏈表"有多diao，甚至還可能會產生一點疑慮：跟隨機化有什么關系?你在下文中很快就能得到答案!

回顧鏈表，我們知道鏈表和順序表(數組)通常都是相愛相殺，成對出現，各有優(yōu)劣。而鏈表的優(yōu)勢就是更高效的插入、刪除。痛點就是查詢很慢很慢!每次查詢都是一種O(n)復雜度的操作，鏈表估計自己都氣的想哭了。

這是一個帶頭結點的鏈表(頭結點相當于一個固定的入口，不存儲有意義的值)，每次查找都需要一個個枚舉，相當的慢，我們能不能稍微優(yōu)化一下，讓它稍微跳一跳呢?答案是可以的，我們知道很多算法和數據結構以空間換時間，我們在上面加一層索引，讓部分節(jié)點在上層能夠直接定位到，這樣鏈表的查詢時間近乎減少一半，鏈表自己雖然沒有開心起來，但收起了它想哭的臉。

這樣，在查詢某個節(jié)點的時候，首先會從上一層快速定位節(jié)點所在的一個范圍，如果找到具體范圍向下然后查找代價很小，當然在表的結構設計上會增加一個向下的索引(指針)用來查找確定底層節(jié)點。平均查找速度平均為O(n/2)。但是當節(jié)點數量很大的時候，它依舊很慢很慢。我們都知道二分查找是每次都能折半的去壓縮查找范圍，要是有序鏈表也能這么跳起來那就太完美了。沒錯跳表就能讓鏈表擁有近乎的接近二分查找的效率的一種數據結構，其原理依然是給上面加若干層索引，優(yōu)化查找速度。

通過上圖你可以看到，通過這樣的一個數據結構對有序鏈表進行查找都能近乎二分的性能。就是在上面維護那么多層的索引，首先在最高級索引上查找最后一個小于當前查找元素的位置，然后再跳到次高級索引繼續(xù)查找，直到跳到最底層為止，這時候以及十分接近要查找的元素的位置了(如果查找元素存在的話)。由于根據索引可以一次跳過多個元素，所以跳查找的查找速度也就變快了。

對于理想的跳表，每向上一層索引節(jié)點數量都是下一層的1/2.那么如果n個節(jié)點增加的節(jié)點數量(1/2+1/4+…)的結構真的存在嗎?大概率不存在的，因為作為一個鏈表，少不了增刪該查的一些操作。而刪除和插入可能會改變整個結構，所以上面的這些都是理想的結構，在插入的時候是否添加上層索引是個概率問題(1>

跳表的增刪改查

上面稍微了解了跳表是個啥，那么在這里就給大家談談跳表的增刪改查過程。在實現本跳表的過程為了便于操作，我們將跳表的頭結點(head)的key設為int的最小值(一定滿足左小右大方便比較)。

對于每個節(jié)點的設置，設置成SkipNode類，為了防止初學者將next向下還是向右搞混，直接設置right，down兩個指針。

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;//頭節(jié)點，入口 
    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)。并且查找的流程也很簡單，設置一個臨時節(jié)點team=head。當team不為null其流程大致如下：

(1) 從team節(jié)點出發(fā)，如果當前節(jié)點的key與查詢的key相等，那么返回當前節(jié)點(如果是修改操作那么一直向下進行修改值即可)。

(2) 如果key不相等，且右側為null，那么證明只能向下(結果可能出現在下右方向)，此時team=team.down

(3) 如果key不相等，且右側不為null，且右側節(jié)點key小于待查詢的key。那么說明同級還可向右，此時team=team.right

(4)(否則的情況)如果key不相等，且右側不為null，且右側節(jié)點key大于待查詢的key 。那么說明如果有結果的話就在這個索引和下個索引之間，此時team=team.down。

最終將按照這個步驟返回正確的節(jié)點或者null(說明沒查到)。

例如上圖查詢12節(jié)點，首先第一步從head出發(fā)發(fā)現右側不為空，且7<12,向右;第二步右側為null向下;第三步節(jié)點7的右側10<12繼續(xù)向右;第四步10右側為null向下;第五步右側12小于等于向右。第六步起始發(fā)現相等返回節(jié)點結束。

而這塊的代碼也非常容易：

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; 
} 

 刪除操作

刪除操作比起查詢稍微復雜一丟丟，但是比插入簡單。刪除需要改變鏈表結構所以需要處理好節(jié)點之間的聯系。對于刪除操作你需要謹記以下幾點：

(1)刪除當前節(jié)點和這個節(jié)點的前后節(jié)點都有關系

(2)刪除當前層節(jié)點之后，下一層該key的節(jié)點也要刪除，一直刪除到最底層

根據這兩點分析一下：如果找到當前節(jié)點了，它的前面一個節(jié)點怎么查找呢?這個總不能再遍歷一遍吧!有的使用四個方向的指針(上下左右)用來找到左側節(jié)點。是可以的，但是這里可以特殊處理一下 ，不直接判斷和操作節(jié)點，先找到待刪除節(jié)點的左側節(jié)點。通過這個節(jié)點即可完成刪除，然后這個節(jié)點直接向下去找下一層待刪除的左側節(jié)點。設置一個臨時節(jié)點team=head，當team不為null具體循環(huán)流程為：

(1)如果team右側為null，那么team=team.down(之所以敢直接這么判斷是因為左側有頭結點在左側，不用擔心特殊情況)

(2)如果team右側不 為null，并且右側的key等于待刪除的key，那么先刪除節(jié)點，再team向下team=team.down為了刪除下層節(jié)點。

(3)如果team右側不 為null，并且右側key小于待刪除的key，那么team向右team=team.right。

(4)如果team右側不 為null，并且右側key大于待刪除的key，那么team向下team=team.down，在下層繼續(xù)查找刪除節(jié)點。

例如上圖刪除10節(jié)點，首先team=head從team出發(fā)，7<10向右(team=team.right后面省略);第二步右側為null只能向下;第三部右側為10在當前層刪除10節(jié)點然后向下繼續(xù)查找下一層10節(jié)點;第四步8<10向右;第五步右側為10刪除該節(jié)點并且team向下。team為null說明刪除完畢退出循環(huán)。

刪除操作實現的代碼如下：

public void delete(int key)//刪除不需要考慮層數 
{ 
    SkipNode team=headNode; 
    while (team!=null) { 
        if (team.right == null) {//右側沒有了，說明這一層找到，沒有只能下降 
            team=team.down; 
        } 
        else if(team.right.key==key)//找到節(jié)點，右側即為待刪除節(jié)點 
        { 
            team.right=team.right.right;//刪除右側節(jié)點 
            team=team.down;//向下繼續(xù)查找刪除 
        } 
        else if(team.right.key>key)//右側已經不可能了，向下 
        { 
            team=team.down; 
        } 
        else { //節(jié)點還在右側 
            team=team.right; 
        } 
    } 
} 

插入操作

插入操作在實現起來是最麻煩的，需要的考慮的東西最多。回顧查詢，不需要動索引;回顧刪除，每層索引如果有刪除就是了。但是插入不一樣了，插入需要考慮是否插入索引，插入幾層等問題。由于需要插入刪除所以我們肯定無法維護一個完全理想的索引結構，因為它耗費的代價太高。但我們使用隨機化的方法去判斷是否向上層插入索引。即產生一個[0-1]的隨機數如果小于0.5就向上插入索引，插入完畢后再次使用隨機數判斷是否向上插入索引。運氣好這個值可能是多層索引，運氣不好只插入最底層(這是100%插入的)。但是索引也不能不限制高度，我們一般會設置索引最高值如果大于這個值就不往上繼續(xù)添加索引了。

我們一步步剖析該怎么做，其流程為

(1)首先通過上面查找的方式，找到待插入的左節(jié)點。插入的話最底層肯定是需要插入的，所以通過鏈表插入節(jié)點(需要考慮是否為末尾節(jié)點)

(2)插入完這一層，需要考慮上一層是否插入，首先判斷當前索引層級，如果大于最大值那么就停止(比如已經到最高索引層了)。否則設置一個隨機數1/2的概率向上插入一層索引(因為理想狀態(tài)下的就是每2個向上建一個索引節(jié)點)。

(3)繼續(xù)(2)的操作，直到概率退出或者索引層數大于最大索引層。

在具體向上插入的時候，實質上還有非常重要的細節(jié)需要考慮。首先如何找到上層的待插入節(jié)點 ?

這個各個實現方法可能不同，如果有左、上指向的指針那么可以向左向上找到上層需要插入的節(jié)點，但是如果只有右指向和下指向的我們也可以巧妙的借助查詢過程中記錄下降的節(jié)點。因為曾經下降的節(jié)點倒序就是需要插入的節(jié)點，最底層也不例外(因為沒有匹配值會下降為null結束循環(huán))。在這里我使用棧這個數據結構進行存儲，當然使用List也可以。下圖就是給了一個插入示意圖。

其次如果該層是目前的最高層索引，需要繼續(xù)向上建立索引應該怎么辦?

首先跳表最初肯定是沒索引的，然后慢慢添加節(jié)點才有一層、二層索引，但是如果這個節(jié)點添加的索引突破當前最高層，該怎么辦呢?

這時候需要注意了，跳表的head需要改變了，新建一個ListNode節(jié)點作為新的head，將它的down指向老head，將這個head節(jié)點加入棧中(也就是這個節(jié)點作為下次后面要插入的節(jié)點)，就比如上面的9節(jié)點如果運氣夠好再往上建立一層節(jié)點，會是這樣的。

插入上層的時候注意所有節(jié)點要新建(拷貝)，除了right的指向down的指向也不能忘記，down指向上一個節(jié)點可以用一個臨時節(jié)點作為前驅節(jié)點。如果層數突破當前最高層，頭head節(jié)點(入口)需要改變。

這部分更多的細節(jié)在代碼中注釋解釋了，詳細代碼為：

public void add(SkipNode node) 
{ 
 
    int key=node.key; 
    SkipNode findNode=search(key); 
    if(findNode!=null)//如果存在這個key的節(jié)點 
    { 
        findNode.value=node.value; 
        return; 
    } 
    Stack<SkipNode>stack=new Stack<SkipNode>();//存儲向下的節(jié)點，這些節(jié)點可能在右側插入節(jié)點 
    SkipNode team=headNode;//查找待插入的節(jié)點   找到最底層的哪個節(jié)點。 
    while (team!=null) {//進行查找操作  
        if(team.right==null)//右側沒有了，只能下降 
        { 
            stack.add(team);//將曾經向下的節(jié)點記錄一下 
            team=team.down; 
        } 
        else if(team.right.key>key)//需要下降去尋找 
        { 
            stack.add(team);//將曾經向下的節(jié)點記錄一下 
            team=team.down; 
        } 
        else //向右 
        { 
            team=team.right; 
        } 
    } 
    int level=1;//當前層數，從第一層添加(第一層必須添加，先添加再判斷) 
    SkipNode downNode=null;//保持前驅節(jié)點(即down的指向，初始為null) 
    while (!stack.isEmpty()) { 
        //在該層插入node 
        team=stack.pop();//拋出待插入的左側節(jié)點 
        SkipNode nodeTeam=new SkipNode(node.key, node.value);//節(jié)點需要重新創(chuàng)建 
        nodeTeam.down=downNode;//處理豎方向 
        downNode=nodeTeam;//標記新的節(jié)點下次使用 
        if(team.right==null) {//右側為null 說明插入在末尾 
            team.right=nodeTeam; 
        } 
        //水平方向處理 
        else {//右側還有節(jié)點，插入在兩者之間 
            nodeTeam.right=team.right; 
            team.right=nodeTeam; 
        } 
        //考慮是否需要向上 
        if(level>MAX_LEVEL)//已經到達最高級的節(jié)點啦 
            break; 
        double num=random.nextDouble();//[0-1]隨機數 
        if(num>0.5)//運氣不好結束 
            break; 
        level++; 
        if(level>highLevel)//比當前最大高度要高但是依然在允許范圍內 需要改變head節(jié)點 
        { 
            highLevel=level; 
            //需要創(chuàng)建一個新的節(jié)點 
            SkipNode highHeadNode=new SkipNode(Integer.MIN_VALUE, null); 
            highHeadNode.down=headNode; 
            headNode=highHeadNode;//改變head 
            stack.add(headNode);//下次拋出head 
        } 
    } 
} 

 總結

對于上面，跳表完整分析就結束啦，當然，你可能看到不同品種跳表的實現，還有的用數組方式表示上下層的關系這樣也可以，但本文只定義right和down兩個方向的鏈表更純正化的講解跳表。

對于跳表以及跳表的同類競爭產品：紅黑樹，為啥Redis的有序集合(zset) 使用跳表呢?因為跳表除了查找插入維護和紅黑樹有著差不多的效率，它是個鏈表，能確定范圍區(qū)間，而區(qū)間問題在樹上可能就沒那么方便查詢啦。而JDK中跳躍表ConcurrentSkipListSet和ConcurrentSkipListMap。 有興趣的也可以查閱一下源碼。

對于學習，完整的代碼是非常重要的，這里我把完整代碼貼出來，需要的自取。

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;//頭節(jié)點，入口 
    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)//找到節(jié)點，右側即為待刪除節(jié)點 
            { 
                team.right=team.right.right;//刪除右側節(jié)點 
                team=team.down;//向下繼續(xù)查找刪除 
            } 
            else if(team.right.key>key)//右側已經不可能了，向下 
            { 
                team=team.down; 
            } 
            else { //節(jié)點還在右側 
                team=team.right; 
            } 
        } 
    } 
    public void add(SkipNode node) 
    { 
 
        int key=node.key; 
        SkipNode findNode=search(key); 
        if(findNode!=null)//如果存在這個key的節(jié)點 
        { 
            findNode.value=node.value; 
            return; 
        } 
 
        Stack<SkipNode>stack=new Stack<SkipNode>();//存儲向下的節(jié)點，這些節(jié)點可能在右側插入節(jié)點 
        SkipNode team=headNode;//查找待插入的節(jié)點   找到最底層的哪個節(jié)點。 
        while (team!=null) {//進行查找操作 
            if(team.right==null)//右側沒有了，只能下降 
            { 
                stack.add(team);//將曾經向下的節(jié)點記錄一下 
                team=team.down; 
            } 
            else if(team.right.key>key)//需要下降去尋找 
            { 
                stack.add(team);//將曾經向下的節(jié)點記錄一下 
                team=team.down; 
            } 
            else //向右 
            { 
                team=team.right; 
            } 
        } 
 
        int level=1;//當前層數，從第一層添加(第一層必須添加，先添加再判斷) 
        SkipNode downNode=null;//保持前驅節(jié)點(即down的指向，初始為null) 
        while (!stack.isEmpty()) { 
            //在該層插入node 
            team=stack.pop();//拋出待插入的左側節(jié)點 
            SkipNode nodeTeam=new SkipNode(node.key, node.value);//節(jié)點需要重新創(chuàng)建 
            nodeTeam.down=downNode;//處理豎方向 
            downNode=nodeTeam;//標記新的節(jié)點下次使用 
            if(team.right==null) {//右側為null 說明插入在末尾 
                team.right=nodeTeam; 
            } 
            //水平方向處理 
            else {//右側還有節(jié)點，插入在兩者之間 
                nodeTeam.right=team.right; 
                team.right=nodeTeam; 
            } 
            //考慮是否需要向上 
            if(level>MAX_LEVEL)//已經到達最高級的節(jié)點啦 
                break; 
            double num=random.nextDouble();//[0-1]隨機數 
            if(num>0.5)//運氣不好結束 
                break; 
            level++; 
            if(level>highLevel)//比當前最大高度要高但是依然在允許范圍內 需要改變head節(jié)點 
            { 
                highLevel=level; 
                //需要創(chuàng)建一個新的節(jié)點 
                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(); 
    } 
} 

 進行測試一下可以發(fā)現跳表還是挺完美的(自夸一下)。