一、為什么Redis一定要用跳表來實現有序集合
跳表的全稱是跳躍表,它的基礎是有序鏈表,在有序鏈表的基礎上,增加多級索引,實現快速查找。跳表的所有額外索引結點總數為 n2+n4+n8+…+4+2=n?2n2+n4+n8+…+4+2=n?2,所以跳表的空間復雜度為 O(n)O(n)。
用跳表查找效率到底可以提升多少
前面我講過,算法的執行效率可以通過時間復雜度來度量,這里依舊可以用。我們知道,在一個單鏈表中查詢某個數據的時間復雜度是 O(n)。那在一個具有多級索引的跳表中,查詢某個數據的時間復雜度是多少呢?
這里先來看一個問題,如果鏈表里有 n 個結點,會有多少級索引呢?
按照我們剛才講的,每兩個結點會抽出一個結點作為上一級索引的結點,那名列前茅級索引的結點個數大概就是 n/2,第二級索引的結點個數大約就是 n/4,第三級索引的結點個數大約就是 n/8,依次類推,也就是說,第 k 級索引的結點個數是第 k-1 級索引的結點個數的 1/2,那第 k 級索引結點的個數就是 n/(2k)。
假設索引有 h 級,較高級的索引有 2 個結點。通過上面的公式,我們可以得到 n/(2h)=2,從而求得 h=log2n-1。如果包含原始鏈表這一層,整個跳表的高度就是 log2n。
我們在跳表中查詢某個數據的時候,如果每一層都要遍歷 m 個結點,那在跳表中查詢一個數據的時間復雜度就是 O(m*logn)。那這個 m 的值是多少呢?按照前面這種索引結構,我們每一級索引都非常多只需要遍歷 3 個結點,也就是說 m=3,為什么是 3 呢?這里解釋一下:
假設我們要查找的數據是 x,在第 k 級索引中,我們遍歷到 y 結點之后,發現 x 大于 y,小于后面的結點 z,所以我們通過 y 的 down 指針,從第 k 級索引下降到第 k-1 級索引。在第 k-1 級索引中,y 和 z 之間只有 3 個結點(包含 y 和 z),所以,我們在 K-1 級索引中非常多只需要遍歷 3 個結點,依次類推,每一級索引都非常多只需要遍歷 3 個結點。通過上面的分析,我們得到 m=3,所以在跳表中查詢任意數據的時間復雜度就是 O(logn)。這個查找的時間復雜度跟二分查找是一樣的。換句話說,我們其實是基于單鏈表實現了二分查找,但是,有一個比較雞肋的地方就是:這種查詢效率的提升,前提是建立了很多級索引,即需要占用額外的內存空間。
延伸閱讀:
二、跳表內存使用情況
比起單純的單鏈表,跳表需要存儲多級索引,肯定要消耗更多的存儲空間。下面來看下跳表的空間復雜度。
假設原始鏈表大小為 n,那名列前茅級索引大約有 n/2 個結點,第二級索引大約有 n/4 個結點,以此類推,每上升一級就減少一半,直到剩下 2 個結點。如果我們把每層索引的結點數寫出來,就是一個等比數列。
原始鏈表大小為n,每2個節點取1個,則每層索引的節點數:n/2, n/4, n/8, … , 8, 4, 2。
這幾級索引的結點總和就是 n/2+n/4+n/8…+8+4+2=n-2。所以,跳表的空間復雜度是 O(n)。也就是說,如果將包含 n 個結點的單鏈表構造成跳表,我們需要額外再用接近 n 個結點的存儲空間。那我們有沒有辦法降低索引占用的內存空間呢?我們前面都是每兩個結點抽一個結點到上級索引,如果我們每三個結點或五個結點,抽一個結點到上級索引,這樣是不是就不用那么多索引結點了呢?
通過等比數列求和公式,總的索引結點大約就是 n/3+n/9+n/27+…+9+3+1=n/2。盡管空間復雜度還是 O(n),但比上面的每兩個結點抽一個結點的索引構建方法,要減少了一半的索引結點存儲空間。
實際上,在程序開發中,我們一般不必太在意索引占用的額外空間。因為當對象比索引結點大很多時,那索引占用的額外空間就可以忽略了。