[[384895]]

1. 跳表的概念

跳表是一個(gè)動態(tài)數(shù)據(jù)結(jié)構(gòu)，可以支持快速地插入、刪除、查找操作，寫起來也不怎么復(fù)雜，甚至可以替代紅黑樹。跳表的空間復(fù)雜度是 O(n)，時(shí)間復(fù)雜度是 O(logn)。

對于一個(gè)有序的單鏈表來說，如果想要查找一個(gè)數(shù)據(jù)也只能從頭到尾遍歷鏈表。為了提高查詢的效率，我們可以借助索引，即對鏈表構(gòu)建一級索引，比如把每兩個(gè)鏈表節(jié)點(diǎn)中較小的那個(gè)節(jié)點(diǎn)提取為一級索引節(jié)點(diǎn)(對于 key value 的值來說，可以只保留 key 值)，一級索引節(jié)點(diǎn)也可以采用同樣的方式提取為二級索引節(jié)點(diǎn)，如圖所示，即為跳表的結(jié)構(gòu)。

針對下圖，假如想要查詢 10 這個(gè)數(shù)據(jù)，那么先在二級索引層遍歷，當(dāng)遍歷到二級索引中 7 這個(gè)索引節(jié)點(diǎn)之后，發(fā)現(xiàn)后面的一個(gè)索引節(jié)點(diǎn)的值是 13，那么10 這個(gè)數(shù)據(jù)節(jié)點(diǎn)肯定是在這兩個(gè)索引節(jié)點(diǎn)之間。然后，我們通過 down 指針，下降到一級索引層繼續(xù)遍歷查找。這個(gè)時(shí)候遍歷到 9 這個(gè)一級索引節(jié)點(diǎn)，而后面一個(gè)索引節(jié)點(diǎn)的值是 13，那么則繼續(xù)通過 down 指針下降到原始鏈表繼續(xù)遍歷查找，從而找到 10 這個(gè)數(shù)據(jù)。

綜上所述，跳表是一個(gè)值有序的鏈表建立多級索引之后的一種數(shù)據(jù)結(jié)構(gòu)，通過上述的查找方式，我們可以看到類似于二叉查找樹的查找方式，所以說跳表查找類似于鏈表的“二分查找”算法。

空間復(fù)雜度

假設(shè)原始鏈表大小為 n，那第一級鏈表有 n/2 個(gè)節(jié)點(diǎn)，第二季索引有 n/4 個(gè)節(jié)點(diǎn)，最頂層有 2 個(gè)節(jié)點(diǎn)。那么總共需要的索引節(jié)點(diǎn)個(gè)數(shù)就是

因此，跳表總的空間復(fù)雜度還是 O(n)，也就說使用跳表查詢數(shù)據(jù)時(shí)，需要額外 n 個(gè)節(jié)點(diǎn)的存儲空間。雖然空間復(fù)雜度還是沒變，但是使用的額外空間還是有點(diǎn)多的。那么，可以采用以下方法來盡可能的降低索引占用的空間復(fù)雜度：可以多幾個(gè)節(jié)點(diǎn)抽取成一個(gè)節(jié)點(diǎn)，比如每 3 個(gè)節(jié)點(diǎn)或者 5 個(gè)節(jié)點(diǎn)抽取成一個(gè)節(jié)點(diǎn)。雖然這樣子空間復(fù)雜度還是 O(n)，但實(shí)際上所需的索引節(jié)點(diǎn)數(shù)量少了好多。

★實(shí)際的軟件開發(fā)中，原始鏈表中存儲的有可能是很大的對象，而索引節(jié)點(diǎn)只需要存儲關(guān)鍵值和幾個(gè)指針，并不需要存儲對象，這個(gè)時(shí)候，索引節(jié)點(diǎn)所占用的額外空間相比大對象來說其實(shí)很小，可以忽略不計(jì)。”

2. 跳表的操作

2.1. 查找

單鏈表查詢的時(shí)間復(fù)雜度是 O(n)，那么針對一個(gè)具有多級索引的跳表，查詢某個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度是多少呢?能否提高查詢的效率呢?

假設(shè)鏈表中有 n 個(gè)節(jié)點(diǎn)，我們假設(shè)每兩個(gè)節(jié)點(diǎn)抽出一個(gè)節(jié)點(diǎn)作為上一級的索引節(jié)點(diǎn)，那么第一級的索引節(jié)點(diǎn)個(gè)數(shù)是 n/2，第二級的索引節(jié)點(diǎn)個(gè)數(shù)是 n/2^2。依次類推，第 k 級的索引節(jié)點(diǎn)個(gè)數(shù)是 n/2^k。假設(shè)索引層最高有 h 級，而最高層的索引節(jié)點(diǎn)有 2 個(gè)節(jié)點(diǎn)，那么得到 ，加上原始鏈表這一層，一共有 層。

我們在跳表中查詢某個(gè)數(shù)據(jù)的時(shí)候，如果每一層都要編譯 m 個(gè)，那么跳表一個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度就是 O(mlogn)。由于我們是每兩個(gè)節(jié)點(diǎn)抽出一個(gè)節(jié)點(diǎn)，而且最高層也只有兩個(gè)節(jié)點(diǎn)，所以每一層最多比較 3 個(gè)節(jié)點(diǎn)。比如我們要查找的數(shù)據(jù)是 x，當(dāng)在第 k 級索引層遍歷到 y 節(jié)點(diǎn)之后，發(fā)現(xiàn) x 大于 y 但是小于 y 后面的 z 節(jié)點(diǎn)，那么則通過 y 的down 指針從 k 級索引下降到 k-1 級索引，而在 k-1 級索引中最多只需要遍歷 3 個(gè)節(jié)點(diǎn)即可。

因此，在跳表中查詢數(shù)據(jù)的時(shí)間復(fù)雜度是 O(logn)，這個(gè)時(shí)間復(fù)雜度和二分查找是一樣的。不過，這種查詢效率的提升，提前是建立了很多級索引，使用了空間換時(shí)間的設(shè)計(jì)思路。

2.2. 插入

在單鏈表中，假如定位到了要插入的位置，那么插入節(jié)點(diǎn)這個(gè)操作的時(shí)間復(fù)雜度很低，為 O(1)。但是要定位到插入的位置的時(shí)間復(fù)雜度是 O(n)，比如原始鏈表中數(shù)據(jù)有序，那么需要遍歷鏈表才能找到要插入的位置。

對于跳表來說，由于查找某個(gè)節(jié)點(diǎn)的時(shí)間復(fù)雜度是 O(logn)，而插入實(shí)際上就是鏈表中的插入，因此插入操作的時(shí)間復(fù)雜度也就是 O(logn)。

2.3. 刪除

刪除操作也是類似的，但是如果這個(gè)節(jié)點(diǎn)在索引中也有出現(xiàn)的話，除了要刪除原始鏈表中的節(jié)點(diǎn)之外，還要刪除索引中的。由于刪除節(jié)點(diǎn)需要前驅(qū)節(jié)點(diǎn)，因此使用雙向鏈表的話，可以很方便的刪除一個(gè)節(jié)點(diǎn)。

綜上，刪除操作的時(shí)間復(fù)雜度也可以做到 O(logn)。

2.4. 索引更新

當(dāng)我們不停地往跳表中插入數(shù)據(jù)而不更新索引節(jié)點(diǎn)的話，那么 2 個(gè)索引節(jié)點(diǎn)之間的數(shù)據(jù)可能會非常的多。極端情況下，跳表可能會退化為單鏈表。因此，我們需要某種手段來維護(hù)索引與原始鏈表大小之間的平衡，也就是說如果鏈表中的節(jié)點(diǎn)變多了，索引節(jié)點(diǎn)也相應(yīng)地增加一些，避免查找、插入、刪除的性能下降。

跳表通過隨機(jī)函數(shù)的方式來維護(hù)這種平衡性。當(dāng)我們往跳表中插入數(shù)據(jù)的時(shí)候，我們通過一個(gè)隨機(jī)函數(shù)，來決定將這個(gè)在哪幾層索引層中添加。比如隨機(jī)函數(shù)生成了值 k，那么我們就在第一級到第 k 級這 k 級索引中添加相應(yīng)的索引節(jié)點(diǎn)。

★對于平衡二叉樹來說，比如紅黑樹、AVL，它們是通過左右旋的方式來保持左右子樹的平衡。”

3. 應(yīng)用

Redis 中的有序集合就是用跳表來實(shí)現(xiàn)的，另外還用到了散列表。為什么使用跳表而不是紅黑樹實(shí)現(xiàn)呢?最主要的是跳表它支持區(qū)間查找。

Redis 中的有序集合支持的核心操作中主要有：

1. 插入、刪除、查找一個(gè)數(shù)據(jù);
2. 按照區(qū)間查找數(shù)據(jù)(比如查找值在 [100, 356] 之間的數(shù)據(jù))
3. 迭代輸出有序序列

其中插入、刪除、查找操作，紅黑樹也可以很快完成，時(shí)間復(fù)雜度也是 O(logn)。但是按照區(qū)間來查找數(shù)據(jù)這個(gè)操作，紅黑樹的效率沒有跳表高。跳表可以做到 O(logn) 的時(shí)間復(fù)雜度定位區(qū)間的起點(diǎn)，然后在原始鏈表中順序往后遍歷就可以了。

★實(shí)際上，在有序集合中，每個(gè)成員對象有兩個(gè)重要的屬性：key 和 value。我們有時(shí)候不僅需要通過 value 來查找數(shù)據(jù)，還會通過 key 來查找數(shù)據(jù)。我們可以按照 value 將成員對象組織成跳表的結(jié)構(gòu)，那么此時(shí)根據(jù) value 來查找對象很方便，但是當(dāng)我們想要通過 key 查找對象時(shí)又會很麻煩。那么，我們可以結(jié)合散列表，也就相當(dāng)于把散列表和跳表結(jié)合。此時(shí)，根據(jù) key 來查找、刪除、插入一個(gè)成員對象的時(shí)間復(fù)雜度就變成了 O(1)。”

4. 總結(jié)

跳表是一種動態(tài)數(shù)據(jù)結(jié)構(gòu)，使用了空間換時(shí)間的設(shè)計(jì)思想來提高查詢的效率，簡單來說就是在原始鏈表的基礎(chǔ)之上構(gòu)建了多級索引層來提高查詢的效率，在查找方式上有點(diǎn)類似于二分查找。

綜上，跳表的查詢、插入、刪除的時(shí)間復(fù)雜度都是 O(logn)，而空間復(fù)雜度是 O(n)。

5. 參考

https://juejin.im/post/6844903446475177998

本文轉(zhuǎn)載自微信公眾號「多選參數(shù)」，可以通過以下二維碼關(guān)注。轉(zhuǎn)載本文請聯(lián)系多選參數(shù)公眾號。