前言

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

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

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

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

快速了解跳表

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

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

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

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

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

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

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

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