前言
跳表可以達(dá)到和紅黑樹(shù)一樣的時(shí)間復(fù)雜度 O(logN)，且實(shí)現(xiàn)簡(jiǎn)單，Redis 中的有序集合對(duì)象的底層數(shù)據(jù)結(jié)構(gòu)就使用了跳表。其作者威廉·普評(píng)價(jià)：跳躍鏈表是在很多應(yīng)用中有可能替代平衡樹(shù)的一種數(shù)據(jù)結(jié)構(gòu)。本篇文章將對(duì)跳表的實(shí)現(xiàn)及在Redis中的應(yīng)用進(jìn)行學(xué)習(xí)。
一. 跳表的基礎(chǔ)概念
跳表，即跳躍鏈表（Skip List），是基于并聯(lián)的鏈表數(shù)據(jù)結(jié)構(gòu)，操作效率可以達(dá)到O(logN)，對(duì)并發(fā)友好，跳表的示意圖如下所示。
跳表的特點(diǎn)，可以概括如下。
?跳表是多層（level）鏈表結(jié)構(gòu)；
?跳表中的每一層都是一個(gè)有序鏈表，并且按照元素升序（默認(rèn)）排列；
?跳表中的元素會(huì)在哪一層出現(xiàn)是隨機(jī)決定的，但是只要元素出現(xiàn)在了第 k 層，那么 k 層以下的鏈表也會(huì)出現(xiàn)這個(gè)元素；
?跳表的底層的鏈表包含所有元素；
?跳表頭節(jié)點(diǎn)和尾節(jié)點(diǎn)不存儲(chǔ)元素，且頭節(jié)點(diǎn)和尾節(jié)點(diǎn)的層數(shù)就是跳表的最大層數(shù)；
?跳表中的節(jié)點(diǎn)包含兩個(gè)指針，一個(gè)指針指向同層鏈表的后一節(jié)點(diǎn)，一個(gè)指針指向下層鏈表的同元素節(jié)點(diǎn)。
以上圖中的跳表為例，如果要查找元素 71，那么查找流程如下圖所示。
??從頂層鏈表的頭節(jié)點(diǎn)開(kāi)始查找，查找到元素71的節(jié)點(diǎn)時(shí)，一共遍歷了4個(gè)節(jié)點(diǎn)，但是如果按照傳統(tǒng)鏈表的方式（即從跳表的底層鏈表的頭節(jié)點(diǎn)開(kāi)始向后查找），那么就需要遍歷7個(gè)節(jié)點(diǎn)，所以跳表以空間換時(shí)間，縮短了操作跳表所需要花費(fèi)的時(shí)間。跳躍列表的算法有同平衡樹(shù)一樣的漸進(jìn)的預(yù)期時(shí)間邊界，并且更簡(jiǎn)單、更快速和使用更少的空間。這種數(shù)據(jù)結(jié)構(gòu)是由William Pugh(音譯為威廉·普)發(fā)明的，最早出現(xiàn)于他在1990年發(fā)表的論文《Skip Lists: A Probabilistic Alternative to Balanced Trees》。 谷歌上找到一篇作者關(guān)于跳表的論文，感興趣強(qiáng)烈建議下載閱讀：
?https://epaperpress.com/sortsearch/download/skiplist.pdf?
跳表在動(dòng)態(tài)查找過(guò)程中使用了一種非嚴(yán)格的平衡機(jī)制來(lái)讓插入和刪除都更加便利和快捷，這種非嚴(yán)格平衡是基于概率的，而不是平衡樹(shù)的嚴(yán)格平衡。說(shuō)到非嚴(yán)格平衡，首先想到的是紅黑樹(shù)RbTree，它同樣采用非嚴(yán)格平衡來(lái)避免像AVL那樣調(diào)整樹(shù)的結(jié)構(gòu)，這里就不展開(kāi)講紅黑樹(shù)了，看來(lái)跳表也是類似的路子，但是是基于概率實(shí)現(xiàn)的。
二. 跳表的節(jié)點(diǎn)
已知跳表中的節(jié)點(diǎn)，需要有指向當(dāng)前層鏈表后一節(jié)點(diǎn)的指針，和指向下層鏈表的同元素節(jié)點(diǎn)的指針，所以跳表中的節(jié)點(diǎn)，定義如下。
public class SkiplistNode {
public int data;
public SkiplistNode next;
public SkiplistNode down;
public int level;
public SkiplistNode(int data, int level) {
this.data = data;
this.level = level;
}上述是跳表中的節(jié)點(diǎn)的最簡(jiǎn)單的定義方式，存儲(chǔ)的元素 data 為整數(shù)，節(jié)點(diǎn)之間進(jìn)行比較時(shí)直接比較元素 data 的大小。
三. 跳表的初始化
跳表初始化時(shí)，將每一層鏈表的頭尾節(jié)點(diǎn)創(chuàng)建出來(lái)并使用集合將頭尾節(jié)點(diǎn)進(jìn)行存儲(chǔ)，頭尾節(jié)點(diǎn)的層數(shù)隨機(jī)指定，且頭尾節(jié)點(diǎn)的層數(shù)就代表當(dāng)前跳表的層數(shù)。初始化后，跳表結(jié)構(gòu)如下所示。
??跳表初始化的相關(guān)代碼如下所示。
public LinkedList<SkiplistNode> headNodes;
public LinkedList<SkiplistNode> tailNodes;
public int curLevel;
public Random random;
public Skiplist() {
random = new Random();
//headNodes用于存儲(chǔ)每一層的頭節(jié)點(diǎn)
headNodes = new LinkedList<>();
//tailNodes用于存儲(chǔ)每一層的尾節(jié)點(diǎn)
tailNodes = new LinkedList<>();
//初始化跳表時(shí)，跳表的層數(shù)隨機(jī)指定
curLevel = getRandomLevel();
//指定了跳表的初始的隨機(jī)層數(shù)后，就需要將每一層的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)創(chuàng)建出來(lái)并構(gòu)建好關(guān)系
SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, 0);
SkiplistNode tail = new SkiplistNode(Integer.MAX_VALUE, 0);
for (int i = 0; i <= curLevel; i++) {
head.next = tail;
headNodes.addFirst(head);
tailNodes.addFirst(tail);
SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);
SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);
headNew.down = head;
tailNew.down = tail;
head = headNew;
tail = tailNew;
}
}
四. 跳表的添加方法
每一個(gè)元素添加到跳表中時(shí)，首先需要隨機(jī)指定這個(gè)元素在跳表中的層數(shù)，如果隨機(jī)指定的層數(shù)大于了跳表的層數(shù)，則在將元素添加到跳表中之前，還需要擴(kuò)大跳表的層數(shù)，而擴(kuò)大跳表的層數(shù)就是將頭尾節(jié)點(diǎn)的層數(shù)擴(kuò)大。下面給出需要擴(kuò)大跳表層數(shù)的一次添加的過(guò)程。
初始狀態(tài)時(shí)，跳表的層數(shù)為 2，如下圖所示。
現(xiàn)在要往跳表中添加元素 120，并且隨機(jī)指定的層數(shù)為 3，大于了當(dāng)前跳表的層數(shù) 2，此時(shí)需要先擴(kuò)大跳表的層數(shù)，2如 下圖所示。
??將元素 120 插入到跳表中時(shí)，從頂層開(kāi)始，逐層向下插入，如下圖所示。
??跳表的添加方法的代碼如下所示。
public void add(int num) {
//獲取本次添加的值的層數(shù)
int level = getRandomLevel();
//如果本次添加的值的層數(shù)大于當(dāng)前跳表的層數(shù)
//則需要在添加當(dāng)前值前先將跳表層數(shù)擴(kuò)充
if (level > curLevel) {
expanLevel(level - curLevel);
}
//curNode表示num值在當(dāng)前層對(duì)應(yīng)的節(jié)點(diǎn)
SkiplistNode curNode = new SkiplistNode(num, level);
//preNode表示curNode在當(dāng)前層的前一個(gè)節(jié)點(diǎn)
SkiplistNode preNode = headNodes.get(curLevel - level);
for (int i = 0; i <= level; i++) {
//從當(dāng)前層的head節(jié)點(diǎn)開(kāi)始向后遍歷，直到找到一個(gè)preNode
//使得preNode.data < num <= preNode.next.data
while (preNode.next.data < num) {
preNode = preNode.next;
}
//將curNode插入到preNode和preNode.next中間
curNode.next = preNode.next;
preNode.next = curNode;
//如果當(dāng)前并不是0層，則繼續(xù)向下層添加節(jié)點(diǎn)
if (curNode.level > 0) {
SkiplistNode downNode = new SkiplistNode(num, curNode.level - 1);
//curNode指向下一層的節(jié)點(diǎn)
curNode.down = downNode;
//curNode向下移動(dòng)一層
curNode = downNode;
}
//preNode向下移動(dòng)一層
preNode = preNode.down;
}
}
private void expanLevel(int expanCount) {
SkiplistNode head = headNodes.getFirst();
SkiplistNode tail = tailNodes.getFirst();
for (int i = 0; i < expanCount; i++) {
SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);
SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);
headNew.down = head;
tailNew.down = tail;
head = headNew;
tail = tailNew;
headNodes.addFirst(head);
tailNodes.addFirst(tail);
}
}五. 跳表的搜索方法
在跳表中搜索一個(gè)元素時(shí)，需要從頂層開(kāi)始，逐層向下搜索。搜索時(shí)遵循如下規(guī)則。
?目標(biāo)值大于當(dāng)前節(jié)點(diǎn)的后一節(jié)點(diǎn)值時(shí)，繼續(xù)在本層鏈表上向后搜索；
?目標(biāo)值大于當(dāng)前節(jié)點(diǎn)值，小于當(dāng)前節(jié)點(diǎn)的后一節(jié)點(diǎn)值時(shí)，向下移動(dòng)一層，從下層鏈表的同節(jié)點(diǎn)位置向后搜索；
?目標(biāo)值等于當(dāng)前節(jié)點(diǎn)值，搜索結(jié)束。
?下圖是一個(gè)搜索過(guò)程的示意圖。
?跳表的搜索的代碼如下所示。
public boolean search(int target) {
//從頂層開(kāi)始尋找，curNode表示當(dāng)前遍歷到的節(jié)點(diǎn)
SkiplistNode curNode = headNodes.getFirst();
while (curNode != null) {
if (curNode.next.data == target) {
//找到了目標(biāo)值對(duì)應(yīng)的節(jié)點(diǎn)，此時(shí)返回true
return true;
} else if (curNode.next.data > target) {
//curNode的后一節(jié)點(diǎn)值大于target
//說(shuō)明目標(biāo)節(jié)點(diǎn)在curNode和curNode.next之間
//此時(shí)需要向下層尋找
curNode = curNode.down;
} else {
//curNode的后一節(jié)點(diǎn)值小于target
//說(shuō)明目標(biāo)節(jié)點(diǎn)在curNode的后一節(jié)點(diǎn)的后面
//此時(shí)在本層繼續(xù)向后尋找
curNode = curNode.next;
}
}
return false;
}六. 跳表的刪除方法
當(dāng)在跳表中需要?jiǎng)h除某一個(gè)元素時(shí)，則需要將這個(gè)元素在所有層的節(jié)點(diǎn)都刪除，具體的刪除規(guī)則如下所示。
?首先按照跳表的搜索的方式，搜索待刪除節(jié)點(diǎn)，如果能夠搜索到，此時(shí)搜索到的待刪除節(jié)點(diǎn)位于該節(jié)點(diǎn)層數(shù)的最高層；
?從待刪除節(jié)點(diǎn)的最高層往下，將每一層的待刪除節(jié)點(diǎn)都刪除掉，刪除方式就是讓待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)直接指向待刪除節(jié)點(diǎn)的后一節(jié)點(diǎn)。
?下圖是一個(gè)刪除過(guò)程的示意圖。
?跳表的刪除的代碼如下所示。
public boolean erase(int num) {
//刪除節(jié)點(diǎn)的遍歷過(guò)程與尋找節(jié)點(diǎn)的遍歷過(guò)程是相同的
//不過(guò)在刪除節(jié)點(diǎn)時(shí)如果找到目標(biāo)節(jié)點(diǎn)，則需要執(zhí)行節(jié)點(diǎn)刪除的操作
SkiplistNode curNode = headNodes.getFirst();
while (curNode != null) {
if (curNode.next.data == num) {
//preDeleteNode表示待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)
SkiplistNode preDeleteNode = curNode;
while (true) {
//刪除當(dāng)前層的待刪除節(jié)點(diǎn)，就是讓待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)指向待刪除節(jié)點(diǎn)的后一節(jié)點(diǎn)
preDeleteNode.next = curNode.next.next;
//當(dāng)前層刪除完后，需要繼續(xù)刪除下一層的待刪除節(jié)點(diǎn)
//這里讓preDeleteNode向下移動(dòng)一層
//向下移動(dòng)一層后，preDeleteNode就不一定是待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)了
preDeleteNode = preDeleteNode.down;
//如果preDeleteNode為null，說(shuō)明已經(jīng)將底層的待刪除節(jié)點(diǎn)刪除了
//此時(shí)就結(jié)束刪除流程，并返回true
if (preDeleteNode == null) {
return true;
}
//preDeleteNode向下移動(dòng)一層后，需要繼續(xù)從當(dāng)前位置向后遍歷
//直到找到一個(gè)preDeleteNode，使得preDeleteNode.next的值等于目標(biāo)值
//此時(shí)preDeleteNode就又變成了待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)
while (preDeleteNode.next.data != num) {
preDeleteNode = preDeleteNode.next;
}
}
} else if (curNode.next.data > num) {
curNode = curNode.down;
} else {
curNode = curNode.next;
}
}
return false;
}七. 跳表完整代碼
跳表完整代碼如下所示。
public class Skiplist {
public LinkedList<SkiplistNode> headNodes;
public LinkedList<SkiplistNode> tailNodes;
public int curLevel;
public Random random;
public Skiplist() {
random = new Random();
//headNodes用于存儲(chǔ)每一層的頭節(jié)點(diǎn)
headNodes = new LinkedList<>();
//tailNodes用于存儲(chǔ)每一層的尾節(jié)點(diǎn)
tailNodes = new LinkedList<>();
//初始化跳表時(shí)，跳表的層數(shù)隨機(jī)指定
curLevel = getRandomLevel();
//指定了跳表的初始的隨機(jī)層數(shù)后，就需要將每一層的頭節(jié)點(diǎn)和尾節(jié)點(diǎn)創(chuàng)建出來(lái)并構(gòu)建好關(guān)系
SkiplistNode head = new SkiplistNode(Integer.MIN_VALUE, 0);
SkiplistNode tail = new SkiplistNode(Integer.MAX_VALUE, 0);
for (int i = 0; i <= curLevel; i++) {
head.next = tail;
headNodes.addFirst(head);
tailNodes.addFirst(tail);
SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);
SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);
headNew.down = head;
tailNew.down = tail;
head = headNew;
tail = tailNew;
}
}
public boolean search(int target) {
//從頂層開(kāi)始尋找，curNode表示當(dāng)前遍歷到的節(jié)點(diǎn)
SkiplistNode curNode = headNodes.getFirst();
while (curNode != null) {
if (curNode.next.data == target) {
//找到了目標(biāo)值對(duì)應(yīng)的節(jié)點(diǎn)，此時(shí)返回true
return true;
} else if (curNode.next.data > target) {
//curNode的后一節(jié)點(diǎn)值大于target
//說(shuō)明目標(biāo)節(jié)點(diǎn)在curNode和curNode.next之間
//此時(shí)需要向下層尋找
curNode = curNode.down;
} else {
//curNode的后一節(jié)點(diǎn)值小于target
//說(shuō)明目標(biāo)節(jié)點(diǎn)在curNode的后一節(jié)點(diǎn)的后面
//此時(shí)在本層繼續(xù)向后尋找
curNode = curNode.next;
}
}
return false;
}
public void add(int num) {
//獲取本次添加的值的層數(shù)
int level = getRandomLevel();
//如果本次添加的值的層數(shù)大于當(dāng)前跳表的層數(shù)
//則需要在添加當(dāng)前值前先將跳表層數(shù)擴(kuò)充
if (level > curLevel) {
expanLevel(level - curLevel);
}
//curNode表示num值在當(dāng)前層對(duì)應(yīng)的節(jié)點(diǎn)
SkiplistNode curNode = new SkiplistNode(num, level);
//preNode表示curNode在當(dāng)前層的前一個(gè)節(jié)點(diǎn)
SkiplistNode preNode = headNodes.get(curLevel - level);
for (int i = 0; i <= level; i++) {
//從當(dāng)前層的head節(jié)點(diǎn)開(kāi)始向后遍歷，直到找到一個(gè)preNode
//使得preNode.data < num <= preNode.next.data
while (preNode.next.data < num) {
preNode = preNode.next;
}
//將curNode插入到preNode和preNode.next中間
curNode.next = preNode.next;
preNode.next = curNode;
//如果當(dāng)前并不是0層，則繼續(xù)向下層添加節(jié)點(diǎn)
if (curNode.level > 0) {
SkiplistNode downNode = new SkiplistNode(num, curNode.level - 1);
//curNode指向下一層的節(jié)點(diǎn)
curNode.down = downNode;
//curNode向下移動(dòng)一層
curNode = downNode;
}
//preNode向下移動(dòng)一層
preNode = preNode.down;
}
}
public boolean erase(int num) {
//刪除節(jié)點(diǎn)的遍歷過(guò)程與尋找節(jié)點(diǎn)的遍歷過(guò)程是相同的
//不過(guò)在刪除節(jié)點(diǎn)時(shí)如果找到目標(biāo)節(jié)點(diǎn)，則需要執(zhí)行節(jié)點(diǎn)刪除的操作
SkiplistNode curNode = headNodes.getFirst();
while (curNode != null) {
if (curNode.next.data == num) {
//preDeleteNode表示待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)
SkiplistNode preDeleteNode = curNode;
while (true) {
//刪除當(dāng)前層的待刪除節(jié)點(diǎn)，就是讓待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)指向待刪除節(jié)點(diǎn)的后一節(jié)點(diǎn)
preDeleteNode.next = curNode.next.next;
//當(dāng)前層刪除完后，需要繼續(xù)刪除下一層的待刪除節(jié)點(diǎn)
//這里讓preDeleteNode向下移動(dòng)一層
//向下移動(dòng)一層后，preDeleteNode就不一定是待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)了
preDeleteNode = preDeleteNode.down;
//如果preDeleteNode為null，說(shuō)明已經(jīng)將底層的待刪除節(jié)點(diǎn)刪除了
//此時(shí)就結(jié)束刪除流程，并返回true
if (preDeleteNode == null) {
return true;
}
//preDeleteNode向下移動(dòng)一層后，需要繼續(xù)從當(dāng)前位置向后遍歷
//直到找到一個(gè)preDeleteNode，使得preDeleteNode.next的值等于目標(biāo)值
//此時(shí)preDeleteNode就又變成了待刪除節(jié)點(diǎn)的前一節(jié)點(diǎn)
while (preDeleteNode.next.data != num) {
preDeleteNode = preDeleteNode.next;
}
}
} else if (curNode.next.data > num) {
curNode = curNode.down;
} else {
curNode = curNode.next;
}
}
return false;
}
private void expanLevel(int expanCount) {
SkiplistNode head = headNodes.getFirst();
SkiplistNode tail = tailNodes.getFirst();
for (int i = 0; i < expanCount; i++) {
SkiplistNode headNew = new SkiplistNode(Integer.MIN_VALUE, head.level + 1);
SkiplistNode tailNew = new SkiplistNode(Integer.MAX_VALUE, tail.level + 1);
headNew.down = head;
tailNew.down = tail;
head = headNew;
tail = tailNew;
headNodes.addFirst(head);
tailNodes.addFirst(tail);
}
}
private int getRandomLevel() {
int level = 0;
while (random.nextInt(2) > 1) {
level++;
}
return level;
}
}八. 跳表在Redis中的應(yīng)用
ZSet結(jié)構(gòu)同時(shí)包含一個(gè)字典和一個(gè)跳躍表，跳躍表按score從小到大保存所有集合元素。字典保存著從member到score的映射。這兩種結(jié)構(gòu)通過(guò)指針共享相同元素的member和score，不會(huì)浪費(fèi)額外內(nèi)存。
typedef struct zset {
dict *dict;
zskiplist *zsl;
} zset;ZSet中的字典和跳表布局：
1.ZSet中跳表的實(shí)現(xiàn)細(xì)節(jié)
隨機(jī)層數(shù)的實(shí)現(xiàn)原理：
跳表是一個(gè)概率型的數(shù)據(jù)結(jié)構(gòu)，元素的插入層數(shù)是隨機(jī)指定的。Willam Pugh在論文中描述了它的計(jì)算過(guò)程如下：指定節(jié)點(diǎn)最大層數(shù) MaxLevel，指定概率 p， 默認(rèn)層數(shù) lvl 為1；
生成一個(gè)0~1的隨機(jī)數(shù)r，若r<p，且lvl<MaxLevel ，則lvl ++；
重復(fù)第 2 步，直至生成的r >p 為止，此時(shí)的 lvl 就是要插入的層數(shù)。
論文中生成隨機(jī)層數(shù)的偽碼：
在Redis中對(duì)跳表的實(shí)現(xiàn)基本上也是遵循這個(gè)思想的，只不過(guò)有微小差異，看下Redis關(guān)于跳表層數(shù)的隨機(jī)源碼src/z_set.c：
/* Returns a random level for the new skiplist node we are going to create.
* The return value of this function is between 1 and ZSKIPLIST_MAXLEVEL
* (both inclusive), with a powerlaw-alike distribution where higher
* levels are less likely to be returned. */
int zslRandomLevel(void) {
int level = 1;
while ((random()&0xFFFF) < (ZSKIPLIST_P * 0xFFFF))
level += 1;
return (level<ZSKIPLIST_MAXLEVEL) ? level : ZSKIPLIST_MAXLEVEL;
}
其中兩個(gè)宏的定義在redis.h中：
#define ZSKIPLIST_MAXLEVEL 32 /* Should be enough for 2^32 elements */
#define ZSKIPLIST_P 0.25 /* Skiplist P = 1/4 */
可以看到while中的：
(random()&0xFFFF) < (ZSKIPLIST_P*0xFFFF)
第一眼看到這個(gè)公式，因?yàn)樯婕拔贿\(yùn)算有些詫異，需要研究一下Antirez為什么使用位運(yùn)算來(lái)這么寫？
最開(kāi)始的猜測(cè)是random()返回的是浮點(diǎn)數(shù)[0-1]，于是乎在線找了個(gè)浮點(diǎn)數(shù)轉(zhuǎn)二進(jìn)制的工具，輸入0.5看了下結(jié)果：
可以看到0.5的32bit轉(zhuǎn)換16進(jìn)制結(jié)果為0x3f000000，如果與0xFFFF做與運(yùn)算結(jié)果還是0，不符合預(yù)期。
實(shí)際應(yīng)用時(shí)對(duì)于隨機(jī)層數(shù)的實(shí)現(xiàn)并不統(tǒng)一，重要的是隨機(jī)數(shù)的生成，在LevelDB中對(duì)跳表層數(shù)的生成代碼是這樣的：
template <typename Key, typename Value>
int SkipList<Key, Value>::randomLevel() {
static const unsigned int kBranching = 4;
int height = 1;
while (height < kMaxLevel && ((::Next(rnd_) % kBranching) == 0)) {
height++;
}
assert(height > 0);
assert(height <= kMaxLevel);
return height;
}
uint32_t Next( uint32_t& seed) {
seed = seed & 0x7fffffffu;
if (seed == 0 || seed == 2147483647L) {
seed = 1;
}
static const uint32_t M = 2147483647L;
static const uint64_t A = 16807;
uint64_t product = seed * A;
seed = static_cast<uint32_t>((product >> 31) + (product & M));
if (seed > M) {
seed -= M;
}
return seed;
}
可以看到leveldb使用隨機(jī)數(shù)與kBranching取模，如果值為0就增加一層，這樣雖然沒(méi)有使用浮點(diǎn)數(shù)，但是也實(shí)現(xiàn)了概率平衡。
2.跳表結(jié)點(diǎn)的平均層數(shù)
我們很容易看出，產(chǎn)生越高的節(jié)點(diǎn)層數(shù)出現(xiàn)概率越低，無(wú)論如何層數(shù)總是滿足冪次定律越大的數(shù)出現(xiàn)的概率越小。
如果某件事的發(fā)生頻率和它的某個(gè)屬性成冪關(guān)系，那么這個(gè)頻率就可以稱之為符合冪次定律。
冪次定律的表現(xiàn)是少數(shù)幾個(gè)事件的發(fā)生頻率占了整個(gè)發(fā)生頻率的大部分， 而其余的大多數(shù)事件只占整個(gè)發(fā)生頻率的一個(gè)小部分。
冪次定律應(yīng)用到跳表的隨機(jī)層數(shù)來(lái)說(shuō)就是大部分的節(jié)點(diǎn)層數(shù)都是黃色部分，只有少數(shù)是綠色部分，并且概率很低。
定量的分析如下：
?節(jié)點(diǎn)層數(shù)至少為1，大于1的節(jié)點(diǎn)層數(shù)滿足一個(gè)概率分布。
?節(jié)點(diǎn)層數(shù)恰好等于1的概率為p^0(1-p)
?節(jié)點(diǎn)層數(shù)恰好等于2的概率為p^1(1-p)
?節(jié)點(diǎn)層數(shù)恰好等于3的概率為p^2(1-p)
?節(jié)點(diǎn)層數(shù)恰好等于4的概率為p^3(1-p)
依次遞推節(jié)點(diǎn)層數(shù)恰好等于K的概率為p^(k-1)(1-p)
因此如果我們要求節(jié)點(diǎn)的平均層數(shù)，那么也就轉(zhuǎn)換成了求概率分布的期望問(wèn)題了：
??表中P為概率，V為對(duì)應(yīng)取值，給出了所有取值和概率的可能，因此就可以求這個(gè)概率分布的期望了。方括號(hào)里面的式子其實(shí)就是高一年級(jí)學(xué)的等比數(shù)列，常用技巧錯(cuò)位相減求和，從中可以看到結(jié)點(diǎn)層數(shù)的期望值與1-p成反比。對(duì)于Redis而言，當(dāng)p=0.25時(shí)結(jié)點(diǎn)層數(shù)的期望是1.33。
總結(jié)
跳表的時(shí)間復(fù)雜度與AVL樹(shù)和紅黑樹(shù)相同，可以達(dá)到O(logN)，但是AVL樹(shù)要維持高度的平衡，紅黑樹(shù)要維持高度的近似平衡，這都會(huì)導(dǎo)致插入或者刪除節(jié)點(diǎn)時(shí)的一些時(shí)間開(kāi)銷，所以跳表相較于AVL樹(shù)和紅黑樹(shù)來(lái)說(shuō)，省去了維持高度的平衡的時(shí)間開(kāi)銷，但是相應(yīng)的也付出了更多的空間來(lái)存儲(chǔ)多個(gè)層的節(jié)點(diǎn)，所以跳表是用空間換時(shí)間的數(shù)據(jù)結(jié)構(gòu)。以Redis中底層的數(shù)據(jù)結(jié)構(gòu)zset作為典型應(yīng)用來(lái)展開(kāi)，進(jìn)一步看到跳躍鏈表的實(shí)際應(yīng)用。
