資料結構 - 跳表

簡介

有序的陣列可以使用二分查找的方法快速檢索一個資料，但是鏈表沒有辦法使用二分查找，

對于一個單向鏈表來說，即使鏈表中存盤的是有序的資料，但如果想要從中查找某個資料時，也只能從頭到尾遍歷鏈表，其時間復雜度是 \(O(n)\)，

為了提高鏈表的查詢效率，使其支持類似“二分查找”的方法，對鏈表進行多層次擴展，這樣的資料結構就是跳表，跳表對標的是平衡樹，是一種提升鏈表插入、洗掉、搜索效率的資料結構，

首先，跳表處理的是有序的鏈表，一般使用雙向鏈表更加方便，

然后，每兩個結點提取一個結點到上一級，提取的這一層被稱作為索引層，

這時候，當想要查找 19 這個數字，可以先從索引層開始查找；當到達 17 時，發現下一個結點存盤 21 這個數字，則可以確定，想要查找的 19 肯定是在 17 到 21 之間；這時候可以轉到下一層（原始鏈表）中查找，快速從 17 開始檢索，很快就可以查找出 19 這個數字，

加入一層索引之后，查找一個結點需要遍歷的結點個數減少了，也就是查找效率提高了，實際上，一般會新增多層索引，擁有多層索引的跳表，查找一個結點需要遍歷的結點個數將再次減少，

這種鏈表加多層索引的結構，就是跳表，

效率分析

為了方便對跳表的效率做分析，在這里設定一個常見的跳表型別，

假設每兩個結點會抽出一個結點作為上一級索引的結點，那第一級的索引個數大約就是 \(\frac{n}{2}\)，第二級的索引個數大約就是 \(\frac{n}{4}\)，以此類推，第 k 個索引的結點個數是第 k-1 個索引的結點個數的 \(\frac{1}{2}\)，那么，第 k 個索引的結點個數就是 \(\frac{n}{2^k}\)，

時間復雜度

假設索引總共有 h 級，最高級的索引有 2 個結點，使用公式 \(\frac{n}{2^h} = 2\) 進行反推，可以計算得出 \(h = \log_2 n - 1\)，如果是包含原始鏈表那一級，跳表的高度就是 \(\log_2 n\) 級，

如果想要從跳表中查詢某個資料時，每層都會遍歷 m 個結點，那么，在跳表中查詢一個資料的時間復雜度就是 \(O(m \log n)\)，

從上面圖中可知，在每一級索引中最多只需要遍歷 3 個結點，其實就可以看作是 m = 3，

實際就是，在最高級索引時最多遍歷 3 個結點，當需要在下一級索引中繼續檢索時，算上前后兩個當做范圍的結點也只有 3 個，因此，在每一級索引最多只需要遍歷 3 個結點，

如果細究的話，m 的值與抽取索引值的間隔有直接關系，但是只是計算時間復雜度的話，可以將 m 值看作是一個常數，

因此，在跳表中做檢索的時間復雜度是 \(O(\log n)\)，

空間復雜度

同樣的，假設每兩個結點會抽出一個結點作為上一級索引的結點，那第一級的索引個數大約就是 \(\frac{n}{2}\)，第二級的索引個數大約就是 \(\frac{n}{4}\)，依次類推，最終索引占用的空間將是 \(\frac{n}{2} + \frac{n}{4} + ... + 4 + 2 = n - 2\)，

所以，跳表的空間復雜度是 \(O(n)\)，

實際上，跳表是一種使用空間換時間的資料結構，以增加索引的方式，提高檢索資料的效率，因此，跳表會比普通鏈表耗費更多記憶體進行資料存盤，

結點間隔

在上述分析跳表的時間復雜度和空間復雜度時，都是以每兩個結點抽出一個結點作為上一級索引的結點，

實際上，也可以使用 3 個結點或 4 個結點甚至更多結點做間隔，當然，以不同個數結點做間隔時，檢索效率和記憶體占用都會有些不一樣，

假設以 3 個結點做間隔，占用的空間會有所降低，在這個跳表上做檢索操作時，檢索的效率也會有一些降低，

因為在每一級索引檢索的最多結點個數將從 2 個變成 3 個，跳表的高度是 \(\log_3 n\) 級，最終占用的空間將是 \(\frac{n}{3} + \frac{n}{9} + ... + 3 + 1 = \frac{n}{2}\)，

在理論上，以 3 個結點做間隔的跳表與以 2 個結點做間隔的跳表的時間復雜度和空間復雜度都是一樣的，但是，實際操作時，以 3 個結點做間隔的跳表的空間占用會比以 2 個結點做間隔的跳表更優一些，

實際上，在軟體開發中，不必太在意索引占用的額外空間，雖然原始鏈表中存盤的有可能是很大的物件，但索引結點可以只存盤關鍵值和幾個指標，并不需要存盤物件，所以當物件比索引結點大很多時，那索引占用的額外空間就可以忽略了，

動態插入和洗掉

上面理解的跳表都是靜態的，實際開發中，跳表在新增、洗掉結點時需要做動態處理，否則容易導致檢索效率降低，

如上圖所示，如果頻繁插入結點，而沒有對索引層做動態處理，很容易出現不滿足一開始設定的跳表規則，

洗掉鏈表的結點時也是同樣道理，如果洗掉結點而沒有更新索引層，索引層容易出現已被洗掉的臟結點，

重建索引

比較容易理解的方法就是重建索引，當每次插入、洗掉結點的時候，把整個跳表的所有索引層洗掉重建，

但是這種方法會降低插入結點時的效率，已知跳表的空間復雜度是 \(O(n)\)，也可以推斷出重建跳表索引層的時間復雜至少是 \(O(n)\)，

也就是說，使用重建索引的方式，跳表插入結點耗費時間將會直線上升，

隨機索引

與重建索引相比，隨機索引的效率會更高一些，像 Redis 實作 SortedSet 底層用的跳表就是使用隨機索引的方式進行動態處理，

這里的做法是通過使用一個隨機函式，來決定這個結點插入時，是否需要插入到索引層、以及插入到第幾級索引，

一般來說，通過隨機函式得到的資料都是比較均勻的，也表示最終得到的跳表索引層也是比較均勻，而且資料量越大，索引層越是均勻，

先設定索引的生成規則：從原始鏈表中隨機選擇 \(\frac{1}{2}\) 個結點作為一級索引，從一級索引中隨機選擇 \(\frac{1}{4}\) 個結點作為二級索引，以此類推，一直到最頂層索引，這時候就需要根據這個規則完成所需的隨機函式，并且是每次插入結點的時候，都通過隨機函式判斷這個結點需要插入到幾級索引，

以下是 Redis 原始碼當中使用到的隨機函式：

/* Returns a random level for the new skiplist node we are going to create.
 * The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
 * (both inclusive), with a powerlaw-alike distribution where higher
 * levels are less likely to be returned. */
int zslRandomLevel(void) {
    int level = 1;
    while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
        level += 1;
    return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}

這個隨機函式會隨機生成 1 到索引最高層數之間的一個數字，該方法有 \(\frac{1}{2}\) 的概率回傳 1、有 \(\frac{1}{4}\) 的概率回傳 2、有 \(\frac{1}{8}\) 的概率回傳 3、以此類推，其中 1 表示不需要生成索引，2 表示需要生成一級索引，3 表示需要生成二級索引，以此類推，

為什么不是回傳 1 時生成一級索引呢？這是因為，在生成比一級索引更高層級的索引時，都會向下生成索引，即如果隨機函式回傳 3，則會給這個結點同時生成二級索引和一級索引，這樣，如果回傳 1 時生成一級索引則會出現生成一級索引的概率為 100%，

使用隨機索引方法的跳表，插入結點的時間復雜度與跳表索引的高度相同，最終時間復雜度降到 \(O(\log n)\)，而不是重建索引的 \(O(n)\)，

應用場景

已經知道，Redis 使用了跳表來實作有序集合，其中的原因就是跳表按區間查找元素的時間復雜度是 \(O(\log n + m)\)，而如果使用紅黑樹實作有序集合，按區間查找元素將會位元表慢很多，

還有其他的一些開源產品也有使用到跳表結構，如 HBase MemStore 內部存盤資料就使用到跳表，Google 開源的 LevelDB 以及 Facebook 基于 LevelDB 優化的 RocksDB 內部的 MemTable 都是使用跳表這種資料結構，

標籤：其他

上一篇：Java案例——游戲次數的限制

下一篇：已實名未成年的帳號登錄華為游戲，不提示防沉迷