怎么設(shè)計(jì)實(shí)現(xiàn)跳表SkipList

本篇內(nèi)容介紹了“怎么設(shè)計(jì)實(shí)現(xiàn)跳表SkipList”的有關(guān)知識(shí)，在實(shí)際案例的操作過(guò)程中，不少人都會(huì)遇到這樣的困境，接下來(lái)就讓小編帶領(lǐng)大家學(xué)習(xí)一下如何處理這些情況吧！希望大家仔細(xì)閱讀，能夠?qū)W有所成！

快速了解跳表

跳躍表(簡(jiǎn)稱跳表)由美國(guó)計(jì)算機(jī)科學(xué)家William Pugh發(fā)明于1989年。他在論文《Skip lists: a probabilistic  alternative to balanced trees》中詳細(xì)介紹了跳表的數(shù)據(jù)結(jié)構(gòu)和插入刪除等操作。

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

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

回顧鏈表，我們知道鏈表和順序表(數(shù)組)通常都是相愛(ài)相殺，成對(duì)出現(xiàn)，各有優(yōu)劣。而鏈表的優(yōu)勢(shì)就是更高效的插入、刪除。痛點(diǎn)就是查詢很慢很慢!每次查詢都是一種O(n)復(fù)雜度的操作，鏈表估計(jì)自己都?xì)獾南肟蘖恕?/p>

這是一個(gè)帶頭結(jié)點(diǎn)的鏈表(頭結(jié)點(diǎn)相當(dāng)于一個(gè)固定的入口，不存儲(chǔ)有意義的值)，每次查找都需要一個(gè)個(gè)枚舉，相當(dāng)?shù)穆?，我們能不能稍微?yōu)化一下，讓它稍微跳一跳呢?答案是可以的，我們知道很多算法和數(shù)據(jù)結(jié)構(gòu)以空間換時(shí)間，我們?cè)谏厦婕右粚铀饕?，讓部分?jié)點(diǎn)在上層能夠直接定位到，這樣鏈表的查詢時(shí)間近乎減少一半，鏈表自己雖然沒(méi)有開(kāi)心起來(lái)，但收起了它想哭的臉。

這樣，在查詢某個(gè)節(jié)點(diǎn)的時(shí)候，首先會(huì)從上一層快速定位節(jié)點(diǎn)所在的一個(gè)范圍，如果找到具體范圍向下然后查找代價(jià)很小，當(dāng)然在表的結(jié)構(gòu)設(shè)計(jì)上會(huì)增加一個(gè)向下的索引(指針)用來(lái)查找確定底層節(jié)點(diǎn)。平均查找速度平均為O(n/2)。但是當(dāng)節(jié)點(diǎn)數(shù)量很大的時(shí)候，它依舊很慢很慢。我們都知道二分查找是每次都能折半的去壓縮查找范圍，要是有序鏈表也能這么跳起來(lái)那就太完美了。沒(méi)錯(cuò)跳表就能讓鏈表?yè)碛薪醯慕咏植檎业男实囊环N數(shù)據(jù)結(jié)構(gòu)，其原理依然是給上面加若干層索引，優(yōu)化查找速度。

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

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

跳表的增刪改查

上面稍微了解了跳表是個(gè)啥，那么在這里就給大家談?wù)勌淼脑鰟h改查過(guò)程。在實(shí)現(xiàn)本跳表的過(guò)程為了便于操作，我們將跳表的頭結(jié)點(diǎn)(head)的key設(shè)為int的最小值(一定滿足左小右大方便比較)。

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

class SkipNode<T> {     int key;     T value;     SkipNode right,down;//右下個(gè)方向的指針     public SkipNode (int key,T value) {         this.key=key;         this.value=value;     } }

跳表的結(jié)構(gòu)和初始化也很重要，其主要參數(shù)和初始化方法為：

public class SkipList <T> {      SkipNode headNode;//頭節(jié)點(diǎn)，入口     int highLevel;//當(dāng)前跳表索引層數(shù)     Random random;// 用于投擲硬幣     final int MAX_LEVEL = 32;//最大的層      SkipList(){         random=new Random();         headNode=new SkipNode(Integer.MIN_VALUE,null);         highLevel=0;     }     //其他方法 }

查詢操作

很多時(shí)候鏈表也可能這樣相連僅僅是某個(gè)元素或者key作為有序的標(biāo)準(zhǔn)。所以有可能鏈表內(nèi)部存在一些value。不過(guò)修改和查詢其實(shí)都是一個(gè)操作，找到關(guān)鍵數(shù)字(key)。并且查找的流程也很簡(jiǎn)單，設(shè)置一個(gè)臨時(shí)節(jié)點(diǎn)team=head。當(dāng)team不為null其流程大致如下：

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

(2) 如果key不相等，且右側(cè)為null，那么證明只能向下(結(jié)果可能出現(xiàn)在下右方向)，此時(shí)team=team.down

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

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

最終將按照這個(gè)步驟返回正確的節(jié)點(diǎn)或者null(說(shuō)明沒(méi)查到)。

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

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

public SkipNode search(int key) {     SkipNode team=headNode;     while (team!=null) {         if(team.key==key)         {             return  team;         }         else if(team.right==null)//右側(cè)沒(méi)有了，只能下降         {             team=team.down;         }         else if(team.right.key>key)//需要下降去尋找         {             team=team.down;         }         else //右側(cè)比較小向右         {             team=team.right;         }     }     return null; }

刪除操作

刪除操作比起查詢稍微復(fù)雜一丟丟，但是比插入簡(jiǎn)單。刪除需要改變鏈表結(jié)構(gòu)所以需要處理好節(jié)點(diǎn)之間的聯(lián)系。對(duì)于刪除操作你需要謹(jǐn)記以下幾點(diǎn)：

(1)刪除當(dāng)前節(jié)點(diǎn)和這個(gè)節(jié)點(diǎn)的前后節(jié)點(diǎn)都有關(guān)系

(2)刪除當(dāng)前層節(jié)點(diǎn)之后，下一層該key的節(jié)點(diǎn)也要?jiǎng)h除，一直刪除到最底層

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

(1)如果team右側(cè)為null，那么team=team.down(之所以敢直接這么判斷是因?yàn)樽髠?cè)有頭結(jié)點(diǎn)在左側(cè)，不用擔(dān)心特殊情況)

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

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

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

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

刪除操作實(shí)現(xiàn)的代碼如下：

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

插入操作

插入操作在實(shí)現(xiàn)起來(lái)是最麻煩的，需要的考慮的東西最多。回顧查詢，不需要?jiǎng)铀饕?回顧刪除，每層索引如果有刪除就是了。但是插入不一樣了，插入需要考慮是否插入索引，插入幾層等問(wèn)題。由于需要插入刪除所以我們肯定無(wú)法維護(hù)一個(gè)完全理想的索引結(jié)構(gòu)，因?yàn)樗馁M(fèi)的代價(jià)太高。但我們使用隨機(jī)化的方法去判斷是否向上層插入索引。即產(chǎn)生一個(gè)[0-1]的隨機(jī)數(shù)如果小于0.5就向上插入索引，插入完畢后再次使用隨機(jī)數(shù)判斷是否向上插入索引。運(yùn)氣好這個(gè)值可能是多層索引，運(yùn)氣不好只插入最底層(這是100%插入的)。但是索引也不能不限制高度，我們一般會(huì)設(shè)置索引最高值如果大于這個(gè)值就不往上繼續(xù)添加索引了。

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

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

(2)插入完這一層，需要考慮上一層是否插入，首先判斷當(dāng)前索引層級(jí)，如果大于最大值那么就停止(比如已經(jīng)到最高索引層了)。否則設(shè)置一個(gè)隨機(jī)數(shù)1/2的概率向上插入一層索引(因?yàn)槔硐霠顟B(tài)下的就是每2個(gè)向上建一個(gè)索引節(jié)點(diǎn))。

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

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

這個(gè)各個(gè)實(shí)現(xiàn)方法可能不同，如果有左、上指向的指針那么可以向左向上找到上層需要插入的節(jié)點(diǎn)，但是如果只有右指向和下指向的我們也可以巧妙的借助查詢過(guò)程中記錄下降的節(jié)點(diǎn)。因?yàn)樵?jīng)下降的節(jié)點(diǎn)倒序就是需要插入的節(jié)點(diǎn)，最底層也不例外(因?yàn)闆](méi)有匹配值會(huì)下降為null結(jié)束循環(huán))。在這里我使用棧這個(gè)數(shù)據(jù)結(jié)構(gòu)進(jìn)行存儲(chǔ)，當(dāng)然使用List也可以。下圖就是給了一個(gè)插入示意圖。

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

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

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

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

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

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

“怎么設(shè)計(jì)實(shí)現(xiàn)跳表SkipList”的內(nèi)容就介紹到這里了，感謝大家的閱讀。如果想了解更多行業(yè)相關(guān)的知識(shí)可以關(guān)注億速云網(wǎng)站，小編將為大家輸出更多高質(zhì)量的實(shí)用文章！