大家想必都知道，數(shù)組和鏈表的搜索操作的時(shí)間復(fù)雜度都是O(N)的，在數(shù)據(jù)量大的時(shí)候是非常耗時(shí)的。對(duì)于數(shù)組來(lái)說(shuō)，我們可以先排序，然后使用二分搜索，就能夠?qū)r(shí)間復(fù)雜度降低到O(logN)，但是有序數(shù)組的插入是一個(gè)O(N)級(jí)別的操作。而鏈表的插入性能相對(duì)優(yōu)秀，卻不能使用二分搜索快速查詢。那么是否有一種數(shù)據(jù)結(jié)構(gòu)，即能夠像鏈表一樣快速插入數(shù)據(jù)，又支持類似于二分搜索這樣的查詢算法呢？答案是肯定的。William Pugh教授在1990發(fā)表的論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》中提出的跳表就是這樣一種有趣的數(shù)據(jù)結(jié)構(gòu)。

跳表的結(jié)構(gòu)

跳表的核心思想是通過(guò)建立索引層來(lái)縮短鏈表的搜索路徑，以達(dá)到快速搜索的目的。
假設(shè)我們從鏈表中的每?jī)蓚€(gè)節(jié)點(diǎn)中提取出一個(gè)建立一級(jí)索引，然后再?gòu)拿績(jī)蓚€(gè)一級(jí)索引中提取一個(gè)建立二級(jí)索引，以此類推，就可以得到如下圖所示的結(jié)構(gòu)，其中綠色節(jié)點(diǎn)表示索引。

在William Pugh的論文中使用了數(shù)組加鏈表的組合來(lái)實(shí)現(xiàn)跳表，就如上圖所示，每一列索引具有相同的key，使用一個(gè)數(shù)組來(lái)表示。還可以使用純鏈表的形式來(lái)實(shí)現(xiàn)跳表，我覺(jué)得這種方式更有助于理解跳表的原理，如下圖所示。

跳表的搜索

跳表的搜索需要從高層索引開(kāi)始向下逐層搜索，每一層的搜索方式和普通鏈表是一樣的，當(dāng)后繼節(jié)點(diǎn)的關(guān)鍵字大于搜索關(guān)鍵字時(shí)結(jié)束本層的搜索，進(jìn)入下一層繼續(xù)搜索。下圖展示了跳表搜索關(guān)鍵字 22 的過(guò)程，其中紅色部分就是搜索的路徑。

從上圖可以很直觀的看出，跳表的搜索和二分搜索是一樣的，其時(shí)間復(fù)雜度也是O(logN)的，我們不妨簡(jiǎn)單證明一下。
假設(shè)跳表中有N個(gè)數(shù)據(jù)節(jié)點(diǎn)（關(guān)鍵字），每m個(gè)低級(jí)索引（或數(shù)據(jù)節(jié)點(diǎn)）中提取出一個(gè)作為高級(jí)索引，那么
一級(jí)索引的數(shù)量
二級(jí)索引的數(shù)量
三級(jí)索引的數(shù)量
以此類推，第i級(jí)索引的數(shù)量
最高級(jí)索引的數(shù)量
所以索引的最大層級(jí)
每一層的搜索次數(shù)
所以跳表的搜索次數(shù)
因?yàn)閙是一個(gè)常量，因此跳表的搜索時(shí)間復(fù)雜度是O(logN)的

跳表的多層索引結(jié)構(gòu)使它的搜索方式非常靈活且強(qiáng)大
比如我們可能有這樣的需求，如果key不存在，我們需要知道這個(gè)key鄰近的nearKey是什么，這用跳表很容易實(shí)現(xiàn)

搜索比key小且最接近key的關(guān)鍵字lowerKey，如上圖所示，后繼節(jié)點(diǎn)大于等于key時(shí)，直接返回當(dāng)前節(jié)點(diǎn)即可

搜索比key大且最接近key的關(guān)鍵字higherKey，如上圖所示，后繼節(jié)點(diǎn)大于key時(shí)，直接返回后繼節(jié)點(diǎn)即可

跳表還可以很容易的搜索一個(gè)關(guān)鍵字區(qū)間[fromKey, toKey]，這點(diǎn)和B+樹很類似，先搜索fromKey，然后向后遍歷鏈表，取出所有小于等于toKey的數(shù)據(jù)即可

跳表的插入

到現(xiàn)在為止，本文描述的都是理想狀態(tài)下的跳表，事實(shí)上，我們不會(huì)嚴(yán)格的為跳表的每m個(gè)低級(jí)索引建立高級(jí)索引，因?yàn)檫@樣做復(fù)雜而且低效。所以William Pugh在他的論文中采用一種隨機(jī)算法來(lái)為每個(gè)新增的節(jié)點(diǎn)隨機(jī)建立索引，下面是我用Java實(shí)現(xiàn)的版本。

int randomLevel(int m, int maxLevel) {ThreadLocalRandom r = ThreadLocalRandom.current();int level = 1;while (r.nextInt(m) == 0 && level < maxLevel)level++;return level; } 復(fù)制代碼

通過(guò)這種隨機(jī)算法，生成第i級(jí)索引的概率為
所以能夠保證每一層索引的數(shù)量都接近于 ，這正好符合我們前面提到的索引層的性質(zhì)。
Doug Lea大佬在Java的ConcurrentSkipListMap中使用了另外一種更加炫酷的隨機(jī)算法的實(shí)現(xiàn)方式，使用隨機(jī)數(shù)末尾連續(xù)為1的位數(shù)作為索引的等級(jí)，顯然這種方式生成第i級(jí)索引的概率為 ，代碼如下所示。

int rn = ThreadLocalRandom.current().nextInt(); // 只有最高位和最低位都為0時(shí)，才建立索引，相當(dāng)于為4個(gè)node建立一個(gè)索引 if ((rn & 0x80000001) == 0) {int level = 1;// 建立索引的等級(jí)等于rn末尾連續(xù)為1的位數(shù)while (((rn >>>= 1) & 1) != 0)level++; } 復(fù)制代碼

通過(guò)隨機(jī)函數(shù)生成一個(gè)隨機(jī)的索引等級(jí)之后，創(chuàng)建一個(gè)新的索引列，并將每一層的新索引鏈接到它的前驅(qū)索引的后面，如果生成的隨機(jī)等級(jí)大于當(dāng)前跳表的最大索引等級(jí)，需要添加一層新的索引。如下圖所示，其中紅色虛線箭頭表示重新建立的鏈接。

跳表的刪除

跳表的刪除操作比較簡(jiǎn)單，先查詢刪除的關(guān)鍵字，如果在索引層匹配到了關(guān)鍵字，就向下刪除所有的索引和數(shù)據(jù)節(jié)點(diǎn)，如果沒(méi)有匹配到索引，只需要?jiǎng)h除數(shù)據(jù)節(jié)點(diǎn)即可。其中有一點(diǎn)需要注意的是，在刪除索引后需要檢測(cè)一下，如果當(dāng)前層的HEAD索引的后繼索引為NIL，則表示這一層已經(jīng)沒(méi)有索引了，需要?jiǎng)h除這個(gè)索引層。如下圖所示，紅色箭頭表示重新建立的鏈接。

跳表的實(shí)現(xiàn)

跳表的實(shí)現(xiàn)相對(duì)AVL樹、紅黑樹等平衡二叉樹來(lái)說(shuō)簡(jiǎn)單了很多，William Pugh的論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》中提供了使用數(shù)組加鏈表實(shí)現(xiàn)跳表的偽代碼，我寫了一個(gè)Java版本的純鏈表實(shí)現(xiàn)的跳表，并上傳到了我的GitHub上，有興趣的朋友可以看一下。如果你需要在開(kāi)發(fā)中使用跳表的話，java.util.concurrent.ConcurrentSkipListMap是一個(gè)強(qiáng)大的實(shí)現(xiàn)，而且它還是線程安全的。

轉(zhuǎn)載于:https://juejin.im/post/5cdc38236fb9a0322d04ac7b

總結(jié)

以上是生活随笔為你收集整理的数据结构进阶篇-跳表的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。