前言

跳表是面試常問(wèn)的一種數(shù)據(jù)結(jié)構(gòu)，它在很多中間件和語(yǔ)言中得到應(yīng)用,，我們熟知的就有Redis跳表,。并且在面試的很多場(chǎng)景可能會(huì)問(wèn)到，偶爾還會(huì)讓你手寫(xiě)試一試(跳表可能會(huì)讓手寫(xiě),，紅黑樹(shù)是不可能的),，這不，給大伙復(fù)原一個(gè)場(chǎng)景

但你別慌,，遇到蘑菇頭這種面試官也別怕,，因?yàn)槟憧吹竭@篇文章了(得意

對(duì)于一個(gè)數(shù)據(jù)結(jié)構(gòu)或算法,，人群數(shù)量從聽(tīng)過(guò)名稱(chēng),、了解基本原理、清楚執(zhí)行流程,、能夠手寫(xiě) 呈抖降的趨勢(shì),。因?yàn)楹芏鄶?shù)據(jù)結(jié)構(gòu)與算法其核心原理可能簡(jiǎn)單，但清楚其執(zhí)行流程就需要?jiǎng)幽X子去思考想明白,，但是如果能夠把它寫(xiě)出來(lái),，那就要自己一步步去設(shè)計(jì)和實(shí)現(xiàn)?？赡芤ê芫貌拍苷嬲龑?xiě)出來(lái),，并且還可能要查閱大量的資料。

而本文在前面進(jìn)行介紹跳表,，后面部分詳細(xì)介紹跳表的設(shè)計(jì)和實(shí)現(xiàn),，搞懂跳表，這一篇真的就夠了。

快速了解跳表

跳躍表(簡(jiǎn)稱(chēng)跳表)由美國(guó)計(jì)算機(jī)科學(xué)家***William Pugh發(fā)明于1989年***,。他在論文《Skip lists: a probabilistic alternative to balanced trees》中詳細(xì)介紹了跳表的數(shù)據(jù)結(jié)構(gòu)和插入刪除等操作,。

跳表(SkipList，全稱(chēng)跳躍表)是用于有序元素序列快速搜索查找的一個(gè)數(shù)據(jù)遠(yuǎn)程桌面結(jié)構(gòu),，跳表是一個(gè)隨機(jī)化的數(shù)據(jù)結(jié)構(gòu),，實(shí)質(zhì)就是一種可以進(jìn)行二分查找的有序鏈表。跳表在原有的有序鏈表上面增加了多級(jí)索引,，通過(guò)索引來(lái)實(shí)現(xiàn)快速查找,。跳表不僅能提高搜索性能，同時(shí)也可以提高插入和刪除操作的性能,。它在性能上和紅黑樹(shù),，AVL樹(shù)不相上下，但是跳表的原理非常簡(jiǎn)單,，實(shí)現(xiàn)也比紅黑樹(shù)簡(jiǎn)單很多,。

在這里你可以看到一些關(guān)鍵詞：鏈表(有序鏈表)、索引,、二分查找,。想必你的腦海中已經(jīng)有了一個(gè)初略的印象，不過(guò)你可能還是不清楚這個(gè)"會(huì)跳的鏈表"有多diao,，甚至還可能會(huì)產(chǎn)生一點(diǎn)疑慮：跟隨機(jī)化有什么關(guān)系,？你在下文中很快就能得到答案！

回顧鏈表,，我們知道鏈表和順序表(數(shù)組)通常都是相愛(ài)相殺,，成對(duì)出現(xiàn)，各有優(yōu)劣,。而鏈表的優(yōu)勢(shì)就是更高效的插入,、刪除。痛點(diǎn)就是查詢(xún)很慢很慢,！每次查詢(xún)都是一種O(n)復(fù)雜度的操作,，鏈表估計(jì)自己都?xì)獾南肟蘖?/p>

這是一個(gè)帶頭結(jié)點(diǎn)的鏈表(頭結(jié)點(diǎn)相當(dāng)于一個(gè)固定的入口，不存儲(chǔ)有意義的值),，每次查找都需要一個(gè)個(gè)枚舉,，相當(dāng)?shù)穆覀兡懿荒苌晕?yōu)化一下,，讓它稍微跳一跳呢,？答案是可以的，我們知道很多算法和數(shù)據(jù)結(jié)構(gòu)以空間換時(shí)間,，我們?cè)谏厦婕右粚铀饕?，讓部分?jié)點(diǎn)在上層能夠直接定位到,，這樣鏈表的查詢(xún)時(shí)間近乎減少一半，鏈表自己雖然沒(méi)有開(kāi)心起來(lái),，但收起了它想哭的臉,。

這樣，在查詢(xún)某個(gè)節(jié)點(diǎn)的時(shí)候,，首先會(huì)從上一層快速定位節(jié)點(diǎn)所在的一個(gè)范圍,，如果找到具體范圍向下然后查找代價(jià)很小，當(dāng)然在表的結(jié)構(gòu)設(shè)計(jì)上會(huì)增加一個(gè)向下的索引(指針)用來(lái)查找確定底層節(jié)點(diǎn),。平均查找速度平均為O(n/2),。但是當(dāng)節(jié)點(diǎn)數(shù)量很大的時(shí)候，它依舊很慢很慢,。我們都知道二分查找是每次都能折半的去壓縮查找范圍,，要是有序鏈表也能這么跳起來(lái)那就太完美了。沒(méi)錯(cuò)跳表就能讓鏈表?yè)碛薪醯慕咏植檎业男实囊环N數(shù)據(jù)結(jié)構(gòu),，其原理依然是給上面加若干層索引,，優(yōu)化查找速度。

 通過(guò)上圖你可以看到,，通過(guò)這樣的一個(gè)數(shù)據(jù)結(jié)構(gòu)對(duì)有序鏈表進(jìn)行查找都能近乎二分的性能,。就是在上面維護(hù)那么多層的索引，首先在最高級(jí)索引上查找最后一個(gè)小于當(dāng)前查找元素的位置,，然后再跳到次高級(jí)索引繼續(xù)查找,，直到跳到最底層為止，這時(shí)候以及十分接近要查找的元素的位置了(如果查找元素存在的話),。由于根據(jù)索引可以一次跳過(guò)多個(gè)元素,，所以跳查找的查找速度也就變快了。

對(duì)于理想的跳表,，每向上一層索引節(jié)點(diǎn)數(shù)量都是下一層的1/2.那么如果n個(gè)節(jié)點(diǎn)增加的節(jié)點(diǎn)數(shù)量(1/2+1/4+…)<n,。并且層數(shù)較低，對(duì)查找效果影響不大,。但是對(duì)于這么一個(gè)結(jié)構(gòu),，你可能會(huì)疑惑,，這樣完美的結(jié)構(gòu)真的存在嗎,？大概率不存在的，因?yàn)樽鳛橐粋€(gè)鏈表,，少不了增刪該查的一些操作,。而刪除和插入可能會(huì)改變整個(gè)結(jié)構(gòu)，所以上面的這些都是理想的結(jié)構(gòu),，在插入的時(shí)候是否添加上層索引是個(gè)概率問(wèn)題(1/2的概率),，在后面會(huì)具體講解,。