目錄
- 什么是跳表
- 跳表的意義究竟在于何處？
- 跳表的搜索時間復雜度
- 跳表是不是很費內存？
- 插入和刪除的時間復雜度
- 跳表的代碼實現（Java 版）
知道跳表（Skip List）是在看關于Redis的書的時候，Redis中的有序集合使用了跳表數據結構。接著就查了一些博客，來學習一下跳表。后面會使用Java代碼來簡單實現跳表。
什么是跳表
跳表由William Pugh發明，他在論文《Skip lists: a probabilistic alternative to balanced trees》中詳細介紹了跳表的數據結構和插入刪除等操作，論文是這么介紹跳表的：
Skip lists are a data structure that can be used in place of balanced trees.Skip lists use probabilistic balancing rather than strictly enforced balancing and as a result the algorithms for insertion and deletion in skip lists are much simpler and significantly faster than equivalent algorithms for balanced trees.
也就是說，跳表可以用來替代紅黑樹，使用概率均衡技術，使得插入、刪除操作更簡單、更快。先來看論文里的一張圖：
觀察上圖
- a：已排好序的鏈表，查找一個結點最多需要比較N個結點。
- b：每隔2個結點增加一個指針，指向該結點間距為2的后續結點，那么查找一個結點最多需要比較ceil(N/2)+1個結點。
- c，每隔4個結點增加一個指針，指向該結點間距為4的后續結點，那么查找一個結點最多需要比較ceil(N/4)+1個結點。
- 若每第
2^i 個結點都有一個指向間距為 2^i的后續結點的指針，這樣不斷增加指針，比較次數會降為log(N)。這樣的話，搜索會很快，但插入和刪除會很困難。
一個擁有k個指針的結點稱為一個k層結點（level k node）。按照上面的邏輯，50%的結點為1層，25%的結點為2層，12.5%的結點為3層…如果每個結點的層數隨機選取，但仍服從這樣的分布呢（上圖e，對比上圖d）？
使一個k層結點的第i個指針指向第i層的下一個結點，而不是它后面的第2^(i-1)個結點，那么結點的插入和刪除只需要原地修改操作；一個結點的層數，是在它被插入的時候隨機選取的，并且永不改變。因為這樣的數據結構是基于鏈表的，并且額外的指針會跳過中間結點，所以作者稱之為跳表（Skip Lists）。
二分查找底層依賴數組隨機訪問的特性，所以只能用數組實現。若數據存儲在鏈表，就沒法用二分搜索了？
其實只需稍微改造下鏈表，就能支持類似“二分”的搜索算法，即跳表（Skip list），支持快速的新增、刪除、搜索操作。
Redis中的有序集合（Sorted Set）就是用跳表實現的。我們知道紅黑樹也能實現快速的插入、刪除和查找操作。那Redis 為何不選擇紅黑樹來實現呢？
跳表的意義究竟在于何處？
單鏈表即使存儲的數據有序，若搜索某數據，也只能從頭到尾遍歷，搜索效率很低，平均時間復雜度是O(n)。
追求極致的程序員就開始想了，那這該如何提高鏈表結構的搜索效率呢？
若如下圖，對鏈表建立一級“索引”，每兩個結點提取一個結點到上一級，把抽出來的那級叫作索引或索引層。圖中的down表示down指針，指向下一級結點。
比如要搜索16：
先遍歷索引層，當遍歷到索引層的13時，發現下一個結點是17，說明目標結點位于這倆結點中間
然后通過down指針，下降到原始鏈表層，繼續遍歷
此時只需再遍歷2個結點，即可找到16！
原先單鏈表結構需遍歷10個結點，現在只需遍歷7個結點即可。可見，加一層索引，所需遍歷的結點個數就減少了，搜索效率提升。
若再加層索引，搜索效率是不是更高？于是每兩個結點再抽出一個結點到第二級索引。現在搜索16，只需遍歷6個結點了！
這里數據量不大，可能你也沒感覺到搜索效率ROI高嗎。
那數據量就變大一點，現有一64結點鏈表，給它建立五級的索引。
原來沒有索引時，單鏈表搜索62需遍歷62個結點！
現在呢？只需遍歷11個！所以你現在能體會到了，當鏈表長度n很大時，建立索引后，搜索性能顯著提升。
這種有多級索引的，可以提高查詢效率的鏈表就是最近火遍面試圈的跳表。
作為嚴謹的程序員，我們又開始好奇了
跳表的搜索時間復雜度
我們都知道單鏈表搜索時間復雜度O(n)，那如此快的跳表呢？
若鏈表有n個結點，會有多少級索引呢？假設每兩個結點抽出一個結點作為上級索引，則：
- 第一級索引結點個數是n/2
- 第二級n/4第
- 三級n/8
- …
- 第k級就是
n/(2^k)
假設索引有h級，最高級索引有2個結點，可得：n/(2h) = 2
所以：h = log2n-1
若包含原始鏈表這一層，整個跳表的高度就是log2 n。我們在跳表中查詢某個數據的時候，如果每一層都要遍歷m個結點，那在跳表中查詢一個數據的時間復雜度就是O(m*logn)。
那這個m的值是多少呢？按照前面這種索引結構，我們每一級索引都最多只需要遍歷3個結點，也就是說m=3，為什么是3呢？我來解釋一下。
假設我們要查找的數據是x，在第k級索引中，我們遍歷到y結點之后，發現x大于y，小于后面的結點z，所以我們通過y的down指針，從第k級索引下降到第k-1級索引。在第k-1級索引中，y和z之間只有3個結點（包含y和z），所以，我們在K-1級索引中最多只需要遍歷3個結點，依次類推，每一級索引都最多只需要遍歷3個結點。
通過上面的分析，我們得到m=3，所以在跳表中查詢任意數據的時間復雜度就是O(logn)。這個查找的時間復雜度跟二分查找是一樣的。換句話說，我們其實是基于單鏈表實現了二分查找，是不是很神奇？不過，天下沒有免費的午餐，這種查詢效率的提升，前提是建立了很多級索引，也就是我們在第6節講過的空間換時間的設計思路。
跳表是不是很費內存？
由于跳表要存儲多級索引，勢必比單鏈表消耗更多存儲空間。那到底是多少呢？
若原始鏈表大小為n：
- 第一級索引大約有n/2個結點
- 第二級索引大約有n/4個結點
- …
- 最后一級2個結點
多級結點數的總和就是：
n/2+n/4+n/8…+8+4+2=n-2
所以空間復雜度是O(n)。這個量還是挺大的，能否再稍微降低索引占用的內存空間呢？
若每三五個結點才抽取一個到上級索引呢？
- 第一級索引需要大約n/3個結點
- 第二級索引需要大約n/9個結點
- 每往上一級，索引結點個數都除以3
假設最高級索引結點個數為1，總索引結點數：n/3+n/9+n/27+…+9+3+1=n/2
盡管空間復雜度還是O(n)，但比上面的每兩個結點抽一個結點的索引構建方法，要減少了一半的索引結點存儲空間。
我們大可不必過分在意索引占用的額外空間，實際開發中，原始鏈表中存儲的有可能是很大的對象，而索引結點只需存儲關鍵值和幾個指針，無需存儲對象，所以當對象比索引結點大很多時，那索引占用的額外空間可忽略。
插入和刪除的時間復雜度
插入
在跳表中插入一個數據，只需O(logn)時間復雜度。
單鏈表中，一旦定位好要插入的位置，插入的時間復雜度是O(1)。但這里為了保證原始鏈表中數據的有序性，要先找到插入位置，所以這個過程中的查找操作比較耗時。
單純的單鏈表，需遍歷每個結點以找到插入的位置。但跳表搜索某結點的的時間復雜度是O(logn)，所以搜索某數據應插入的位置的時間復雜度也是O(logn)。
刪除
如果這個結點在索引中也有出現，除了要刪除原始鏈表的結點，還要刪除索引中的。
因為單鏈表刪除操作需拿到要刪除結點的前驅結點，然后通過指針完成刪除。所以查找要刪除結點時，一定要獲取前驅結點。若是雙向鏈表，就沒這個問題了。
跳表索引動態更新
當不停往跳表插入數據時，若不更新索引，就可能出現某2個索引結點之間數據非常多。極端情況下，跳表還會退化成單鏈表。
作為一種動態數據結構，我們需要某種手段來維護索引與原始鏈表大小之間的平衡，也就是說，如果鏈表中結點多了，索引結點就相應地增加一些，避免復雜度退化，以及查找、插入、刪除操作性能下降。
像紅黑樹、AVL樹這樣的平衡二叉樹通過左右旋保持左右子樹的大小平衡，而跳表是通過隨機函數維護前面提到的“平衡性”。
往跳表插入數據時，可以選擇同時將這個數據插入到部分索引層中。
那如何選擇加入哪些索引層呢？
通過一個隨機函數決定將這個結點插入到哪幾級索引中，比如隨機函數生成了值K，那就把這個結點添加到第一級到第K級這K級索引中。
為何Redis要用跳表來實現有序集合，而不是紅黑樹？
Redis中的有序集合支持的核心操作主要支持：
- 插入一個數據
- 刪除一個數據
- 查找一個數據
- 迭代輸出有序序列：以上操作，紅黑樹也能完成，時間復雜度跟跳表一樣。
- 按照區間查找數據：紅黑樹的效率低于跳表。跳表可以做到
O(logn)定位區間的起點，然后在原始鏈表順序往后遍歷即可。
除了性能，還有其它原因：
- 代碼實現比紅黑樹好懂、好寫多了，因為簡單就代表可讀性好，不易出錯
- 跳表更靈活，可通過改變索引構建策略，有效平衡執行效率和內存消耗
因為紅黑樹比跳表誕生更早，很多編程語言中的Map類型（比如JDK 的 HashMap）都是通過紅黑樹實現的。業務開發時，直接從JDK拿來用，但跳表沒有一個現成的實現，只能自己實現。
跳表的代碼實現（Java 版）
數據結構定義
表中的元素使用結點來表示，結點的層數在它被插入時隨機計算決定（與表中已有結點數目無關）。
一個i層的結點有i個前向指針（java中使用結點對象數組forward來表示），索引為從1到i。用MaxLevel來記錄跳表的最大層數。
跳表的層數為當前所有結點中的最大層數（如果list為空，則層數為1）。
列表頭header擁有從1到MaxLevel的前向指針：
public class SkipListT> {
// 最高層數
private final int MAX_LEVEL;
// 當前層數
private int listLevel;
// 表頭
private SkipListNodeT> listHead;
// 表尾
private SkipListNodeT> NIL;
// 生成randomLevel用到的概率值
private final double P;
// 論文里給出的最佳概率值
private static final double OPTIMAL_P = 0.25;
public SkipList() {
// 0.25, 15
this(OPTIMAL_P, (int)Math.ceil(Math.log(Integer.MAX_VALUE) / Math.log(1 / OPTIMAL_P)) - 1);
}
public SkipList(double probability, int maxLevel) {
P = probability;
MAX_LEVEL = maxLevel;
listLevel = 1;
listHead = new SkipListNodeT>(Integer.MIN_VALUE, null, maxLevel);
NIL = new SkipListNodeT>(Integer.MAX_VALUE, null, maxLevel);
for (int i = listHead.forward.length - 1; i >= 0; i--) {
listHead.forward[i] = NIL;
}
}
// 內部類
class SkipListNodeT> {
int key;
T value;
SkipListNode[] forward;
public SkipListNode(int key, T value, int level) {
this.key = key;
this.value = value;
this.forward = new SkipListNode[level];
}
}
}
搜索算法
按key搜索，找到返回該key對應的value，未找到則返回null。
通過遍歷forward數組來需找特定的searchKey。假設skip list的key按照從小到大的順序排列，那么從跳表的當前最高層listLevel開始尋找searchKey。在某一層找到一個非小于searchKey的結點后，跳到下一層繼續找，直到最底層為止。那么根據最后搜索停止位置的下一個結點，就可以判斷searchKey在不在跳表中。
在跳表中找8的過程：
插入和刪除算法
都是通過查找與連接（search and splice）：
維護一個update數組，在搜索結束之后，update[i]保存的是待插入/刪除結點在第i層的左側結點。
插入
若key不存在，則插入該key與對應的value；若key存在，則更新value。
如果待插入的結點的層數高于跳表的當前層數listLevel，則更新listLevel。
選擇待插入結點的層數randomLevel：
randomLevel只依賴于跳表的最高層數和概率值p。
另一種實現方法為，如果生成的randomLevel大于當前跳表的層數listLevel，那么將randomLevel設置為listLevel+1，這樣方便以后的查找，在工程上是可以接受的，但同時也破壞了算法的隨機性。
刪除
刪除特定的key與對應的value。如果待刪除的結點為跳表中層數最高的結點，那么刪除之后，要更新listLevel。
public class SkipListT> {
// 最高層數
private final int MAX_LEVEL;
// 當前層數
private int listLevel;
// 表頭
private SkipListNodeT> listHead;
// 表尾
private SkipListNodeT> NIL;
// 生成randomLevel用到的概率值
private final double P;
// 論文里給出的最佳概率值
private static final double OPTIMAL_P = 0.25;
public SkipList() {
// 0.25, 15
this(OPTIMAL_P, (int)Math.ceil(Math.log(Integer.MAX_VALUE) / Math.log(1 / OPTIMAL_P)) - 1);
}
public SkipList(double probability, int maxLevel) {
P = probability;
MAX_LEVEL = maxLevel;
listLevel = 1;
listHead = new SkipListNodeT>(Integer.MIN_VALUE, null, maxLevel);
NIL = new SkipListNodeT>(Integer.MAX_VALUE, null, maxLevel);
for (int i = listHead.forward.length - 1; i >= 0; i--) {
listHead.forward[i] = NIL;
}
}
// 內部類
class SkipListNodeT> {
int key;
T value;
SkipListNode[] forward;
public SkipListNode(int key, T value, int level) {
this.key = key;
this.value = value;
this.forward = new SkipListNode[level];
}
}
public T search(int searchKey) {
SkipListNodeT> curNode = listHead;
for (int i = listLevel; i > 0; i--) {
while (curNode.forward[i].key searchKey) {
curNode = curNode.forward[i];
}
}
if (curNode.key == searchKey) {
return curNode.value;
} else {
return null;
}
}
public void insert(int searchKey, T newValue) {
SkipListNodeT>[] update = new SkipListNode[MAX_LEVEL];
SkipListNodeT> curNode = listHead;
for (int i = listLevel - 1; i >= 0; i--) {
while (curNode.forward[i].key searchKey) {
curNode = curNode.forward[i];
}
// curNode.key searchKey = curNode.forward[i].key
update[i] = curNode;
}
curNode = curNode.forward[0];
if (curNode.key == searchKey) {
curNode.value = newValue;
} else {
int lvl = randomLevel();
if (listLevel lvl) {
for (int i = listLevel; i lvl; i++) {
update[i] = listHead;
}
listLevel = lvl;
}
SkipListNodeT> newNode = new SkipListNodeT>(searchKey, newValue, lvl);
for (int i = 0; i lvl; i++) {
newNode.forward[i] = update[i].forward[i];
update[i].forward[i] = newNode;
}
}
}
public void delete(int searchKey) {
SkipListNodeT>[] update = new SkipListNode[MAX_LEVEL];
SkipListNodeT> curNode = listHead;
for (int i = listLevel - 1; i >= 0; i--) {
while (curNode.forward[i].key searchKey) {
curNode = curNode.forward[i];
}
// curNode.key searchKey = curNode.forward[i].key
update[i] = curNode;
}
curNode = curNode.forward[0];
if (curNode.key == searchKey) {
for (int i = 0; i listLevel; i++) {
if (update[i].forward[i] != curNode) {
break;
}
update[i].forward[i] = curNode.forward[i];
}
while (listLevel > 0 listHead.forward[listLevel - 1] == NIL) {
listLevel--;
}
}
}
private int randomLevel() {
int lvl = 1;
while (lvl MAX_LEVEL Math.random() P) {
lvl++;
}
return lvl;
}
public void print() {
for (int i = listLevel - 1; i >= 0; i--) {
SkipListNodeT> curNode = listHead.forward[i];
while (curNode != NIL) {
System.out.print(curNode.key + "->");
curNode = curNode.forward[i];
}
System.out.println("NIL");
}
}
public static void main(String[] args) {
SkipListInteger> sl = new SkipListInteger>();
sl.insert(20, 20);
sl.insert(5, 5);
sl.insert(10, 10);
sl.insert(1, 1);
sl.insert(100, 100);
sl.insert(80, 80);
sl.insert(60, 60);
sl.insert(30, 30);
sl.print();
System.out.println("---");
sl.delete(20);
sl.delete(100);
sl.print();
}
}
到此這篇關于為何Redis使用跳表而非紅黑樹實現SortedSet的文章就介紹到這了,更多相關Redis跳表實現SortedSet內容請搜索腳本之家以前的文章或繼續瀏覽下面的相關文章希望大家以后多多支持腳本之家！
