摘要：跳表分析通過上面的理解，你應(yīng)該知道了跳表，其實(shí)就是通過建立多級(jí)索引來提升查找效率的一種數(shù)據(jù)結(jié)構(gòu)。一般的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)都會(huì)維持平衡，保證插入查詢操作的性能不會(huì)下降。例如在中已經(jīng)有跳表的兩個(gè)實(shí)現(xiàn)類，分別是和，并且是線程安全的。

1. 概述

前面說到了二分查找，并且它是基于順序表結(jié)構(gòu)的，即數(shù)組，如果直接用于鏈表，時(shí)間復(fù)雜度會(huì)比較的高，是 O(logn)，一般我們不會(huì)這樣做。那么有沒有基于鏈表的二分查找呢？答案就是今天說到的跳躍鏈表。

2. 跳表長(zhǎng)什么樣子？

對(duì)于一般的鏈表，我們進(jìn)行查找的話，需要遍歷整個(gè)鏈表，就像下面這樣：如果我們要找節(jié)點(diǎn) 9 ，需要遍歷 9 個(gè)節(jié)點(diǎn)。

如果我們?cè)谠兼湵碇辖⒁患?jí)鏈表，會(huì)是什么樣子呢？如下圖：

新建立的一級(jí)鏈表，我們叫做索引層或是索引，那么建立了一級(jí)索引之后，再來查找節(jié)點(diǎn) 9，會(huì)遍歷多少節(jié)點(diǎn)呢？我們從第一級(jí)索引中開始查找，到了節(jié)點(diǎn) 9 的時(shí)候，通過向下的指針，可以找到節(jié)點(diǎn) 9，總共遍歷了 6 個(gè)節(jié)點(diǎn)，相比沒有索引，查找的效率提高了。

這樣效果其實(shí)還不是非常的明顯，如果我們?cè)偌由蠋准?jí)索引，查找會(huì)不會(huì)更快呢？

如上圖，總共建立了三級(jí)索引，現(xiàn)在查找節(jié)點(diǎn) 9 ，只需要遍歷 5 個(gè)節(jié)點(diǎn)了，查找的效率再一步提升了。其實(shí)，上面我舉的例子，總共只有 10 個(gè)節(jié)點(diǎn)，所以看不出來性能有多大的提升，但是在實(shí)際的開發(fā)中，存儲(chǔ)的數(shù)據(jù)成千上萬，那么跳表的效率就更能體現(xiàn)了。

3. 跳表分析

通過上面的理解，你應(yīng)該知道了跳表，其實(shí)就是通過建立多級(jí)索引來提升查找效率的一種數(shù)據(jù)結(jié)構(gòu)。跳表的查詢時(shí)間復(fù)雜度是 O(logn)，跟二分查找一樣，空間復(fù)雜度是 O(n)，因?yàn)槊恳患?jí)建立的索引的節(jié)點(diǎn)個(gè)數(shù)都是上一級(jí)的一半，總共加起來就還需要原始鏈表的空間大小。
綜合分析，其實(shí)你已經(jīng)不能看到，跳表其實(shí)利用的是空間換時(shí)間的思想。

其實(shí)跳表不只是能夠在 O(logn) 內(nèi)查詢數(shù)據(jù)，并且也可以高效的插入和刪除數(shù)據(jù)，時(shí)間復(fù)雜度還是 O(logn)。

刪除操作其實(shí)很簡(jiǎn)單，找到之后直接刪除節(jié)點(diǎn)即可。
插入操作也類似，因?yàn)檎麄€(gè)鏈表是有序的，所以查找之后，直接插入。只不過這里涉及到一個(gè)動(dòng)態(tài)更新的問題。一般的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)都會(huì)維持平衡，保證插入查詢操作的性能不會(huì)下降。
例如跳表，假如沒有動(dòng)態(tài)更新，則可能會(huì)出現(xiàn)插入之后，鏈表節(jié)點(diǎn)特別集中的問題：

在極端的情況下，跳表還是會(huì)退化為鏈表。
所以跳表借助了隨機(jī)函數(shù)這種方式來維持整個(gè)索引的平衡性，每插入一個(gè)節(jié)點(diǎn)，都會(huì)生成一個(gè)隨機(jī)函數(shù) k，然后不僅是在原始鏈表中插入這個(gè)節(jié)點(diǎn)，還會(huì)在 1-k 層索引中插入這個(gè)節(jié)點(diǎn)。

4. 跳表實(shí)現(xiàn)

跳表的具體實(shí)現(xiàn)其實(shí)還是比較復(fù)雜的，代碼理解起來比較的困難，這里我就不貼出來了，大家有興趣的可以到我的 Github 上面參考借鑒。點(diǎn)擊進(jìn)入我的 Github

只不過我們也不用死扣跳表的代碼實(shí)現(xiàn)，在實(shí)際的開發(fā)環(huán)境中，我們能夠利用已有的實(shí)現(xiàn)就很不錯(cuò)了，這就是避免重復(fù)造輪子。例如在 Java 中已經(jīng)有跳表的兩個(gè)實(shí)現(xiàn)類，分別是 ConcurrentSkipListSet 和 ConcurrentSkipListMap，并且是線程安全的。