從零開始學演算法：7.跳錶
作者: tiankonguse | 更新日期:
業界都沒有真正理解跳錶。
在公眾號中回覆“ACM模板”你將免費獲得我大學耗時四年整理的《ACM演算法模板》。
如果大家想加入我的星球，可以加我微信，我免費給你拉進去，加我時暗號”演算法星球”。
一、背景
大家好，我是tiankonguse。
由於某些原因，經常有人想學習演算法但之前又沒有相關經驗，不知道從何做起。
我思考了許久，計劃寫一個系列來分享如何入門學習演算法。
之前已經分享了《 ofollow,noindex" target="_blank">認識演算法 》、《 瞭解套路長啥樣 》、《 排序演算法 》、《 二分查詢 》、《 連結串列 》，這是第七篇《跳錶》。
一、基礎知識
在上一篇文章《 連結串列 》最後我們通過分塊把複雜度降到了O(sqrt(n))，還提到有一個方法可以做到O(log(n))的插入或刪除複雜度。
這個資料結構就是跳錶。
寫完這篇文章時，發現一個重大祕密：跳錶其實與順序沒有關係的，也就是跳錶可以無序的。
業界都是用於維護有序序列，實際情況是跳錶完全可以用於操作隨機序列。
原來跳錶才是一個真實的萬能陣列了，各種複雜度都可以接受，REDIS的LIST看來要重寫了。
不過這裡我們先以有序序列為例來講解跳錶，對於無序的，只需要忽略比大小操作就行了。
對於跳錶是啥，其實不好描述，但是看圖模擬操作一下，應該就可以馬上明白他的原理了。
（圖片來自維基百科）
首先可以看出來，我們有一個數組連結串列頭，長度固定，並且表頭的每個位置都是一個指標，指向後面。
對於每個位置，同樣也有一個數組連結串列頭，有不定的高度以及值資訊，結構如下.
二、查詢
看一個數據結構如何設計的，最簡單的方式就是看查詢的實現了。
跳錶的查詢步驟如下：
0.定義左邊界為head
1.左邊界從上到下依次遍歷表頭
2.發現是NULL代表當前層數沒找到，層數下移
3.如果不是NULL，所在位置我們稱為A，A對應的值和查詢的值比大小
4.查詢的值小於A，說明答案在A左邊，從下一層數繼續查詢。
5.查詢的值大於等於A，說明答案在右邊，左邊界更新為A，從當前層數繼續查詢（重點注意）。
6.如果遍歷到最後一層了，還沒找到，說明不存在。
可能看著上面的描述步驟太抽象，那我們舉個具體的例子吧。
這裡以查詢5為例。
0.左邊界為head，總共有4層 ，當前層數3
1.位置（head, 3）從第3層開始，遇到節點1，比較5大於1，左邊界置為1
2.位置（1, 3）從第3層開始，遇到nul，層數下降
3.位置（1, 2）從第2層開始，遇到節點4，比較5大於等於4，左邊界置為4
4.位置（4, 2）從第2層開始，遇到節點6，比較5小於6，層數下降
5.位置（4, 1）從第1層開始，遇到節點6，比較5小於6，層數下降
6.位置（4, 0）從第0層開始，遇到節點5，比較5大於等於5，左邊界置為5
7.位置（5, 0）從第0層開始，遇到節點6，比較5小於6，層數下降
8.位置（5, -1）結束了
上面步驟的實現程式碼如下，可以發現，非常簡單。
裡面多了一個num, 用於計算偏移量，這樣就可以知道查詢值得座標了。
三、插入
我們查詢的時候，知道了節點的關鍵資訊有三個：節點值、節點每層到下層的指標和距離。
現在我們需要在指定的位置插入一個值了，必然需要更新MAXLEVEL個連結串列，以及更新2*MAXLEVEL個連結串列間的距離。
如上圖，假設我們要插入 5.5。
棕黃色的含義是當前節點到下個節點之間的節點個數，也就是我們儲存的num欄位。
淺藍色的含義是當前位置之前有多少個節點，我們命名為preNum。
各層的藍色線終點和preNum都可以在查詢5.5的時候計算出來。
這樣，我們插入5.5的時候，5.5的各層num與各層連結串列之前的num都可以通過簡單的數學運算計算出來。
比如第3層前半段連結串列的num = 第0層的preNum（最長的藍線）- 第三層的preNum（最短的藍線） + 1.
而對於第三層後半段連結串列的num = 第三層的num(最長的黃線) - 第3層前半段連結串列的num(上面計算的值)
上面描述對應的程式碼就是下面這個函式，實現也不復雜。
有個地方需要說明一下，新插入的節點的高度是隨機計算的，這樣做的風險可能會導致這個演算法退化為O(n)的複雜度。
四、刪除
刪除和插入是相反的操作，而且更簡單。
找到位置後，直接把刪除位置的num加到之前的節點，然後刪除聊表即可。
這裡就不多說了。
五、下標定位
由於儲存了每個位置每層到下個next之間的節點數，這裡就可以快速的判斷是否可以跳過下個next。
跳過了更新總偏移量，沒跳過則進入下一層，程式碼如下。
六、最後
知道了跳錶節點儲存的資訊：值、各層到下個節點的指標和距離，我們就可以輕鬆的實現跳錶了。
如果你沒看明白，不要緊，多看幾遍查詢的步驟，你應該就能明白跳錶的實現原理。
對於跳錶，是個有序的序列，我們可以Log(n)的複雜度插入或刪除一個數據，也可以在log(n)的複雜度內通過下標定位到對應的位置。
文章的開頭說了，我們並不需要跳錶有序。
我們只使用下標來增加資料或刪除資料的話，跳錶就是一個強大的陣列了，而且平均複雜度也是O(n)的。
那為啥大家分享的跳錶都是有序的呢？
第一個原因是無序的跳錶意義不大，實現難度相比陣列高出幾個數量級，真要使用無序的了還不如使用其他的代替資料結構。
更關鍵的原因是業界都是使用跳錶來實現有序集，從而做到快速查詢。
比如redis、levelDB等開源軟體都實現了有序跳錶。
這樣想來，無序跳錶活得好憋屈，google了一下，竟然沒有人使用這個方法。
redis如果使用跳錶優化一下list一下的話，複雜度就可以從O(n)的複雜度提升到O(log(n))了。
震驚，我發現了一個log(n)的list資料結構，有序跳錶，哈哈。
本文首發於公眾號：天空的程式碼世界，微訊號：tiankonguse-code。
推薦閱讀：
今天長按識別上面的二維碼，在公眾號中回覆“ ACM模板 ”，你將免費獲得我大學耗時四年整理的《ACM演算法模板》。
回覆“ 演算法的世界 ”，或點選 閱讀原文 加入“tiankonguse的朋友們”，已有三百多個小夥伴加入。