一.skiplist簡介
跳表是由William Pugh發(fā)明。他在 Communications of the ACM June 1990, 33(6) 668-676 發(fā)表了Skip lists: a probabilistic alternative to balanced trees,在該論文中詳細(xì)解釋了跳表的數(shù)據(jù)結(jié)構(gòu)和插入刪除操作。跳躍表使用概率均衡技術(shù)而不是使用強(qiáng)制性均衡,因此,對(duì)于插入和刪除結(jié)點(diǎn)比傳統(tǒng)上的平衡樹算法更為簡潔高效。參考算法導(dǎo)論,跳表插入、刪除、查找的復(fù)雜度均為O(logN)。LevelDB的核心數(shù)據(jù)結(jié)構(gòu)是用跳表實(shí)現(xiàn)的,redis的sorted
set數(shù)據(jù)結(jié)構(gòu)也是用跳表實(shí)現(xiàn)的。
下面來研究一下跳表的核心思想:
先從鏈表開始,如果是一個(gè)單鏈表,那么我們知道在鏈表中查找一個(gè)元素I的話,需要將整個(gè)鏈表遍歷一次,時(shí)間復(fù)雜度為O(n)。
如果是說鏈表是排序的,并且結(jié)點(diǎn)中還存儲(chǔ)了指向后面第二個(gè)結(jié)點(diǎn)的指針的話,那么在查找一個(gè)結(jié)點(diǎn)時(shí),僅僅需要遍歷N/2個(gè)結(jié)點(diǎn)即可。因?yàn)槲覀兛梢韵韧ㄟ^每個(gè)結(jié)點(diǎn)最上面的指針先進(jìn)行查找,這樣子就能跳過一半的節(jié)點(diǎn)。比如我們想查找19,首先和6比較,大于6之后,在和9進(jìn)行比較,然后在和12進(jìn)行比較......最后比較到21的時(shí)候,發(fā)現(xiàn)21大于19,說明查找的點(diǎn)在17和21之間,從這個(gè)過程中,我們可以看出,查找的時(shí)候跳過了3、7、12等點(diǎn),因此查找的時(shí)間復(fù)雜度為O(n/2)(只是下圖的情況)。
其實(shí),上面基本上就是跳躍表的思想,每一個(gè)結(jié)點(diǎn)不單單只包含指向下一個(gè)結(jié)點(diǎn)的指針,可能包含很多個(gè)指向后續(xù)結(jié)點(diǎn)的指針,這樣就可以跳過一些不必要的結(jié)點(diǎn),從而加快查找、刪除等操作。對(duì)于一個(gè)鏈表內(nèi)每一個(gè)結(jié)點(diǎn)包含多少個(gè)指向后續(xù)元素的指針,這個(gè)過程是通過一個(gè)隨機(jī)函數(shù)生成器得到,這樣子就構(gòu)成了一個(gè)跳躍表。這就是為什么論文“Skip Lists : A Probabilistic Alternative to Balanced Trees ”中有“概率”的原因了,就是通過隨機(jī)生成一個(gè)結(jié)點(diǎn)中指向后續(xù)結(jié)點(diǎn)的指針數(shù)目。隨機(jī)生成的跳躍表可能如下圖所示。
如果一個(gè)結(jié)點(diǎn)存在k個(gè)指向后續(xù)元素指針的話,那么稱該結(jié)點(diǎn)是一個(gè)k層結(jié)點(diǎn)。一個(gè)跳表的層MaxLevel義為跳表中所有結(jié)點(diǎn)中最大的層數(shù)。跳表的所有操作均從上向下逐層進(jìn)行,越上層一次next操作的跨度越大。
二.skiplist原理
為了描述方便,將跳表結(jié)構(gòu)繪畫成如下形式。
跳表結(jié)構(gòu):
(1) 由多層結(jié)構(gòu)組成
(2) 每一層都是一個(gè)有序的鏈表
(3) 最底層(Level 1)的鏈表包含所有元素
(4) 如果一個(gè)元素出現(xiàn)在 Level i 的鏈表中,則它在 Level i 之下的鏈表也都會(huì)出現(xiàn)。
(5) 每個(gè)節(jié)點(diǎn)包含兩個(gè)指針,一個(gè)指向同一鏈表中的下一個(gè)元素,一個(gè)指向下面一層的元素。
1.跳表的查找
例子:查找元素 117
(1) 比較 21, 比 21 大,往后面找
(2) 比較 37, ? 比 37大,比鏈表最大值小,從 37 的下面一層開始找
(3) 比較 71, ?比 71 大,比鏈表最大值小,從 71 的下面一層開始找
(4) 比較 85, 比 85 大,從后面找
(5) 比較 117, 等于 117, 找到了節(jié)點(diǎn)。
2.跳表的插入
1)K小于鏈表的層數(shù)
先確定該元素要占據(jù)的層數(shù) K(采用丟硬幣的方式,這完全是隨機(jī)的),然后在 Level 1 ... Level K 各個(gè)層的鏈表都插入元素。
例子:插入 119, K = 2
2)K大于鏈表的層數(shù)
如果 K 大于鏈表的層數(shù),則要添加新的層。
例子:插入 119, K = 4
插入元素的時(shí)候,元素所占有的層數(shù)完全是隨機(jī)的,通過某種隨機(jī)算法產(chǎn)生。
3.跳表的刪除
在各個(gè)層中找到包含 x 的節(jié)點(diǎn),使用標(biāo)準(zhǔn)的 delete from list 方法刪除該節(jié)點(diǎn)。
例子:刪除 71
三.簡單的skiplist實(shí)現(xiàn)
#include#include#define?MAX_LEVEL?10?//最大層數(shù)?? //結(jié)點(diǎn) typedef??struct?nodeStructure { int?key; int?value; //指針數(shù)組 //定義?int?*p[n];[]優(yōu)先級(jí)高,先與p結(jié)合成為一個(gè)數(shù)組,再由int*說明這是一個(gè)整型指針數(shù)組,它有n個(gè)指針類型的數(shù)組元素。 //這里執(zhí)行p?+?1時(shí),則p指向下一個(gè)數(shù)組元素,這樣賦值是錯(cuò)誤的:p?=?a;因?yàn)閜是個(gè)不可知的表示,只存在p[0]、p[1]、p[2] //...p[n?-?1],?而且它們分別是指針變量可以用來存放變量地址。但可以這樣?*p?=?a;?這里*p表示指針數(shù)組第一個(gè)元素的值, //即a的首地址的值。 //這里定義了一個(gè)變長指針數(shù)組,數(shù)組中默認(rèn)只有一個(gè)元素nodeStructure*。使用變長數(shù)組(柔性數(shù)組)的目的是為了后續(xù)對(duì) //該數(shù)組擴(kuò)容,達(dá)到動(dòng)態(tài)分配內(nèi)存,節(jié)約空間的目的。 struct?nodeStructure?*next[1]; }nodeStructure; //跳表?? typedef??struct?skiplist { int?level; nodeStructure?*header; }skiplist; //創(chuàng)建結(jié)點(diǎn)? nodeStructure*?createNode(int?level,?int?key,?int?value) { //?nodeStructure::next是一個(gè)變長數(shù)組,額外分配時(shí)為什么是level-1倍呢??? //?因?yàn)檫@里是為了兼容性變長數(shù)組聲明為struct?nodeStructure?*next[1];(也可以用next[0],但是有些編譯器不支持)?? //?所以nodeStructure自身已經(jīng)占了一個(gè),再添加level-1個(gè)即可,如果是next[0]的話,就不能減一了。?? nodeStructure?*ns?=?(nodeStructure?*)malloc(sizeof(nodeStructure)?+?(level-1)*sizeof(nodeStructure*)); ns->key?=?key; ns->value?=?value; return?ns; } //初始化跳表?? skiplist*?createSkiplist() { skiplist?*sl?=?(skiplist?*)malloc(sizeof(skiplist)); sl->level?=?0; sl->header?=?createNode(MAX_LEVEL?,?0,?0); for?(int?i?=?0;?i?<?MAX_LEVEL;?i++) { sl->header->next[i]?=?NULL; } return?sl; } //隨機(jī)產(chǎn)生層數(shù)?? int?randomLevel() { int?k?=?1; while?(rand()?%?2) k++; k?=?(k?<?MAX_LEVEL)???k?:?MAX_LEVEL; return?k; } //插入節(jié)點(diǎn)?? bool?insert(skiplist?*sl,?int?key,?int?value) { nodeStructure?*update[MAX_LEVEL]; nodeStructure?*p,?*q?=?NULL; p?=?sl->header; int?k?=?sl->level; //這里還是查找插入位置階段,并未開始插入 //從最高層往下,每層都查找插入位置,當(dāng)遍歷到該層的尾部(p->next[i]==NULL) //也沒有找到比key大的結(jié)點(diǎn)時(shí),將該層的最后一個(gè)結(jié)點(diǎn)的指針放到update[i]中。 //如果在某層中找到了比key大或等于key的結(jié)點(diǎn)時(shí),將該結(jié)點(diǎn)之前的那個(gè)比key小的結(jié)點(diǎn)的指針 //放到update[i]中。 //這樣一來,參考(二.skiplist原理中的跳表插入章節(jié)圖),以插入119為例,因?yàn)榇藭r(shí)k暫時(shí)是最大層數(shù), //update[i]存放的是37、71和117所在結(jié)點(diǎn)的指針。 for?(int?i?=?k?-?1;?i?>=?0;?i--){ while?((q?=?p->next[i])?&&?(q->key?<?key)) { p?=?q; } update[i]?=?p; } //不能插入相同的key,這里排除掉了上述等于key的情況。 //此時(shí)q是第一層中的某個(gè)結(jié)點(diǎn)。 if?(q&&q->key?==?key) { return?false; } //產(chǎn)生一個(gè)隨機(jī)層數(shù)k?? k?=?randomLevel(); //更新跳表的level,這里假設(shè)k=sl->level+1,參考(二.skiplist原理中的跳表插入章節(jié)圖),以插入119為例, //update[3]應(yīng)該直接等于新增那層頭結(jié)點(diǎn)的指針,就像下面代碼寫的那樣。 if?(k?>?(sl->level)) { for?(int?i?=?sl->level;?i?<?k;?i++){ update[i]?=?sl->header; } sl->level?=?k; } //新建一個(gè)待插入結(jié)點(diǎn)q,從低到高一層層插入?? q?=?createNode(k,?key,?value); //逐層更新結(jié)點(diǎn)的指針,和普通鏈表插入一樣?? for?(int?i?=?0;?i?<?k;?i++) { q->next[i]?=?update[i]->next[i]; update[i]->next[i]?=?q; } return?true; } //搜索指定key的value?? int?search(skiplist?*sl,?int?key) { nodeStructure?*p,?*q?=?NULL; p?=?sl->header; //從最高層往下開始搜索? int?k?=?sl->level; for?(int?i?=?k?-?1;?i?>=?0;?i--){ while?((q?=?p->next[i])?&&?(q->key?key?==?key) { return?q->value; } p?=?q; } } return?NULL; } //刪除指定的key?? bool?deleteSL(skiplist?*sl,?int?key) { nodeStructure?*update[MAX_LEVEL]; nodeStructure?*p,?*q?=?NULL; p?=?sl->header; //從最高層往下開始搜索?? int?k?=?sl->level; for?(int?i?=?k?-?1;?i?>=?0;?i--){ while?((q?=?p->next[i])?&&?(q->key?<?key)) { p?=?q; } update[i]?=?p; } //這里和插入類似,只不過找到該結(jié)點(diǎn)后刪除 if?(q&&q->key?==?key) { //逐層刪除,和普通鏈表刪除一樣?? for?(int?i?=?0;?i?<?sl->level;?i++){ if?(update[i]->next[i]?==?q){ update[i]->next[i]?=?q->next[i]; } } free(q); //如果某些層只有被刪除的這個(gè)結(jié)點(diǎn),那么需要更新跳表的level?? for?(int?i?=?sl->level?-?1;?i?>=?0;?i--){ if?(sl->header->next[i]?==?NULL){ sl->level--; } } return?true; } else { return?false; } } //釋放跳表,雖然每個(gè)結(jié)點(diǎn)分了很多層,單歸根結(jié)底是一個(gè)結(jié)點(diǎn),所以和單鏈表的釋放是一樣的。 void?freeSL(skiplist?*sl) { if?(!sl) return; nodeStructure?*p,?*q?=?NULL; p?=?sl->header; while?(p) { q?=?p->next[0]; free(p); p?=?q; } free(sl); } void?printSL(skiplist?*sl) { //從最高層開始打印?? nodeStructure?*p,?*q?=?NULL; int?k?=?sl->level; for?(int?i?=?k?-?1;?i?>=?0;?i--) { p?=?sl->header; while?(1) { q?=?p->next[i]; printf("%d?->?",?p->value); p?=?q; if?(p==NULL) { break; } } printf("n"); } printf("n"); } int?main() { skiplist?*sl?=?createSkiplist(); printf("插入結(jié)點(diǎn):1<key=value<11n"); for?(int?i?=?1;?i?<?11;?i++) { insert(sl,?i,?i); } printSL(sl); //搜索?? printf("搜索key=3的valuen"); int?i?=?search(sl,?3); printf("搜索結(jié)果value=%dn",i); //刪除?? printf("刪除key=3的結(jié)點(diǎn)n"); bool?b?=?deleteSL(sl,?3); if?(b) { printf("刪除成功n"); } printSL(sl); freeSL(sl); system("pause"); return?0; }
運(yùn)行結(jié)果如下,由于K值得隨機(jī)性,并不是每次的運(yùn)行結(jié)果都是這樣。