[[434690]]

跳表這一數(shù)據(jù)結(jié)構(gòu)，已經(jīng)成為了Redis面試的高頻考點(diǎn)。前兩年沒這么卷的時(shí)候，可能大家從開始學(xué)習(xí)，到拿到大廠offer這一過程，都可能沒聽說過跳表這一數(shù)據(jù)結(jié)構(gòu)。

那什么是跳表呢?它是用來干啥的?AVL樹紅黑樹知道吧，對(duì)，跳表跟他干的事情差不多。我舉個(gè)例子大家就明白了。假設(shè)目前有一個(gè)有序數(shù)列：

[2, 11，22, 33, 44, 52, 63] 

我們想基于單鏈表的思想，設(shè)計(jì)一個(gè)數(shù)據(jù)結(jié)構(gòu)，實(shí)現(xiàn)查找時(shí)間復(fù)雜度為O(logn)。單鏈表的話，它的結(jié)構(gòu)長這個(gè)樣子。

跳表1

當(dāng)然這個(gè)結(jié)構(gòu)，查找時(shí)間復(fù)雜度妥妥的O(n)，那咋改呢?

那換個(gè)問法：一般做算法題，手撕代碼面試的時(shí)候，當(dāng)咱寫了個(gè)時(shí)間復(fù)雜度為O(n)的解法，面試官搖搖頭，問你有沒有更好的方法，你會(huì)怎么做?

常見復(fù)雜度O(nlogn) O(n) O(logn) O(1)，要優(yōu)化，一步步來的話，只能上O(logn)了，那復(fù)雜度logn最常見的算法是哪個(gè)?當(dāng)然是二分!

思路對(duì)了，那對(duì)著鏈表，咋把二分思想融合進(jìn)去呢?

要不單鏈表指針這邊動(dòng)動(dòng)刀子?讓指針除了指向后面元素，還能越過幾個(gè)節(jié)點(diǎn)，指向更后面元素?類似二叉查找樹?先來看看這個(gè)數(shù)組對(duì)應(yīng)的二叉查找樹長什么樣。

跳表2

當(dāng)然，由于我們的結(jié)構(gòu)是單鏈表，所以只能有由小值，指向大值，這個(gè)二叉樹得改改。

跳表2

好像有點(diǎn)意思在里面了，再把原先單鏈表的性質(zhì)加上。

跳表2

走線有點(diǎn)凌亂，按單鏈表的布局顯示方式改改：(值得注意的是，我們需要新建一個(gè)數(shù)組項(xiàng)，每個(gè)數(shù)組項(xiàng)存儲(chǔ)一個(gè)指針，指向剛剛二叉搜索樹每一層最左側(cè)的節(jié)點(diǎn))

(咋感覺越看越像B+樹了(霧))

來看個(gè)查找邏輯吧：

當(dāng)查找到的結(jié)點(diǎn)保存的數(shù)，比要查找的數(shù)小時(shí)，跳表就會(huì)繼續(xù)訪問該層上的下一個(gè)結(jié)點(diǎn)。

當(dāng)不滿足時(shí)，跳表就會(huì)用到當(dāng)前查找到的結(jié)點(diǎn)的指針數(shù)組的下一層指針，然后沿著下一層指針繼續(xù)查找。

對(duì)于這種數(shù)據(jù)結(jié)構(gòu)，我們需要從上往下依次查詢?nèi)齻€(gè)鏈表，比如我們想查大于35的數(shù)字。

首先按左側(cè)數(shù)組第一個(gè)找，發(fā)現(xiàn)中間節(jié)點(diǎn)是33，比較一下比35小。

發(fā)現(xiàn)33比35小，跳下一個(gè)節(jié)點(diǎn)。

發(fā)現(xiàn)該節(jié)點(diǎn)是Null，跳33的下一層節(jié)點(diǎn)。

發(fā)現(xiàn)52比35大，再跳下一層節(jié)點(diǎn)。

發(fā)現(xiàn)44比35大，跳下一層節(jié)點(diǎn)，但由于這是最后一層節(jié)點(diǎn)，即44是第一個(gè)比33大的數(shù)，滿足最終條件，就找到了第一個(gè)比35大的數(shù)字。

我們知道，二叉平衡樹，如果設(shè)計(jì)插入操作，會(huì)特別特別麻煩。對(duì)于由二叉平衡樹思想改的跳表也是如此，對(duì)于我們這邊的情況，每增加，或者減少一個(gè)新節(jié)點(diǎn)，每個(gè)節(jié)點(diǎn)的高度都需要變化。。那有沒有高人改進(jìn)呢?

既然把二叉平衡樹改成這四不像了，為啥再不改改，能不能讓他不平衡的同時(shí)，還能保證查找效率?

說實(shí)話，還真可以，來看看這種跳表。

跳表1

雖然這個(gè)跳表跟咱剛剛講的跳表比起來，奇形怪狀的，但按剛剛的查找思路，還是能做比較好的查詢工作的。

而且既然表都長這么奇形怪狀了，那添加或者刪新元素，其他節(jié)點(diǎn)高度不變問題也不大了。

而且驚人的是，如果我們對(duì)新插入節(jié)點(diǎn)的高度進(jìn)行隨機(jī)產(chǎn)生(每次隨機(jī)大于p，接著往上加高度，小于p停下來)，然后別的節(jié)點(diǎn)高度保持不變，查找效率還是為O(logn)，不會(huì)出現(xiàn)像二叉查找樹那種直接退化成O(logn)的情況。

有興趣想看推導(dǎo)的同學(xué)點(diǎn)個(gè)贊，點(diǎn)贊破100，咱寫波推導(dǎo)。(目前面試還沒卷到要證明跳表時(shí)間復(fù)雜度的程度，所以不知道咋推沒問題)