? ??????【文章僅供非商業(yè)用途或交流學(xué)習(xí)使用】
? ? ? ? 最近研究Redis的相關(guān)內(nèi)容，發(fā)現(xiàn)SkipList跳表多次用到，在這里記錄一下。
? ? ? ? 一、跳表簡(jiǎn)介
????????SkipList（后面簡(jiǎn)稱SL）是一種支持快速查找的隨機(jī)化數(shù)據(jù)結(jié)構(gòu)，是一種可以進(jìn)行二分查找的有序鏈表。跳表在原有的有序鏈表上增加了多級(jí)索引，通過(guò)索引可以實(shí)現(xiàn)快速查找，不僅提高了搜索性能，同時(shí)也可以提高插入和刪除操作的性能。
? ? ? ? 二、數(shù)據(jù)結(jié)構(gòu)
? ? ? ? SL的主要設(shè)計(jì)思想是將鏈表與二分查找相結(jié)合，它維護(hù)了一個(gè)多層級(jí)的鏈表結(jié)構(gòu)，這是一個(gè)用空間換時(shí)間的思路。可以把SL看做是一個(gè)含有多個(gè)行的鏈表結(jié)合，并具有如下性質(zhì)：
? ? ? ? 1? SL由很多層組成；
? ? ? ? 2? 每一層都是一個(gè)有序的鏈表；
? ? ? ? 3? 最底層包含的連接包含所有元素；
? ? ? ? 4? 如果一個(gè)額元素出現(xiàn)在Level i 層的鏈表中，則它在level i 之下所有層的鏈表中都會(huì)出現(xiàn)；
? ? ? ? 5? 每個(gè)節(jié)點(diǎn)包含兩個(gè)指針，一個(gè)指向同一個(gè)鏈表中的下一個(gè)元素，一個(gè)指向下面一層的元素。
? ? ? ? 三、搜索方式
????????對(duì)一個(gè)目標(biāo)元素的搜索會(huì)從頂層鏈表的頭部元素開(kāi)始，然后遍歷該鏈表，直到找到元素大于或等于目標(biāo)元素的節(jié)點(diǎn)：
? ? ? ? 1? 如果當(dāng)前元素正好等于目標(biāo)，那么就直接返回它；
? ? ? ? 2? 如果當(dāng)前元素小于目標(biāo)元素，那么就跳到下一層繼續(xù)搜索；
? ? ? ? 3? 如果當(dāng)前元素大于目標(biāo)或到達(dá)鏈表尾部，則先移動(dòng)到前一個(gè)節(jié)點(diǎn)的位置，然后跳到下一層。
? ? ? ? 四、隨機(jī)產(chǎn)生的層
? ? ? ? SL具體產(chǎn)生多少層，是完全隨機(jī)的，業(yè)界最恰當(dāng)?shù)谋扔魇莵G硬幣，正面則將節(jié)點(diǎn)復(fù)制到上層，反面則停止。
? ? ? ? 參考文獻(xiàn)：
????????https://en.wikipedia.org/wiki/Skip_list
? ? ? ? https://baike.baidu.com/item/%E8%B7%B3%E8%A1%A8/22819833?fr=aladdin#6_1
