[[408437]]

本文轉(zhuǎn)載自微信公眾號「后端技術(shù)指南針」，作者大白斯基。轉(zhuǎn)載本文請聯(lián)系后端技術(shù)指南針公眾號。

跳躍鏈表及其應(yīng)用是非常熱門的問題，深入了解其中奧秘大有裨益，不吹了，快開始品嘗這美味的知識吧!

跳躍鏈表的基本概念

初識跳表

跳躍列表是一種數(shù)據(jù)結(jié)構(gòu)。它允許快速查詢一個有序連續(xù)元素的數(shù)據(jù)鏈表。跳躍列表的平均查找和插入時間復(fù)雜度都是O(log n)，優(yōu)于普通隊列的O(n)。

跳躍列表由威廉·普發(fā)明，發(fā)明者對跳躍列表的評價：跳躍鏈表是在很多應(yīng)用中有可能替代平衡樹而作為實現(xiàn)方法的一種數(shù)據(jù)結(jié)構(gòu)。

跳躍列表的算法有同平衡樹一樣的漸進(jìn)的預(yù)期時間邊界，并且更簡單、更快速和使用更少的空間。

這種數(shù)據(jù)結(jié)構(gòu)是由William Pugh(音譯為威廉·普)發(fā)明的，最早出現(xiàn)于他在1990年發(fā)表的論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。

大白在谷歌上找到一篇作者關(guān)于跳表的論文，感興趣強(qiáng)烈建議下載閱讀：

https://epaperpress.com/sortsearch/download/skiplist.pdf

看下這篇論文的摘要部分：

從中我們獲取到的信息是：跳表在動態(tài)查找過程中使用了一種非嚴(yán)格的平衡機(jī)制來讓插入和刪除都更加便利和快捷，這種非嚴(yán)格平衡是基于概率的，而不是平衡樹的嚴(yán)格平衡。

說到非嚴(yán)格平衡，首先想到的是紅黑樹RbTree，它同樣采用非嚴(yán)格平衡來避免像AVL那樣調(diào)整樹的結(jié)構(gòu)，這里就不展開講紅黑樹了，看來跳表也是類似的路子，但是是基于概率實現(xiàn)的。

動態(tài)查找的數(shù)據(jù)結(jié)構(gòu)

所謂動態(tài)查找就是查找的過程中存在元素的刪除和插入，這樣就對實現(xiàn)查找的數(shù)據(jù)結(jié)構(gòu)有一定的挑戰(zhàn)，因為在每次刪除和插入時都要調(diào)整數(shù)據(jù)結(jié)構(gòu)，來保持秩序。

可以作為查找數(shù)據(jù)結(jié)構(gòu)的包括：

• 線性結(jié)構(gòu)：數(shù)組、鏈表
• 非線性結(jié)構(gòu)：平衡樹

來分析一下各種數(shù)據(jù)結(jié)構(gòu)在應(yīng)對動態(tài)查找時的優(yōu)劣吧!

數(shù)組結(jié)構(gòu)

數(shù)組結(jié)構(gòu)簡單內(nèi)存連續(xù)，可以實現(xiàn)二分查找等基于下標(biāo)的操作，我一直認(rèn)為數(shù)組的殺手锏就是下標(biāo)，連續(xù)的內(nèi)存也帶來了問題。

當(dāng)進(jìn)行插入和刪除時就面臨著整體的調(diào)整，就像在火車站排隊買票，隊頭走一個整個隊伍向前挪一步，有加塞的后面的又整體向后挪一步，這種整體移動操作在數(shù)組結(jié)構(gòu)中性能損耗很大，并且在大數(shù)據(jù)量時對連續(xù)內(nèi)存要求很高，當(dāng)然這個在大內(nèi)存機(jī)器上可能沒有什么問題。

如圖插入6和刪除5時 數(shù)組元素的移動：

鏈表結(jié)構(gòu)

鏈表結(jié)構(gòu)也比較簡單，但是不要求內(nèi)存連續(xù)，不連續(xù)也就沒有下標(biāo)可以加速，但是鏈表在執(zhí)行刪除和插入時影響的只是插入刪除點的前后元素，影響非常小。

但是每次查找元素是需要進(jìn)行遍歷，就算我知道某個元素一定在大致的什么位置，也只能一步步走過去，看到這里要覺得有優(yōu)化的空間，那你也蠻厲害的了，說不定早幾年跳表就是你的發(fā)明了。

如圖刪除元素5和插入元素49時的處理：

平衡樹

平衡樹也是處理動態(tài)查找問題的一把好手，樹一般是基于鏈表實現(xiàn)的，只不過樹的節(jié)點之間并不是鏈表簡單的線性關(guān)系，會有兄弟姐妹父親等節(jié)點，并且各個層級有數(shù)量的限制，可以看到樹其實還是蠻復(fù)雜的。

節(jié)點需要存儲的信息很多，各個指針指來指去，復(fù)雜的結(jié)構(gòu)增加了調(diào)整平衡性的難度，不同情況下的左旋右旋，所以出現(xiàn)了紅黑樹這種工程版本的AVL，但是在實際場景中可能并不需要這些兄弟姐妹父親關(guān)系，有種殺雞宰牛刀的意味了。

紅黑樹的節(jié)點結(jié)構(gòu)定義：

#define COLOR_RED  0x0 
#define COLOR_BLACK 0x1 
 
typedef struct RBNode{ 
   int key; 
   unsigned char color; 
   struct RBNode *left; 
   struct RBNode *right; 
   struct RBNode *parent; 
}rb_node_t, *rb_tree_t; 

另外紅黑樹調(diào)整屬性過程中插入分為3種情況，刪除分為4種情況，還是比較難以理解的，除非你穿紅上衣&黑褲子來瘋狂暗示面試官，要不然被問到的概率還不太大。

三種結(jié)構(gòu)對比

從上面的對比可以看到：數(shù)組并不能很好滿足要求，鏈表在搜索過程又顯得更笨拙，平衡樹又有點復(fù)雜，到底該怎么辦?

跳表的雛形

上面的三類結(jié)構(gòu)都存在一些問題，所以要進(jìn)行改造，可以看到數(shù)組和平衡樹的某些特性決定了它們不容易被改造(數(shù)組內(nèi)存連續(xù)性、平衡樹節(jié)點多指針和層級關(guān)系)，相反鏈表最有潛力被改造優(yōu)化。

在有序鏈表中插入和刪除都比較簡單，搜索時無法依靠下標(biāo)只能遍歷，但是明明知道要走兩步可以到達(dá)目的地，偏偏只能一步步走，這就是痛點。

如圖演示了O(n)遍歷元素35和跳躍搜索元素35的過程：

貌似看到了曙光，那么如何實現(xiàn)跳躍呢?

沒錯!給鏈表加索引，讓索引告訴我們下一步該跳到哪里。

看到這里又讓我想起來那個經(jīng)典的中間層理論，遇到問題，試著加個中間層試試，或許就完美解決了。

跳躍鏈表的實現(xiàn)原理

前面說了可以給普通鏈表加索引來解決，但是具體該怎么操作，以及其中有什么難點?一步步來分析。

在工程中對跳表索引層數(shù)和結(jié)點是否作為索引結(jié)點，是其很重要的屬性，后面就詳細(xì)講一下，現(xiàn)在先看一種簡單場景，說明索引帶來的便利性。

簡單的索引

選擇每隔1個結(jié)點為索引結(jié)點，并且索引為一層，雖然在工程中這種形式比較標(biāo)準(zhǔn)化，不過足以說明索引帶來的加速。

可以將鏈表中的偶數(shù)序號節(jié)點增加一層指針，讓其指向下一個偶數(shù)節(jié)點，如圖所示：

搜索過程：

加入要搜索值為55的節(jié)點，則先在上層進(jìn)行搜索，由16跳到38，在38的下一跳將到達(dá)72，因此向下降一級繼續(xù)類似的搜索，則找到55。

多級索引

基于偶數(shù)節(jié)點增加索引并且只有兩層的情況下，最高層的節(jié)點數(shù)是n/2，整體來看搜索的復(fù)雜度降低為O(n/2)，并不要小看這個1/2的系數(shù)，看到這里會想 增加索引層數(shù)到k，那么復(fù)雜度將指數(shù)降低為O(n/2^k)。

索引層數(shù)不是無休止增加的，取決于該層索引的節(jié)點數(shù)量，如果該層的索引的節(jié)點數(shù)量等于2了，那么再往上加層也就沒有意義了，畫個圖看一下：

這個非常好理解，如果所在層索引結(jié)點只有1個，比如4層索引的結(jié)點16，只能順著16向下遍歷，無法向后跳到4層其他結(jié)點，因此當(dāng)所在層索引結(jié)點數(shù)量等于2，則到達(dá)最高索引層，這個約束在分析跳表復(fù)雜度時很重要。

索引層數(shù)和索引結(jié)點密度

跳表的復(fù)雜度和索引層數(shù)、索引結(jié)點的稀疏程度有很大關(guān)系。

索引層數(shù)我們從上面也看到了，稀疏程度相當(dāng)于索引結(jié)點的數(shù)量比例，如果跳表的索引結(jié)點數(shù)量很少，那么將接近退化為普通鏈表，這種情況在數(shù)據(jù)量是較大時非常明顯，畫圖看下(藍(lán)色部分表示有很多結(jié)點)：

圖中可以看到雖然有索引層，但是索引結(jié)點數(shù)量相對全部數(shù)據(jù)比例較低，這種情況下搜索35相比無索引情況優(yōu)勢并不明顯。

所以跳表的效率和索引層數(shù)和索引結(jié)點的密度有密切的關(guān)系，當(dāng)然索引結(jié)點太多也就等于沒有索引了。

太少的索引結(jié)點和太多的索引結(jié)點都是一樣的低效。

復(fù)雜度分析

從前面的分析可知，跳表的復(fù)雜度和索引層數(shù)m以及索引結(jié)點間隙d有直接關(guān)系，其中索引結(jié)點間隙理解為相隔幾個結(jié)點出現(xiàn)索引結(jié)點，體現(xiàn)了對應(yīng)層索引結(jié)點的稀疏程度，在無索引結(jié)點時只能遍歷無法跳躍。

如何確定最高索引層數(shù)m呢?

如果一個鏈表有 n 個結(jié)點，如果每兩個結(jié)點取出一個結(jié)點建立索引，那么第一級索引的結(jié)點數(shù)是 n/2，第二級索引的結(jié)點數(shù)是n/4，以此類推第 m 級索引的結(jié)點數(shù)為 n/(2^m)，前面說過最高層結(jié)點數(shù)為2，因此存在關(guān)系：

算上最底層的原始鏈表，整個跳表的高度為h=logn(底數(shù)為2)，每一層需要遍歷的結(jié)點數(shù)是d，那么整個過程的復(fù)雜度為:O(d*logn)。

d表明了層間結(jié)點的稀疏程度，也就是每隔2個結(jié)點選取索引結(jié)點、或者每隔3個結(jié)點選取索引結(jié)點，每個4個結(jié)點選取索引結(jié)點......

最密集的情況下d=2，借用知乎某大佬的文章的圖片：

但是索引結(jié)點密集也意味著存儲空間的增加，跳表相比較普通鏈表就是典型的用空間換時間的數(shù)據(jù)結(jié)構(gòu)，這樣就達(dá)到了AVL的復(fù)雜度O(logn)。

跳表的空間存儲

以d=2的最密集情況為例，計算跳表的索引結(jié)點總數(shù)：2+4+8+......n/8+n/4+n/2=n-2

由等比數(shù)列求和公式得d=2的跳表額外空間為O(n-2)。

跳表的插入和刪除

工程中的跳表并不嚴(yán)格要求索引層結(jié)點數(shù)量遵循2:1的關(guān)系，因為這種要求將導(dǎo)致插入和刪除數(shù)據(jù)時的調(diào)整，成本很大.

跳表的每個插入的結(jié)點在插入時進(jìn)行選擇是否作為索引結(jié)點，如果作為索引結(jié)點則隨機(jī)出層數(shù)，整個過程都是基于概率的，但是在大數(shù)據(jù)量時卻能很好地解決索引層數(shù)和結(jié)點數(shù)的權(quán)衡。

我們針對插入和刪除來看下基本的操作過程吧!

跳表元素17插入：

鏈表的插入和刪除是結(jié)合搜索過程完成的，貼一張William Pugh在論文中給出的在跳表中插入元素17的過程圖(暫時忽略結(jié)點17是否作為索引結(jié)點以及索引層數(shù)，后面會詳細(xì)說明)：

跳表元素1刪除：

跳表元素的刪除與普通鏈表相比增加了索引層的判斷，如果結(jié)點是非索引結(jié)點則正常處理，如果結(jié)點是索引結(jié)點那邊需要進(jìn)行索引層結(jié)點的處理。

跳躍鏈表的應(yīng)用

一般討論查找問題時首先想到的是平衡樹和哈希表，但是跳表這種數(shù)據(jù)結(jié)構(gòu)也非常犀利，性能和實現(xiàn)復(fù)雜度都可以和紅黑樹媲美，甚至某些場景由于紅黑樹，從1990年被發(fā)明目前廣泛應(yīng)用于多種場景中，包括Redis、LevelDB等數(shù)據(jù)存儲引擎中，后續(xù)將詳細(xì)介紹。

跳表在Redis中的應(yīng)用

ZSet結(jié)構(gòu)同時包含一個字典和一個跳躍表，跳躍表按score從小到大保存所有集合元素。字典保存著從member到score的映射。這兩種結(jié)構(gòu)通過指針共享相同元素的member和score，不會浪費額外內(nèi)存。

typedef struct zset { 
    dict *dict; 
    zskiplist *zsl; 
} zset; 

ZSet中的字典和跳表布局：

ZSet中跳表的實現(xiàn)細(xì)節(jié)

隨機(jī)層數(shù)的實現(xiàn)原理

跳表是一個概率型的數(shù)據(jù)結(jié)構(gòu)，元素的插入層數(shù)是隨機(jī)指定的。Willam Pugh在論文中描述了它的計算過程如下：指定節(jié)點最大層數(shù) MaxLevel，指定概率 p， 默認(rèn)層數(shù) lvl 為1

生成一個0~1的隨機(jī)數(shù)r，若r

重復(fù)第 2 步，直至生成的r >p 為止，此時的 lvl 就是要插入的層數(shù)。

論文中生成隨機(jī)層數(shù)的偽碼：

在Redis中對跳表的實現(xiàn)基本上也是遵循這個思想的，只不過有微小差異，看下Redis關(guān)于跳表層數(shù)的隨機(jī)源碼src/z_set.c：

/* 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; 
} 

其中兩個宏的定義在redis.h中：

#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */ 
#define ZSKIPLIST_P 0.25      /* Skiplist P = 1/4 */ 

可以看到while中的：

(random()&0xFFFF) < (ZSKIPLIST_P*0xFFFF) 

第一眼看到這個公式，因為涉及位運算有些詫異，需要研究一下Antirez為什么使用位運算來這么寫?

最開始的猜測是random()返回的是浮點數(shù)[0-1]，于是乎在線找了個浮點數(shù)轉(zhuǎn)二進(jìn)制的工具，輸入0.5看了下結(jié)果：

可以看到0.5的32bit轉(zhuǎn)換16進(jìn)制結(jié)果為0x3f000000，如果與0xFFFF做與運算結(jié)果還是0，不符合預(yù)期。

我印象中C語言的math庫好像并沒有直接random函數(shù)，所以就去Redis源碼中找找看，于是下載了3.2版本代碼，也并沒有找到random()的實現(xiàn)，不過找到了其他幾個地方的應(yīng)用：

random()在dict.c中的使用：

random()在cluster.c中的使用：

看到這里的取模運算，后知后覺地發(fā)現(xiàn)原以為random()是個[0-1]的浮點數(shù)，但是現(xiàn)在看來是uint32才對，這樣Antirez的式子就好理解了。

ZSKIPLIST_P*0xFFFF 

由于ZSKIPLIST_P=0.25，所以相當(dāng)于0xFFFF右移2位變?yōu)?x3FFF，假設(shè)random()比較均勻，在進(jìn)行0xFFFF高16位清零之后，低16位取值就落在0x0000-0xFFFF之間，這樣while為真的概率只有1/4，更一般地說為真的概率為1/ZSKIPLIST_P。

對于隨機(jī)層數(shù)的實現(xiàn)并不統(tǒng)一，重要的是隨機(jī)數(shù)的生成，在LevelDB中對跳表層數(shù)的生成代碼是這樣的：

template <typename Key, typename Value> 
int SkipList<Key, Value>::randomLevel() { 
 
  static const unsigned int kBranching = 4; 
  int height = 1; 
  while (height < kMaxLevel && ((::Next(rnd_) % kBranching) == 0)) { 
    height++; 
  } 
  assert(height > 0); 
  assert(height <= kMaxLevel); 
  return height; 
} 
 
uint32_t Next( uint32_t& seed) { 
  seed = seed & 0x7fffffffu; 
 
  if (seed == 0 || seed == 2147483647L) {  
    seed = 1; 
  } 
  static const uint32_t M = 2147483647L; 
  static const uint64_t A = 16807; 
  uint64_t product = seed * A; 
  seed = static_cast<uint32_t>((product >> 31) + (product & M)); 
  if (seed > M) { 
    seed -= M; 
  } 
  return seed; 
} 

可以看到leveldb使用隨機(jī)數(shù)與kBranching取模，如果值為0就增加一層，這樣雖然沒有使用浮點數(shù)，但是也實現(xiàn)了概率平衡。

跳表結(jié)點的平均層數(shù)

我們很容易看出，產(chǎn)生越高的節(jié)點層數(shù)出現(xiàn)概率越低，無論如何層數(shù)總是滿足冪次定律越大的數(shù)出現(xiàn)的概率越小。

如果某件事的發(fā)生頻率和它的某個屬性成冪關(guān)系，那么這個頻率就可以稱之為符合冪次定律。

冪次定律的表現(xiàn)是少數(shù)幾個事件的發(fā)生頻率占了整個發(fā)生頻率的大部分， 而其余的大多數(shù)事件只占整個發(fā)生頻率的一個小部分。

冪次定律應(yīng)用到跳表的隨機(jī)層數(shù)來說就是大部分的節(jié)點層數(shù)都是黃色部分，只有少數(shù)是綠色部分，并且概率很低。

定量的分析如下：

• 節(jié)點層數(shù)至少為1，大于1的節(jié)點層數(shù)滿足一個概率分布。
• 節(jié)點層數(shù)恰好等于1的概率為p^0(1-p)
• 節(jié)點層數(shù)恰好等于2的概率為p^1(1-p)
• 節(jié)點層數(shù)恰好等于3的概率為p^2(1-p)
• 節(jié)點層數(shù)恰好等于4的概率為p^3(1-p)
• 依次遞推節(jié)點層數(shù)恰好等于K的概率為p^(k-1)(1-p)

因此如果我們要求節(jié)點的平均層數(shù)，那么也就轉(zhuǎn)換成了求概率分布的期望問題了，靈魂畫手大白再次上線：

表中P為概率，V為對應(yīng)取值，給出了所有取值和概率的可能，因此就可以求這個概率分布的期望了。

方括號里面的式子其實就是高一年級學(xué)的等比數(shù)列，常用技巧錯位相減求和，從中可以看到結(jié)點層數(shù)的期望值與1-p成反比。

對于Redis而言，當(dāng)p=0.25時結(jié)點層數(shù)的期望是1.33。

在Redis源碼中有詳盡的關(guān)于插入和刪除調(diào)整跳表的過程，本文就不再展開了，代碼并不算難懂，都是純C寫的沒有那么多炫技的特效，放心大膽讀起來。

小結(jié)

本文主要講述了跳表的基本概念和簡單原理、以及索引結(jié)點層級、時間和空間復(fù)雜度等相關(guān)部分，并沒有涉及概率平衡以及工程實現(xiàn)部分，并且以Redis中底層的數(shù)據(jù)結(jié)構(gòu)zset作為典型應(yīng)用來展開，進(jìn)一步看到跳躍鏈表的實際應(yīng)用。

需要注意的是跳躍鏈表的原理、應(yīng)用、實現(xiàn)細(xì)節(jié)也是面試的熱點問題，值得大家花費時間來研究掌握。