常见索引结构—跳跃表
原文作者:JeemyJohn
原文地址:跳躍表的原理及實現
推薦閱讀:漫畫算法:什么是跳躍表?
1. 跳躍表的原理
??????學過數據結構的都知道,在單鏈表中查詢一個元素的時間復雜度為O(n),即使該單鏈表是有序的,我們也不能通過2分的方式縮減時間復雜度。?
??????如上圖,我們要查詢元素為55的結點,必須從頭結點,循環遍歷到最后一個節點,不算-INF(負無窮)一共查詢8次。那么用什么辦法能夠用更少的次數訪問55呢?最直觀的,當然是新開辟一條捷徑去訪問55。?
??????如上圖,我們要查詢元素為55的結點,只需要在L2層查找4次即可。在這個結構中,查詢結點為46的元素將耗費最多的查詢次數5次。即先在L2查詢46,查詢4次后找到元素55,因為鏈表是有序的,46一定在55的左邊,所以L2層沒有元素46。然后我們退回到元素37,到它的下一層即L1層繼續搜索46。非常幸運,我們只需要再查詢1次就能找到46。這樣一共耗費5次查詢。
那么,如何才能更快的搜尋55呢?有了上面的經驗,我們就很容易想到,再開辟一條捷徑。?
 ?
 ??????如上圖,我們搜索55只需要2次查找即可。這個結構中,查詢元素46仍然是最耗時的,需要查詢5次。即首先在L3層查找2次,然后在L2層查找2次,最后在L1層查找1次,共5次。很顯然,這種思想和2分非常相似,那么我們最后的結構圖就應該如下圖。
 ?
?
?????? 我們可以看到,最耗時的訪問46需要6次查詢。即L4訪問55,L3訪問21、55,L2訪問37、55,L1訪問46。我們直覺上認為,這樣的結構會讓查詢有序鏈表的某個元素更快。那么究竟算法復雜度是多少呢?
?????? 如果有n個元素,因為是2分,所以層數就應該是log n層 (本文所有log都是以2為底),再加上自身的1層。以上圖為例,如果是4個元素,那么分層為L3和L4,再加上本身的L2,一共3層;如果是8個元素,那么就是3+1層。最耗時間的查詢自然是訪問所有層數,耗時logn+logn,即2logn。為什么是2倍的logn呢?我們以上圖中的46為例,查詢到46要訪問所有的分層,每個分層都要訪問2個元素,中間元素和最后一個元素。所以時間復雜度為O(logn)。
?????? 至此為止,我們引入了最理想的跳躍表,但是如果想要在上圖中插入或者刪除一個元素呢?比如我們要插入一個元素22、23、24……,自然在L1層,我們將這些元素插入在元素21后,那么L2層,L3層呢?我們是不是要考慮插入后怎樣調整連接,才能維持這個理想的跳躍表結構。我們知道,平衡二叉樹的調整是一件令人頭痛的事情,左旋右旋左右旋……一般人還真記不住,而調整一個理想的跳躍表將是一個比調整平衡二叉樹還復雜的操作。幸運的是,我們并不需要通過復雜的操作調整連接來維護這樣完美的跳躍表。有一種基于概率統計的插入算法,也能得到時間復雜度為O(logn)的查詢效率,這種跳躍表才是我們真正要實現的。
2. 跳躍表的實現步驟分析
?????? 先討論插入,我們先看理想的跳躍表結構,L2層的元素個數是L1層元素個數的1/2,L3層的元素個數是L2層的元素個數的1/2,以此類推。從這里,我們可以想到,只要在插入時盡量保證上一層的元素個數是下一層元素的1/2,我們的跳躍表就能成為理想的跳躍表。那么怎么樣才能在插入時保證上一層元素個數是下一層元素個數的1/2呢?很簡單,拋硬幣就能解決了!假設元素X要插入跳躍表,很顯然,L1層肯定要插入X。那么L2層要不要插入X呢?我們希望上層元素個數是下層元素個數的1/2,所以我們有1/2的概率希望X插入L2層,那么拋一下硬幣吧,正面就插入,反面就不插入。那么L3到底要不要插入X呢?相對于L2層,我們還是希望1/2的概率插入,那么繼續拋硬幣吧!以此類推,元素X插入第n層的概率是(1/2)的n次。這樣,我們能在跳躍表中插入一個元素了。
在此還是以上圖為例:跳躍表的初試狀態如下圖,表中沒有一個元素:?
 ?
?
如果我們要插入元素2,首先是在底部插入元素2,如下圖:?
 ?
?
然后我們拋硬幣,結果是正面,那么我們要將2插入到L2層,如下圖:?
 ?
 繼續拋硬幣,結果是反面,那么元素2的插入操作就停止了,插入后的表結構就是上圖所示。接下來,我們插入元素33,跟元素2的插入一樣,現在L1層插入33,如下圖:?
 ?
?
然后拋硬幣,結果是反面,那么元素33的插入操作就結束了,插入后的表結構就是上圖所示。接下來,我們插入元素55,首先在L1插入55,插入后如下圖:?
 ?
?
然后拋硬幣,結果是正面,那么L2層需要插入55,如下圖:?
 ?
?
繼續拋硬幣,結果又是正面,那么L3層需要插入55,如下圖:?
 ?
?
?????? 以此類推,我們插入剩余的元素。當然因為規模小,結果很可能不是一個理想的跳躍表。但是如果元素個數n的規模很大,學過概率論的同學都知道,最終的表結構肯定非常接近于理想跳躍表。
?????? 當然,這樣的分析在感性上是很直接的,但是時間復雜度的證明實在復雜,在此我就不深究了,感興趣的可以去看關于跳躍表的paper。再討論刪除,刪除操作沒什么講的,直接刪除元素,然后調整一下刪除元素后的指針即可。跟普通的鏈表刪除操作完全一樣。再來討論一下時間復雜度,插入和刪除的時間復雜度就是查詢元素插入位置的時間復雜度,這不難理解,所以是O(logn)。
3. 代碼實現
在章節2中,我們采用拋硬幣的方式來決定新元素插入的最高層數,這當然不能在程序中實現。代碼中,我們采用隨機數生成的方式來獲取新元素插入的最高層數。我們先估摸一下n的規模,然后定義跳躍表的最大層數maxLevel,那么底層,也就是第0層,元素是一定要插入的,概率為1;最高層,也就是maxLevel層,元素插入的概率為1/2^maxLevel。
我們先隨機生成一個范圍為0~2^maxLevel-1的一個整數r。那么元素r小于2^(maxLevel-1)的概率為1/2,r小于2^(maxLevel-2)的概率為1/4,……,r小于2的概率為1/2^(maxLevel-1),r小于1的概率為1/2^maxLevel。
舉例,假設maxLevel為4,那么r的范圍為0~15,則r小于8的概率為1/2,r小于4的概率為1/4,r小于2的概率為1/8,r小于1的概率為1/16。1/16正好是maxLevel層插入元素的概率,1/8正好是maxLevel層插入的概率,以此類推。
通過這樣的分析,我們可以先比較r和1,如果r<1,那么元素就要插入到maxLevel層以下;否則再比較r和2,如果r<2,那么元素就要插入到maxLevel-1層以下;再比較r和4,如果r<4,那么元素就要插入到maxLevel-2層以下……如果r>2^(maxLevel - 1),那么元素就只要插入在底層即可。
以上分析是隨機數算法的關鍵。算法跟實現跟語言無關,但是Java程序員還是更容易看明白Java代碼實現的跳躍表,以下貼一下別人的java代碼實現。
/*************************** SkipList.java *********************/import java.util.Random;public class SkipList<T extends Comparable<? super T>> {private int maxLevel;private SkipListNode<T>[] root;private int[] powers;private Random rd = new Random();SkipList() {this(4);}SkipList(int i) {maxLevel = i;root = new SkipListNode[maxLevel];powers = new int[maxLevel];for (int j = 0; j < maxLevel; j++)root[j] = null;choosePowers();}public boolean isEmpty() {return root[0] == null;}public void choosePowers() {powers[maxLevel-1] = (2 << (maxLevel-1)) - 1; // 2^maxLevel - 1for (int i = maxLevel - 2, j = 0; i >= 0; i--, j++)powers[i] = powers[i+1] - (2 << j); // 2^(j+1)}public int chooseLevel() {int i, r = Math.abs(rd.nextInt()) % powers[maxLevel-1] + 1;for (i = 1; i < maxLevel; i++)if (r < powers[i])return i-1; // return a level < the highest level;return i-1; // return the highest level;}// make sure (with isEmpty()) that search() is called for a nonempty list;public T search(T key) { int lvl;SkipListNode<T> prev, curr; // find the highest nonnullfor (lvl = maxLevel-1; lvl >= 0 && root[lvl] == null; lvl--); // level;prev = curr = root[lvl];while (true) {if (key.equals(curr.key)) // success if equal;return curr.key;else if (key.compareTo(curr.key) < 0) { // if smaller, go down,if (lvl == 0) // if possiblereturn null; else if (curr == root[lvl]) // by one levelcurr = root[--lvl]; // starting from theelse curr = prev.next[--lvl]; // predecessor which} // can be the root;else { // if greater,prev = curr; // go to the nextif (curr.next[lvl] != null) // non-null nodecurr = curr.next[lvl]; // on the same levelelse { // or to a list on a lower level;for (lvl--; lvl >= 0 && curr.next[lvl] == null; lvl--);if (lvl >= 0)curr = curr.next[lvl];else return null;}}}}public void insert(T key) {SkipListNode<T>[] curr = new SkipListNode[maxLevel];SkipListNode<T>[] prev = new SkipListNode[maxLevel];SkipListNode<T> newNode;int lvl, i;curr[maxLevel-1] = root[maxLevel-1];prev[maxLevel-1] = null;for (lvl = maxLevel - 1; lvl >= 0; lvl--) {while (curr[lvl] != null && curr[lvl].key.compareTo(key) < 0) { prev[lvl] = curr[lvl]; // go to the nextcurr[lvl] = curr[lvl].next[lvl]; // if smaller;}if (curr[lvl] != null && key.equals(curr[lvl].key)) // don't return; // include duplicates;if (lvl > 0) // go one level downif (prev[lvl] == null) { // if not the lowestcurr[lvl-1] = root[lvl-1]; // level, using a linkprev[lvl-1] = null; // either from the root}else { // or from the predecessor;curr[lvl-1] = prev[lvl].next[lvl-1];prev[lvl-1] = prev[lvl];}}lvl = chooseLevel(); // generate randomly level newNode = new SkipListNode<T>(key,lvl+1); // for newNode;for (i = 0; i <= lvl; i++) { // initialize next fields ofnewNode.next[i] = curr[i]; // newNode and reset to newNodeif (prev[i] == null) // either fields of the rootroot[i] = newNode; // or next fields of newNode'selse prev[i].next[i] = newNode; // predecessors;}} }原文地址:https://blog.csdn.net/u013709270/article/details/53470428?
總結
以上是生活随笔為你收集整理的常见索引结构—跳跃表的全部內容,希望文章能夠幫你解決所遇到的問題。
 
                            
                        - 上一篇: Doug Cutting—访谈录
- 下一篇: 常见索引结构—B-树
