? ? ? ? 二分查找的底層依賴的是數(shù)組隨機(jī)訪問(wèn)的特性，那么如果數(shù)據(jù)存在鏈表中，我們就無(wú)法進(jìn)行二分查找了嗎？事實(shí)上是闊以滴。比如Redis就是通過(guò)跳表來(lái)實(shí)現(xiàn)的。它是一種各方面性能都比較優(yōu)秀的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，可以支持快速的插入、刪除、查找操作。但是紅黑樹也可以呀，哼，你跳表可以的，我紅黑樹也可以呢！
? ? ? ? 為什么Redis使用了跳表，而沒(méi)有用紅黑樹，繼續(xù)往下看~
? ? 1如何理解跳表
? ? ? ? 如下圖，對(duì)于一個(gè)單鏈表來(lái)說(shuō)，即便是最好的情況——它里面存儲(chǔ)的元素都是有序的，但是查找某一個(gè)元素也需要一個(gè)一個(gè)從頭到尾遍歷鏈表元素，直到找到它，時(shí)間復(fù)雜度是比較高的，要O(n)呢~這樣查找效率就比較低~
? ? ? ? 那么如何提高它的查找效率呢？我們可以采用提取索引的方式，每?jī)蓚€(gè)節(jié)點(diǎn)提取一個(gè)索引到上一級(jí)，我們把抽出來(lái)的那一級(jí)叫做索引或者索引層。其中down是指針，指向下一個(gè)索引~
? ? ? ? 現(xiàn)在我們要查找某一個(gè)節(jié)點(diǎn)，比如說(shuō)16，我們先遍歷索引節(jié)點(diǎn)1、4、7、9、13、17，發(fā)現(xiàn)13<16,17>16，此時(shí)就不用繼續(xù)往后遍歷索引，只需遍歷節(jié)點(diǎn)13與節(jié)點(diǎn)17之間的元素即可。原始鏈表按順序從頭到尾需要遍歷10個(gè)節(jié)點(diǎn)，提取索引之后我們只需遍歷7個(gè)節(jié)點(diǎn)就好啦。
????????上面我們只提取了一層索引，我們把它叫做一級(jí)索引。
? ? ? ? 我們?cè)诘谝患?jí)索引的基礎(chǔ)上，還可以提取出二級(jí)索引，如下圖：
? ? ? ? 這樣遍歷的節(jié)點(diǎn)個(gè)數(shù)就又變少啦。
? ? ? ? 我們這個(gè)例子中的數(shù)據(jù)量不大，可能看不出跳表的優(yōu)勢(shì)，實(shí)際上它在大數(shù)據(jù)量面前是非常高效滴。
? ? ? ? 比如下面畫了一個(gè)5級(jí)索引的圖：
? ? ? ? 顯而易見(jiàn)速度提高了灰常多。當(dāng)這個(gè)維度更大時(shí)，跳表的優(yōu)勢(shì)也更加明顯。
? ? ? ? 這種鏈表加多級(jí)索引的結(jié)構(gòu)，就是跳表。
? ? 2跳表查詢到底有多快？
? ? ? ? 衡量速度的標(biāo)準(zhǔn)當(dāng)然是時(shí)間復(fù)雜度啦。
? ? ? ? 下面我們來(lái)分析一下跳表的時(shí)間復(fù)雜度。
? ? ? ? 假設(shè)鏈表中有n個(gè)元素，那么一級(jí)索引有n/2個(gè)元素，二級(jí)索引有n/4個(gè)元素，三級(jí)索引有n/8個(gè)元素，依次類推，k級(jí)索引有n/2^k個(gè)元素。
? ? ? ? 假設(shè)索引一共有h級(jí)，最高級(jí)的索引有2個(gè)節(jié)點(diǎn)，那么n/2^h=2，log(2)n=h+1，h=log(2)n-1。如果包含原始鏈表層，我們的整個(gè)跳表高度就是log(2)n。
? ? ? ? 如果每一層要遍歷的節(jié)點(diǎn)個(gè)數(shù)是m，那么跳表中查詢一個(gè)元素的時(shí)間復(fù)雜度就是O（m*logn）。在這里，我們的m值為3。為啥是3捏？因?yàn)閺淖铐攲铀饕_始，最頂層索引只有2個(gè)，并且每?jī)蓚€(gè)索引之間（包括它自己）只有一共三個(gè)節(jié)點(diǎn)，所以當(dāng)然最多才是3啦?？梢詤⒖贾聢D來(lái)思考：
? ? ? ? 綜上，在跳表中查詢?nèi)我庠氐臅r(shí)間復(fù)雜度為O(logn)。這和二分查找是一樣噠。
? ? ? ? 但是，高的時(shí)間效率也是在其他方面有做犧牲的——空間。因?yàn)樗⒘嗽S多索引，需要額外的存儲(chǔ)空間，這就是空間換時(shí)間的設(shè)計(jì)思路。
? ? 3跳表是不是很浪費(fèi)內(nèi)存？
? ? ? ? 說(shuō)內(nèi)存，我們就要算一算時(shí)間復(fù)雜度啦。
? ? ? ? 第一層索引有n/2個(gè)，第二層有n/4個(gè)，依次類推，最后一層有2個(gè)：
????????我們把它們加起來(lái)，總和是n-2。所以，跳表的空間復(fù)雜度是O(n)。
? ? ? ? 我們也有辦法稍微降低一下存儲(chǔ)空間，隔3個(gè)、5個(gè)節(jié)點(diǎn)抽取一個(gè)索引。這樣空間復(fù)雜度得到了一些降低，而時(shí)間復(fù)雜度還是O(logn)。（因?yàn)橹皇菍從3換成了其他常數(shù)）
????????但是，在軟件開發(fā)中，我們不必太在意索引占用的額外空間。因?yàn)樵趯?shí)際開發(fā)中，原始鏈表中存儲(chǔ)的可能是很大的對(duì)象，而索引節(jié)點(diǎn)只需要存關(guān)鍵字和指針，當(dāng)對(duì)象比索引節(jié)點(diǎn)大很多的情況下時(shí)，索引占用的額外空間就可以忽略了。
? ? 4高效的動(dòng)態(tài)插入和刪除
? ? ? ? 跳表除了可以進(jìn)行高效的查找，也可以進(jìn)行高效的插入和刪除。
? ? ? ? 首先說(shuō)插入，很好理解，通過(guò)查找操作找到要插入的位置，時(shí)間復(fù)雜度是O(logn)，然后進(jìn)行插入操作，時(shí)間復(fù)雜度是O(1)，可忽略不計(jì)。所以插入的時(shí)間復(fù)雜度也是O(logn)。
? ? ? ? 然后是刪除，也是先通過(guò)查找操作找到要?jiǎng)h除的位置，不過(guò)這里注意我們還需要獲取刪除位置的前驅(qū)節(jié)點(diǎn)（雙向鏈表就無(wú)需額外考慮這個(gè)問(wèn)題啦），另外還要注意的是，如果這個(gè)元素在索引中出現(xiàn)了，我們也要將索引刪掉哦。刪除操作的時(shí)間復(fù)雜度也是O(logn)。
? ? 5跳表索引動(dòng)態(tài)更新
? ? ? ? 當(dāng)對(duì)鏈表進(jìn)行不斷的插入操作之后，就會(huì)出現(xiàn)這樣的情況，如下圖所示，兩個(gè)索引之間的元素變得非常多，甚至退化回了單鏈表：
? ? ? ? 跳表是通過(guò)動(dòng)態(tài)函數(shù)來(lái)維護(hù)這個(gè)平衡性的。
? ? ? ? 通過(guò)動(dòng)態(tài)函數(shù)生成一個(gè)隨機(jī)數(shù)K，在向鏈表中插入某個(gè)數(shù)時(shí)，同時(shí)也會(huì)將它插入第1-K層索引中去。從隨機(jī)概率的角度來(lái)講，這樣就維護(hù)了跳表的平衡性。如下圖所示：
? ? 6解答開篇
? ? ? ? 之所以Redis沒(méi)有用紅黑樹而用了跳表，是因?yàn)镽edis有一個(gè)按照區(qū)間查找數(shù)據(jù)的操作，通過(guò)跳表可以做到用O(logn)的時(shí)間復(fù)雜度找到區(qū)間的起點(diǎn)，然后依次往下遍歷就好啦，它的代碼實(shí)現(xiàn)相對(duì)紅黑樹更加好懂、好寫、可讀性好、不易出錯(cuò)（雖然跳表的實(shí)現(xiàn)也不簡(jiǎn)單，哼哼o(￣ヘ￣o＃)）。
? ? ? ? 當(dāng)然，跳表也不能完全取代紅黑樹啦。作為比跳表出現(xiàn)更早的紅黑樹，在很多編程語(yǔ)言中的Map類型都是通過(guò)紅黑樹來(lái)實(shí)現(xiàn)的，我們可以直接拿來(lái)用，如果用調(diào)表的話，我們需要自己實(shí)現(xiàn)。
? ? 7內(nèi)容小結(jié)
????????跳表使用空間換時(shí)間的設(shè)計(jì)思路，通過(guò)構(gòu)建多級(jí)索引來(lái)提高查詢的效率，實(shí)現(xiàn)了基于鏈表的“二分查找”。跳表是一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，支持快速的插入、刪除、查找操作，時(shí)間復(fù)雜度都是O(logn)。
? ? ? ? 跳表的空間復(fù)雜度是O(n)。不過(guò)跳表的實(shí)現(xiàn)非常靈活，可以通過(guò)改變索引構(gòu)建策略，有效平衡執(zhí)行效率和內(nèi)存消耗。雖然跳表的代碼實(shí)現(xiàn)并不簡(jiǎn)單，但是作為一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，比起紅黑樹來(lái)說(shuō)，實(shí)現(xiàn)要簡(jiǎn)單多啦。所以很多時(shí)候，我們?yōu)榱舜a的簡(jiǎn)單、易讀，比起紅黑樹，我們更傾向于鏈表。? ? ? ??
? ??????
? ??????
