跳表這一數據結構，已經成為了Redis面試的高頻考點。前兩年沒這么卷的時候，可能大家從開始學習，到拿到大廠offer這一過程，都可能沒聽說過跳表這一數據結構。
那什么是跳表呢?它是用來干啥的?AVL樹紅黑樹知道吧，對，跳表跟他干的事情差不多。我舉個例子大家就明白了。假設目前有一個有序數列：
- [2, 11，22, 33, 44, 52, 63]
我們想基于單鏈表的思想，設計一個數據結構，實現查找時間復雜度為O(logn)。單鏈表的話，它的結構長這個樣子。
跳表1
當然這個結構，查找時間復雜度妥妥的O(n)，那咋改呢?
那換個問法：一般做算法題，手撕代碼面試的時候，當咱寫了個時間復雜度為O(n)的解法，面試官搖搖頭，問你有沒有更好的方法，你會怎么做?
常見復雜度O(nlogn) O(n) O(logn) O(1)，要優化，一步步來的話，只能上O(logn)了，那復雜度logn最常見的算法是哪個?當然是二分!
思路對了，那對著鏈表，咋把二分思想融合進去呢?
要不單鏈表指針這邊動動刀子?讓指針除了指向后面元素，還能越過幾個節點，指向更后面元素?類似二叉查找樹?先來看看這個數組對應的二叉查找樹長什么樣。
跳表2
當然，由于我們的結構是單鏈表，所以只能有由小值，指向大值，這個二叉樹得改改。
跳表2
好像有點意思在里面了，再把原先單鏈表的性質加上。
跳表2
走線有點凌亂，按單鏈表的布局顯示方式改改：(值得注意的是，我們需要新建一個數組項，每個數組項存儲一個指針，指向剛剛二叉搜索樹每一層最左側的節點)
(咋感覺越看越像B+樹了(霧))
來看個查找邏輯吧：
當查找到的結點保存的數，比要查找的數小時，跳表就會繼續訪問該層上的下一個結點。
當不滿足時，跳表就會用到當前查找到的結點的指針數組的下一層指針，然后沿著下一層指針繼續查找。
對于這種數據結構，我們需要從上往下依次查詢三個鏈表，比如我們想查大于35的數字。
首先按左側數組第一個找，發現中間節點是33，比較一下比35小。
發現33比35小，跳下一個節點。
發現該節點是Null，跳33的下一層節點。
發現52比35大，再跳下一層節點。
發現44比35大，跳下一層節點，但由于這是最后一層節點，即44是第一個比33大的數，滿足最終條件，就找到了第一個比35大的數字。
我們知道，二叉平衡樹，如果設計插入操作，會特別特別麻煩。對于由二叉平衡樹思想改的跳表也是如此，對于我們這邊的情況，每增加，或者減少一個新節點，每個節點的高度都需要變化。。那有沒有高人改進呢?
既然把二叉平衡樹改成這四不像了，為啥再不改改，能不能讓他不平衡的同時，還能保證查找效率?
說實話，還真可以，來看看這種跳表。
跳表1
雖然這個跳表跟咱剛剛講的跳表比起來，奇形怪狀的，但按剛剛的查找思路，還是能做比較好的查詢工作的。
而且既然表都長這么奇形怪狀了，那添加或者刪新元素，其他節點高度不變問題也不大了。
而且驚人的是，如果我們對新插入節點的高度進行隨機產生(每次隨機大于p，接著往上加高度，小于p停下來)，然后別的節點高度保持不變，查找效率還是為O(logn)，不會出現像二叉查找樹那種直接退化成O(logn)的情況。
有興趣想看推導的同學點個贊，點贊破100，咱寫波推導。(目前面試還沒卷到要證明跳表時間復雜度的程度，所以不知道咋推沒問題)
原文鏈接：https://mp.weixin.qq.com/s/uaEOIKEmiBcmo6gGAIXtyg
