問(wèn)題：如果數(shù)據(jù)存儲(chǔ)在鏈表中，就真的沒(méi)法用二分查找算法了嗎？可以對(duì)鏈表進(jìn)行“改造”，就可以支持類(lèi)似“二分”的查找算法。

跳表

定義：對(duì)鏈表經(jīng)過(guò)改造之后的數(shù)據(jù)結(jié)構(gòu)叫做跳表（Skip list），是一種各方面性能都比較優(yōu)秀的動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，

特點(diǎn)：

• 可以支持快速地插入、刪除、查找操作，甚至可以替代紅黑樹(shù)（Red-black tree）。
• Redis 中的有序集合（Sorted Set）就是用跳表來(lái)實(shí)現(xiàn)的。類(lèi)似的紅黑樹(shù)也可以實(shí)現(xiàn)快速地插入、刪除和查找操作

如何理解跳表？

1、原始的鏈表：查找效率很低，時(shí)間復(fù)雜度會(huì)很高，是 O(n)

2、改造：對(duì)鏈表建立一級(jí)“索引”，每?jī)蓚€(gè)結(jié)點(diǎn)提取一個(gè)結(jié)點(diǎn)到上一級(jí)，把抽出來(lái)的那一級(jí)叫做索引或索引層。圖中的 down 表示 down 指針，指向下一級(jí)結(jié)點(diǎn)。

此時(shí)查找結(jié)點(diǎn)16可以先遍歷第一級(jí)索引，找到結(jié)點(diǎn)13發(fā)現(xiàn)下一個(gè)結(jié)點(diǎn)17>16，然后我們通過(guò)索引層結(jié)點(diǎn)的 down 指針，下降到原始鏈表這一層，繼續(xù)遍歷。只需要再遍歷 2 個(gè)結(jié)點(diǎn)，就可以找到值等于 16的結(jié)點(diǎn)。依次類(lèi)推，繼續(xù)向上建立多級(jí)索引：

這種鏈表加多級(jí)索引的結(jié)構(gòu)，就是跳表。當(dāng)鏈表的長(zhǎng)度 n 比較大時(shí)，比如 1000、10000 的時(shí)候，在構(gòu)建索引之后，查找效率的提升就會(huì)非常明顯。

跳表查詢的時(shí)間復(fù)雜度

1、如果鏈表里有 n 個(gè)結(jié)點(diǎn)，會(huì)有多少級(jí)索引呢？每?jī)蓚€(gè)結(jié)點(diǎn)會(huì)抽出一個(gè)結(jié)點(diǎn)作為上一級(jí)索引的結(jié)點(diǎn)，那第一級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)大約就是 n/2，第二級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)大約就是 n/4，第三級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)大約就是 n/8，依次類(lèi)推，也就是說(shuō)，第 k 級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)是第 k-1 級(jí)索引的結(jié)點(diǎn)個(gè)數(shù)的 1/2，那第 k級(jí)索引結(jié)點(diǎn)的個(gè)數(shù)就是 n/(2k)。

2、假設(shè)索引有 h 級(jí)，最高級(jí)的索引有 2 個(gè)結(jié)點(diǎn)。通過(guò)上面的公式可以得到 n/(2h)=2，從而求得 h=log2n-1。如果包含原始鏈表這一層，整個(gè)跳表的高度就是 log2n。在跳表中查詢某個(gè)數(shù)據(jù)的時(shí)候，如果每一層都要遍歷 m 個(gè)結(jié)點(diǎn)，那在跳表中查詢一個(gè)數(shù)據(jù)的時(shí)間復(fù)雜度就是 O(m*logn)。

3、按照前面這種索引結(jié)構(gòu)，我們每一級(jí)索引都最多只需要遍歷 3 個(gè)結(jié)點(diǎn)，也就是說(shuō) m=3

解釋：假設(shè)我們要查找的數(shù)據(jù)是 x，在第 k 級(jí)索引中，我們遍歷到 y 結(jié)點(diǎn)之后，發(fā)現(xiàn) x 大于 y，小于后面的結(jié)點(diǎn) z，所以我們通過(guò) y 的 down 指針，從第 k 級(jí)索引下降到第 k-1 級(jí)索引。在第 k-1 級(jí)索引中，y 和 z 之間只有 3 個(gè)結(jié)點(diǎn)（包含 y 和 z），所以，我們?cè)?K-1 級(jí)索引中最多只需要遍歷 3 個(gè)結(jié)點(diǎn)，依次類(lèi)推，每一級(jí)索引都最多只需要遍歷 3 個(gè)結(jié)點(diǎn)。

4、跳表中查詢?nèi)我鈹?shù)據(jù)的時(shí)間復(fù)雜度就是 O(logn)。這個(gè)查找的時(shí)間復(fù)雜度跟二分查找是一樣的。基于單鏈表實(shí)現(xiàn)了二分查找，不過(guò)，這種查詢效率的提升前提是建立了很多級(jí)索引，使用到了空間換時(shí)間的設(shè)計(jì)思路。

跳表查詢的空間復(fù)雜度

假設(shè)原始鏈表大小為 n，那第一級(jí)索引大約有 n/2 個(gè)結(jié)點(diǎn)，第二級(jí)索引大約有 n/4 個(gè)結(jié)點(diǎn)，以此類(lèi)推，每上升一級(jí)就減少一半，直到剩下 2 個(gè)結(jié)點(diǎn)。這幾級(jí)索引的結(jié)點(diǎn)總和就是 n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空間復(fù)雜度是 O(n)。也就是說(shuō)，如果將包含 n 個(gè)結(jié)點(diǎn)的單鏈表構(gòu)造成跳表，我們需要額外再用接近 n 個(gè)結(jié)點(diǎn)的存儲(chǔ)空間。那如何降低索引占用的內(nèi)存空間呢？

如果我們每三個(gè)結(jié)點(diǎn)或五個(gè)結(jié)點(diǎn)，抽一個(gè)結(jié)點(diǎn)到上級(jí)索引，就可以減少空間占用。實(shí)際上，在軟件開(kāi)發(fā)中，我們不必太在意索引占用的額外空間。在講數(shù)據(jù)結(jié)構(gòu)和算法時(shí)，我們習(xí)慣性地把要處理的數(shù)據(jù)看成整數(shù)，但是在實(shí)際的軟件開(kāi)發(fā)中，原始鏈表中存儲(chǔ)的有可能是很大的對(duì)象，而索引結(jié)點(diǎn)只需要存儲(chǔ)關(guān)鍵值和幾個(gè)指針，并不需要存儲(chǔ)對(duì)象，所以當(dāng)對(duì)象比索引結(jié)點(diǎn)大很多時(shí)，那索引占用的額外空間就可以忽略了。

高效的動(dòng)態(tài)插入和刪除

1、對(duì)于跳表來(lái)說(shuō)，我們講過(guò)查找某個(gè)結(jié)點(diǎn)的時(shí)間復(fù)雜度是 O(logn)，所以這里查找某個(gè)數(shù)據(jù)應(yīng)該插入的位置，方法也是類(lèi)似的，時(shí)間復(fù)雜度也是 O(logn)

2、跳表的刪除操作除了要?jiǎng)h除原始鏈表中的結(jié)點(diǎn)，還要?jiǎng)h除索引中的。因?yàn)閱捂湵碇械膭h除操作需要拿到要?jiǎng)h除結(jié)點(diǎn)的前驅(qū)結(jié)點(diǎn)，然后通過(guò)指針操作完成刪除。所以在查找要?jiǎng)h除的結(jié)點(diǎn)的時(shí)候，一定要獲取前驅(qū)結(jié)點(diǎn)。當(dāng)然，如果我們用的是雙向鏈表，就不需要考慮這個(gè)問(wèn)題了

跳表索引動(dòng)態(tài)更新

當(dāng)我們不停地往跳表中插入數(shù)據(jù)時(shí)，如果我們不更新索引，就有可能出現(xiàn)某 2 個(gè)索引結(jié)點(diǎn)之間數(shù)據(jù)非常多的情況。極端情況下，跳表還會(huì)退化成單鏈表。

作為一種動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，需要某種手段來(lái)維護(hù)索引與原始鏈表大小之間的平衡。如果鏈表中結(jié)點(diǎn)多了，索引結(jié)點(diǎn)就相應(yīng)地增加一些，避免復(fù)雜度退化，以及查找、插入、刪除操作性能下降。紅黑樹(shù)、AVL 樹(shù)這樣平衡二叉樹(shù)是通過(guò)左右旋的方式保持左右子樹(shù)的大小平衡，而跳表是通過(guò)隨機(jī)函數(shù)來(lái)維護(hù)前面提到的“平衡性”。

1、當(dāng)我們往跳表中插入數(shù)據(jù)的時(shí)候，我們可以選擇同時(shí)將這個(gè)數(shù)據(jù)插入到部分索引層中。索引在垂直方向上也必須是一個(gè)完整的鏈表，如果一個(gè)數(shù)據(jù)在某一層索引中，那么它必須同時(shí)存在于所有的下級(jí)索引中

2、通過(guò)一個(gè)隨機(jī)函數(shù)，來(lái)決定將這個(gè)結(jié)點(diǎn)插入到哪幾級(jí)索引中。隨機(jī)函數(shù)生成了值 K，那我們就將這個(gè)結(jié)點(diǎn)添加到第一級(jí)到第 K 級(jí)這 K 級(jí)索引中

3、隨機(jī)函數(shù)的選擇很有講究，從概率上來(lái)講，能夠保證跳表的索引大小和數(shù)據(jù)大小平衡性，不至于性能過(guò)度退化

Redis 為什么用跳表來(lái)實(shí)現(xiàn)有序集合？

Redis 中的有序集合支持的核心操作主要有下面這幾個(gè)：

• 插入一個(gè)數(shù)據(jù)；
• 刪除一個(gè)數(shù)據(jù)；
• 查找一個(gè)數(shù)據(jù)；
• 按照區(qū)間查找數(shù)據(jù)（比如查找值在[100, 356]之間的數(shù)據(jù)）；
• 迭代輸出有序序列。

原因：

1、只有按照區(qū)間來(lái)查找數(shù)據(jù)這個(gè)操作，紅黑樹(shù)的效率沒(méi)有跳表高，其他的操作紅黑樹(shù)都可以完成。按照區(qū)間查找數(shù)據(jù)這個(gè)操作，跳表可以做到 O(logn) 的時(shí)間復(fù)雜度定位區(qū)間的起點(diǎn)，然后在原始鏈表中順序往后遍歷就可以了。這樣做非常高效。

2、相對(duì)于紅黑樹(shù)的代碼實(shí)現(xiàn)，跳表代碼實(shí)現(xiàn)更容易。雖然跳表的實(shí)現(xiàn)也不簡(jiǎn)單，但比起紅黑樹(shù)來(lái)說(shuō)還是好懂、好寫(xiě)多了，而簡(jiǎn)單就意味著可讀性好，不容易出錯(cuò)。

3、跳表更加靈活，它可以通過(guò)改變索引構(gòu)建策略，有效平衡執(zhí)行效率和內(nèi)存消耗。

總結(jié)

以上是生活随笔為你收集整理的17 | 跳表：为什么Redis一定要用跳表来实现有序集合？的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。