跳转至

跳錶

跳錶 (Skip List) 是由 William Pugh 發明的一種查找數據結構，支持對數據的快速查找，插入和刪除。

跳錶的期望空間複雜度為 \(O(n)\)，跳錶的查詢，插入和刪除操作的期望時間複雜度都為 \(O(\log n)\)。

基本思想

顧名思義，跳錶是一種類似於鏈表的數據結構。更加準確地説，跳錶是對有序鏈表的改進。

為方便討論，後續所有有序鏈表默認為 升序 排序。

一個有序鏈表的查找操作，就是從頭部開始逐個比較，直到當前節點的值大於或者等於目標節點的值。很明顯，這個操作的複雜度是 \(O(n)\)。

跳錶在有序鏈表的基礎上，引入了 分層 的概念。首先，跳錶的每一層都是一個有序鏈表，特別地，最底層是初始的有序鏈表。每個位於第 \(i\) 層的節點有 \(p\) 的概率出現在第 \(i+1\) 層，\(p\) 為常數。

記在 n 個節點的跳錶中，期望包含 \(\frac{1}{p}\) 個元素的層為第 \(L(n)\) 層，易得 \(L(n) = \log_{\frac{1}{p}}n\)。

在跳錶中查找，就是從第 \(L(n)\) 層開始，水平地逐個比較直至當前節點的下一個節點大於等於目標節點，然後移動至下一層。重複這個過程直至到達第一層且無法繼續進行操作。此時，若下一個節點是目標節點，則成功查找；反之，則元素不存在。這樣一來，查找的過程中會跳過一些沒有必要的比較，所以相比於有序鏈表的查詢，跳錶的查詢更快。可以證明，跳錶查詢的平均複雜度為 \(O(\log n)\)。

複雜度證明

空間複雜度

對於一個節點而言，節點的最高層數為 \(i\) 的概率為 \(p^{i-1}(1 - p)\)。所以，跳錶的期望層數為 \(\sum_{i>=1} ip^{i - 1}(1-p) = \frac{1}{1 - p}\)，且因為 \(p\) 為常數，所以跳錶的 期望空間複雜度 為 \(O(n)\)。

在最壞的情況下，每一層有序鏈表等於初始有序鏈表，即跳錶的 最差空間複雜度 為 \(O(n \log n)\)。

時間複雜度

從後向前分析查找路徑，這個過程可以分為從最底層爬到第 \(L(n)\) 層和後續操作兩個部分。在分析時，假設一個節點的具體信息在它被訪問之前是未知的。

假設當前我們處於一個第 \(i\) 層的節點 \(x\)，我們並不知道 \(x\) 的最大層數和 \(x\) 左側節點的最大層數，只知道 \(x\) 的最大層數至少為 \(i\)。如果 \(x\) 的最大層數大於 \(i\)，那麼下一步應該是向上走，這種情況的概率為 \(p\)；如果 \(x\) 的最大層數等於 \(i\)，那麼下一步應該是向左走，這種情況概率為 \(1-p\)。

令 \(C(i)\) 為在一個無限長度的跳錶中向上爬 \(i\) 層的期望代價，那麼有：

\[ \begin{aligned} C(0) & = 0 \\ C(i) & = (1-p)(1+C(i)) + p(1+C(i-1)) \end{aligned} \]

解得 \(C(i)=\frac{i}{p}\)。

由此可以得出：在長度為 \(n\) 的跳錶中，從最底層爬到第 \(L(n)\) 層的期望步數存在上界 \(\frac{L(n) - 1}{p}\)。

現在只需要分析爬到第 \(L(n)\) 層後還要再走多少步。易得，到了第 \(L(n)\) 層後，向左走的步數不會超過第 \(L(n)\) 層及更高層的節點數總和，而這個總和的期望為 \(\frac{1}{p}\)。所以到了第 \(L(n)\) 層後向左走的期望步數存在上界 \(\frac{1}{p}\)。同理，到了第 \(L(n)\) 層後向上走的期望步數存在上界 \(\frac{1}{p}\)。

所以，跳錶查詢的期望查找步數為 \(\frac{L(n) - 1}{p} + \frac{2}{p}\)，又因為 \(L(n)=\log_{\frac{1}{p}}n\)，所以跳錶查詢的 期望時間複雜度 為 \(O(\log n)\)。

在最壞的情況下，每一層有序鏈表等於初始有序鏈表，查找過程相當於對最高層的有序鏈表進行查詢，即跳錶查詢操作的 最差時間複雜度 為 \(O(n)\)。

插入操作和刪除操作就是進行一遍查詢的過程，途中記錄需要修改的節點，最後完成修改。易得每一層至多隻需要修改一個節點，又因為跳錶期望層數為 \(\log_{\frac{1}{p}}n\)，所以插入和修改的 期望時間複雜度 也為 \(O(\log n)\)。

具體實現

獲取節點的最大層數

模擬以 \(p\) 的概率往上加一層，最後和上限值取最小。

1
2
3
4
5
6
int randomLevel() {
  int lv = 1;
  // MAXL = 32, S = 0xFFFF, PS = S * P, P = 1 / 4
  while ((rand() & S) < PS) ++lv;
  return min(MAXL, lv);
}

查詢

查詢跳錶中是否存在鍵值為 key 的節點。具體實現時，可以設置兩個哨兵節點以減少邊界條件的討論。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
V& find(const K& key) {
  SkipListNode<K, V>* p = head;

  // 找到該層最後一個鍵值小於 key 的節點，然後走向下一層
  for (int i = level; i >= 0; --i) {
    while (p->forward[i]->key < key) {
      p = p->forward[i];
    }
  }
  // 現在是小於，所以還需要再往後走一步
  p = p->forward[0];

  // 成功找到節點
  if (p->key == key) return p->value;

  // 節點不存在，返回 INVALID
  return tail->value;
}

插入

插入節點 (key, value)。插入節點的過程就是先執行一遍查詢的過程，中途記錄新節點是要插入哪一些節點的後面，最後再執行插入。每一層最後一個鍵值小於 key 的節點，就是需要進行修改的節點。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
void insert(const K &key, const V &value) {
  // 用於記錄需要修改的節點
  SkipListNode<K, V> *update[MAXL + 1];

  SkipListNode<K, V> *p = head;
  for (int i = level; i >= 0; --i) {
    while (p->forward[i]->key < key) {
      p = p->forward[i];
    }
    // 第 i 層需要修改的節點為 p
    update[i] = p;
  }
  p = p->forward[0];

  // 若已存在則修改
  if (p->key == key) {
    p->value = value;
    return;
  }

  // 獲取新節點的最大層數
  int lv = randomLevel();
  if (lv > level) {
    lv = ++level;
    update[lv] = head;
  }

  // 新建節點
  SkipListNode<K, V> *newNode = new SkipListNode<K, V>(key, value, lv);
  // 在第 0~lv 層插入新節點
  for (int i = lv; i >= 0; --i) {
    p = update[i];
    newNode->forward[i] = p->forward[i];
    p->forward[i] = newNode;
  }

  ++length;
}

刪除

刪除鍵值為 key 的節點。刪除節點的過程就是先執行一遍查詢的過程，中途記錄要刪的節點是在哪一些節點的後面，最後再執行刪除。每一層最後一個鍵值小於 key 的節點，就是需要進行修改的節點。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
bool erase(const K &key) {
  // 用於記錄需要修改的節點
  SkipListNode<K, V> *update[MAXL + 1];

  SkipListNode<K, V> *p = head;
  for (int i = level; i >= 0; --i) {
    while (p->forward[i]->key < key) {
      p = p->forward[i];
    }
    // 第 i 層需要修改的節點為 p
    update[i] = p;
  }
  p = p->forward[0];

  // 節點不存在
  if (p->key != key) return false;

  // 從最底層開始刪除
  for (int i = 0; i <= level; ++i) {
    // 如果這層沒有 p 刪除就完成了
    if (update[i]->forward[i] != p) {
      break;
    }
    // 斷開 p 的連接
    update[i]->forward[i] = p->forward[i];
  }

  // 回收空間
  delete p;

  // 刪除節點可能導致最大層數減少
  while (level > 0 && head->forward[level] == tail) --level;

  // 跳錶長度
  --length;
  return true;
}

完整代碼

下列代碼是用跳錶實現的 map。未經正經測試，僅供參考。

參考代碼 
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
#include <bits/stdc++.h>
using namespace std;

template <typename K, typename V>
struct SkipListNode {
  int level;
  K key;
  V value;
  SkipListNode **forward;

  SkipListNode() {}

  SkipListNode(K k, V v, int l, SkipListNode *nxt = NULL) {
    key = k;
    value = v;
    level = l;
    forward = new SkipListNode *[l + 1];
    for (int i = 0; i <= l; ++i) forward[i] = nxt;
  }

  ~SkipListNode() {
    if (forward != NULL) delete[] forward;
  }
};

template <typename K, typename V>
struct SkipList {
  static const int MAXL = 32;
  static const int P = 4;
  static const int S = 0xFFFF;
  static const int PS = S / P;
  static const int INVALID = INT_MAX;

  SkipListNode<K, V> *head, *tail;
  int length;
  int level;

  SkipList() {
    srand(time(0));

    level = length = 0;
    tail = new SkipListNode<K, V>(INVALID, 0, 0);
    head = new SkipListNode<K, V>(INVALID, 0, MAXL, tail);
  }

  ~SkipList() {
    delete head;
    delete tail;
  }

  int randomLevel() {
    int lv = 1;
    while ((rand() & S) < PS) ++lv;
    return MAXL > lv ? lv : MAXL;
  }

  void insert(const K &key, const V &value) {
    SkipListNode<K, V> *update[MAXL + 1];

    SkipListNode<K, V> *p = head;
    for (int i = level; i >= 0; --i) {
      while (p->forward[i]->key < key) {
        p = p->forward[i];
      }
      update[i] = p;
    }
    p = p->forward[0];

    if (p->key == key) {
      p->value = value;
      return;
    }

    int lv = randomLevel();
    if (lv > level) {
      lv = ++level;
      update[lv] = head;
    }

    SkipListNode<K, V> *newNode = new SkipListNode<K, V>(key, value, lv);
    for (int i = lv; i >= 0; --i) {
      p = update[i];
      newNode->forward[i] = p->forward[i];
      p->forward[i] = newNode;
    }

    ++length;
  }

  bool erase(const K &key) {
    SkipListNode<K, V> *update[MAXL + 1];
    SkipListNode<K, V> *p = head;

    for (int i = level; i >= 0; --i) {
      while (p->forward[i]->key < key) {
        p = p->forward[i];
      }
      update[i] = p;
    }
    p = p->forward[0];

    if (p->key != key) return false;

    for (int i = 0; i <= level; ++i) {
      if (update[i]->forward[i] != p) {
        break;
      }
      update[i]->forward[i] = p->forward[i];
    }

    delete p;

    while (level > 0 && head->forward[level] == tail) --level;
    --length;
    return true;
  }

  V &operator[](const K &key) {
    V v = find(key);
    if (v == tail->value) insert(key, 0);
    return find(key);
  }

  V &find(const K &key) {
    SkipListNode<K, V> *p = head;
    for (int i = level; i >= 0; --i) {
      while (p->forward[i]->key < key) {
        p = p->forward[i];
      }
    }
    p = p->forward[0];
    if (p->key == key) return p->value;
    return tail->value;
  }

  bool count(const K &key) { return find(key) != tail->value; }
};

int main() {
  SkipList<int, int> L;
  map<int, int> M;

  clock_t s = clock();

  for (int i = 0; i < 1e5; ++i) {
    int key = rand(), value = rand();
    L[key] = value;
    M[key] = value;
  }

  for (int i = 0; i < 1e5; ++i) {
    int key = rand();
    if (i & 1) {
      L.erase(key);
      M.erase(key);
    } else {
      int r1 = L.count(key) ? L[key] : 0;
      int r2 = M.count(key) ? M[key] : 0;
      assert(r1 == r2);
    }
  }

  clock_t e = clock();
  cout << "Time elapsed: " << (double)(e - s) / CLOCKS_PER_SEC << endl;
  // about 0.2s

  return 0;
}

跳錶的隨機訪問優化

訪問跳錶中第 \(k\) 個節點，相當於訪問初始有序鏈表中的第 \(k\) 個節點，很明顯這個操作的時間複雜度是 \(O(n)\) 的，並不足夠優秀。

跳錶的隨機訪問優化就是對每一個前向指針，再多維護這個前向指針的長度。假設 \(A\) 和 \(B\) 都是跳錶中的節點，其中 \(A\) 為跳錶的第 \(a\) 個節點，\(B\) 為跳錶的第 \(b\) 個節點 \((a < b)\)，且在跳錶的某一層中 \(A\) 的前向指針指向 \(B\)，那麼這個前向指針的長度為 \(b - a\)。

現在訪問跳錶中的第 \(k\) 個節點，就可以從頂層開始，水平地遍歷該層的鏈表，直到當前節點的位置加上當前節點在該層的前向指針長度大於等於 \(k\)，然後移動至下一層。重複這個過程直至到達第一層且無法繼續行操作。此時，當前節點就是跳錶中第 \(k\) 個節點。

這樣，就可以快速地訪問到跳錶的第 \(k\) 個元素。可以證明，這個操作的時間複雜度為 \(O(\log n)\)。

參考資料

  1. Skip Lists: A Probabilistic Alternative to Balanced Trees
  2. Skip List
  3. A Skip List Cookbook
本页面最近更新：，更新历史
发现错误？想一起完善？ 在 GitHub 上编辑此页！
本页面贡献者：OI-wiki
本页面的全部内容在 CC BY-SA 4.0 和 SATA 协议之条款下提供，附加条款亦可能应用