一、為何有skipList這種數(shù)據(jù)結(jié)構(gòu)的出現(xiàn)

我們知道二分查找算法之所以能達(dá)到 O(logn) 這樣高效的一個(gè)重要原因在于它所依賴(lài)的數(shù)據(jù)結(jié)構(gòu)是數(shù)組，數(shù)組支持隨機(jī)訪問(wèn)一個(gè)元素，通過(guò)下標(biāo)很容易定位到中間元素。而鏈表是不支持隨機(jī)訪問(wèn)的，只能從頭到尾依次訪問(wèn)。但是數(shù)組有數(shù)組的局限性，比如需要連續(xù)的內(nèi)存空間，插入刪除操作會(huì)引起數(shù)組的擴(kuò)容和元素移動(dòng)，鏈表有鏈表的優(yōu)勢(shì)，鏈表不需要先申請(qǐng)連續(xù)的空間，插入刪除操作的效率非常高。在很多情況下，數(shù)據(jù)是通過(guò)鏈表這種數(shù)據(jù)結(jié)構(gòu)存儲(chǔ)的，如果是有序鏈表，真的就沒(méi)有辦法使用二分查找算法了嗎？實(shí)際上對(duì)有序鏈表稍加改造，我們就可以對(duì)鏈表進(jìn)行二分查找。這就是我們要說(shuō)的跳表。說(shuō)到底，skipList的出現(xiàn)就是為了實(shí)現(xiàn)有序鏈表的二分查找，使有序鏈表的查找速度能夠媲美它的效率和紅黑樹(shù)以及 AVL 樹(shù)，而刪除和插入的速度又能比他們速度更快。下面我們來(lái)看一下，跳表是怎么跳的。這里記住一句話：跳表的查找、插入、刪除的時(shí)間復(fù)雜度都是 O(logn）

二、跳表的特點(diǎn)及結(jié)構(gòu)

總結(jié)就是一句話：給有序的鏈表再加索引，在n級(jí)索引的基礎(chǔ)上，還可以再加n+1級(jí)索引，直至該級(jí)索引的索引點(diǎn)只有2個(gè)時(shí)，就沒(méi)必要再加索引

先看一下跳表的特點(diǎn)

由很多層組成

每一層都是一個(gè)有序鏈表

最底層的鏈表包含所有元素

每個(gè)元素插入時(shí)隨機(jī)生成它的leve

如果一個(gè)元素出現(xiàn)在第i層的鏈表中，則它在i-1層中也會(huì)出現(xiàn)

上層節(jié)點(diǎn)可以跳轉(zhuǎn)到下層

跳表查詢(xún)、插入、刪除的時(shí)間復(fù)雜度為O(log n)，與平衡二叉樹(shù)接近

跳表的最終結(jié)構(gòu)圖：

三、跳表相關(guān)操作

查找操作，查找的時(shí)間復(fù)雜度

查找元素的過(guò)程是從最高級(jí)索引開(kāi)始，一層一層遍歷最后下沉到原始鏈表。所以，時(shí)間復(fù)雜度 = 索引的高度 * 每層索引遍歷元素的個(gè)數(shù)。

圖中所示，現(xiàn)在到達(dá)第 k 級(jí)索引，我們發(fā)現(xiàn)要查找的元素 x 比 y 大比 z 小，所以，我們需要從 y 處下降到 k-1 級(jí)索引繼續(xù)查找，k-1級(jí)索引中比 y 大比 z 小的只有一個(gè) w，所以在 k-1 級(jí)索引中，我們遍歷的元素最多就是 y、w、z，發(fā)現(xiàn) x 比w大比 z 小之后，再下降到 k-2 級(jí)索引。所以，k-2 級(jí)索引最多遍歷的元素為
w、u、z。其實(shí)每級(jí)索引都是類(lèi)似的道理，每級(jí)索引中都是兩個(gè)結(jié)點(diǎn)抽出一個(gè)結(jié)點(diǎn)作為上一級(jí)索引的結(jié)點(diǎn)。
現(xiàn)在我們得出結(jié)論：當(dāng)每級(jí)索引都是兩個(gè)結(jié)點(diǎn)抽出一個(gè)結(jié)點(diǎn)作為上一級(jí)索引的結(jié)點(diǎn)時(shí)，每一層最多遍歷3個(gè)結(jié)點(diǎn)。
跳表的索引高度 h = log2n，且每層索引最多遍歷 3 個(gè)元素。所以跳表中查找一個(gè)元素的時(shí)間復(fù)雜度為 O(3*logn)，省略常數(shù)即：O(logn)。

空間復(fù)雜度

跳表通過(guò)建立索引，來(lái)提高查找元素的效率，就是典型的“空間換時(shí)間”的思想，所以在空間上做了一些犧牲，那空間復(fù)雜度到底是多少呢？

假如原始鏈表包含 n 個(gè)元素，則一級(jí)索引元素個(gè)數(shù)為 n/2、二級(jí)索引元素個(gè)數(shù)為 n/4、三級(jí)索引元素個(gè)數(shù)為 n/8 以此類(lèi)推。所以，索引節(jié)點(diǎn)的總和是：n/2 + n/4 + n/8 + … + 8 + 4 + 2 = n-2，空間復(fù)雜度是 O(n)。
如下圖所示：如果每三個(gè)結(jié)點(diǎn)抽一個(gè)結(jié)點(diǎn)做為索引，索引總和數(shù)就是 n/3 + n/9 + n/27 + … + 9 + 3 + 1= n/2，減少了一半。所以我們可以通過(guò)較少索引數(shù)來(lái)減少空間復(fù)雜度，但是相應(yīng)的肯定會(huì)造成查找效率有一定下降，我們可以根據(jù)我們的應(yīng)用場(chǎng)景來(lái)控制這個(gè)閾值，看我們更注重時(shí)間還是空間。

插入數(shù)據(jù)

插入數(shù)據(jù)看起來(lái)也很簡(jiǎn)單，跳表的原始鏈表需要保持有序，所以我們會(huì)向查找元素一樣，找到元素應(yīng)該插入的位置。如下圖所示，要插入數(shù)據(jù)6，整個(gè)過(guò)程類(lèi)似于查找6，整個(gè)的查找路徑為 1、1、1、4、4、5。查找到第底層原始鏈表的元素 5 時(shí)，發(fā)現(xiàn) 5 小于 6 但是后繼節(jié)點(diǎn) 7 大于 6，所以應(yīng)該把 6 插入到 5 之后 7 之前。整個(gè)時(shí)間復(fù)雜度為查找元素的時(shí)間復(fù)雜度 O(logn)。

這里有一個(gè)需要格外注意的地方：如果只是單純插入數(shù)據(jù)而不更新索引，跳表最后也會(huì)退化成鏈表，如下圖：

4. randomLevel() 方法

對(duì)于這個(gè)問(wèn)題 ，可能大家普遍想到的方法就是，插入數(shù)據(jù)后刪除原來(lái)的索引，再重新建立索引。那么重建索引的重建索引的時(shí)間復(fù)雜度是多少呢？因?yàn)樗饕目臻g復(fù)雜度是 O(n)，即：索引節(jié)點(diǎn)的個(gè)數(shù)是 O(n) 級(jí)別，每次完全重新建一個(gè) O(n) 級(jí)別的索引，時(shí)間復(fù)雜度也是 O(n) 。造成的后果是：為了維護(hù)索引，導(dǎo)致每次插入數(shù)據(jù)的時(shí)間復(fù)雜度變成了 O(n)。

那有沒(méi)有其他效率比較高的方式來(lái)維護(hù)索引呢？假如跳表每一層的晉升概率是 1/2，最理想的索引就是在原始鏈表中每隔一個(gè)元素抽取一個(gè)元素做為一級(jí)索引。換種說(shuō)法，我們?cè)谠兼湵碇须S機(jī)的選 n/2 個(gè)元素做為一級(jí)索引是不是也能通過(guò)索引提高查找的效率呢？ 當(dāng)然可以了，因?yàn)橐话汶S機(jī)選的元素相對(duì)來(lái)說(shuō)都是比較均勻的。如下圖所示，隨機(jī)選擇了n/2 個(gè)元素做為一級(jí)索引，雖然不是每隔一個(gè)元素抽取一個(gè)，但是對(duì)于查找效率來(lái)講，影響不大，比如我們想找元素 16，仍然可以通過(guò)一級(jí)索引，使得遍歷路徑較少了將近一半。如果抽取的一級(jí)索引的元素恰好是前一半的元素 1、3、4、5、7、8，那么查找效率確實(shí)沒(méi)有提升，但是這樣的概率太小了。我們可以認(rèn)為：當(dāng)原始鏈表中元素?cái)?shù)量足夠大，且抽取足夠隨機(jī)的話，我們得到的索引是均勻的。我們要清楚設(shè)計(jì)良好的數(shù)據(jù)結(jié)構(gòu)都是為了應(yīng)對(duì)大數(shù)據(jù)量的場(chǎng)景，如果原始鏈表只有 5 個(gè)元素，那么依次遍歷 5 個(gè)元素也沒(méi)有關(guān)系，因?yàn)閿?shù)據(jù)量太少了。所以，我們可以維護(hù)一個(gè)這樣的索引：隨機(jī)選 n/2 個(gè)元素做為一級(jí)索引、隨機(jī)選 n/4 個(gè)元素做為二級(jí)索引、隨機(jī)選 n/8 個(gè)元素做為三級(jí)索引，依次類(lèi)推，一直到最頂層索引。這里每層索引的元素個(gè)數(shù)已經(jīng)確定，且每層索引元素選取的足夠隨機(jī)，所以可以通過(guò)索引來(lái)提升跳表的查找效率。

那代碼該如何實(shí)現(xiàn)，才能使跳表滿(mǎn)足上述這個(gè)樣子呢？可以在每次新插入元素的時(shí)候，盡量讓該元素有 1/2 的幾率建立一級(jí)索引、1/4 的幾率建立二級(jí)索引、1/8 的幾率建立三級(jí)索引，以此類(lèi)推，就能滿(mǎn)足我們上面的條件。現(xiàn)在我們就需要一個(gè)概率算法幫我們把控這個(gè) 1/2、1/4、1/8 ... ，當(dāng)每次有數(shù)據(jù)要插入時(shí)，先通過(guò)概率算法告訴我們這個(gè)元素需要插入到幾級(jí)索引中，然后開(kāi)始維護(hù)索引并把數(shù)據(jù)插入到原始鏈表中。下面開(kāi)始講解這個(gè)概率算法代碼如何實(shí)現(xiàn)。
我們可以實(shí)現(xiàn)一個(gè) randomLevel() 方法，該方法會(huì)隨機(jī)生成 1~MAX_LEVEL 之間的數(shù)（MAX_LEVEL表示索引的最高層數(shù)），且該方法有 1/2 的概率返回 1、1/4 的概率返回 2、1/8的概率返回 3，以此類(lèi)推。

randomLevel() 方法返回 1 表示當(dāng)前插入的該元素不需要建索引，只需要存儲(chǔ)數(shù)據(jù)到原始鏈表即可（概率 1/2）

randomLevel() 方法返回 2 表示當(dāng)前插入的該元素需要建一級(jí)索引（概率 1/4）

randomLevel() 方法返回 3表示當(dāng)前插入的該元素需要建二級(jí)索引（概率 1/8） randomLevel() 方法返回 4 表示當(dāng)前插入的該元素需要建三級(jí)索引（概率1/16）

。。。以此類(lèi)推

所以，通過(guò) randomLevel() 方法，我們可以控制整個(gè)跳表各級(jí)索引中元素的個(gè)數(shù)。重點(diǎn)來(lái)了：randomLevel() 方法返回 2 的時(shí)候會(huì)建立一級(jí)索引，我們想要一級(jí)索引中元素個(gè)數(shù)占原始數(shù)據(jù)的 1/2，但是 randomLevel() 方法返回 2 的概率為 1/4，那是不是有矛盾呢？明明說(shuō)好的 1/2，結(jié)果一級(jí)索引元素個(gè)數(shù)怎么變成了原始鏈表的 1/4？我們先看下圖，應(yīng)該就明白了。

假設(shè)我們?cè)诓迦朐?6 的時(shí)候，randomLevel() 方法返回 1，則我們不會(huì)為 6 建立索引。插入 7 的時(shí)候，randomLevel() 方法返回3 ，所以我們需要為元素 7 建立二級(jí)索引。這里我們發(fā)現(xiàn)了一個(gè)特點(diǎn)：當(dāng)建立二級(jí)索引的時(shí)候，同時(shí)也會(huì)建立一級(jí)索引；當(dāng)建立三級(jí)索引時(shí)，同時(shí)也會(huì)建立一級(jí)、二級(jí)索引。所以，一級(jí)索引中元素的個(gè)數(shù)等于 [ 原始鏈表元素個(gè)數(shù) ] * [ randomLevel() 方法返回值 > 1 的概率 ]。因?yàn)?randomLevel() 方法返回值 > 1就會(huì)建索引，凡是建索引，無(wú)論幾級(jí)索引必然有一級(jí)索引，所以一級(jí)索引中元素個(gè)數(shù)占原始數(shù)據(jù)個(gè)數(shù)的比率為 randomLevel() 方法返回值 > 1 的概率。那 randomLevel() 方法返回值 > 1 的概率是多少呢？因?yàn)?randomLevel() 方法隨機(jī)生成 1~MAX_LEVEL 的數(shù)字，且 randomLevel() 方法返回值 1 的概率為 1/2，則 randomLevel() 方法返回值 > 1 的概率為 1 - 1/2 = 1/2。即通過(guò)上述流程實(shí)現(xiàn)了一級(jí)索引中元素個(gè)數(shù)占原始數(shù)據(jù)個(gè)數(shù)的 1/2。

同理，當(dāng) randomLevel() 方法返回值 > 2 時(shí)，會(huì)建立二級(jí)或二級(jí)以上索引，都會(huì)在二級(jí)索引中增加元素，因此二級(jí)索引中元素個(gè)數(shù)占原始數(shù)據(jù)的比率為 randomLevel() 方法返回值 > 2 的概率。 randomLevel() 方法返回值 > 2 的概率為 1 減去 randomLevel() = 1 或 =2 的概率，即 1 - 1/2 - 1/4 = 1/4。OK，達(dá)到了我們?cè)O(shè)計(jì)的目標(biāo)：二級(jí)索引中元素個(gè)數(shù)占原始數(shù)據(jù)的 1/4。

以此類(lèi)推，可以得出，遵守以下兩個(gè)條件：

randomLevel() 方法，隨機(jī)生成 1~MAX_LEVEL 之間的數(shù)（MAX_LEVEL表示索引的最高層數(shù)），且有 1/2的概率返回1、1/4的概率返回 2、1/8的概率返回 3 …

randomLevel() 方法返回 1 不建索引、返回2建一級(jí)索引、返回 3建二級(jí)索引、返回 4 建三級(jí)索引 …

就可以滿(mǎn)足我們想要的結(jié)果，即：一級(jí)索引中元素個(gè)數(shù)應(yīng)該占原始數(shù)據(jù)的 1/2，二級(jí)索引中元素個(gè)數(shù)占原始數(shù)據(jù)的 1/4，三級(jí)索引中元素個(gè)數(shù)占原始數(shù)據(jù)的 1/8 ，依次類(lèi)推，一直到最頂層索引。

randomLevel() 方法代碼：

// 理論來(lái)講，一級(jí)索引中元素個(gè)數(shù)應(yīng)該占原始數(shù)據(jù)的 50%，二級(jí)索引中元素個(gè)數(shù)占 25%，三級(jí)索引12.5% ，一直到最頂層。// 因?yàn)檫@里每一層的晉升概率是 50%。對(duì)于每一個(gè)新插入的節(jié)點(diǎn)，都需要調(diào)用 randomLevel 生成一個(gè)合理的層數(shù)。// 該 randomLevel 方法會(huì)隨機(jī)生成 1~MAX_LEVEL 之間的數(shù)，且 ：// 50%的概率返回 1// 25%的概率返回 2// 12.5%的概率返回 3 ...private int randomLevel() {int level = 1;while (Math.random() < SKIPLIST_P && level < MAX_LEVEL) {level += 1;}return level;}

完整的插入流程：

整個(gè)插入過(guò)程的路徑與查找元素路徑類(lèi)似， 每層索引中插入元素的時(shí)間復(fù)雜度 O(1)，所以整個(gè)插入的時(shí)間復(fù)雜度是 O(logn)。

刪除數(shù)據(jù)

刪除元素的時(shí)間復(fù)雜度：
刪除元素的過(guò)程跟查找元素的過(guò)程類(lèi)似，只不過(guò)在查找的路徑上如果發(fā)現(xiàn)了要?jiǎng)h除的元素 x，則執(zhí)行刪除操作。跳表中，每一層索引其實(shí)都是一個(gè)有序的單鏈表，單鏈表刪除元素的時(shí)間復(fù)雜度為 O(1)，索引層數(shù)為 logn 表示最多需要?jiǎng)h除 logn 個(gè)元素，所以刪除元素的總時(shí)間包含 查找元素的時(shí)間 加 刪除 logn個(gè)元素的時(shí)間 為 O(logn) + O(logn) = 2 O(logn)，忽略常數(shù)部分，刪除元素的時(shí)間復(fù)雜度為 O(logn)。

本文轉(zhuǎn)自

總結(jié)

以上是生活随笔為你收集整理的跳表（skipList）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。