知識星球（給演演算法愛好者加星標，修煉程式設計內功）
作者：苦逼碼農 / 帥地
假如我們要用某種資料結構來維護一組有序的int型資料的集合，並且希望這個資料結構在插入、刪除、查詢等操作上能夠盡可能著快速，那麼，你會用什麼樣的資料結構呢？
陣列
一種很簡單的方法應該就是採用陣列了，在查詢方面，用陣列儲存的話，採用二分法可以在 O(logn) 的時間裡找到指定的元素，不過陣列在插入、刪除這些操作中比較不友好，找到標的位置所需時間為 O(logn) ，進行插入和刪除這個動作所需的時間複雜度為 O(n) ，因為都需要移動移動元素，所以最終所需要的時間複雜度為 O(n) 。
例如對於下麵這個陣列：
插入元素 3
連結串列
另外一種簡單的方法應該就是用連結串列了，連結串列在插入、刪除的支援上就相對友好，當我們找到標的位置之後，插入、刪除元素所需的時間複雜度為 O(1) ，註意，我說的是找到標的位置之後，插入、刪除的時間複雜度才為O(1)。
但連結串列在查詢上就不友好了，不能像陣列那樣採用二分查詢的方式，只能一個一個結點遍歷，所以加上查詢所需的時間，插入、刪除所需的總的時間複雜度為O(n)。
假如我們能夠提高連結串列的查詢效率，使連結串列的查詢的時間複雜度盡可能接近 O(logn) ，那連結串列將會是很棒的選擇。
提高連結串列的查詢速度
那連結串列的查詢速度可以提高嗎？
對於下麵這個連結串列
假如我們要查詢元素9，按道理我們需要從頭結點開始遍歷，一共遍歷8個結點才能找到元素9。能否採取某些策略，讓我們遍歷5次以內就找到元素9呢？請大家花一分鐘時間想一下如何實現？
由於元素的有序的，我們是可以透過增加一些路徑來加快查詢速度的。例如
透過這種方法，我們只需要遍歷5次就可以找到元素9了（紅色的線為查詢路徑）。
還能繼續加快查詢速度嗎？
答是可以的，再增加一層就行了，這樣只需要4次就能找到了，這就如同我們搭地鐵的時候，去某個站點時，有快線和慢線幾種路線，透過快線 + 慢線的搭配，我們可以更快著到達某個站點。
當然，還能在增加一層，
基於這種方法，對於具有 n 個元素的連結串列，我們可以採取 ** (logn + 1) 層指標路徑的形式，就可以實現在 O(logn) 的時間複雜度內，查詢到某個標的元素了，這種資料結構，我們也稱之為跳躍表，跳躍表也可以算是連結串列的一種變形，只是它具有二分查詢的功能。
插入與刪除
上面例子中，9個結點，一共4層，可以說是理想的跳躍表了，不過隨著我們對跳躍表進行插入/刪除結點的操作，那麼跳躍表結點數就會改變，意味著跳躍表的層數也會動態改變。
這裡我們面臨一個問題，就是新插入的結點應該跨越多少層？
這個問題已經有大牛替我們解決好了，採取的策略是透過拋硬幣來決定新插入結點跨越的層數：每次我們要插入一個結點的時候，就來拋硬幣，如果丟擲來的是正面，則繼續拋，直到出現負面為止，統計這個過程中出現正面的次數，這個次數作為結點跨越的層數。
透過這種方法，可以盡可能著接近理想的層數。大家可以想一下為啥會這樣呢？
插入
例如，我們要插入結點 3，4，透過拋硬幣知道3，4跨越的層數分別為 0，2 (層數從0開始算)，則插入的過程如下：
插入 3，跨越0層。
插入 4，跨越2層。
刪除
解決了插入之後，我們來看看刪除，刪除就比較簡單了，例如我們要刪除4，那我們直接把4及其所跨越的層數刪除就行了。
小結
跳躍表的插入與刪除至此都講完了，總結下跳躍表的有關性質：
(1). 跳躍表的每一層都是一條有序的連結串列.
(2). 跳躍表的查詢次數近似於層數，時間複雜度為O(logn)，插入、刪除也為 O(logn)。
(3). 最底層的連結串列包含所有元素。
(4). 跳躍表是一種隨機化的資料結構(透過拋硬幣來決定層數)。
(5). 跳躍表的空間複雜度為 O(n)。
跳躍表 vs 二叉查詢樹
有人可能會說，也可以採用二叉查詢樹啊，因為查詢查詢樹的插入、刪除、查詢也是近似 O(logn) 的時間複雜度。
不過，二叉查詢樹是有可能出現一種極端的情況的，就是如果插入的資料剛好一直有序，那麼所有節點會偏向某一邊。例如
這種接結構會導致二叉查詢樹的查詢效率變為 O(n),這會使二叉查詢樹大打折扣。
跳躍表 vs 紅黑樹
紅黑可以說是二叉查詢樹的一種變形，紅黑在查詢，插入，刪除也是近似O(logn)的時間複雜度，但學過紅黑樹的都知道，紅黑樹比跳躍表複雜多了，反正我是被紅黑樹虐過。在選擇一種資料結構時，有時候也是需要考慮學習成本的。
而且紅黑樹插入，刪除結點時，是透過調整結構來保持紅黑樹的平衡，比起跳躍表直接透過一個隨機數來決定跨越幾層，在時間複雜度的花銷上是要高於跳躍表的。
當然，紅黑樹並不是一定比跳躍表差，在有些場合紅黑樹會是更好的選擇，所以選擇一種資料結構，關鍵還得看場合。
總上所述，維護一組有序的集合，並且希望在查詢、插入、刪除等操作上盡可能快，那麼跳躍表會是不錯的選擇。redis 中的資料資料便是採用了跳躍表，當然，ridis也結合了雜湊表等資料結構，採用的是一種複合資料結構。
程式碼如下
1//節點
2class Node{
3 int value = -1;
4 int level;//跨越幾層
5 Node[] next;//指向下一個節點
6
7 public Node(int value, int level) {
8 this.value = value;
9 this.level = level;
10 this.next = new Node[level];
11 }
12}
13//跳躍表
14public class SkipList {
15 //允許的最大層數
16 int maxLevel = 16;
17 //頭節點，充當輔助。
18 Node head = new Node(-1, 16);
19 //當前跳躍表節點的個數
20 int size = 0;
21 //當前跳躍表的層數,初始化為1層。
22 int levelCount = 1;
23
24
25 public Node find(int value) {
26 Node temp = head;
27 for (int i = levelCount - 1; i >= 0; i--) {
28 while (temp.next[i] != null && temp.next[i].value value) {
29 temp = temp.next[i];
30 }
31 }
32 //判斷是否有該元素存在
33 if (temp.next[0] != null && temp.next[0].value == value) {
34 System.out.println(value + " 查詢成功");
35 return temp.next[0];
36 } else {
37 return null;
38 }
39 }
40 // 為了方便，跳躍表在插入的時候，插入的節點在當前跳躍表是不存在的
41 //不允許插入重覆數值的節點。
42 public void insert(int value) {
43 int level = getLevel();
44 Node newNode = new Node(value, level);
45 //update用於記錄要插入節點的前驅
46 Node[] update = new Node[level];
47
48 Node temp = head;
49 for (int i = level - 1; i >= 0; i--) {
50 while (temp.next[i] != null && temp.next[i].value value) {
51 temp = temp.next[i];
52 }
53 update[i] = temp;
54 }
55 //把插入節點的每一層連線起來
56 for (int i = 0; i 57 newNode.next[i] = update[i].next[i];
58 update[i].next[i] = newNode;
59 }
60 //判斷是否需要更新跳躍表的層數
61 if (level > levelCount) {
62 levelCount = level;
63 }
64 size++;
65 System.out.println(value + " 插入成功");
66 }
67
68 public void delete(int value) {
69 Node[] update = new Node[levelCount];
70 Node temp = head;
71
72 for (int i = levelCount - 1; i >= 0; i--) {
73 while (temp.next[i] != null && temp.next[i].value value) {
74 temp = temp.next[i];
75 }
76 update[i] = temp;
77 }
78
79 if (temp.next[0] != null && temp.next[0].value == value) {
80 size--;
81 System.out.println(value + " 刪除成功");
82 for (int i = levelCount - 1; i >= 0; i--) {
83 if (update[i].next[i] != null && update[i].next[i].value == value) {
84 update[i].next[i] = update[i].next[i].next[i];
85 }
86 }
87 }
88 }
89
90 //列印所有節點
91 public void printAllNode() {
92 Node temp = head;
93 while (temp.next[0] != null) {
94 System.out.println(temp.next[0].value + " ");
95 temp = temp.next[0];
96 }
97 }
98
99 //模擬拋硬幣
100 private int getLevel() {
101 int level = 1;
102 while (true) {
103 int t = (int)(Math.random() * 100);
104 if (t % 2 == 0) {
105 level++;
106 } else {
107 break;
108 }
109 }
110 System.out.println("當前的level = " + level);
111 return level;
112 }
113
114 //測試資料
115 public static void main(String[] args) {
116 SkipList list = new SkipList();
117 for (int i = 0; i 6; i++) {
118 list.insert(i);
119 }
120 list.printAllNode();
121 list.delete(4);
122 list.printAllNode();
123 System.out.println(list.find(3));
124 System.out.println(list.size + " " + list.levelCount);
125 }
126}
註：程式碼可以左右拉動
【本文作者】
帥地：一個熱愛程式設計的在校生，我的世界不只有coding，還有writing。目前維護訂閱號「苦逼的碼農」，專註於寫計算機網路，資料結構等相關文章
