前言

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

但你別慌，遇到蘑菇頭這種面試官也別怕，因為你看到這篇文章了(得意

對于一個數據結構或算法，人群數量從聽過名稱、了解基本原理、清楚執(zhí)行流程、能夠手寫 呈抖降的趨勢。因為很多數據結構與算法其核心原理可能簡單，但清楚其執(zhí)行流程就需要動腦子去思考想明白，但是如果能夠把它寫出來，那就要自己一步步去設計和實現(xiàn)?？赡芤ê芫貌拍苷嬲龑懗鰜?，并且還可能要查閱大量的資料。

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

快速了解跳表

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

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

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

回顧鏈表，我們知道鏈表和順序表(數組)通常都是相愛相殺，成對出現(xiàn)，各有優(yōu)劣。而鏈表的優(yōu)勢就是更高效的插入、刪除。痛點就是查詢很慢很慢！每次查詢都是一種O(n)復雜度的操作，鏈表估計自己都氣的想哭了

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

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

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

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