跳表是一種數(shù)據(jù)結(jié)構(gòu)。它使得包含n個元素的有序序列的查找和插入操作的平均時間復(fù)雜度都是 O(logn)，優(yōu)于數(shù)組的 O(n)復(fù)雜度。快速的查詢效果是通過維護(hù)一個多層次的鏈表實(shí)現(xiàn)的，且與前一層（下面一層）鏈表元素的數(shù)量相比，每一層鏈表中的元素的數(shù)量更少。

一、什么是跳表？？

跳表全稱為跳躍列表，它允許快速查詢，插入和刪除一個有序連續(xù)元素的數(shù)據(jù)鏈表。跳躍列表的平均查找和插入時間復(fù)雜度都是O(logn)。快速查詢是通過維護(hù)一個多層次的鏈表，且每一層鏈表中的元素是前一層鏈表元素的子集（見右邊的示意圖）。一開始時，算法在最稀疏的層次進(jìn)行搜索，直至需要查找的元素在該層兩個相鄰的元素中間。這時，算法將跳轉(zhuǎn)到下一個層次，重復(fù)剛才的搜索，直到找到需要查找的元素為止。

一張?zhí)S列表的示意圖。每個帶有箭頭的框表示一個指針, 而每行是一個稀疏子序列的鏈表；底部的編號框（黃色）表示有序的數(shù)據(jù)序列。查找從頂部最稀疏的子序列向下進(jìn)行, 直至需要查找的元素在該層兩個相鄰的元素中間。

二、跳表的演化過程

對于單鏈表來說，即使數(shù)據(jù)是已經(jīng)排好序的，想要查詢其中的一個數(shù)據(jù)，只能從頭開始遍歷鏈表，這樣效率很低，時間復(fù)雜度很高，是 O(n)。

那我們有沒有什么辦法來提高查詢的效率呢？我們可以為鏈表建立一個“索引”，這樣查找起來就會更快，如下圖所示，我們在原始鏈表的基礎(chǔ)上，每兩個結(jié)點(diǎn)提取一個結(jié)點(diǎn)建立索引，我們把抽取出來的結(jié)點(diǎn)叫做索引層或者索引，down 表示指向原始鏈表結(jié)點(diǎn)的指針。

現(xiàn)在如果我們想查找一個數(shù)據(jù)，比如說 15，我們首先在索引層遍歷，當(dāng)我們遍歷到索引層中值為 14 的結(jié)點(diǎn)時，我們發(fā)現(xiàn)下一個結(jié)點(diǎn)的值為 17，所以我們要找的 15 肯定在這兩個結(jié)點(diǎn)之間。這時我們就通過 14 結(jié)點(diǎn)的 down 指針，回到原始鏈表，然后繼續(xù)遍歷，這個時候我們只需要再遍歷兩個結(jié)點(diǎn)，就能找到我們想要的數(shù)據(jù)。好我們從頭看一下，整個過程我們一共遍歷了 7 個結(jié)點(diǎn)就找到我們想要的值，如果沒有建立索引層，而是用原始鏈表的話，我們需要遍歷 10 個結(jié)點(diǎn)。

通過這個例子我們可以看出來，通過建立一個索引層，我們查找一個基點(diǎn)需要遍歷的次數(shù)變少了，也就是查詢的效率提高了。

那么如果我們給索引層再加一層索引呢？遍歷的結(jié)點(diǎn)會不會更少呢，效率會不會更高呢？我們試試就知道了。

現(xiàn)在我們再來查找 15，我們從第二級索引開始，最后找到 15，一共遍歷了 6 個結(jié)點(diǎn)，果然效率更高。

當(dāng)然，因?yàn)槲覀兣e的這個例子數(shù)據(jù)量很小，所以效率提升的不是特別明顯，如果數(shù)據(jù)量非常大的時候，我們多建立幾層索引，效率提升的將會非常的明顯，感興趣的可以自己試一下，這里我們就不舉例子了。

這種通過對鏈表加多級索引的機(jī)構(gòu)，就是跳表了。

三、跳表具體有多快

通過上邊的例子我們知道，跳表的查詢效率比鏈表高，那具體高多少呢？下面我們一起來看一下。

衡量一個算法的效率我們可以用時間復(fù)雜度，這里我們也用時間復(fù)雜度來比較一下鏈表和跳表。前面我們已經(jīng)講過了，鏈表的查詢的時間復(fù)雜度為 O(n)，那跳表的呢？

如果一個鏈表有 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)。

假如一共有 m 級索引，第 m 級的結(jié)點(diǎn)數(shù)為兩個，通過上邊我們找到的規(guī)律，那么得出 n/(2^m)=2，從而求得 m=log(n)-1。如果加上原始鏈表，那么整個跳表的高度就是 log(n)。我們在查詢跳表的時候，如果每一層都需要遍歷 k 個結(jié)點(diǎn)，那么最終的時間復(fù)雜度就為 O(k*log(n))。

那這個 k 值為多少呢，按照我們每兩個結(jié)點(diǎn)提取一個基點(diǎn)建立索引的情況，我們每一級最多需要遍歷兩個個結(jié)點(diǎn)，所以 k=2。為什么每一層最多遍歷兩個結(jié)點(diǎn)呢？

因?yàn)槲覀兪敲績蓚€結(jié)點(diǎn)提取一個結(jié)點(diǎn)建立索引，最高一級索引只有兩個結(jié)點(diǎn)，然后下一層索引比上一層索引兩個結(jié)點(diǎn)之間增加了一個結(jié)點(diǎn)，也就是上一層索引兩結(jié)點(diǎn)的中值，看到這里是不是想起來我們前邊講過的二分查找，每次我們只需要判斷要找的值在不在當(dāng)前結(jié)點(diǎn)和下一個結(jié)點(diǎn)之間即可。

如上圖所示，我們要查詢紅色結(jié)點(diǎn)，我們查詢的路線即黃線表示出的路徑查詢，每一級最多遍歷兩個結(jié)點(diǎn)即可。

所以跳表的查詢?nèi)我鈹?shù)據(jù)的時間復(fù)雜度為 O(2*log(n))，前邊的常數(shù) 2 可以忽略，為 O(log(n))。

四、跳表是用空間來換時間

跳表的效率比鏈表高了，但是跳表需要額外存儲多級索引，所以需要的更多的內(nèi)存空間。

跳表的空間復(fù)雜度分析并不難，如果一個鏈表有 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)，我們可以看出來這是一個等比數(shù)列。

這幾級索引的結(jié)點(diǎn)總和就是 n/2+n/4+n/8…+8+4+2=n-2，所以跳表的空間復(fù)雜度為 o(n)。

那么我們有沒有辦法減少索引所占的內(nèi)存空間呢？可以的，我們可以每三個結(jié)點(diǎn)抽取一個索引，或者沒五個結(jié)點(diǎn)抽取一個索引。這樣索引結(jié)點(diǎn)的數(shù)量減少了，所占的空間也就少了。

五、跳表的插入和刪除

我們想要為跳表插入或者刪除數(shù)據(jù)，我們首先需要找到插入或者刪除的位置，然后執(zhí)行插入或刪除操作，前邊我們已經(jīng)知道了，跳表的查詢的時間復(fù)雜度為 O(logn），因?yàn)檎业轿恢弥蟛迦牒蛣h除的時間復(fù)雜度很低，為 O(1)，所以最終插入和刪除的時間復(fù)雜度也為 O(longn)。

我么通過圖看一下插入的過程。

刪除操作的話，如果這個結(jié)點(diǎn)在索引中也有出現(xiàn)，我們除了要刪除原始鏈表中的結(jié)點(diǎn)，還要刪除索引中的。因?yàn)閱捂湵碇械膭h除操作需要拿到要刪除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，然后通過指針操作完成刪除。所以在查找要刪除的結(jié)點(diǎn)的時候，一定要獲取前驅(qū)結(jié)點(diǎn)。當(dāng)然，如果我們用的是雙向鏈表，就不需要考慮這個問題了。

如果我們不停的向跳表中插入元素，就可能會造成兩個索引點(diǎn)之間的結(jié)點(diǎn)過多的情況。結(jié)點(diǎn)過多的話，我們建立索引的優(yōu)勢也就沒有了。所以我們需要維護(hù)索引與原始鏈表的大小平衡，也就是結(jié)點(diǎn)增多了，索引也相應(yīng)增加，避免出現(xiàn)兩個索引之間結(jié)點(diǎn)過多的情況，查找效率降低。

跳表是通過一個隨機(jī)函數(shù)來維護(hù)這個平衡的，當(dāng)我們向跳表中插入數(shù)據(jù)的的時候，我們可以選擇同時把這個數(shù)據(jù)插入到索引里，那我們插入到哪一級的索引呢，這就需要隨機(jī)函數(shù)，來決定我們插入到哪一級的索引中。

這樣可以很有效的防止跳表退化，而造成效率變低。