7.跳錶:各方面都非常優秀的動態數據結構

點擊使用幕布網頁版查看

跳錶基於單鏈表實現,鏈表查找、插入、刪除絕大部分時間花在遍歷鏈表上,跳錶使用索引來優化鏈表遍歷的過程,使得跳錶具有非常優秀的查找、插入、刪除性能,並且是天然的動態數據結構

  • 查找、插入、刪除時間複雜度都是O(logn)

  • 跳錶原理的理解

    • 二叉搜索通過計算mid的值,使得每一次要遍歷的數據量減半,那麼鏈表可不可以實現類似的功能呢

    • 如果有一個指針指向鏈表中點,那麼在搜索時先與中點比較,根據比較結果決定是從鏈表頭開始遍歷還是從中點開始遍歷,這樣平均每次要遍歷的數據量就減少了一半

    • 如果多設置幾個索引,甚至設置多級索引,那麼遍歷鏈表所花費的時間將大大降低,而額外付出的空間不過是幾個指針

    • 跳錶示意圖

    • 原鏈表查找4,需要1->2->3->4,而加了索引之後1->3->4;查找5更是只需1->5;在鏈表很大時跳錶的查找效率會顯著提高。

  • 跳錶實現上的注意點

    • 與紅黑樹相比跳錶的實現難度要簡單不少,但還是有幾處注意點

    • 節點設置

      • 數據(data):存儲該節點數據

      • 索引數組(forward[]):存儲該節點各層的索引(每個索引也是一個節點),索引指是指向下一節點的指針

      • 查找結點(值設為value)

    • 實際上跳錶實現的核心就是結點的查找

      • 查找時從頭節點、最上層索引開始
      1. 找到該層索引中data小於value的最大節點(這個節點後面的節點值要麼等於value要麼大於value)

      2. 若本層已經是第0層索引(也就是到了原鏈表)則此時的節點就是值小於等於value的最後一個節點,這個節點後面一個就是我們要找的值

      3. 若本層不是第0層索引,則去下一層,重複1-2-3過程

跳錶Java實現(insert優化)

/**
 * 跳錶是在單鏈表的基礎上加入索引,使查找效率大大提高的一種各方面性能都很優秀的數據結構
 *
 * @author hzk
 */
public class mySkipList {
    private final int MAX_LEVEL = 16;//最大索引層數(0~原鏈表 15~最高一級索引)
    private int levelCount = 1;//跳錶當前索引層數
    public Node head = new Node();//跳錶頭

    /**
     * 查找跳錶中值為value的節點
     *
     * @param value 要查找的值
     * @return 找到返回對應節點,否則返回null
     */
    public Node find(int value) {
        Node p = head;
        //找到該層索引中小於value的最大節點
        for (int i = levelCount - 1; i >= 0; i--) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
        }

        if (p.forwards[0] != null && p.forwards[0].data == value)
            return p.forwards[0];
        else
            return null;
    }

    /**
     * 將value插入跳錶中
     *
     * @param value 待加入數據
     */
    public void insert(int value) {
        int level = randomLevel();
        if (levelCount < level) levelCount = level;

        Node p = head;
        Node newNode = new Node();
        newNode.data = value;
        newNode.maxLevel = level;

        Node path[] = new Node[level];//存儲查找value時經過各層的索引
        for (int i = level - 1; i >= 0; i--) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
            path[i] = p;
        }

        //將value插入各層索引中
        for (int i = level - 1; i >= 0; i--) {
            newNode.forwards[i] = path[i].forwards[i];
            path[i].forwards[i] = newNode;
        }
    }

    /**
     * insert的優化版本,去掉了path[]
     * @param value 待加入數據
     */
    public void insert_optimized(int value) {
        int level = randomLevel();
        if (levelCount < level) levelCount = level;

        Node p = head;
        Node newNode = new Node();
        newNode.data = value;
        newNode.maxLevel = level;

        for (int i = level - 1; i >= 0; i--) {
            while (p.forwards[i] != null && p.forwards[i].data < value)
                p = p.forwards[i];

            //這層索引是最後一個則直接插入
            if (p.forwards[i] == null) {
                p.forwards[i] = newNode;
            }
            //否則插在中間
            else {
                newNode.forwards[i] = p.forwards[i];
                p.forwards[i] = newNode;
            }
        }
    }

    /**
     * 刪除跳錶中值為value的節點及索引
     *
     * @param value 待刪除結點的值
     */
    public void delete(int value) {
        Node path[] = new Node[levelCount];
        Node p = head;

        for (int i = levelCount - 1; i >= 0; i--) {
            while (p.forwards[i] != null && p.forwards[i].data < value)
                p = p.forwards[i];
            path[i] = p;
        }

        //找到
        if (p.forwards[0] != null && p.forwards[0].data == value) {
            //刪除節點所有索引
            for (int i = levelCount - 1; i >= 0; i--) {
                if (p.forwards[i] != null && p.forwards[i].data == value) {
                    p.forwards[i] = p.forwards[i].forwards[i];
                }
            }
        }
    }

    /**
     * 隨機生成索引層數,索引層數和生成概率負相關
     * 盡量使一級索引佔全部索引的50%,二級索引佔25%,三級索引佔12.5%……
     * 隨機函數能放置數據全部集中在某兩個索引之間
     *
     * @return
     */
    private int randomLevel() {
        int level = 1;

        while (Math.random() < 0.5 && level < MAX_LEVEL)
            level++;

        return level;
    }

    public void printAll() {
        Node p = head;
        while (p.forwards[0] != null) {
            System.out.print(p.forwards[0].data + " ");
            p = p.forwards[0];
        }
        System.out.println();
    }

    public void skipListText() {
        mySkipList list = new mySkipList();
        list.insert(1);
        list.insert(2);
        list.insert(3);
        list.printAll();
        System.out.println(list.find(2));
        list.delete(2);
        list.printAll();
        list.insert_optimized(2);
        list.printAll();
    }

    public class Node {
        private int data = -1;//節點數據
        private Node forwards[] = new Node[MAX_LEVEL];//存儲節點上層索引
        private int maxLevel = 0;//最大索引層數

        @Override
        public String toString() {
            StringBuilder builder = new StringBuilder();

            builder.append("{ data: ");
            builder.append(data);
            builder.append("; levels: ");
            builder.append(maxLevel);
            builder.append(" }");

            return builder.toString();
        }
    }
}