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

本文轉載自微信公眾號「潛行前行」，作者cscw。轉載本文請聯(lián)系潛行前行公眾號。

專注于為中小企業(yè)提供成都網站設計、做網站服務,電腦端+手機端+微信端的三站合一,更高效的管理,為中小企業(yè)銀州免費做網站提供優(yōu)質的服務。我們立足成都，凝聚了一批互聯(lián)網行業(yè)人才，有力地推動了上千余家企業(yè)的穩(wěn)健成長，幫助中小企業(yè)通過網站建設實現規(guī)模擴充和轉變。

什么是跳躍鏈表

開發(fā)時經常使用的平衡數據結構有B數、紅黑數，AVL數。但是如果讓你實現其中一種，很難，實現起來費時間。而跳躍鏈表一種基于鏈表數組實現的快速查找數據結構，目前開源軟件 Redis 和 LevelDB 都有用到它。它的效率和紅黑樹以及 AVL 樹不相上下

跳躍鏈表結構

結構

 
 
 
 

  
  
  
  
public class SkipList {
  
  
  
  
    //跳躍表的頭尾
  
  
  
  
    private SkipListNode head;
  
  
  
  
    //跳躍表含的元素長度
  
  
  
  
    private int length;
  
  
  
  
    //跳表的層數 的歷史最大層數
  
  
  
  
    public int maxLevel;
  
  
  
  
    public SecureRandom random;
  
  
  
  
    private static final int MAX_LEVEL = 31;
  
  
  
  
    public SkipList() {
  
  
  
  
        //初始化頭尾節(jié)點及兩者的關系
  
  
  
  
        head = new SkipListNode<>(SkipListNode.HEAD_SCORE, null, MAX_LEVEL);
  
  
  
  
        //初始化大小，層，隨機
  
  
  
  
        length = 0;
  
  
  
  
        maxLevel = 0; // 層數從零開始計算
  
  
  
  
        random = new SecureRandom();
  
  
  
  
    }
  
  
  
  
    ...
 
 
 
 

• header：指向跳躍表的頭節(jié)點
• maxLevel：記錄目前跳躍表，層數最大節(jié)點的層數
• length：鏈表存在的元素長度

節(jié)點

跳躍鏈表節(jié)點的組成：前節(jié)點、后節(jié)點、分值(map的key值)、及存儲對象 value

 
 
 
 

  
  
  
  
public class SkipListNode {
  
  
  
  
    //在跳表中排序的 分數值
  
  
  
  
    public double score;
  
  
  
  
    public T value;
  
  
  
  
    public int level;
  
  
  
  
    // 前后節(jié)點
  
  
  
  
    public SkipListNode next,pre;
  
  
  
  
    //上下節(jié)點形成的層
  
  
  
  
    public SkipListNode[] levelNode;
  
  
  
  
    private SkipListNode(double score, int level){
  
  
  
  
        this.score = score;
  
  
  
  
        this.level = level;
  
  
  
  
    }
  
  
  
  
    public SkipListNode(double score, T value, int level) {
  
  
  
  
        this.score = score;
  
  
  
  
        this.value = value;
  
  
  
  
        this.level = level;
  
  
  
  
        this.levelNode = new SkipListNode[level+1];
  
  
  
  
        //初始化 SkipListNode 及 每一層的 node
  
  
  
  
        for (int i = level; i > 0; --i) {
  
  
  
  
            levelNode[i] = new SkipListNode(score, level);
  
  
  
  
            levelNode[i].levelNode = levelNode;
  
  
  
  
        }
  
  
  
  
        this.levelNode[0] = this;
  
  
  
  
    }
  
  
  
  
    @Override
  
  
  
  
    public String toString() {  return "Node[score=" + score + ", value=" + value + "]"; }
  
  
  
  
}
 
 
 
 

跳表是用空間來換時間

在我實現的跳躍鏈表節(jié)點，包括一個 levelNode 成員屬性。它就是節(jié)點層。跳躍鏈表能實現快速訪問的關鍵點就是它

平時訪問一個數組，我們是順序遍歷的，而跳躍鏈表效率比數組鏈表高，是因為它使用節(jié)點層存儲多級索引，形成一個稀疏索引，所以需要的更多的內存空間

跳躍鏈表有多快

如果一個鏈表有 n 個結點，每兩個結點抽取出一個結點建立索引的話，那么第一層索引的結點數大約就是 n/2，第二層索引的結點數大約為 n/4，以此類推第 m 層索引的節(jié)點數大約為 n/(2^m)

訪問數據時可以從 m 層索引查詢定位到 m-1 層索引數據。而 m-1 大約是 m 層的1/2。也就是說最優(yōu)的時間復雜度為O(log/N)

最差情況。在實際實現中，每一層索引是無法每次以數據數量對折一次實現一層索引。因此折中的方式，每一層的索引是隨機用全量數據建一條。也就是說最差情況時間復雜度為O(N)，但最優(yōu)時間復雜度不變

查詢

查詢一開始是遍歷最高層 maxLevel 的索引 m。按照以下步驟查詢出等于 score 或者最接近 score 的左節(jié)點

1：如果同層索引的 next 節(jié)點分值小于查詢分值，則跳到 next 節(jié)點。cur = next

2：如果 next 為空?；蛘遪ext節(jié)點分值大于查詢分值。則跳到下一層 m-1 索引，循環(huán) 2

循環(huán) 1、2 步驟直到訪問到節(jié)點分值和查詢分值一致，或者索引層為零

 
 
 
 

  
  
  
  
// SkipList
  
  
  
  
    private SkipListNode findNearestNode(double score) {
  
  
  
  
        int curLevel = maxLevel;
  
  
  
  
        SkipListNode cur = head.levelNode[curLevel];
  
  
  
  
        SkipListNode next = cur.next;
  
  
  
  
        // 和當前節(jié)點分數相同 或者 next 為 null
  
  
  
  
        while (score != cur.score && curLevel > 0) {
  
  
  
  
            // 1 向右 next 遍歷
  
  
  
  
            if (next != null && score >= next.levelNode[0].score) {
  
  
  
  
                cur = next;
  
  
  
  
            }
  
  
  
  
            next = cur.levelNode[curLevel].next;
  
  
  
  
            // 2 向下遍歷，層數減1
  
  
  
  
            while ((next == null || score < next.levelNode[0].score) && curLevel > 0) {
  
  
  
  
                next = cur.levelNode[--curLevel].next;
  
  
  
  
            }
  
  
  
  
        }
  
  
  
  
        // 最底層的 node。
  
  
  
  
        return cur.levelNode[0];
  
  
  
  
    }
  
  
  
  
    public SkipListNode get(double score) {
  
  
  
  
        //返回跳表最底層中，最接近這個 score 的node
  
  
  
  
        SkipListNode p = findNearestNode(score);
  
  
  
  
        //score 相同，返回這個node
  
  
  
  
        return p.score == score ? p : null;
  
  
  
  
    }
 
 
 
 

插入

如果分值存在則替換 value

如果分值對應節(jié)點不存在，則隨機一個索引層數 level (取值 0~31)。然后依靠節(jié)點屬性 levelNode 加入 0 到 level 層的索引

 
 
 
 

  
  
  
  
//SkipList
  
  
  
  
    public T put(double score, T value) {
  
  
  
  
        //首先得到跳表最底層中，最接近這個key的node
  
  
  
  
        SkipListNode p = findNearestNode(score);
  
  
  
  
        if (p.score == score) {
  
  
  
  
            // 在跳表中，只有最底層的node才有真正的value，只需修改最底層的value就行
  
  
  
  
            T old = p.value;
  
  
  
  
            p.value = value;
  
  
  
  
            return old;
  
  
  
  
        }
  
  
  
  
        // nowNode 為新建的最底層的node。索引層數 0 到 31
  
  
  
  
        int nodeLevel = (int) Math.round(random.nextDouble() * 32);
  
  
  
  
        SkipListNode nowNode = new SkipListNode(score, value, nodeLevel);
  
  
  
  
        //初始化每一層，并連接每一層前后節(jié)點
  
  
  
  
        int level = 0;
  
  
  
  
        while (nodeLevel >= p.level) {
  
  
  
  
            for (; level <= p.level; level++) {
  
  
  
  
                insertNodeHorizontally(p.levelNode[level], nowNode.levelNode[level]);
  
  
  
  
            }
  
  
  
  
            p = p.pre;
  
  
  
  
        }
  
  
  
  
        // 此時 p 的層數大于 nowNode 的層數才進入循環(huán)
  
  
  
  
        for (; level <= nodeLevel; level++) {
  
  
  
  
            insertNodeHorizontally(p.levelNode[level], nowNode.levelNode[level]);
  
  
  
  
        }
  
  
  
  
        this.length ++ ;
  
  
  
  
        if (this.maxLevel < nodeLevel) {
  
  
  
  
            maxLevel = nodeLevel;
  
  
  
  
        }
  
  
  
  
        return value;
  
  
  
  
    }
  
  
  
  

  
  
  
  
    private void insertNodeHorizontally(SkipListNode pre, SkipListNode now) {
  
  
  
  
        //先考慮now
  
  
  
  
        now.next = pre.next;
  
  
  
  
        now.pre = pre;
  
  
  
  
        //再考慮pre的next節(jié)點
  
  
  
  
        if (pre.next != null) {
  
  
  
  
            pre.next.pre = now;
  
  
  
  
        }
  
  
  
  
        //最后考慮pre
  
  
  
  
        pre.next = now;
  
  
  
  
    }
 
 
 
 

刪除

使用 get 方法找到元素，然后解除節(jié)點屬性 levelNode 在每一層索引的前后引用關系即可

 
 
 
 

  
  
  
  
//SkipList
  
  
  
  
    public T remove(double score){
  
  
  
  
        //在底層找到對應這個key的節(jié)點
  
  
  
  
        SkipListNode now = get(score);
  
  
  
  
        if (now == null) {
  
  
  
  
            return null;
  
  
  
  
        }
  
  
  
  
        SkipListNode curNode, next;
  
  
  
  
        //解除節(jié)點屬性 levelNode 在每一層索引的前后引用關系
  
  
  
  
        for (int i = 0; i <= now.level; i++){
  
  
  
  
            curNode = now.levelNode[i];
  
  
  
  
            next = curNode.next;
  
  
  
  
            if (next != null) {
  
  
  
  
                next.pre = curNode.pre;
  
  
  
  
            }
  
  
  
  
            curNode.pre.next = curNode.next;
  
  
  
  
        }
  
  
  
  
        this.length--; //更新size，返回舊值
  
  
  
  
        return now.value;
  
  
  
  
    }
 
 
 
 

使用示例

 
 
 
 

  
  
  
  
public static void main(String[] args) {
  
  
  
  
    SkipList list=new SkipList<>();
  
  
  
  
    list.printSkipList();
  
  
  
  
    list.put(1, "csc");
  
  
  
  
    list.printSkipList();
  
  
  
  
    list.put(3, "lwl");
  
  
  
  
    list.printSkipList();
  
  
  
  
    list.put(2, "hello world!");
  
  
  
  
    list.printSkipList();
  
  
  
  

  
  
  
  
    System.out.println(list.get(2));
  
  
  
  
    System.out.println(list.get(4));
  
  
  
  
    list.remove(2);
  
  
  
  
    list.printSkipList();
  
  
  
  
}
 
 
 
 

歡迎指正文中錯誤

參考文章

• redis設計與實現
• 跳表(跳躍表，skipList)總結-java版[1]
• 數據結構與算法——跳表[2]

當前標題：數據結構：跳躍鏈表
轉載注明：http://www.dlmjj.cn/article/djcpgsj.html