探索c#之跳躍表(SkipList)

閱讀目錄：

1. 基本介紹
2. 算法思想
3. 演化步驟
4. 實(shí)現(xiàn)細(xì)節(jié)
5. 總結(jié)

基本介紹

SkipList是William Pugh在1990年提出的，它是一種可替代平衡樹(shù)的數(shù)據(jù)結(jié)構(gòu)。 SkipList在實(shí)現(xiàn)上相對(duì)比較簡(jiǎn)單，比如在限定時(shí)間條件下，能非常輕松的實(shí)現(xiàn)SkipList，但卻實(shí)現(xiàn)不了B樹(shù)、紅黑樹(shù)、AVL樹(shù)等，想一想單B樹(shù)的刪除，就要考慮非常多的細(xì)節(jié)。雖說(shuō)SkipList簡(jiǎn)單，但性能卻非常高，在平均情況下，其插入、刪除、查找數(shù)據(jù)時(shí)間復(fù)雜度都是O(log(N))，其最壞情況下都為O(N)，這點(diǎn)要低于平衡樹(shù)。 SkipList依賴隨機(jī)生成數(shù)以一定概率來(lái)保持?jǐn)?shù)據(jù)在樹(shù)上的平衡分布，所以SkipList也屬于概率算性的數(shù)據(jù)結(jié)構(gòu)，和之前介紹的BoolFilter屬于一個(gè)類型C#之布隆過(guò)濾器(Bloom filter)。

算法思想

舉個(gè)例子，樓主逛完街要回張江玉蘭香苑，如果從人民廣場(chǎng)做公交車(chē)回去，要路過(guò)非常多的站：想想這么遠(yuǎn)的路程,多悲慘(在大數(shù)據(jù)情況下找對(duì)應(yīng)項(xiàng)同樣的問(wèn)題)，相較來(lái)說(shuō)坐地鐵就快很多，然后到廣蘭路換程。 這就是SkipList最核心的思想非常簡(jiǎn)單。 現(xiàn)在路線變成：

因?yàn)榭梢砸淮慰缭胶芏嗖恍枰恼荆跃涂炝撕芏唷Ｈ绻梢源钆笥秧橈L(fēng)車(chē)的話，變成：這個(gè)圖就非常接近SkipList的結(jié)構(gòu)及思想了。

演化步驟

大致了解怎么回事了、看具體怎么實(shí)現(xiàn)。 首先我們忘記樹(shù)、圖等高級(jí)概念及結(jié)構(gòu)，回到我們剛學(xué)到鏈表的時(shí)候。 再看上面的回家路線圖，我們把最下面一層當(dāng)成一個(gè)鏈表，每個(gè)節(jié)點(diǎn)(站)指針指向下一個(gè)節(jié)點(diǎn)(站)。單個(gè)有序鏈表：

按照傳統(tǒng)的操作有序鏈表的做法，如果需要查找其中一條數(shù)據(jù)，需要順序遍歷。 按照地鐵的思路，如果給一部分的節(jié)點(diǎn)增加個(gè)指向后面的節(jié)點(diǎn)指針，假設(shè)一半節(jié)點(diǎn)增加，最多遍歷[n/2]+1次即可找到任意節(jié)點(diǎn)。這里把18、23、33、40、47節(jié)點(diǎn)都多增加個(gè)指針指向后面的節(jié)點(diǎn)：

以此類推，繼續(xù)增加3、4個(gè)等更多的指針，使其指向更遠(yuǎn)的后方節(jié)點(diǎn)，這樣可以更好的提高查詢效率。 3個(gè)節(jié)點(diǎn)的情況：

如果理想情況下查找，就類似二分查找了。 SkipList通過(guò)隨機(jī)數(shù)(丟硬幣決定)在插入節(jié)點(diǎn)時(shí)，隨機(jī)判定該節(jié)點(diǎn)應(yīng)該有多少個(gè)執(zhí)行后續(xù)節(jié)點(diǎn)的指針。 有幾個(gè)執(zhí)行后面節(jié)點(diǎn)指針，就是在第幾層，比如上圖18存在3個(gè)指針指向后面，它就在第三層，23有2個(gè)指針就在第二層。

實(shí)現(xiàn)細(xì)節(jié)

搜索

在同一層查找節(jié)點(diǎn)時(shí)和普通有序鏈表一樣，順序向后查找，查到返回，否則進(jìn)入下一層繼續(xù)向后查找。比如查找35，會(huì)從最頂層搜索比較18、相等返回，大于比較40繼續(xù)下一層找，比較1、23、33、40后繼續(xù)下一層，比較33、35正確返回、否則不存在。

更新

搜索到值后更新：

        SkipListNode<TKey, TValue> position;        bool found = search(key, out position);        if(found)            position.value = value;

插入

插入時(shí)，如果值存在則更新，不存在插入。 如上圖，假如要插入29，需要先查找到27插入到后面，如果扔硬幣后得到3，那么依次增加指向后面節(jié)點(diǎn)的指針。

隨機(jī)數(shù)

也稱丟硬幣做法。

       Random generator = new Random();        int levels = 0;        while (generator.NextDouble() < 0.5&&levels<=maxlevel)            levels++;        return levels;

刪除同插入一樣，如果找到，調(diào)整相對(duì)應(yīng)的指針順序，然后刪除節(jié)點(diǎn)。

總結(jié)

由于skipList的高效及維護(hù)簡(jiǎn)單，所以很多大數(shù)據(jù)系統(tǒng)中在維護(hù)有序列表是都會(huì)使用SkipList。比如LevelDB在內(nèi)存中暫存數(shù)據(jù)的結(jié)構(gòu)MemTable是使用SkipList實(shí)現(xiàn)的，Redis在Sorted Set數(shù)據(jù)結(jié)構(gòu)時(shí)也采用的是SkipList，還有Lucene中同樣采用SkipList來(lái)對(duì)倒排列表進(jìn)行快速查找。

關(guān)于就算法的實(shí)現(xiàn)， 可參考https://github.com/kencausey/SkipList

探索C#之系列導(dǎo)航