深喉东京热毛片,小色网色综合

背景

在查找算法的解決方案中，即根據(jù) key 來查找其所在的位置，主要思想一般是基于兩種，一種是基于平衡樹，還有一種是基于哈希表。

而跳躍表（Skip List，下文簡稱跳表），也可以理解為查找算法的解決方案之一，但是它卻沒法歸類到上述兩種方案中，并且跳表實(shí)現(xiàn)起來也是比較簡單的，在大部分應(yīng)用場景下，跳表的性能是和平衡樹相差無幾的。

簡介

跳躍表這種數(shù)據(jù)結(jié)構(gòu)是由 William Pugh 發(fā)明的，首次公開出現(xiàn)于他的論文中【下載】，該種數(shù)據(jù)結(jié)構(gòu)是一種很精妙的設(shè)計。

跳躍表（Skip List），顧名思義，首先它是一個 list，是一個基于鏈表而改進(jìn)的數(shù)據(jù)結(jié)構(gòu)。眾所周知，鏈表的優(yōu)勢是增刪，而不是查詢，因?yàn)殒湵碇忻總€節(jié)點(diǎn)都會記錄并且只會記錄下一個節(jié)點(diǎn)，所以在鏈表中查找數(shù)據(jù)時，是需要從首個數(shù)據(jù)開始挨個進(jìn)行查找的（時間復(fù)雜度為O(n)）。而跳表的優(yōu)勢在于，查找數(shù)據(jù)時是不會挨個進(jìn)行查找的，可以抽象理解為它是會按照某些規(guī)則跳過部分節(jié)點(diǎn)來進(jìn)行查找的，所以查詢的性能是高于鏈表的。

如下的簡圖，目標(biāo)是查找77：

首先找到1，然后由于77大于1，所以找到下個等高節(jié)點(diǎn)20，而不是7
繼續(xù)從20出發(fā)，下個等高的節(jié)點(diǎn)是80，所以找到80，
發(fā)現(xiàn)77比80小，所以繼續(xù)從20出發(fā)，找下一個矮一點(diǎn)點(diǎn)的節(jié)點(diǎn)，此時正好找到了我們的目標(biāo)值77

SkipList 簡圖

從上面的初窺中可以看出，我們要查找一個值的時候，并不需要像鏈表一樣挨個查找，而是在期間跳過了部分節(jié)點(diǎn)，從而在性能上得到了提升。

另外上圖中體現(xiàn)了一個高度的概念，如上面的第二步，我們從20開始向后查找到的節(jié)點(diǎn)是80而不是77，因?yàn)楫?dāng)時我們處于20的第三層高度，而第三層高度是指向80的，所以我們只會查找到80，但是對比發(fā)現(xiàn)80嫌大，所以便往下退一層，即第二層，而第二層也是指向80的，再向下到達(dá)了第一層，第一層指向的節(jié)點(diǎn)是77，此時正好找到了目標(biāo)值。

下圖展示了每層的關(guān)聯(lián)關(guān)系：

鏈表關(guān)系

其實(shí)從某種意義上來說，跳表和二分查找還是有些些相似的，跳表的時間復(fù)雜度為O(log n)。

跳躍表中的數(shù)據(jù)插入

上文介紹了跳表的基本思路，但是是基于查詢的，那么跳表是如何一步步形成的呢？換句話說，數(shù)據(jù)是如何插入的呢？

其實(shí)上文有一個概念沒有講清楚，即每個節(jié)點(diǎn)的層高是如何產(chǎn)生的，至于是如何產(chǎn)生的，偷偷告訴你，是在一定限制下隨機(jī)生成的，哈哈哈，驚不驚喜，意不意外。

下面畫圖介紹了一下數(shù)據(jù)的插入過程。

跳躍表中插入數(shù)據(jù)

在插入一個數(shù)據(jù)的時候，會影響前后相關(guān)的關(guān)聯(lián)索引，主要會影響第一層至當(dāng)前層的關(guān)聯(lián)索引。

在上圖中，如果我們要查找30，則過程見下圖中帶序號的虛線：

跳躍表中查詢步驟

當(dāng)然，在新增一個節(jié)點(diǎn)的時候，肯定也是要先進(jìn)行一下查詢動作的。

而刪除節(jié)點(diǎn)，也是和新增的過程差不多，也是需要調(diào)整前后數(shù)據(jù)的關(guān)聯(lián)索引的。

層數(shù)的計算

上面提到的層數(shù)是一個隨機(jī)數(shù)，但是是在一定的限制范圍之內(nèi)的。

關(guān)于此處的限制，主要設(shè)計到兩個概念:

層高上限（MaxLevel），即層高至少為1，并且不允許超出該上限，
某個有 i 層高的節(jié)點(diǎn)，則出現(xiàn)在 i+1 層的概率為 p，該 p 為固定值

在 Redis 的 SkipList 中，默認(rèn)的 p 為 1/4，默認(rèn)的 MaxLevel 為 32

獲取層高的偽代碼為：

function getRandomLevel() {
    int level = 1;
    while(random() < p && level < MaxLevel) {
        level ++;
    }
    return level;
}

至于具體的細(xì)節(jié)，建議參考 Redis 中的跳躍表，暫不贅述，此處僅用 Java 語言來大概實(shí)現(xiàn)一下跳躍表。

Java 實(shí)現(xiàn)

skipList

/**
* @Description: 跳躍表
* @Author: Jet.Chen
* @Date: 2019/9/16 17:39
*/
public class SkipList <T>{    
    private SkipListNode<T> head,tail;    
    private int nodes; // 節(jié)點(diǎn)總數(shù)    
    private int listLevel; // 最大層數(shù)    
    private Random random; // 隨機(jī)數(shù)，用于投擲硬幣決定是否要加層高    
    private static final double PROBABILITY = 0.25; // 向上提升一個的概率（此處采用redis中的默認(rèn)值）
    private static final int MAXLEVEL = 32; // 最大層高（此處采用redis中的默認(rèn)值）    
    
    public SkipList() {        
        random = new Random();        
        clear();
    }    
    
    /**    
    * @Description: 清空跳躍表    
    * @Param: []    
    * @return: void    
    * @Author: Jet.Chen    
    * @Date: 2019/9/16 17:41    
    */    
    public void clear(){        
        head = new SkipListNode<T>(SkipListNode.HEAD_KEY, null);        
        tail = new SkipListNode<T>(SkipListNode.TAIL_KEY, null);        
        horizontalLink(head, tail);        
        listLevel = 0;        
        nodes = 0;   
    }    
    
    public boolean isEmpty(){        
        return nodes == 0;    
    }     
    
    public int size() {        
        return nodes;    
    }   
    
    /**    
    * @Description: 找到要插入的位置前面的那個key 的最底層節(jié)點(diǎn)    
    * @Param: [key]    
    * @return: com.jet.SkipListNode<T>    
    * @Author: Jet.Chen    
    * @Date: 2019/9/16 17:42    
    */    
    private SkipListNode<T> findNode(int key){        
        SkipListNode<T> p = head;        
        while(true){            
            while (p.right.getKey() != SkipListNode.TAIL_KEY && p.right.getKey() <= key) {                
                p = p.right;           
            }            
            if (p.down != null) {                
                p = p.down;            
            } else {                
                break;            
            }         
        }        
        return p;    
    }    
    
    /**    
    * @Description: 查找是否存在key，存在則返回該節(jié)點(diǎn)，否則返回null    
    * @Param: [key]    
    * @return: com.wailian.SkipListNode<T>    
    * @Author: Jet.Chen    
    * @Date: 2019/9/16 17:43    
    */    
    public SkipListNode<T> search(int key){        
        SkipListNode<T> p = findNode(key);        
        if (key == p.getKey()) {            
            return p;        
        } else {            
            return null;        
        }    
    }    
    
    /**    
    * @Description: 向跳躍表中添加key-value    
    * @Param: [k, v]    
    * @return: void    
    * @Author: Jet.Chen    
    * @Date: 2019/9/16 17:43    
    */    
    public void put(int k,T v){        
        SkipListNode<T> p = findNode(k);        
        // 如果key值相同，替換原來的value即可結(jié)束        
        if (k == p.getKey()) {            
            p.setValue(v);            
            return;        
        }
        SkipListNode<T> q = new SkipListNode<>(k, v);        
        backLink(p, q);        
        int currentLevel = 0; // 當(dāng)前所在的層級是0       
        // 拋硬幣        
        while (random.nextDouble() < PROBABILITY && currentLevel < MAXLEVEL) {            
            // 如果超出了高度，需要重新建一個頂層            
            if (currentLevel >= listLevel) {                
                listLevel++;                
                SkipListNode<T> p1 = new SkipListNode<>(SkipListNode.HEAD_KEY, null);                
                SkipListNode<T> p2 = new SkipListNode<>(SkipListNode.TAIL_KEY, null);                
                horizontalLink(p1, p2);                
                verticalLink(p1, head);                
                verticalLink(p2, tail);                
                head = p1;                
                tail = p2;            
            }           
            // 將p移動到上一層            
            while (p.up == null) {                
                p = p.left;            
            }            
            p = p.up;             
            SkipListNode<T> e = new SkipListNode<>(k, null); // 只保存key就ok            
            backLink(p, e); // 將e插入到p的后面            
            verticalLink(e, q); // 將e和q上下連接            
            q = e;            
            currentLevel++;        
        }        
        nodes++; // 層數(shù)遞增    
    }    
    
    /**    
    * @Description: node1后面插入node2    
    * @Param: [node1, node2]    
    * @return: void    
    * @Author: Jet.Chen    
    * @Date: 2019/9/16 17:45    
    */    
    private void backLink(SkipListNode<T> node1,SkipListNode<T> node2){        
        node2.left = node1;        
        node2.right = node1.right;        
        node1.right.left = node2;        
        node1.right = node2;    
    }    
    
    /**    
    * @Description: 水平雙向連接    
    * @Param: [node1, node2]    
    * @return: void    
    * @Author: Jet.Chen    
    * @Date: 2019/9/16 17:45    
    */    
    private void horizontalLink(SkipListNode<T> node1,SkipListNode<T> node2){        
        node1.right = node2;        
        node2.left = node1;    
    }   
    
    /**    
    * @Description: 垂直雙向連接    
    * @Param: [node1, node2]    
    * @return: void    
    * @Author: Jet.Chen    
    * @Date: 2019/9/16 17:45    
    */    
    private void verticalLink(SkipListNode<T> node1, kipListNode<T> node2){        
        node1.down = node2;        
        node2.up = node1;    
    }    
    
    @Override    
    public String toString() {        
        if (isEmpty()) {            
            return "跳躍表為空！";        
        }        
        StringBuilder builder = new StringBuilder();        
        SkipListNode<T> p=head;        
        while (p.down != null) {            
            p = p.down;        
        }         
        while (p.left != null) {            
            p = p.left;        
        }        
        if (p.right!= null) {            
            p = p.right;        
        }        
        while (p.right != null) {            
            builder.append(p).append("\n");            
            p = p.right;        
        }         
        return builder.toString();    
        } 
    }

skipListNode

/**
* @Description: 跳躍表的節(jié)點(diǎn),包括key-value和上下左右4個指針
* @Author: Jet.Chen
* @Date: 2019/9/16 17:48
*/
public class SkipListNode <T>{    
    private int key;    
    private T value;    
    public SkipListNode<T> up, down, left, right; // 上下左右 四個指針    
    public static final int HEAD_KEY = Integer.MIN_VALUE; // 負(fù)無窮    
    public static final int  TAIL_KEY = Integer.MAX_VALUE; // 正無窮    
    public SkipListNode(int k, T v) {        
        key = k;        
        value = v;    
    }    
    public int getKey() {        
        return key;    
    }    
    public void setKey(int key) {        
        this.key = key;    
    }    
    public T getValue() {        
        return value;    
    }    
    public void setValue(T value) {        
        this.value = value;    
    }    
    public boolean equals(Object o) {        
        if (this == o) {            
            return true;        
        }        
        if (o == null) {            
            return false;        
        }        
        if (!(o instanceof SkipListNode<?>)) {            
            return false;        
        }        
        SkipListNode<T> ent;        
        try {            
            ent = (SkipListNode<T>) o; // 檢測類型        
        } catch (ClassCastException ex) {            
            return false;        
        }        
        return (ent.getKey() == key) && (ent.getValue() == value);    
    }    
    @Override    
    public String toString() {        
        return "key-value:" + key + "-" + value;    
    }
}

test

public class Main {    
    public static void main(String[] args) {        
        SkipList<String> list = new SkipList<>();        
        System.out.println(list);        
        list.put(6, "cn");        
        list.put(1, "https");        
        list.put(2, ":");        
        list.put(3, "http://");        
        list.put(1, "http");        
        list.put(4, "jetchen");        
        list.put(5, ".");        
        System.out.println(list);        
        System.out.println(list.size());    
    }
}

其它

java demo源碼見地址
java 的 concurrent 包中其實(shí)也有實(shí)現(xiàn)，詳見 ConcurrentSkipListMap 和 ConcurrentSkipListSet

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av

跳躍表之初體驗(yàn)

跳躍表之初體驗(yàn)

背景

簡介

跳躍表中的數(shù)據(jù)插入

層數(shù)的計算

Java 實(shí)現(xiàn)

其它

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九 欧美,1769亚洲,黄色成人av

跳躍表之初體驗(yàn)

背景

簡介

跳躍表中的數(shù)據(jù)插入

層數(shù)的計算

Java 實(shí)現(xiàn)

其它

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容

色偷偷精品伊人,欧洲久久精品,欧美综合婷婷骚逼,国产AV主播,国产最新探花在线,九色在线视频一区,伊人大交九欧美,1769亚洲,黄色成人av