繼承，是幸福的延續(xù)；重載，是幸福的重生。

數(shù)組與鏈表

數(shù)組

在計(jì)算機(jī)科學(xué)中，數(shù)組數(shù)據(jù)結(jié)構(gòu)（英語：array data structure），簡(jiǎn)稱數(shù)組（英語：Array），是由相同類型的元素（element）的集合所組成的數(shù)據(jù)結(jié)構(gòu)，分配一塊連續(xù)的內(nèi)存來存儲(chǔ)。利用元素的索引（index）可以計(jì)算出該元素對(duì)應(yīng)的存儲(chǔ)地址。

優(yōu)點(diǎn)

隨機(jī)訪問速度較快（基于下標(biāo)訪問）。
實(shí)現(xiàn)簡(jiǎn)單，使用簡(jiǎn)單。
內(nèi)存地址連續(xù)，對(duì)cpu緩存很友好，比如高性能隊(duì)列 disruptor 也是利用了cpu緩存+數(shù)組地址的連續(xù)性大大的優(yōu)化了性能。

缺點(diǎn)

內(nèi)存連續(xù)可以是優(yōu)點(diǎn)，也可以是缺點(diǎn)，如果在內(nèi)存緊張的情況下，數(shù)組將會(huì)被大大限制。
插入和刪除的時(shí)候會(huì)導(dǎo)致元素的移動(dòng)（數(shù)據(jù)拷貝），較慢。
數(shù)組大小固定，大大的限制了元素的個(gè)數(shù)，對(duì)于很多動(dòng)態(tài)的數(shù)據(jù)不友好。

鏈表

鏈表（Linked list）是一種常見的基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，是一種線性表，但是并不會(huì)按線性的順序存儲(chǔ)數(shù)據(jù)，而是在每一個(gè)節(jié)點(diǎn)里存到下一個(gè)節(jié)點(diǎn)的指針(Pointer)。由于不必須按順序存儲(chǔ)，鏈表在插入的時(shí)候可以達(dá)到O(1)的復(fù)雜度，比另一種線性表順序表快得多，但是查找一個(gè)節(jié)點(diǎn)或者訪問特定編號(hào)的節(jié)點(diǎn)則需要O(n)的時(shí)間。

優(yōu)點(diǎn)

鏈表結(jié)構(gòu)可以充分利用計(jì)算機(jī)內(nèi)存空間，實(shí)現(xiàn)靈活的內(nèi)存動(dòng)態(tài)管理。
刪除插入不用移動(dòng)其他元素。
不受元素大小限制，可以隨意擴(kuò)展。

缺點(diǎn)

失去了數(shù)組隨機(jī)讀取的優(yōu)點(diǎn)，同時(shí)鏈表由于增加了結(jié)點(diǎn)的指針域，空間開銷比較大。
隨機(jī)訪問效率相對(duì)數(shù)組來說較低。

時(shí)間復(fù)雜度分析

隨機(jī)訪問
數(shù)組：O(1)
不支持隨機(jī)訪問
插入，刪除
數(shù)組：有序數(shù)組 ->O(n)，無序數(shù)組 ->（1）
鏈表：O(1)

鏈表又可以分為單鏈表和雙向鏈表，不過這都不是這篇文章需要討論的問題，這里講一下數(shù)組和鏈表，只是做一下鋪墊，因?yàn)橄旅嬷v到的跳表就會(huì)用到鏈表的相關(guān)知識(shí)，所以對(duì)鏈表還不怎么熟悉的同學(xué)，可以先學(xué)習(xí)一下，然后在開始今天的正文：跳表。

什么是跳表？

上文講到了鏈表的概念，鏈表的查詢時(shí)間復(fù)雜度為：O(n)，即使是有序的鏈表，也得從鏈表的第一個(gè)元素開始遍歷查找，時(shí)間復(fù)雜度偏高，那如果讓你來優(yōu)化，你有什么解決方案嗎？這個(gè)時(shí)候跳表就出現(xiàn)了。

跳表，全程：跳躍鏈表，在計(jì)算機(jī)科學(xué)中，跳躍列表是一種數(shù)據(jù)結(jié)構(gòu)。它使得包含n個(gè)元素的有序序列的查找和插入操作的平均時(shí)間復(fù)雜度都是：
$logn$
我們來畫一個(gè)普通的鏈表結(jié)構(gòu)

普通鏈表

這是一個(gè)普通的單鏈表結(jié)構(gòu)，如果我們想查找出 58 這個(gè)節(jié)點(diǎn)，我們就得查詢 1 -> 4 -> 7 -> 15 -> 20 -> 35 -> 50 -> 58 ，一共查找了8次，才將我們需要的結(jié)果查找出來，時(shí)間復(fù)雜度：O(n)，效率可想而知，那我們一起試著來優(yōu)化一下。

mysql在數(shù)據(jù)量大的時(shí)候查詢效率也會(huì)急劇下降，他們是怎么來優(yōu)化效率問題呢？那就是索引，這里我們也可以使用一個(gè)類似 “索引” 的東西來對(duì)這個(gè)普通的單鏈表進(jìn)行優(yōu)化。

file

我們將原始鏈表中每隔兩個(gè)結(jié)點(diǎn)之后的節(jié)點(diǎn)復(fù)制一份出來，用于制作索引，方便數(shù)據(jù)的查找。

我們還是繼續(xù)查找58，我們只需要經(jīng)過：1 -> 7 -> 20 --> 50 -> 58，發(fā)現(xiàn)了沒有，這里居然只搜索了5次就找到了我們想要的結(jié)點(diǎn)，效率是不是提升了一丟丟？我現(xiàn)在來解釋一下這張圖，由于我們建立了一層索引，所以查詢的時(shí)候優(yōu)先往第一層索引層搜索，搜索索引層時(shí)，發(fā)現(xiàn) 50 以及之前的節(jié)點(diǎn)都小于 58 ，遍歷到 50 的時(shí)候，他的下一個(gè)節(jié)點(diǎn) 66 大于需要查詢的節(jié)點(diǎn) ，所以這個(gè)時(shí)候就會(huì)找到50這個(gè)節(jié)點(diǎn)中的down（原始鏈表節(jié)點(diǎn)為 50 的指針）節(jié)點(diǎn)，然后再往下遍歷一個(gè)就就找到了 58 。

加了“索引” 也才少查詢了三次，優(yōu)化的并不是很明顯啊，這個(gè)優(yōu)化是否有存在的必要呢？我們這里之建立了一層“索引”，我們多建立幾層”索引“之后呢？會(huì)是什么樣呢？

file

這個(gè)時(shí)候我們發(fā)現(xiàn)只需要4次就能找到我們需要查找的節(jié)點(diǎn) 58 ，4 次相對(duì)于8次來說已經(jīng)快了一半了，我這里的數(shù)據(jù)不是太多，當(dāng)數(shù)據(jù)足夠多的時(shí)候，效果將會(huì)更為明顯。

這種一層一層的索引組成的數(shù)據(jù)結(jié)構(gòu)，我們稱他為：跳表，現(xiàn)在相信你對(duì)什么是跳表應(yīng)該有了比較深的理解了吧，這個(gè)時(shí)候你可能又有一個(gè)疑問了？我們?yōu)榱私⑺饕龑?，肯定?huì)消耗大量的空間，這是屬于空間換時(shí)間的一種方式，但是在數(shù)據(jù)量大的時(shí)候，會(huì)不會(huì)存在空間不夠的情況呢？

那我們現(xiàn)在一起來分析一下跳表的時(shí)間/空間復(fù)雜度吧

跳表分析

假設(shè)原始鏈表結(jié)點(diǎn)個(gè)數(shù)為：n，我們知道，我們每隔兩個(gè)節(jié)點(diǎn)抽離一個(gè)結(jié)點(diǎn)作為索引層的一個(gè)結(jié)點(diǎn)，那么第一層索引層的結(jié)點(diǎn)個(gè)數(shù)應(yīng)該是原始鏈表結(jié)點(diǎn)個(gè)數(shù)的1/2，也就是n/2，第二層索引的結(jié)點(diǎn)個(gè)數(shù)是第一層索引結(jié)點(diǎn)個(gè)數(shù)的1/2，是 1/4 原始鏈表結(jié)點(diǎn)個(gè)數(shù)，也就是 n/4，第三層索引的結(jié)點(diǎn)個(gè)數(shù)是第二層結(jié)點(diǎn)個(gè)數(shù)的1/2，是第一層索引結(jié)點(diǎn)個(gè)數(shù)的4/1，是原始鏈表結(jié)點(diǎn)個(gè)數(shù)的1/8，依次類推，在k層索引的節(jié)點(diǎn)個(gè)數(shù)是k-1層索引的1/2，那么k層索引的節(jié)點(diǎn)個(gè)數(shù)：
$\frac {n}{2^k}$
一個(gè)鏈表，假設(shè)我們都是每隔兩個(gè)結(jié)點(diǎn)分配一個(gè)索引結(jié)點(diǎn)，最高層索引只有兩個(gè)結(jié)點(diǎn)，索引層高度為：h，那么將會(huì)得到這么一個(gè)公式：
$\frac {n}{2^h}=2$
我們求解一下 h：
$2^h=\frac {n}{2}$

$h=log_2(\frac{n}{2})$

我們將這個(gè)公式拆分一下：
$h=log_2(n) - log_22$
所以 h 的值為：
$h = \log_2n -1$
由于 h 是索引層的高度，我們算上原始鏈表，那么真?zhèn)€跳表的高度就是：
$\log_2n$
現(xiàn)在我們一起來算算跳表查詢的時(shí)間復(fù)雜度，跳表有許多層索引，每層索引都會(huì)進(jìn)行相對(duì)應(yīng)次數(shù)的遍歷，假設(shè)每次索引遍歷的最大次數(shù)為：x，那么一個(gè)查詢需要遍歷的次數(shù)為：
$x * \log_2n$
所以用 O 表示法表示，跳表的時(shí)間復(fù)雜度為：
$O(x * \log(n))$
為什么對(duì)數(shù)中的底數(shù) 2 沒有了呢？其實(shí)在時(shí)間復(fù)雜度分析中，分析的只是一種趨勢(shì)，并不是固定的值，相對(duì)數(shù)級(jí)別的，底數(shù)可以忽略，具體相關(guān)的介紹，這里就不展開介紹了，感興趣的可以百度一下，并不復(fù)雜，我們現(xiàn)在需要搞明白的是這個(gè) x 到底是多少呢？

在前面所畫的跳表結(jié)構(gòu)圖中，我們以每隔兩個(gè)結(jié)點(diǎn)提取一個(gè)索引結(jié)點(diǎn)，所以，當(dāng)我們需要查詢跳表中某一個(gè)結(jié)點(diǎn)時(shí)，需要在索引層從上而下開始遍歷，每層最多不會(huì)超過3個(gè)，為什么是 3 個(gè)而不是 4 個(gè)、5 個(gè)、6 個(gè)呢？我們畫一個(gè)簡(jiǎn)單的圖來說明一下。

file

我們需要查找 12 這個(gè)結(jié)點(diǎn)，當(dāng)走到 9 這個(gè)結(jié)點(diǎn)時(shí)發(fā)現(xiàn) 12 > 9 而 < 13 所以下降一層索引，到達(dá)第一層索引，而在 9 - 13 之間只有三個(gè)結(jié)點(diǎn)，就算是下降到原始鏈表也是一樣的，兩個(gè)范圍結(jié)點(diǎn)之前最多只有三個(gè)結(jié)點(diǎn)，所以每層需要遍歷的最多結(jié)點(diǎn)數(shù)就是這么得出來的，因?yàn)?x 是常數(shù) 3 ，可以直接省略，所以跳表最終的時(shí)間復(fù)雜度為：
$\log(n)$
雖然查詢的效率提高了非常多，但是這也存在一個(gè)非常重要的問題，那就是跳表會(huì)占用額外的內(nèi)存空間，因?yàn)?，它需要很多層的索引，這樣這個(gè)數(shù)據(jù)結(jié)構(gòu)還值不值得推薦使用呢？既然redis官方都在使用了，你還在怕什么呢？我們?cè)賮矸治鲆幌绿淼目臻g復(fù)雜度，看看是不是對(duì)內(nèi)存有著極大的消耗呢？

假設(shè)原始鏈表長(zhǎng)度為 n ，那么第一層索引長(zhǎng)度為 n/2，第二層索引長(zhǎng)度為：n/4，第三層索引長(zhǎng)度：n/8，最后一層（最高層）索引長(zhǎng)度：2，很明顯這是一個(gè)等比數(shù)列：
$\frac{n}{2},\frac{n}{4},\frac{n}{8},\frac{n}{16}......8,4,2$
等比數(shù)列求和公式：
$當(dāng)q≠1時(shí)，Sn = \frac{1-q^n}{1-q}=\frac{a_1-a_n*q}{1-q}$

$②當(dāng)q=1時(shí)，Sn = n * a_1$

套入公式：
$\frac{\frac{n}{2} - 2 * \frac{1}{2}}{1-\frac{1}{2}} = \frac{\frac{n}{2} - 1}{\frac{1}{2}}=\frac{\frac{1}{2}(n-2)}{\frac{1}{2}}=n-2$
索引層占用總大小為：n - 2，加上原始鏈表 n = 2n -2 ，所以跳表的空間復(fù)雜度為：O(n)，常數(shù)可以省略，這是每個(gè)兩個(gè)結(jié)點(diǎn)提取一個(gè)索引結(jié)點(diǎn)的空間復(fù)雜度，那多隔幾個(gè)結(jié)點(diǎn)提取一個(gè)索引結(jié)點(diǎn)呢？比如每隔 3 個(gè)提取一個(gè)，每隔 5 個(gè)提取一個(gè)，計(jì)算方式和上面一樣，結(jié)果空間復(fù)雜度也是：O(n)，但是空間確實(shí)減少了很多。

查詢我們講完了，那跳表的插入和刪除效果怎么樣呢？會(huì)不會(huì)也表現(xiàn)得很優(yōu)秀？我們一起來看看。

由于我們的鏈表是有序的，所以在插入的時(shí)候我們得先找到插入的位置，跳表的查詢時(shí)間復(fù)雜度為O(logn )，找到了需要插入的位置之后就是插入操作，單鏈表的插入時(shí)間復(fù)雜度時(shí)O(1)，這里就不證明了，所以整個(gè)插入的過程等于查找插入的位置+插入=O(logn)。

其實(shí)刪除操作的時(shí)間復(fù)雜也是O(logn)，為什么呢？其實(shí)和插入也是一樣的，但是會(huì)多一個(gè)查找前驅(qū)結(jié)點(diǎn)的操作，因?yàn)閯h除，會(huì)導(dǎo)致前后驅(qū)結(jié)點(diǎn)的指針變動(dòng)，后驅(qū)結(jié)點(diǎn)在當(dāng)前刪除的結(jié)點(diǎn)中存在，但是前前驅(qū)節(jié)點(diǎn)沒有，查詢也是O(logn)，所以刪除 O(logn)+O(logn)，所以刪除的時(shí)間復(fù)雜度最終還是：O(logn)，但是刪除有一點(diǎn)需要注意，如果需要?jiǎng)h除的結(jié)點(diǎn)在索引層也存在，那么同時(shí)需要?jiǎng)h除索引層的結(jié)點(diǎn)，關(guān)于前驅(qū)結(jié)點(diǎn)的問題，可以使用雙向鏈表解決。

索引更新

跳表的查詢、刪除、添加在性能方面都比較優(yōu)秀，那它能一直保持這么優(yōu)秀嗎？既然跳表也是用來存放數(shù)據(jù)的，那么肯定會(huì)伴隨著頻繁的新增和刪除，假設(shè)在某一個(gè)相鄰區(qū)間的索引結(jié)點(diǎn)之間被插入了較多的數(shù)據(jù)，那么就會(huì)導(dǎo)致數(shù)據(jù)分布不均勻，在某一個(gè)區(qū)間的查詢時(shí)間效率降低，最壞情況可能會(huì)被退化成單鏈表，所有的數(shù)據(jù)都在這一個(gè)區(qū)間內(nèi)，所以我們?cè)跀?shù)據(jù)插入的時(shí)候?qū)λ饕龑幼鰧?shí)時(shí)更新維護(hù)，保證跳表的數(shù)據(jù)結(jié)構(gòu)不會(huì)過度退化，那我們?cè)趺淳S護(hù)索引層的變化呢？

其實(shí)也不難，跳表通過隨機(jī)函數(shù)來保持?jǐn)?shù)據(jù)的平衡性，也就是讓數(shù)據(jù)保持相對(duì)均勻，當(dāng)我們往跳表中添加數(shù)據(jù)的時(shí)候，通過隨機(jī)函數(shù)生成一個(gè)隨機(jī)數(shù)，這個(gè)隨機(jī)數(shù)就是索引的層數(shù)，然后在這一層把需要添加的結(jié)點(diǎn)添加到這一層索引層節(jié)點(diǎn)中，假設(shè)我們需要插入的數(shù)據(jù)為 7 ，隨機(jī)函數(shù)生成的隨機(jī)數(shù)為： 2，那么插入的時(shí)候就會(huì)如下圖所示：

file

這里就對(duì)隨機(jī)函數(shù)的要求很高了，它可以很好地保證跳表的平衡性，不會(huì)讓跳表的性能退化，這點(diǎn)和紅黑樹的左旋/右旋是一個(gè)道理。

代碼實(shí)現(xiàn)

上面的都是理論基礎(chǔ)，我們看完了理論，那一定要真刀真槍的干一下，不然不就白看了嗎，那我們一起來看看跳表的代碼如何實(shí)現(xiàn)

package com.lx.cloud.test;

import java.util.Random;

/**
 * @ClassName SkipList
 * @Description 跳表
 */
public class SkipList {
    private static final int MAX_LEVEL = 16;
    private int levelCount = 1;

    /**
     * 帶頭鏈表
     */
    private Node head = new Node(MAX_LEVEL);
    private Random r = new Random();

    public Node find(int value) {
        Node p = head;
        // 從最大層開始查找，找到前一節(jié)點(diǎn)，通過--i，移動(dòng)到下層再開始查找
        for (int i = levelCount - 1; i >= 0; --i) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                // 找到前一節(jié)點(diǎn)
                p = p.forwards[i];
            }
        }

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

    /**
     * 優(yōu)化了作者zheng的插入方法
     *
     * @param value 值
     */
    public void insert(int value) {
        int level = head.forwards[0] == null ? 1 : randomLevel();
        // 每次只增加一層，如果條件滿足
        if (level > levelCount) {
            level = ++levelCount;
        }
        Node newNode = new Node(level);
        newNode.data = value;
        Node update[] = new Node[level];
        for (int i = 0; i < level; ++i) {
            update[i] = head;
        }

        Node p = head;
        // 從最大層開始查找，找到前一節(jié)點(diǎn)，通過--i，移動(dòng)到下層再開始查找
        for (int i = levelCount - 1; i >= 0; --i) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                // 找到前一節(jié)點(diǎn)
                p = p.forwards[i];
            }
            // levelCount 會(huì) > level，所以加上判斷
            if (level > i) {
                update[i] = p;
            }

        }
        for (int i = 0; i < level; ++i) {
            newNode.forwards[i] = update[i].forwards[i];
            update[i].forwards[i] = newNode;
        }

    }

    /**
     * 優(yōu)化了作者zheng的插入方法2
     *
     * @param value 值
     */
    public void insert2(int value) {
        int level = head.forwards[0] == null ? 1 : randomLevel();
        // 每次只增加一層，如果條件滿足
        if (level > levelCount) {
            level = ++levelCount;
        }
        Node newNode = new Node(level);
        newNode.data = value;
        Node p = head;
        // 從最大層開始查找，找到前一節(jié)點(diǎn)，通過--i，移動(dòng)到下層再開始查找
        for (int i = levelCount - 1; i >= 0; --i) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                // 找到前一節(jié)點(diǎn)
                p = p.forwards[i];
            }
            // levelCount 會(huì) > level，所以加上判斷
            if (level > i) {
                if (p.forwards[i] == null) {
                    p.forwards[i] = newNode;
                } else {
                    Node next = p.forwards[i];
                    p.forwards[i] = newNode;
                    newNode.forwards[i] = next;
                }
            }

        }

    }

    /**
     * 作者zheng的插入方法，未優(yōu)化前，優(yōu)化后參見上面insert()
     *
     * @param value
     * @param level 0 表示隨機(jī)層數(shù)，不為0，表示指定層數(shù)，指定層數(shù)
     *              可以讓每次打印結(jié)果不變動(dòng)，這里是為了便于學(xué)習(xí)理解
     */
    public void insert(int value, int level) {
        // 隨機(jī)一個(gè)層數(shù)
        if (level == 0) {
            level = randomLevel();
        }
        // 創(chuàng)建新節(jié)點(diǎn)
        Node newNode = new Node(level);
        newNode.data = value;
        // 表示從最大層到低層，都要有節(jié)點(diǎn)數(shù)據(jù)
        newNode.maxLevel = level;
        // 記錄要更新的層數(shù)，表示新節(jié)點(diǎn)要更新到哪幾層
        Node update[] = new Node[level];
        for (int i = 0; i < level; ++i) {
            update[i] = head;
        }

        /**
         *
         * 1，說明：層是從下到上的，這里最下層編號(hào)是0，最上層編號(hào)是15
         * 2，這里沒有從已有數(shù)據(jù)最大層（編號(hào)最大）開始找，（而是隨機(jī)層的最大層）導(dǎo)致有些問題。
         *    如果數(shù)據(jù)量為1億，隨機(jī)level=1 ，那么插入時(shí)間復(fù)雜度為O（n）
         */
        Node p = head;
        for (int i = level - 1; i >= 0; --i) {
            while (p.forwards[i] != null && p.forwards[i].data < value) {
                p = p.forwards[i];
            }
            // 這里update[i]表示當(dāng)前層節(jié)點(diǎn)的前一節(jié)點(diǎn)，因?yàn)橐业角耙还?jié)點(diǎn)，才好插入數(shù)據(jù)
            update[i] = p;
        }

        // 將每一層節(jié)點(diǎn)和后面節(jié)點(diǎn)關(guān)聯(lián)
        for (int i = 0; i < level; ++i) {
            // 記錄當(dāng)前層節(jié)點(diǎn)后面節(jié)點(diǎn)指針
            newNode.forwards[i] = update[i].forwards[i];
            // 前一個(gè)節(jié)點(diǎn)的指針，指向當(dāng)前節(jié)點(diǎn)
            update[i].forwards[i] = newNode;
        }

        // 更新層高
        if (levelCount < level){
            levelCount = level;
        }
    }

    public void delete(int value) {
        Node[] update = 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];
            }
            update[i] = p;
        }

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

    /**
     * 隨機(jī) level 次，如果是奇數(shù)層數(shù) +1，防止偽隨機(jī)
     *
     * @return
     */
    private int randomLevel() {
        int level = 1;
        for (int i = 1; i < MAX_LEVEL; ++i) {
            if (r.nextInt() % 2 == 1) {
                level++;
            }
        }
        return level;
    }

    /**
     * 打印每個(gè)節(jié)點(diǎn)數(shù)據(jù)和最大層數(shù)
     */
    public void printAll() {
        Node p = head;
        while (p.forwards[0] != null) {
            System.out.print(p.forwards[0] + " ");
            p = p.forwards[0];
        }
        System.out.println();
    }

    /**
     * 打印所有數(shù)據(jù)
     */
    public void printAll_beautiful() {
        Node p = head;
        Node[] c = p.forwards;
        Node[] d = c;
        int maxLevel = c.length;
        for (int i = maxLevel - 1; i >= 0; i--) {
            do {
                System.out.print((d[i] != null ? d[i].data : null) + ":" + i + "-------");
            } while (d[i] != null && (d = d[i].forwards)[i] != null);
            System.out.println();
            d = c;
        }
    }

    /**
     * 跳表的節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)記錄了當(dāng)前節(jié)點(diǎn)數(shù)據(jù)和所在層數(shù)數(shù)據(jù)
     */
    public class Node {
        private int data = -1;
        /**
         * 表示當(dāng)前節(jié)點(diǎn)位置的下一個(gè)節(jié)點(diǎn)所有層的數(shù)據(jù)，從上層切換到下層，就是數(shù)組下標(biāo)-1，
         * forwards[3]表示當(dāng)前節(jié)點(diǎn)在第三層的下一個(gè)節(jié)點(diǎn)。
         */
        private Node forwards[];

        /**
         * 這個(gè)值其實(shí)可以不用，看優(yōu)化insert()
         */
        private int maxLevel = 0;

        public Node(int level) {
            forwards = new Node[level];
        }

        @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();
        }
    }

    public static void main(String[] args) {
        SkipList list = new SkipList();
        list.insert(1, 3);
        list.insert(2, 3);
        list.insert(3, 2);
        list.insert(4, 4);
        list.insert(5, 10);
        list.insert(6, 4);
        list.insert(8, 5);
        list.insert(7, 4);
        list.printAll_beautiful();
        list.printAll();

        SkipList list2 = new SkipList();
        list2.insert2(1);
        list2.insert2(2);
        list2.insert2(6);
        list2.insert2(7);
        list2.insert2(8);
        list2.insert2(3);
        list2.insert2(4);
        list2.insert2(5);
        System.out.println();
        list2.printAll_beautiful();

    }


}

打印結(jié)果

`null:15-------
null:14-------
null:13-------
null:12-------
null:11-------
null:10-------
5:9-------
5:8-------
5:7-------
5:6-------
5:5-------
5:4-------8:4-------
4:3-------5:3-------6:3-------7:3-------8:3-------
1:2-------2:2-------4:2-------5:2-------6:2-------7:2-------8:2-------
1:1-------2:1-------3:1-------4:1-------5:1-------6:1-------7:1-------8:1-------
1:0-------2:0-------3:0-------4:0-------5:0-------6:0-------7:0-------8:0-------
{ data: 1; levels: 3 } { data: 2; levels: 3 } { data: 3; levels: 2 } { data: 4; levels: 4 } { data: 5; levels: 10 } { data: 6; levels: 4 } { data: 7; levels: 4 } { data: 8; levels: 5 }

null:15-------
null:14-------
null:13-------
null:12-------
null:11-------
null:10-------
null:9-------
null:8-------
null:7-------
null:6-------
null:5-------
5:4-------
3:3-------5:3-------
3:2-------4:2-------5:2-------7:2-------8:2-------
2:1-------3:1-------4:1-------5:1-------6:1-------7:1-------8:1-------
1:0-------2:0-------3:0-------4:0-------5:0-------6:0-------7:0-------8:0-------

代碼來源github，并非本人編寫：https://github.com/wangzheng0822/algo/blob/master/java/17_skiplist/SkipList2.java

總結(jié)

什么是跳表？

跳表，全程：跳躍鏈表，在計(jì)算機(jī)科學(xué)中，跳躍列表是一種數(shù)據(jù)結(jié)構(gòu)。它使得包含n個(gè)元素的有序序列的查找和插入操作的平均時(shí)間復(fù)雜度都是：
$logn$

跳表的時(shí)間/空間復(fù)雜度

時(shí)間復(fù)雜度：O(logn)，空間復(fù)雜度：O(n)，空間復(fù)雜度會(huì)隨著索引間隔距離的增大而減少，但是空間復(fù)雜度的趨勢(shì)還是O(n)不變，由于索引層存儲(chǔ)的信息相對(duì)于原始鏈表來說會(huì)少很多，所以即使是O(n)的空間復(fù)雜度，也是可以接受的。

跳表的應(yīng)用

1.redis的有序集合。

2.google開源的key/value存儲(chǔ)引擎。

3.HBase MemStore 內(nèi)部存儲(chǔ)結(jié)構(gòu)

跳表的動(dòng)態(tài)更新

由于跳表是由多層索引組成的，所以再頻繁插入的時(shí)候會(huì)導(dǎo)致某一端相鄰索引結(jié)點(diǎn)之前的數(shù)據(jù)過多，最壞情nixuefeileam況下，會(huì)導(dǎo)致所有的數(shù)據(jù)都集中在某一段相鄰索引結(jié)點(diǎn)之間，這將會(huì)導(dǎo)致跳表退化成普通鏈表，時(shí)間復(fù)雜度也會(huì)退化到O(n)，所以這個(gè)時(shí)候就需要?jiǎng)討B(tài)的去更新跳表中的索引結(jié)點(diǎn)，目前通過隨機(jī)函數(shù)實(shí)現(xiàn)。

為什么redis采用跳表實(shí)現(xiàn)有序集合？

1.跳表是鏈表+多級(jí)索引組成的數(shù)據(jù)結(jié)構(gòu)，通過空間換時(shí)間的設(shè)計(jì)思路，實(shí)現(xiàn)了基于鏈表的“二分查找”，查找、刪除、插入時(shí)間復(fù)雜度皆為：O(logn)。

2.跳表實(shí)現(xiàn)方式相對(duì)于B樹、紅黑樹、AVL樹等簡(jiǎn)單許多，這幾種樹的平衡維護(hù)相當(dāng)麻煩，而跳表的動(dòng)態(tài)索引更新相對(duì)來說就簡(jiǎn)單很多了。

3.跳表的區(qū)間查找要比紅黑樹等優(yōu)秀。

朋友，你學(xué)廢了嗎？

本文由博客群發(fā)一文多發(fā)等運(yùn)營工具平臺(tái) OpenWrite 發(fā)布

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

是什么讓普通的鏈表也能達(dá)到二分查找的效率？沒錯(cuò)，就是跳表

是什么讓普通的鏈表也能達(dá)到二分查找的效率？沒錯(cuò)，就是跳表

數(shù)組與鏈表

數(shù)組

鏈表

什么是跳表？

跳表分析

索引更新

代碼實(shí)現(xiàn)

總結(jié)

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

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

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

是什么讓普通的鏈表也能達(dá)到二分查找的效率？沒錯(cuò)，就是跳表

數(shù)組與鏈表

數(shù)組

鏈表

什么是跳表？

跳表分析

索引更新

代碼實(shí)現(xiàn)

總結(jié)

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

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

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