[[415029]]

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

什么是跳躍鏈表

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

跳躍鏈表結(jié)構(gòu)

結(jié)構(gòu)

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

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

節(jié)點(diǎn)

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

public class SkipListNode<T> { 
    //在跳表中排序的 分?jǐn)?shù)值 
    public double score; 
    public T value; 
    public int level; 
    // 前后節(jié)點(diǎn) 
    public SkipListNode<T> next,pre; 
    //上下節(jié)點(diǎn)形成的層 
    public SkipListNode<T>[] 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<T>(score, level); 
            levelNode[i].levelNode = levelNode; 
        } 
        this.levelNode[0] = this; 
    } 
    @Override 
    public String toString() {  return "Node[score=" + score + ", value=" + value + "]"; } 
} 

跳表是用空間來換時(shí)間

在我實(shí)現(xiàn)的跳躍鏈表節(jié)點(diǎn)，包括一個(gè) levelNode 成員屬性。它就是節(jié)點(diǎn)層。跳躍鏈表能實(shí)現(xiàn)快速訪問的關(guān)鍵點(diǎn)就是它

平時(shí)訪問一個(gè)數(shù)組，我們是順序遍歷的，而跳躍鏈表效率比數(shù)組鏈表高，是因?yàn)樗褂霉?jié)點(diǎn)層存儲多級索引，形成一個(gè)稀疏索引，所以需要的更多的內(nèi)存空間

跳躍鏈表有多快

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

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

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

查詢

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

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

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

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

// SkipList 
    private SkipListNode<T> findNearestNode(double score) { 
        int curLevel = maxLevel; 
        SkipListNode<T> cur = head.levelNode[curLevel]; 
        SkipListNode<T> next = cur.next; 
        // 和當(dāng)前節(jié)點(diǎn)分?jǐn)?shù)相同 或者 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 向下遍歷，層數(shù)減1 
            while ((next == null || score < next.levelNode[0].score) && curLevel > 0) { 
                next = cur.levelNode[--curLevel].next; 
            } 
        } 
        // 最底層的 node。 
        return cur.levelNode[0]; 
    } 
    public SkipListNode<T> get(double score) { 
        //返回跳表最底層中，最接近這個(gè) score 的node 
        SkipListNode<T> p = findNearestNode(score); 
        //score 相同，返回這個(gè)node 
        return p.score == score ? p : null; 
    } 

插入

如果分值存在則替換 value

如果分值對應(yīng)節(jié)點(diǎn)不存在，則隨機(jī)一個(gè)索引層數(shù) level (取值 0~31)。然后依靠節(jié)點(diǎn)屬性 levelNode 加入 0 到 level 層的索引

//SkipList 
    public T put(double score, T value) { 
        //首先得到跳表最底層中，最接近這個(gè)key的node 
        SkipListNode<T> p = findNearestNode(score); 
        if (p.score == score) { 
            // 在跳表中，只有最底層的node才有真正的value，只需修改最底層的value就行 
            T old = p.value; 
            p.value = value; 
            return old; 
        } 
        // nowNode 為新建的最底層的node。索引層數(shù) 0 到 31 
        int nodeLevel = (int) Math.round(random.nextDouble() * 32); 
        SkipListNode<T> nowNode = new SkipListNode<T>(score, value, nodeLevel); 
        //初始化每一層，并連接每一層前后節(jié)點(diǎn) 
        int level = 0; 
        while (nodeLevel >= p.level) { 
            for (; level <= p.level; level++) { 
                insertNodeHorizontally(p.levelNode[level], nowNode.levelNode[level]); 
            } 
            p = p.pre; 
        } 
        // 此時(shí) p 的層數(shù)大于 nowNode 的層數(shù)才進(jìn)入循環(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<T> pre, SkipListNode<T> now) { 
        //先考慮now 
        now.next = pre.next; 
        now.pre = pre; 
        //再考慮pre的next節(jié)點(diǎn) 
        if (pre.next != null) { 
            pre.next.pre = now; 
        } 
        //最后考慮pre 
        pre.next = now; 
    } 

刪除

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

//SkipList 
    public T remove(double score){ 
        //在底層找到對應(yīng)這個(gè)key的節(jié)點(diǎn) 
        SkipListNode<T> now = get(score); 
        if (now == null) { 
            return null; 
        } 
        SkipListNode<T> curNode, next; 
        //解除節(jié)點(diǎn)屬性 levelNode 在每一層索引的前后引用關(guān)系 
        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<String> 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(); 
} 

歡迎指正文中錯(cuò)誤

參考文章 

• redis設(shè)計(jì)與實(shí)現(xiàn)
• 跳表(跳躍表，skipList)總結(jié)-java版[1]
• 數(shù)據(jù)結(jié)構(gòu)與算法——跳表[2]