何為skiplist

一.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é)果都是這樣。