跳躍鏈表及其應(yīng)用是非常熱門的問題，面試時也非常常問，深入了解其中奧秘大有裨益，不吹了，直接開始！

跳躍鏈表的基本概念

初識跳表

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

跳躍列表由威廉·普發(fā)明，發(fā)明者對跳躍列表的評價：跳躍鏈表是在很多應(yīng)用中有可能替代平衡樹而作為實(shí)現(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)，這里就不展開講紅黑樹了，看來跳表也是類似的路子，但是是基于概率實(shí)現(xiàn)的。

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

所謂動態(tài)查找就是查找的過程中存在元素的刪除和插入，這樣就對實(shí)現(xiàn)查找的數(shù)據(jù)結(jié)構(gòu)有一定的挑戰(zhàn)，因?yàn)樵诿看蝿h除和插入時都要調(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ù)，可以實(shí)現(xiàn)二分查找等基于下標(biāo)的操作，我一直認(rèn)為數(shù)組的殺手锏就是下標(biāo)，連續(xù)的內(nèi)存也帶來了問題。

當(dāng)進(jìn)行插入和刪除時就面臨著整體的調(diào)整，就像在火車站排隊(duì)買票，隊(duì)頭走一個整個隊(duì)伍向前挪一步，有加塞的后面的又整體向后挪一步，這種整體移動操作在數(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í)行刪除和插入時影響的只是插入刪除點(diǎn)的前后元素，影響非常小。

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

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

平衡樹

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

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

紅黑樹的節(jié)點(diǎn)結(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ù)組并不能很好滿足要求，鏈表在搜索過程又顯得更笨拙，平衡樹又有點(diǎn)復(fù)雜，到底該怎么辦？

跳表的雛形

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

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

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

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

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

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

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

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

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

簡單的索引

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

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

搜索過程：

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

多級索引

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

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

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

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

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

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

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

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

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

復(fù)雜度分析

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

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

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

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

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

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

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

跳表的空間存儲

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

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

跳表的插入和刪除

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

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

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

跳表元素17插入：

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

跳表元素1刪除：

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

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

一般討論查找問題時首先想到的是平衡樹和哈希表，但是跳表這種數(shù)據(jù)結(jié)構(gòu)也非常犀利，性能和實(shí)現(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，不會浪費(fèi)額外內(nèi)存。

typedef struct zset {

dict *dict;

zskiplist *zsl;

} zset;

ZSet中的字典和跳表布局：

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

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

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

生成一個0~1的隨機(jī)數(shù)r，若r《p，且lvl《MaxLevel ，則lvl ++

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

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

在Redis中對跳表的實(shí)現(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）

第一眼看到這個公式，因?yàn)樯婕拔贿\(yùn)算有些詫異，需要研究一下Antirez為什么使用位運(yùn)算來這么寫？

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

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

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

random（）在dict.c中的使用：

random（）在cluster.c中的使用：

看到這里的取模運(yùn)算，后知后覺地發(fā)現(xiàn)原以為random（）是個［0-1］的浮點(diǎn)數(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ù)的實(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就增加一層，這樣雖然沒有使用浮點(diǎn)數(shù)，但是也實(shí)現(xiàn)了概率平衡。

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

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

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

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

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

定量的分析如下：

節(jié)點(diǎn)層數(shù)至少為1，大于1的節(jié)點(diǎn)層數(shù)滿足一個概率分布。

節(jié)點(diǎn)層數(shù)恰好等于1的概率為p^0（1-p）

節(jié)點(diǎn)層數(shù)恰好等于2的概率為p^1（1-p）

節(jié)點(diǎn)層數(shù)恰好等于3的概率為p^2（1-p）

節(jié)點(diǎn)層數(shù)恰好等于4的概率為p^3（1-p）

依次遞推節(jié)點(diǎn)層數(shù)恰好等于K的概率為p^（k-1）（1-p）

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

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

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

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

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

小結(jié)

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

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

責(zé)任編輯：haq