日本综合一区二区|亚洲中文天堂综合|日韩欧美自拍一区|男女精品天堂一区|欧美自拍第6页亚洲成人精品一区|亚洲黄色天堂一区二区成人|超碰91偷拍第一页|日韩av夜夜嗨中文字幕|久久蜜综合视频官网|精美人妻一区二区三区

前言

跳表可以達(dá)到和紅黑樹(shù)一樣的時(shí)間復(fù)雜度 O(logN)，且實(shí)現(xiàn)簡(jiǎn)單，Redis 中的有序集合對(duì)象的底層數(shù)據(jù)結(jié)構(gòu)就使用了跳表。其作者威廉·普評(píng)價(jià)：跳躍鏈表是在很多應(yīng)用中有可能替代平衡樹(shù)的一種數(shù)據(jù)結(jié)構(gòu)。本篇文章將對(duì)跳表的實(shí)現(xiàn)及在Redis中的應(yīng)用進(jìn)行學(xué)習(xí)。

成都網(wǎng)站設(shè)計(jì)、成都網(wǎng)站建設(shè)服務(wù)團(tuán)隊(duì)是一支充滿(mǎn)著熱情的團(tuán)隊(duì)，執(zhí)著、敏銳、追求更好，是創(chuàng)新互聯(lián)的標(biāo)準(zhǔn)與要求，同時(shí)竭誠(chéng)為客戶(hù)提供服務(wù)是我們的理念。成都創(chuàng)新互聯(lián)公司把每個(gè)網(wǎng)站當(dāng)做一個(gè)產(chǎn)品來(lái)開(kāi)發(fā)，精雕細(xì)琢，追求一名工匠心中的細(xì)致，我們更用心！

一. 跳表的基礎(chǔ)概念

跳表，即跳躍鏈表（Skip List），是基于并聯(lián)的鏈表數(shù)據(jù)結(jié)構(gòu)，操作效率可以達(dá)到O(logN)，對(duì)并發(fā)友好，跳表的示意圖如下所示。

跳表的特點(diǎn)，可以概括如下。

?跳表是多層（level）鏈表結(jié)構(gòu)；

?跳表中的每一層都是一個(gè)有序鏈表，并且按照元素升序（默認(rèn)）排列；

?跳表中的元素會(huì)在哪一層出現(xiàn)是隨機(jī)決定的，但是只要元素出現(xiàn)在了第 k 層，那么 k 層以下的鏈表也會(huì)出現(xiàn)這個(gè)元素；

?跳表的底層的鏈表包含所有元素；

?跳表頭節(jié)點(diǎn)和尾節(jié)點(diǎn)不存儲(chǔ)元素，且頭節(jié)點(diǎn)和尾節(jié)點(diǎn)的層數(shù)就是跳表的最大層數(shù)；

?跳表中的節(jié)點(diǎn)包含兩個(gè)指針，一個(gè)指針指向同層鏈表的后一節(jié)點(diǎn)，一個(gè)指針指向下層鏈表的同元素節(jié)點(diǎn)。

以上圖中的跳表為例，如果要查找元素 71，那么查找流程如下圖所示。

??從頂層鏈表的頭節(jié)點(diǎn)開(kāi)始查找，查找到元素71的節(jié)點(diǎn)時(shí)，一共遍歷了4個(gè)節(jié)點(diǎn)，但是如果按照傳統(tǒng)鏈表的方式（即從跳表的底層鏈表的頭節(jié)點(diǎn)開(kāi)始向后查找），那么就需要遍歷7個(gè)節(jié)點(diǎn)，所以跳表以空間換時(shí)間，縮短了操作跳表所需要花費(fèi)的時(shí)間。跳躍列表的算法有同平衡樹(shù)一樣的漸進(jìn)的預(yù)期時(shí)間邊界，并且更簡(jiǎn)單、更快速和使用更少的空間。這種數(shù)據(jù)結(jié)構(gòu)是由William Pugh(音譯為威廉·普)發(fā)明的，最早出現(xiàn)于他在1990年發(fā)表的論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。 谷歌上找到一篇作者關(guān)于跳表的論文，感興趣強(qiáng)烈建議下載閱讀：

?https://epaperpress.com/sortsearch/download/skiplist.pdf?

跳表在動(dòng)態(tài)查找過(guò)程中使用了一種非嚴(yán)格的平衡機(jī)制來(lái)讓插入和刪除都更加便利和快捷，這種非嚴(yán)格平衡是基于概率的，而不是平衡樹(shù)的嚴(yán)格平衡。說(shuō)到非嚴(yán)格平衡，首先想到的是紅黑樹(shù)RbTree，它同樣采用非嚴(yán)格平衡來(lái)避免像AVL那樣調(diào)整樹(shù)的結(jié)構(gòu)，這里就不展開(kāi)講紅黑樹(shù)了，看來(lái)跳表也是類(lèi)似的路子，但是是基于概率實(shí)現(xiàn)的。

二. 跳表的節(jié)點(diǎn)

已知跳表中的節(jié)點(diǎn)，需要有指向當(dāng)前層鏈表后一節(jié)點(diǎn)的指針，和指向下層鏈表的同元素節(jié)點(diǎn)的指針，所以跳表中的節(jié)點(diǎn)，定義如下。

public class SkiplistNode {

    public int data;
    public SkiplistNode next;
    public SkiplistNode down;
    public int level;

    public SkiplistNode(int data, int level) {
        this.data = data;
        this.level = level;
    }

上述是跳表中的節(jié)點(diǎn)的最簡(jiǎn)單的定義方式，存儲(chǔ)的元素 data 為整數(shù)，節(jié)點(diǎn)之間進(jìn)行比較時(shí)直接比較元素 data 的大小。

三. 跳表的初始化

跳表初始化時(shí)，將每一層鏈表的頭尾節(jié)點(diǎn)創(chuàng)建出來(lái)并使用集合將頭尾節(jié)點(diǎn)進(jìn)行存儲(chǔ)，頭尾節(jié)點(diǎn)的層數(shù)隨機(jī)指定，且頭尾節(jié)點(diǎn)的層數(shù)就代表當(dāng)前跳表的層數(shù)。初始化后，跳表結(jié)構(gòu)如下所示。

??跳表初始化的相關(guān)代碼如下所示。

public LinkedList headNodes;
public LinkedList tailNodes;

public int curLevel;

public Random random;

public Skiplist() {
    random = new Random();

    //headNodes用于存儲(chǔ)每一層的頭節(jié)點(diǎn)
    headNodes = new LinkedList<>();
    //tailNodes用于存儲(chǔ)每一層的尾節(jié)點(diǎn)
    tailNodes = new LinkedList<>();

    //初始化跳表時(shí)，跳表的層數(shù)隨機(jī)指定
    curLevel = getRandomLevel();
    //指定了跳表的初始的隨機(jī)層數(shù)后，就需要將每一層的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)創(chuàng)建出來(lái)并構(gòu)建好關(guān)系
    SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, 0);
    SkiplistNode tail = new SkiplistNode(Integer.MAX_VALUE, 0);
    for (int i = 0; i <= curLevel; i++) {
        head.next = tail;
        headNodes.addFirst(head);
        tailNodes.addFirst(tail);

        SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);
        SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);
        headNew.down = head;
        tailNew.down = tail;

        head = headNew;
        tail = tailNew;
    }
}

四. 跳表的添加方法

每一個(gè)元素添加到跳表中時(shí)，首先需要隨機(jī)指定這個(gè)元素在跳表中的層數(shù)，如果隨機(jī)指定的層數(shù)大于了跳表的層數(shù)，則在將元素添加到跳表中之前，還需要擴(kuò)大跳表的層數(shù)，而擴(kuò)大跳表的層數(shù)就是將頭尾節(jié)點(diǎn)的層數(shù)擴(kuò)大。下面給出需要擴(kuò)大跳表層數(shù)的一次添加的過(guò)程。

初始狀態(tài)時(shí)，跳表的層數(shù)為 2，如下圖所示。

現(xiàn)在要往跳表中添加元素 120，并且隨機(jī)指定的層數(shù)為 3，大于了當(dāng)前跳表的層數(shù) 2，此時(shí)需要先擴(kuò)大跳表的層數(shù)，2如 下圖所示。

??將元素 120 插入到跳表中時(shí)，從頂層開(kāi)始，逐層向下插入，如下圖所示。

??跳表的添加方法的代碼如下所示。

public void add(int num) {
    //獲取本次添加的值的層數(shù)
    int level = getRandomLevel();
    //如果本次添加的值的層數(shù)大于當(dāng)前跳表的層數(shù)
    //則需要在添加當(dāng)前值前先將跳表層數(shù)擴(kuò)充
    if (level > curLevel) {
        expanLevel(level - curLevel);
    }

    //curNode表示num值在當(dāng)前層對(duì)應(yīng)的節(jié)點(diǎn)
    SkiplistNode curNode = new SkiplistNode(num, level);
    //preNode表示curNode在當(dāng)前層的前一個(gè)節(jié)點(diǎn)
    SkiplistNode preNode = headNodes.get(curLevel - level);
    for (int i = 0; i <= level; i++) {
        //從當(dāng)前層的head節(jié)點(diǎn)開(kāi)始向后遍歷，直到找到一個(gè)preNode
        //使得preNode.data < num <= preNode.next.data
        while (preNode.next.data < num) {
            preNode = preNode.next;
        }

        //將curNode插入到preNode和preNode.next中間
        curNode.next = preNode.next;
        preNode.next = curNode;

        //如果當(dāng)前并不是0層，則繼續(xù)向下層添加節(jié)點(diǎn)
        if (curNode.level > 0) {
            SkiplistNode downNode = new SkiplistNode(num, curNode.level - 1);
            //curNode指向下一層的節(jié)點(diǎn)
            curNode.down = downNode;
            //curNode向下移動(dòng)一層
            curNode = downNode;
        }
        //preNode向下移動(dòng)一層
        preNode = preNode.down;
    }
}

private void expanLevel(int expanCount) {
    SkiplistNode head = headNodes.getFirst();
    SkiplistNode tail = tailNodes.getFirst();
    for (int i = 0; i < expanCount; i++) {
        SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);
        SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);
        headNew.down = head;
        tailNew.down = tail;

        head = headNew;
        tail = tailNew;

        headNodes.addFirst(head);
        tailNodes.addFirst(tail);
    }
}

五. 跳表的搜索方法

在跳表中搜索一個(gè)元素時(shí)，需要從頂層開(kāi)始，逐層向下搜索。搜索時(shí)遵循如下規(guī)則。

?目標(biāo)值大于當(dāng)前節(jié)點(diǎn)的后一節(jié)點(diǎn)值時(shí)，繼續(xù)在本層鏈表上向后搜索；

?目標(biāo)值大于當(dāng)前節(jié)點(diǎn)值，小于當(dāng)前節(jié)點(diǎn)的后一節(jié)點(diǎn)值時(shí)，向下移動(dòng)一層，從下層鏈表的同節(jié)點(diǎn)位置向后搜索；

?目標(biāo)值等于當(dāng)前節(jié)點(diǎn)值，搜索結(jié)束。

?下圖是一個(gè)搜索過(guò)程的示意圖。

?跳表的搜索的代碼如下所示。

public boolean search(int target) {
    //從頂層開(kāi)始尋找，curNode表示當(dāng)前遍歷到的節(jié)點(diǎn)
    SkiplistNode curNode = headNodes.getFirst();
    while (curNode != null) {
        if (curNode.next.data == target) {
            //找到了目標(biāo)值對(duì)應(yīng)的節(jié)點(diǎn)，此時(shí)返回true
            return true;
        } else if (curNode.next.data > target) {
            //curNode的后一節(jié)點(diǎn)值大于target
            //說(shuō)明目標(biāo)節(jié)點(diǎn)在curNode和curNode.next之間
            //此時(shí)需要向下層尋找
            curNode = curNode.down;
        } else {
            //curNode的后一節(jié)點(diǎn)值小于target
            //說(shuō)明目標(biāo)節(jié)點(diǎn)在curNode的后一節(jié)點(diǎn)的后面
            //此時(shí)在本層繼續(xù)向后尋找
            curNode = curNode.next;
        }
    }
    return false;
}

六. 跳表的刪除方法

當(dāng)在跳表中需要?jiǎng)h除某一個(gè)元素時(shí)，則需要將這個(gè)元素在所有層的節(jié)點(diǎn)都刪除，具體的刪除規(guī)則如下所示。

?首先按照跳表的搜索的方式，搜索待刪除節(jié)點(diǎn)，如果能夠搜索到，此時(shí)搜索到的待刪除節(jié)點(diǎn)位于該節(jié)點(diǎn)層數(shù)的最高層；

?從待刪除節(jié)點(diǎn)的最高層往下，將每一層的待刪除節(jié)點(diǎn)都刪除掉，刪除方式就是讓待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)直接指向待刪除節(jié)點(diǎn)的后一節(jié)點(diǎn)。

?下圖是一個(gè)刪除過(guò)程的示意圖。

?跳表的刪除的代碼如下所示。

public boolean erase(int num) {
    //刪除節(jié)點(diǎn)的遍歷過(guò)程與尋找節(jié)點(diǎn)的遍歷過(guò)程是相同的
    //不過(guò)在刪除節(jié)點(diǎn)時(shí)如果找到目標(biāo)節(jié)點(diǎn)，則需要執(zhí)行節(jié)點(diǎn)刪除的操作
    SkiplistNode curNode = headNodes.getFirst();
    while (curNode != null) {
        if (curNode.next.data == num) {
            //preDeleteNode表示待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)
            SkiplistNode preDeleteNode = curNode;
            while (true) {
                //刪除當(dāng)前層的待刪除節(jié)點(diǎn)，就是讓待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)指向待刪除節(jié)點(diǎn)的后一節(jié)點(diǎn)
                preDeleteNode.next = curNode.next.next;
                //當(dāng)前層刪除完后，需要繼續(xù)刪除下一層的待刪除節(jié)點(diǎn)
                //這里讓preDeleteNode向下移動(dòng)一層
                //向下移動(dòng)一層后，preDeleteNode就不一定是待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)了
                preDeleteNode = preDeleteNode.down;

                //如果preDeleteNode為null，說(shuō)明已經(jīng)將底層的待刪除節(jié)點(diǎn)刪除了
                //此時(shí)就結(jié)束刪除流程，并返回true
                if (preDeleteNode == null) {
                    return true;
                }

                //preDeleteNode向下移動(dòng)一層后，需要繼續(xù)從當(dāng)前位置向后遍歷
                //直到找到一個(gè)preDeleteNode，使得preDeleteNode.next的值等于目標(biāo)值
                //此時(shí)preDeleteNode就又變成了待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)
                while (preDeleteNode.next.data != num) {
                    preDeleteNode = preDeleteNode.next;
                }
            }
        } else if (curNode.next.data > num) {
            curNode = curNode.down;
        } else {
            curNode = curNode.next;
        }
    }
    return false;
}

七. 跳表完整代碼

跳表完整代碼如下所示。

public class Skiplist {

    public LinkedList headNodes;
    public LinkedList tailNodes;

    public int curLevel;

    public Random random;

    public Skiplist() {
        random = new Random();

        //headNodes用于存儲(chǔ)每一層的頭節(jié)點(diǎn)
        headNodes = new LinkedList<>();
        //tailNodes用于存儲(chǔ)每一層的尾節(jié)點(diǎn)
        tailNodes = new LinkedList<>();

        //初始化跳表時(shí)，跳表的層數(shù)隨機(jī)指定
        curLevel = getRandomLevel();
        //指定了跳表的初始的隨機(jī)層數(shù)后，就需要將每一層的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)創(chuàng)建出來(lái)并構(gòu)建好關(guān)系
        SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, 0);
        SkiplistNode tail = new SkiplistNode(Integer.MAX_VALUE, 0);
        for (int i = 0; i <= curLevel; i++) {
            head.next = tail;
            headNodes.addFirst(head);
            tailNodes.addFirst(tail);

            SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);
            SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);
            headNew.down = head;
            tailNew.down = tail;

            head = headNew;
            tail = tailNew;
        }
    }

    public boolean search(int target) {
        //從頂層開(kāi)始尋找，curNode表示當(dāng)前遍歷到的節(jié)點(diǎn)
        SkiplistNode curNode = headNodes.getFirst();
        while (curNode != null) {
            if (curNode.next.data == target) {
                //找到了目標(biāo)值對(duì)應(yīng)的節(jié)點(diǎn)，此時(shí)返回true
                return true;
            } else if (curNode.next.data > target) {
                //curNode的后一節(jié)點(diǎn)值大于target
                //說(shuō)明目標(biāo)節(jié)點(diǎn)在curNode和curNode.next之間
                //此時(shí)需要向下層尋找
                curNode = curNode.down;
            } else {
                //curNode的后一節(jié)點(diǎn)值小于target
                //說(shuō)明目標(biāo)節(jié)點(diǎn)在curNode的后一節(jié)點(diǎn)的后面
                //此時(shí)在本層繼續(xù)向后尋找
                curNode = curNode.next;
            }
        }
        return false;
    }

    public void add(int num) {
        //獲取本次添加的值的層數(shù)
        int level = getRandomLevel();
        //如果本次添加的值的層數(shù)大于當(dāng)前跳表的層數(shù)
        //則需要在添加當(dāng)前值前先將跳表層數(shù)擴(kuò)充
        if (level > curLevel) {
            expanLevel(level - curLevel);
        }

        //curNode表示num值在當(dāng)前層對(duì)應(yīng)的節(jié)點(diǎn)
        SkiplistNode curNode = new SkiplistNode(num, level);
        //preNode表示curNode在當(dāng)前層的前一個(gè)節(jié)點(diǎn)
        SkiplistNode preNode = headNodes.get(curLevel - level);
        for (int i = 0; i <= level; i++) {
            //從當(dāng)前層的head節(jié)點(diǎn)開(kāi)始向后遍歷，直到找到一個(gè)preNode
            //使得preNode.data < num <= preNode.next.data
            while (preNode.next.data < num) {
                preNode = preNode.next;
            }

            //將curNode插入到preNode和preNode.next中間
            curNode.next = preNode.next;
            preNode.next = curNode;

            //如果當(dāng)前并不是0層，則繼續(xù)向下層添加節(jié)點(diǎn)
            if (curNode.level > 0) {
                SkiplistNode downNode = new SkiplistNode(num, curNode.level - 1);
                //curNode指向下一層的節(jié)點(diǎn)
                curNode.down = downNode;
                //curNode向下移動(dòng)一層
                curNode = downNode;
            }
            //preNode向下移動(dòng)一層
            preNode = preNode.down;
        }
    }

    public boolean erase(int num) {
        //刪除節(jié)點(diǎn)的遍歷過(guò)程與尋找節(jié)點(diǎn)的遍歷過(guò)程是相同的
        //不過(guò)在刪除節(jié)點(diǎn)時(shí)如果找到目標(biāo)節(jié)點(diǎn)，則需要執(zhí)行節(jié)點(diǎn)刪除的操作
        SkiplistNode curNode = headNodes.getFirst();
        while (curNode != null) {
            if (curNode.next.data == num) {
                //preDeleteNode表示待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)
                SkiplistNode preDeleteNode = curNode;
                while (true) {
                    //刪除當(dāng)前層的待刪除節(jié)點(diǎn)，就是讓待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)指向待刪除節(jié)點(diǎn)的后一節(jié)點(diǎn)
                    preDeleteNode.next = curNode.next.next;
                    //當(dāng)前層刪除完后，需要繼續(xù)刪除下一層的待刪除節(jié)點(diǎn)
                    //這里讓preDeleteNode向下移動(dòng)一層
                    //向下移動(dòng)一層后，preDeleteNode就不一定是待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)了
                    preDeleteNode = preDeleteNode.down;

                    //如果preDeleteNode為null，說(shuō)明已經(jīng)將底層的待刪除節(jié)點(diǎn)刪除了
                    //此時(shí)就結(jié)束刪除流程，并返回true
                    if (preDeleteNode == null) {
                        return true;
                    }

                    //preDeleteNode向下移動(dòng)一層后，需要繼續(xù)從當(dāng)前位置向后遍歷
                    //直到找到一個(gè)preDeleteNode，使得preDeleteNode.next的值等于目標(biāo)值
                    //此時(shí)preDeleteNode就又變成了待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)
                    while (preDeleteNode.next.data != num) {
                        preDeleteNode = preDeleteNode.next;
                    }
                }
            } else if (curNode.next.data > num) {
                curNode = curNode.down;
            } else {
                curNode = curNode.next;
            }
        }
        return false;
    }

    private void expanLevel(int expanCount) {
        SkiplistNode head = headNodes.getFirst();
        SkiplistNode tail = tailNodes.getFirst();
        for (int i = 0; i < expanCount; i++) {
            SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);
            SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);
            headNew.down = head;
            tailNew.down = tail;

            head = headNew;
            tail = tailNew;

            headNodes.addFirst(head);
            tailNodes.addFirst(tail);
        }
    }

    private int getRandomLevel() {
        int level = 0;
        while (random.nextInt(2) > 1) {
            level++;
        }
        return level;
    }

}

八. 跳表在Redis中的應(yīng)用

ZSet結(jié)構(gòu)同時(shí)包含一個(gè)字典和一個(gè)跳躍表，跳躍表按score從小到大保存所有集合元素。字典保存著從member到score的映射。這兩種結(jié)構(gòu)通過(guò)指針共享相同元素的member和score，不會(huì)浪費(fèi)額外內(nèi)存。

typedef struct zset {
    dict *dict;
    zskiplist *zsl;
} zset;

ZSet中的字典和跳表布局：

1.ZSet中跳表的實(shí)現(xiàn)細(xì)節(jié)

隨機(jī)層數(shù)的實(shí)現(xiàn)原理：

跳表是一個(gè)概率型的數(shù)據(jù)結(jié)構(gòu)，元素的插入層數(shù)是隨機(jī)指定的。Willam Pugh在論文中描述了它的計(jì)算過(guò)程如下：指定節(jié)點(diǎn)最大層數(shù) MaxLevel，指定概率 p， 默認(rèn)層數(shù) lvl 為1；

生成一個(gè)0~1的隨機(jī)數(shù)r，若r

重復(fù)第 2 步，直至生成的r >p 為止，此時(shí)的 lvl 就是要插入的層數(shù)。

論文中生成隨機(jī)層數(shù)的偽碼：

在Redis中對(duì)跳表的實(shí)現(xiàn)基本上也是遵循這個(gè)思想的，只不過(guò)有微小差異，看下Redis關(guān)于跳表層數(shù)的隨機(jī)源碼src/z_set.c：

/* Returns a random level for the new skiplist node we are going to create.
 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned. */
int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level}

其中兩個(gè)宏的定義在redis.h中：

#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */

可以看到while中的：

(random()&0xFFFF) < (ZSKIPLIST_P*0xFFFF)

第一眼看到這個(gè)公式，因?yàn)樯婕拔贿\(yùn)算有些詫異，需要研究一下Antirez為什么使用位運(yùn)算來(lái)這么寫(xiě)？

最開(kāi)始的猜測(cè)是random()返回的是浮點(diǎn)數(shù)[0-1]，于是乎在線(xiàn)找了個(gè)浮點(diǎn)數(shù)轉(zhuǎn)二進(jìn)制的工具，輸入0.5看了下結(jié)果：

可以看到0.5的32bit轉(zhuǎn)換16進(jìn)制結(jié)果為0x3f000000，如果與0xFFFF做與運(yùn)算結(jié)果還是0，不符合預(yù)期。

實(shí)際應(yīng)用時(shí)對(duì)于隨機(jī)層數(shù)的實(shí)現(xiàn)并不統(tǒng)一，重要的是隨機(jī)數(shù)的生成，在LevelDB中對(duì)跳表層數(shù)的生成代碼是這樣的：

template 
int SkipList::randomLevel() {

  static const unsigned int kBranching = 4;
  int height = 1;
  while (height < kMaxLevel && ((::Next(rnd_) % kBranching) == 0)) {
    height++;
  }
  assert(height > 0);
  assert(height <= kMaxLevel);
  return height;
}

uint32_t Next( uint32_t& seed) {
  seed = seed & 0x7fffffffu;

  if (seed == 0 || seed == 2147483647L) { 
    seed = 1;
  }
  static const uint32_t M = 2147483647L;
  static const uint64_t A = 16807;
  uint64_t product = seed * A;
  seed = static_cast((product >> 31) + (product & M));
  if (seed > M) {
    seed -= M;
  }
  return seed;
}

可以看到leveldb使用隨機(jī)數(shù)與kBranching取模，如果值為0就增加一層，這樣雖然沒(méi)有使用浮點(diǎn)數(shù)，但是也實(shí)現(xiàn)了概率平衡。

2.跳表結(jié)點(diǎn)的平均層數(shù)

我們很容易看出，產(chǎn)生越高的節(jié)點(diǎn)層數(shù)出現(xiàn)概率越低，無(wú)論如何層數(shù)總是滿(mǎn)足冪次定律越大的數(shù)出現(xiàn)的概率越小。

如果某件事的發(fā)生頻率和它的某個(gè)屬性成冪關(guān)系，那么這個(gè)頻率就可以稱(chēng)之為符合冪次定律。

冪次定律的表現(xiàn)是少數(shù)幾個(gè)事件的發(fā)生頻率占了整個(gè)發(fā)生頻率的大部分， 而其余的大多數(shù)事件只占整個(gè)發(fā)生頻率的一個(gè)小部分。

冪次定律應(yīng)用到跳表的隨機(jī)層數(shù)來(lái)說(shuō)就是大部分的節(jié)點(diǎn)層數(shù)都是黃色部分，只有少數(shù)是綠色部分，并且概率很低。

定量的分析如下：

?節(jié)點(diǎn)層數(shù)至少為1，大于1的節(jié)點(diǎn)層數(shù)滿(mǎn)足一個(gè)概率分布。

?節(jié)點(diǎn)層數(shù)恰好等于1的概率為p^0(1-p)

?節(jié)點(diǎn)層數(shù)恰好等于2的概率為p^1(1-p)

?節(jié)點(diǎn)層數(shù)恰好等于3的概率為p^2(1-p)

?節(jié)點(diǎn)層數(shù)恰好等于4的概率為p^3(1-p)

依次遞推節(jié)點(diǎn)層數(shù)恰好等于K的概率為p^(k-1)(1-p)

因此如果我們要求節(jié)點(diǎn)的平均層數(shù)，那么也就轉(zhuǎn)換成了求概率分布的期望問(wèn)題了：

??表中P為概率，V為對(duì)應(yīng)取值，給出了所有取值和概率的可能，因此就可以求這個(gè)概率分布的期望了。方括號(hào)里面的式子其實(shí)就是高一年級(jí)學(xué)的等比數(shù)列，常用技巧錯(cuò)位相減求和，從中可以看到結(jié)點(diǎn)層數(shù)的期望值與1-p成反比。對(duì)于Redis而言，當(dāng)p=0.25時(shí)結(jié)點(diǎn)層數(shù)的期望是1.33。

總結(jié)

跳表的時(shí)間復(fù)雜度與AVL樹(shù)和紅黑樹(shù)相同，可以達(dá)到O(logN)，但是AVL樹(shù)要維持高度的平衡，紅黑樹(shù)要維持高度的近似平衡，這都會(huì)導(dǎo)致插入或者刪除節(jié)點(diǎn)時(shí)的一些時(shí)間開(kāi)銷(xiāo)，所以跳表相較于AVL樹(shù)和紅黑樹(shù)來(lái)說(shuō)，省去了維持高度的平衡的時(shí)間開(kāi)銷(xiāo)，但是相應(yīng)的也付出了更多的空間來(lái)存儲(chǔ)多個(gè)層的節(jié)點(diǎn)，所以跳表是用空間換時(shí)間的數(shù)據(jù)結(jié)構(gòu)。以Redis中底層的數(shù)據(jù)結(jié)構(gòu)zset作為典型應(yīng)用來(lái)展開(kāi)，進(jìn)一步看到跳躍鏈表的實(shí)際應(yīng)用。

當(dāng)前標(biāo)題：深入理解跳表及其在Redis中的應(yīng)用
新聞來(lái)源：http://www.dlmjj.cn/article/dhspjed.html