跳表(SkipList)
簡介
首先，我們在心里思考一個問題：排序單鏈表的查找時間復(fù)雜度能否比 好呢？
對于一個已經(jīng)排好序的單鏈表來說，想要查詢其中的一個數(shù)據(jù)，也只能從頭開始遍歷鏈表，不能跳過節(jié)點（skip nodes）查找，這樣效率很低，時間復(fù)雜度為 。
如上圖所示，對于平衡二叉搜索樹（AVL 樹），在與根進行一次比較后，我們跳過了幾乎一半的節(jié)點。
對于排序的數(shù)組，我們可以隨機訪問，并且可以對數(shù)組應(yīng)用二分查找法。
那我們是不是可以對排序單鏈表進行增強（比如像二分查找一樣）來提高查找速度呢？那就是 跳表（Skip List）。
這個想法很簡單，我們通過創(chuàng)建多層鏈表，這樣我們就可以跳過一些節(jié)點。
如上圖中例子，其中包含 10個節(jié)點和兩層。上層是只連接主要車站的 “快車道”，下層是連接每個車站的 “普通車道”。就像你從北京出發(fā)，自駕到西藏，如果你走 “國道”，你可能要路過很多站點，速度也會比較慢；但是也有直達的 “高速公路” 呀（京藏高速），高速公路上的出站口少，但是你到達目的地更快呀。
假設(shè)我們要查找 35，我們從“快車道” 的第一個節(jié)點開始，一直沿著“快車道”前進，直到找到下一個節(jié)點大于 35 的節(jié)點。一旦我們在“快速車道”上找到這樣的節(jié)點( 28 就是我們找到的節(jié)點，28 的下一個節(jié)點 50 大于 35)，我們就使用節(jié)點 28 的指針移動到 “普通車道” ，并在 “普通車道” 上線性查找 35 。在圖中的例子中，我們從“普通車道”上的 28 開始，通過線性搜索，我們找到了 35。
原本需要 6 次才能查找到元素 35 ，現(xiàn)在僅查找了 4 次。
那么圖中的兩層情況下的時間復(fù)雜度是多少？
最壞情況下的時間復(fù)雜度是“快車道”上的節(jié)點數(shù)加上“普通車道”上的一個段（段表示兩個“快車道”節(jié)點之間的“普通車道”節(jié)點的數(shù)目）的節(jié)點數(shù)。
因此，如果我們在“正常車道”上有 n 個節(jié)點，在“快速車道”上有 節(jié)點，并且我們將 “普通車道” 均分，那么在 “普通車道” 的每一段中都有 個節(jié)點。 實際上是具有兩層跳表結(jié)構(gòu)的最優(yōu)除法。通過這種規(guī)則，搜索遍歷鏈表節(jié)點將為 。因此，在增加 空間的情況下，可以將時間復(fù)雜度降低到 。
那么我們能將時間復(fù)雜度降得更低嗎？
通過增加更多的層可以進一步降低跳表的時間復(fù)雜度。實際上，在 個額外空間的情況下，查找、插入和刪除的期望時間復(fù)雜度都可以達到 。
跳表的插入操作
在深入理解跳表的插入操作之前，一定要解決跳表的層數(shù)問題?。?！
層數(shù)的確定
鏈表中的每個元素都由一個節(jié)點表示，節(jié)點的層級是在插入鏈表時隨機選擇的。跳表中節(jié)點的層級不取決于節(jié)點中的元素數(shù)量，而是由下面一個算法確定的，算法的 Java 代碼為：
private int randomLevel() {
int level = 1;
while (Math.random() < P && level < MaxLevel {
level++;
}
return level;
}
MaxLevel 是跳表層數(shù)的上限。它可以確定為 ， 是中的節(jié)點總數(shù)。上述算法保證了隨機層數(shù)永遠不會大于 MaxLevel 。這里 P 是第 i+1 層節(jié)點的個數(shù)與第 i 層節(jié)點個數(shù)的比值，比如 ，就表示第 i 層的節(jié)點個數(shù)是第 i+1 層節(jié)點個數(shù)的兩倍，理論情況下如下圖所示，跳表可以和 AVL 樹達到幾乎一樣的效果：
理論來講，對于 ， 一級索引中元素個數(shù)應(yīng)該占原始數(shù)據(jù)的 50% （原始數(shù)據(jù) 8 個，第一層索引 4 個），二級索引中元素個數(shù)占原始的 25%，三級索引占原始數(shù)據(jù)的 12.5% ，一直到最頂層。
對于每一個新插入的節(jié)點，都需要調(diào)用 randomLevel() 生成一個合理的層數(shù)。該randomLevel() 方法會隨機生成 1 ~ MaxLevel 之間的數(shù)，且 ： 的概率返回 1， 的概率返回 2， 的概率返回 3 ...
節(jié)點結(jié)構(gòu)
每個節(jié)點由一個關(guān)鍵字 key 和一個前向數(shù)組 forwards[] 組成，該數(shù)組存儲指向不同層的節(jié)點的指針。i 層的節(jié)點的前向數(shù)組保存了從第 0 層到第 i 層前向節(jié)點的指針。
public class Node {
private int key = -1; //結(jié)點的 key
private Node forwards[] = new Node[MAX_LEVEL]; // 結(jié)點key 所對應(yīng)的前向數(shù)組
}
插入操作
我們將從列表的最高層開始，將當(dāng)前節(jié)點的下一個節(jié)點的 key 與要插入的 key 進行比較?；舅枷胧牵?/p>
- 如果下一個節(jié)點的 key 小于要插入的 key ，則我們在同一層上繼續(xù)前進查找。
- 如果下一個節(jié)點的 key 大于要插入的 key ，則我們將指向當(dāng)前節(jié)點
i 的指針存儲在 update[i] 處，并向下移動一層，繼續(xù)搜索。
在第 0 層，我們一定會找到一個位置來插入給定的 key 。
以下是插入操作的偽代碼：
public void insert(int key) {
int level = randomLevel();
Node newNode = new Node();
newNode.key = key;
newNode.maxLevel = level;
// 創(chuàng)建 update 數(shù)組并初始化
Node update[] = new Node[level];
for (int i = 0; i < level; ++i) {
update[i] = head;
}
// 將查找路徑上結(jié)點的前向結(jié)點設(shè)置為新插入結(jié)點
Node current = head;
for (int i = level - 1; i >= 0; --i) {
while (current.forwards[i] != null && current.forwards[i].key < key) {
current = current.forwards[i];
}
update[i] = current;// 第 i 層需要修改的節(jié)點為 p
}
current = current.forwards[0];
if (current == null || current.key != key) {
// 在第0到level層插入新結(jié)點
for (int i = 0; i < level; ++i) {
newNode.forwards[i] = update[i].forwards[i];
update[i].forwards[i] = newNode;
}
}
// 更新跳表的層數(shù)
if (currentLevel < level) currentLevel = level;
}
在這里，update[i] 表示插入值為 key 的節(jié)點時，第 i 層需要修改的節(jié)點為 p，也就是位于查找路徑上的節(jié)點 。考慮以下示例，我們想要在其中插入值 17，設(shè)隨機層數(shù)為 randomLevel() == 2 ，update[] 函數(shù)就包含兩個元素，update[1] 存儲的是 key 為 9 的結(jié)點的地址，update[0] 存儲的是值為 12 的結(jié)點的地址，當(dāng)插入值 17 之后，9 和 12 的前向結(jié)點就變成了 17 ，而 17 的前向結(jié)點就變成了**9** 和 12 原始的前向結(jié) 25 和 19 。
跳表的查找操作
跳表的查找操縱非常類似于在跳表插入操作中搜索插入元素的位置的方法?；镜南敕ㄊ牵?/p>
- 下一個節(jié)點的關(guān)鍵字 key 小于查找的關(guān)鍵字，則我們在同一層上繼續(xù)前進查找。
- 下一個節(jié)點的關(guān)鍵字 key 大于查找的關(guān)鍵字，則我們將指向當(dāng)前節(jié)點i的指針存儲在 update[i] 處，并向下移動一層，繼續(xù)搜索。
在最底層（第 0 層），如果最右邊元素的前向元素的值等于搜索關(guān)鍵字的值，則我們找到了關(guān)鍵字，否則未找到。
如圖所示，查找關(guān)鍵字 17 ，紅色的路線表示查找路徑，其中的藍色箭頭表示最右邊元素 12 的前向指針，該指針的值 17 與查找的關(guān)鍵字 key 相等，返回值為 key 的結(jié)點。
實現(xiàn)代碼相當(dāng)簡單了：
public Node search(int key) {
Node current = head;
for (int i = currentLevel - 1; i >= 0; --i) {
while (current.forwards[i] != null && current.forwards[i].key < value) {
current = current.forwards[i];
}
}
// current.key = 12
if (current.forwards[0] != null && current.forwards[0].key == key) {
return current.forwards[0];
} else {
return null;
}
}
其中 currentLevel 表示當(dāng)前跳表的層數(shù)，如上圖中的 currentLevel = 4 。
跳表的刪除操作
在刪除元素 key 之前，使用上述查找方法在跳表中定位元素。如果找到了元素，就像我們在單鏈表中所做的那樣，重新排列指針以刪除列表中的元素。
我們從最底層（第 0 層）開始向上重新排列，直到 update[i] 的下一個元素不是 key 。刪除元素后，可能會導(dǎo)致跳表層數(shù) currentLevel 的降低，最后對其進行更新即可。
如上圖所示，刪除 key = 6 的結(jié)點之后，第三層沒有了元素(紅色虛線箭頭)。所以我們將跳表的層數(shù)減 1。
public void delete(int key) {
Node[] update = new Node[currentLevel];
Node current = head;
// 查找要刪除結(jié)點的前序結(jié)點并保存至 update[] 中
for (int i = currentLevel - 1; i >= 0; --i) {
while (current.forwards[i] != null && current.forwards[i].key < key) {
current = current.forwards[i];
}
update[i] = current;
}
// 將 update[] 的前向結(jié)點設(shè)置為要刪除結(jié)點的forwords[i]
if (current.forwards[0] != null && current.forwards[0].key == key) {
for (int i = currentLevel - 1; i >= 0; --i) {
if (update[i].forwards[i] != null && update[i].forwards[i].data == key) {
update[i].forwards[i] = update[i].forwards[i].forwards[i];
}
}
}
// 更新跳表的層數(shù)
while (currentLevel > 1 && head.forwards[currentLevel] == null) {
currentLevel--;
}
}
復(fù)雜度分析
空間復(fù)雜度
跳表的 期望空間復(fù)雜度 為 。
在最壞的情況下，每一層有序鏈表等于初始有序鏈表，即跳表的 最差空間復(fù)雜度 為 。
時間復(fù)雜度
跳表的查找、插入和刪除操作的時間復(fù)雜度均取決于查找的時間，查找的 最壞時間復(fù)雜 為 。
平均時間復(fù)雜度 為 。大家就當(dāng)二分查找。
當(dāng)然按照論文中的證明，沒有這么簡單了。
跳表的應(yīng)用
適用場景：節(jié)點插入和刪除操作比較少，查詢頻次較多的情況。
使用跳表的產(chǎn)品：
Redis：Redis sorted set的內(nèi)部使用 HashMap 和 跳表(SkipList)來保證數(shù)據(jù)的存儲和有序，HashMap 里放的是成員到 score 的映射，而跳躍表里存放的是所有的成員，排序依據(jù)是 HashMap 里存的 score ，使用跳表的結(jié)構(gòu)可以獲得比較高的查找效率，并且在實現(xiàn)上比較簡單。
HBase MemStore 內(nèi)部數(shù)據(jù)存儲
