[TOC] ### **skiplist數據結構簡介** skiplist本質上也是一種查找結構，用于解決算法中的查找問題（Searching），即根據給定的key，快速查到它所在的位置（或者對應的value）。 ` ` 一般查找問題的解法分為兩個大類：一個是基于各種平衡樹，一個是基于哈希表。但skiplist卻比較特殊，它沒法歸屬到這兩大類里面。 ### **skiplist數據結構演變** skiplist，顧名思義，首先它是一個list。實際上，它是在有序鏈表的基礎上發展起來的。 ` ` **有序鏈表**，如下圖（最左側的灰色節點表示一個空的頭結點）：  ` ` 在這樣一個鏈表中，如果我們要查找某個數據，需要從頭開始逐個進行比較，直到找到包含數據的那個節點，或者找到第一個比給定數據大的節點為止（沒找到），**時間復雜度為O(n)**；當我們要插入新數據的時候，也要經歷同樣的查找過程，從而確定插入位置。 ` ` 假如我們每相鄰兩個節點增加一個指針，讓指針指向下下個節點，如下圖：  ` ` 這樣所有新增加的指針連成了一個新的鏈表，但它包含的節點個數只有原來的一半（上圖中是7, 19, 26）。現在當我們想查找數據的時候，可以先沿著這個新鏈表進行查找。當碰到比待查數據大的節點時，再回到原來的鏈表中進行查找。 ` ` 比如，我們想查找23，查找的路徑是沿著下圖中標紅的指針所指向的方向進行的：  ` ` * 23首先和7比較，再和19比較，比它們都大，繼續向后比較。 * 但23和26比較的時候，比26要小，因此回到下面的鏈表（原鏈表），與22比較。 * 23比22要大，沿下面的指針繼續向后和26比較。23比26小，說明待查數據23在原鏈表中不存在，而且它的插入位置應該在22和26之間。 ` ` 在這個查找過程中，由于新增加的指針，我們不再需要與鏈表中每個節點逐個進行比較了。**需要比較的節點數大概只有原來的一半**。 ` ` 利用同樣的方式，我們可以在上層新產生的鏈表上，繼續為每相鄰的兩個節點增加一個指針，從而產生第三層鏈表。如下圖：  ` ` 在這個新的三層鏈表結構上，如果我們還是查找23，那么沿著最上層鏈表首先要比較的是19，發現23比19大，接下來我們就知道只需要到19的后面去繼續查找，從而一下子跳過了19前面的所有節點。可以想象，當鏈表足夠長的時候，這種多層鏈表的查找方式能讓我們跳過很多下層節點，大大加快查找的速度。 >優勢：按照上面生成鏈表的方式，上面每一層鏈表的節點個數，是下面一層的節點個數的一半，這樣查找過程就非常類似于一個二分查找，使得查找的時間復雜度可以降低到O(log n) 缺點：新插入一個節點之后，就會打亂上下相鄰兩層鏈表上節點個數嚴格的2:1的對應關系。如果要維持這種對應關系，就必須把新插入的節點后面的所有節點（也包括新插入的節點）重新進行調整，這會讓時間復雜度重新蛻化成O(n)。刪除數據也有同樣的問題。 ` ` skiplist為了避免這一問題，它不要求上下相鄰兩層鏈表之間的節點個數有嚴格的對應關系，而是為**每個節點隨機出一個層數(level)**。比如，一個節點隨機出的層數是3，那么就把它鏈入到第1層到第3層這三層鏈表中。為了表達清楚，下圖展示了如何通過一步步的插入操作從而形成一個skiplist的過程（點擊看大圖）：  ` ` **skiplist重要特性**：從上面skiplist的創建和插入過程可以看出，每一個節點的層數（level）是隨機出來的，而且新插入一個節點不會影響其它節點的層數。因此，插入操作只需要修改插入節點前后的指針，而不需要對很多節點都進行調整。這就降低了插入操作的復雜度。**這讓它在插入性能上明顯優于平衡樹的方案** ` ` 剛剛創建的這個skiplist總共包含4層鏈表，現在假設我們在它里面依然查找23，下圖給出了查找路徑：  ` ` 前面演示的各個節點的插入過程，實際上在插入之前也要先經歷一個類似的查找過程，在確定插入位置后，再完成插入操作, 刪除操作與插入操作類似. ` ` #### **隨機數計算過程** * 首先，每個節點肯定都有第1層指針（每個節點都在第1層鏈表里）。 * 如果一個節點有第i層(i>=1)指針（即節點已經在第1層到第i層鏈表中），那么它有第(i+1)層指針的概率為p。 * 節點最大的層數不允許超過一個最大值，記為MaxLevel。 ` ` 這個計算隨機層數的偽碼如下所示： ``` randomLevel() level := 1 // random()返回一個[0...1)的隨機數 while random() < p and level < MaxLevel do level := level + 1 return level ``` randomLevel()的偽碼中包含兩個參數，一個是p，一個是MaxLevel。在Redis的skiplist實現中，這兩個參數的取值為： ``` p = 1/4MaxLevel = 32 ``` ### skiplist的算法性能分析 ### **skiplist與平衡樹、哈希表的比較** * skiplist和各種平衡樹（如AVL、紅黑樹等）的元素是有序排列的，而哈希表不是有序的。因此，在哈希表上只能做單個key的查找，不適宜做范圍查找。所謂范圍查找，指的是查找那些大小在指定的兩個值之間的所有節點。 * 在做范圍查找的時候，平衡樹比skiplist操作要復雜。在平衡樹上，我們找到指定范圍的小值之后，還需要以中序遍歷的順序繼續尋找其它不超過大值的節點。如果不對平衡樹進行一定的改造，這里的中序遍歷并不容易實現。而在skiplist上進行范圍查找就非常簡單，只需要在找到小值之后，對第1層鏈表進行若干步的遍歷就可以實現。 * 平衡樹的插入和刪除操作可能引發子樹的調整，邏輯復雜，而skiplist的插入和刪除只需要修改相鄰節點的指針，操作簡單又快速。 * 從內存占用上來說，skiplist比平衡樹更靈活一些。一般來說，平衡樹每個節點包含2個指針（分別指向左右子樹），而skiplist每個節點包含的指針數目平均為1/(1-p)，具體取決于參數p的大小。如果像Redis里的實現一樣，取p=1/4，那么平均每個節點包含1.33個指針，比平衡樹更有優勢。 * 查找單個key，skiplist和平衡樹的時間復雜度都為O(log n)，大體相當；而哈希表在保持較低的哈希值沖突概率的前提下，查找時間復雜度接近O(1)，性能更高一些。所以我們平常使用的各種Map或dictionary結構，大都是基于哈希表實現的。 * 從算法實現難度上來比較，skiplist比平衡樹要簡單得多。