跳表的基本概念和實(shí)際應(yīng)用

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

跳躍鏈表的基本概念

初識(shí)跳表

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

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

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

這種數(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

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

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

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

所謂動(dòng)態(tài)查找就是查找的過(guò)程中存在元素的刪除和插入，這樣就對(duì)實(shí)現(xiàn)查找的數(shù)據(jù)結(jié)構(gòu)有一定的挑戰(zhàn)，因?yàn)樵诿看蝿h除和插入時(shí)都要調(diào)整數(shù)據(jù)結(jié)構(gòu)，來(lái)保持秩序。

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

線性結(jié)構(gòu)：數(shù)組、鏈表

非線性結(jié)構(gòu)：平衡樹(shù)

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

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

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

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

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

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

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

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

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

平衡樹(shù)

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

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

紅黑樹(shù)的節(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;

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

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

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

跳表的雛形

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

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

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

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

沒(méi)錯(cuò)！給鏈表加索引，讓索引告訴我們下一步該跳到哪里。

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

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

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

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

簡(jiǎn)單的索引

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

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

搜索過(guò)程：

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

多級(jí)索引

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

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

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

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

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

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

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

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

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

復(fù)雜度分析

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

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

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

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

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

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

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

跳表的空間存儲(chǔ)

以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ù)時(shí)的調(diào)整，成本很大。

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

我們針對(duì)插入和刪除來(lái)看下基本的操作過(guò)程吧！

跳表元素17插入：

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

跳表元素1刪除：

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

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

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

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

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

typedef struct zset {

dict *dict;

zskiplist *zsl;

} zset;

ZSet中的字典和跳表布局：

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

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

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

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

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

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

在Redis中對(duì)跳表的實(shí)現(xiàn)基本上也是遵循這個(gè)思想的，只不過(guò)有微小差異，看下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;

}

其中兩個(gè)宏的定義在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）

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

最開(kāi)始的猜測(cè)是random（）返回的是浮點(diǎn)數(shù)［0-1］，于是乎在線找了個(gè)浮點(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語(yǔ)言的math庫(kù)好像并沒(méi)有直接random函數(shù)，所以就去Redis源碼中找找看，于是下載了3.2版本代碼，也并沒(méi)有找到random（）的實(shí)現(xiàn)，不過(guò)找到了其他幾個(gè)地方的應(yīng)用：

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

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

看到這里的取模運(yùn)算，后知后覺(jué)地發(fā)現(xiàn)原以為random（）是個(gè)［0-1］的浮點(diǎn)數(shù)，但是現(xiàn)在看來(lái)是uint32才對(duì)，這樣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，更一般地說(shuō)為真的概率為1/ZSKIPLIST_P。

對(duì)于隨機(jī)層數(shù)的實(shí)現(xiàn)并不統(tǒng)一，重要的是隨機(jī)數(shù)的生成，在LevelDB中對(duì)跳表層數(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就增加一層，這樣雖然沒(méi)有使用浮點(diǎn)數(shù)，但是也實(shí)現(xiàn)了概率平衡。

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

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

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

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

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

定量的分析如下：

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

節(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)換成了求概率分布的期望問(wèn)題了，靈魂畫手的我再次上線：

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

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

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

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

小結(jié)

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

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

責(zé)任編輯：haq