每日一博 - 如何了解跳表(SkipList)

文章目錄

什麼是跳躍表SkipList
跳表關鍵字
Why Skip List
Code
跳表-查詢
跳表-删除
跳表-插入
小結
完整Code

什麼是跳躍表SkipList

跳躍表(簡稱跳表)由美國計算機科學家William Pugh于1989年發明

跳表(SkipList，全稱跳躍表)是用于有序元素序列快速搜尋查找的一個資料結構，跳表是一個随機化的資料結構，實質就是一種可以進行二分查找的有序連結清單。

跳表在原有的有序連結清單上面增加了多級索引，通過索引來實作快速查找。

跳表不僅能提高搜尋性能，同時也可以提高插入和删除操作的性能。它在性能上和紅黑樹，AVL樹不相上下，但是跳表的原理非常簡單，實作也比紅黑樹簡單很多。

跳表關鍵字

随機化
有序連結清單
索引
二分查找

每日一博 - 如何了解跳表(SkipList)

Why Skip List

地球人都知道的事兒：

順序表（數組）是記憶體上一塊連續的區域，基于下标，查找速度快。
連結清單：記憶體上不連續，通過指針相連，插入和删除動作效率特别高，但是查詢呢，時間複雜度o(n)

那麼連結清單上查詢的時間複雜度能優化一下嗎？

我們知道有很多算法有個思想：空間換時間。如果在連結清單的上面加一層索引，讓部分節點在上層能夠直接定位到，這樣連結清單的查詢時間近乎減少一半。

那查詢的時候，就會發生某些變化 -----------> 如果要查找某個節點，首先需要從上一層快速定位到節點所在的一個範圍，如果向下查找的有個向下的指針指向真實的資料，那理論上，以前有n, 現在就是 n/2 .

當然了，如果節點資料量超巨，一樣很慢，可能就損耗在了，一層一層的查找上。我們知道二分查找每次都能折半的去壓縮查找範圍，那用上這個二分查找是不是就會快很多？？？？

事實上，跳表就能讓連結清單擁有近乎的接近二分查找的效率的一種資料結構，其原理依然是給上面加若幹層索引，優化查找速度。

通過上圖我們可以知道，這樣的一個資料結構對有序連結清單進行查找都能近乎二分的性能。

究其原因就是在上面維護了多層的索引，

首先在最進階索引上查找最後一個小于目前查找元素的位置，然後再跳到次進階索引繼續查找，直到跳到最底層為止，這時候以及十分接近要查找的元素的位置了(如果查找元素存在的話)。

由于根據索引可以一次跳過多個元素，是以跳查找的查找速度也就變快了。

對于理想的跳表，每向上一層索引節點數量都是下一層的1/2.那麼如果n個節點增加的節點數量(1/2+1/4+…)<n。并且層數較低，對查找效果影響不大。

但是對于這麼一個結構，你可能會疑惑，這樣完美的結構真的存在嗎？大機率不存在的，因為作為一個連結清單，少不了增删該查的一些操作。而删除和插入可能會改變整個結構，是以上面的這些都是理想的結構，在插入的時候是否添加上層索引是個機率問題(1/2的機率)。

Code

在實作本跳表的過程為了便于操作，我們将跳表的頭結點(head)的key設為int的最小值(一定滿足左小右大友善比較)。

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

(1) 從team節點出發，如果目前節點的key與查詢的key相等，那麼傳回目前節點(如果是修改操作那麼一直向下進行修改值即可)。
(2) 如果key不相等，且右側為null，那麼證明隻能向下(結果可能出現在下右方向)，此時team=team.down
(3) 如果key不相等，且右側不為null，且右側節點key小于待查詢的key。那麼說明同級還可向右，此時team=team.right
(4)（否則的情況）如果key不相等，且右側不為null，且右側節點key大于待查詢的key 。那麼說明如果有結果的話就在這個索引和下個索引之間，此時team=team.down。

最終将按照這個步驟傳回正确的節點或者null(說明沒查到)。

例如上圖查詢12節點.

第一步從head出發發現右側不為空，且7<12,向右；
第二步右側為null向下；
第三步節點7的右側10<12繼續向右；
第四步10右側為null向下；
第五步右側12小于等于向右。
第六步起始發現相等傳回節點結束。

代碼如下

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

删除操作比起查詢稍微複雜一丢丢，但是比插入簡單。删除需要改變連結清單結構是以需要處理好節點之間的聯系。對于删除操作需要謹記以下幾點：

(1)删除目前節點和這個節點的前後節點都有關系
(2)删除目前層節點之後，下一層該key的節點也要删除，一直删除到最底層

根據這兩點分析一下：如果找到目前節點了，它的前面一個節點怎麼查找呢？這個總不能再周遊一遍吧！有的使用四個方向的指針(上下左右)用來找到左側節點。是可以的，但是這裡可以特殊處理一下，不直接判斷和操作節點，先找到待删除節點的左側節點。通過這個節點即可完成删除，然後這個節點直接向下去找下一層待删除的左側節點。

設定一個臨時節點team=head，當team不為null具體循環流程為：

(1)如果team右側為null，那麼team=team.down(之是以敢直接這麼判斷是因為左側有頭結點在左側，不用擔心特殊情況)
(2)如果team右側不為null，并且右側的key等于待删除的key，那麼先删除節點，再team向下team=team.down為了删除下層節點。
(3)如果team右側不為null，并且右側key小于待删除的key，那麼team向右team=team.right。
(4)如果team右側不為null，并且右側key大于待删除的key，那麼team向下team=team.down，在下層繼續查找删除節點。

例如上圖删除10節點，

首先team=head從team出發，7<10向右(team=team.right後面省略)；
第二步右側為null隻能向下；
第三部右側為10在目前層删除10節點然後向下繼續查找下一層10節點；
第四步8<10向右；
第五步右側為10删除該節點并且team向下。
team為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)//找到節點，右側即為待删除節點
        {
team.right=team.right.right;//删除右側節點
team=team.down;//向下繼續查找删除
        }
else if(team.right.key>key)//右側已經不可能了，向下
        {
team=team.down;
        }
else { //節點還在右側
team=team.right;
        }
    }
}

插入操作在實作起來是最麻煩的，需要的考慮的東西最多。

查詢，不需要動索引；

删除，每層索引如果有删除就是了。

插入不一樣了，插入需要考慮是否插入索引，插入幾層等問題。

由于需要插入删除是以我們肯定無法維護一個完全理想的索引結構，因為它耗費的代價太高。但我們使用随機化的方法去判斷是否向上層插入索引。

即産生一個[0-1]的随機數如果小于0.5就向上插入索引，插入完畢後再次使用随機數判斷是否向上插入索引。運氣好這個值可能是多層索引，運氣不好隻插入最底層(這是100%插入的)。但是索引也不能不限制高度，我們一般會設定索引最高值如果大于這個值就不往上繼續添加索引了。

其流程為

(1)首先通過上面查找的方式，找到待插入的左節點。插入的話最底層肯定是需要插入的，是以通過連結清單插入節點(需要考慮是否為末尾節點)
(2)插入完這一層，需要考慮上一層是否插入，首先判斷目前索引層級，如果大于最大值那麼就停止(比如已經到最高索引層了)。否則設定一個随機數1/2的機率向上插入一層索引(因為理想狀态下的就是每2個向上建一個索引節點)。
(3)繼續(2)的操作，直到機率退出或者索引層數大于最大索引層。

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

這個各個實作方法可能不同，如果有左、上指向的指針那麼可以向左向上找到上層需要插入的節點，但是如果隻有右指向和下指向的我們也可以巧妙的借助查詢過程中記錄下降的節點。因為曾經下降的節點倒序就是需要插入的節點，最底層也不例外(因為沒有比對值會下降為null結束循環)。在這裡我使用棧這個資料結構進行存儲，當然使用List也可以。

下圖就是給了一個插入示意圖。

其次如果該層是目前的最高層索引，需要繼續向上建立索引應該怎麼辦？

首先跳表最初肯定是沒索引的，然後慢慢添加節點才有一層、二層索引，但是如果這個節點添加的索引突破目前最高層，該怎麼辦呢？

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

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

public void add(SkipNode node)
{

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

小結

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

對于跳表以及跳表的同類競争産品：紅黑樹，為啥Redis的有序集合(zset) 使用跳表呢？因為跳表除了查找插入維護和紅黑樹有着差不多的效率，它是個連結清單，能确定範圍區間，而區間問題在樹上可能就沒那麼友善查詢啦。

而JDK中跳躍表ConcurrentSkipListSet和ConcurrentSkipListMap。

完整Code

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;//頭節點，入口
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)//找到節點，右側即為待删除節點
            {
team.right=team.right.right;//删除右側節點
team=team.down;//向下繼續查找删除
            }
else if(team.right.key>key)//右側已經不可能了，向下
            {
team=team.down;
            }
else { //節點還在右側
team=team.right;
            }
        }
    }
public void add(SkipNode node)
    {

int key=node.key;
SkipNode findNode=search(key);
if(findNode!=null)//如果存在這個key的節點
        {
findNode.value=node.value;
return;
        }

Stack<SkipNode>stack=new Stack<SkipNode>();//存儲向下的節點，這些節點可能在右側插入節點
SkipNode team=headNode;//查找待插入的節點   找到最底層的哪個節點。
while (team!=null) {//進行查找操作
if(team.right==null)//右側沒有了，隻能下降
            {
stack.add(team);//将曾經向下的節點記錄一下
team=team.down;
            }
else if(team.right.key>key)//需要下降去尋找
            {
stack.add(team);//将曾經向下的節點記錄一下
team=team.down;
            }
else //向右
            {
team=team.right;
            }
        }

int level=1;//目前層數，從第一層添加(第一層必須添加，先添加再判斷)
SkipNode downNode=null;//保持前驅節點(即down的指向，初始為null)
while (!stack.isEmpty()) {
//在該層插入node
team=stack.pop();//抛出待插入的左側節點
SkipNode nodeTeam=new SkipNode(node.key, node.value);//節點需要重新建立
nodeTeam.down=downNode;//處理豎方向
downNode=nodeTeam;//标記新的節點下次使用
if(team.right==null) {//右側為null 說明插入在末尾
team.right=nodeTeam;
            }
//水準方向處理
else {//右側還有節點，插入在兩者之間
nodeTeam.right=team.right;
team.right=nodeTeam;
            }
//考慮是否需要向上
if(level>MAX_LEVEL)//已經到達最進階的節點啦
break;
double num=random.nextDouble();//[0-1]随機數
if(num>0.5)//運氣不好結束
break;
level++;
if(level>highLevel)//比目前最大高度要高但是依然在允許範圍内 需要改變head節點
            {
highLevel=level;
//需要建立一個新的節點
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();
    }
}

每日一博 - 如何了解跳表(SkipList)

文章目錄

繼續閱讀

GSL--GNU Scientific Library

D5|哈希表，善用資料結構

如何成為一名.net 工程師?

BMP檔案結構及圖像每行位元組計算方法

c寫檔案

D. Ehab the Xorcist(構造+思維)

查找算法之二分查找查找算法之二分查找

JAVA高效程式設計指南

CQ V1.0分詞bates(基于雙數組tire樹)—應該是目前最快的中文分詞算法

【資料結構】醫院選址

[轉]ISUP信令的IAM消息詳細内容

筆試面試題目：滑動視窗(二)

交通/城市相關的公開的資料集上學時整理的Xie et al., 2020收集的

資料結構與算法（27）——排序（二）

GitHub連夜封殺！這份阿裡 10W 字内部 Java 字面試手冊到底有多強？

Linux裝置模型（中）之上層容器