国产一区二区精品-国产一区二区精品久-国产一区二区精品久久-国产一区二区精品久久91-免费毛片播放-免费毛片基地

千鋒教育-做有情懷、有良心、有品質的職業教育機構

手機站
千鋒教育

千鋒學習站 | 隨時隨地免費學

千鋒教育

掃一掃進入千鋒手機站

領取全套視頻
千鋒教育

關注千鋒學習站小程序
隨時隨地免費學習課程

當前位置:首頁  >  技術干貨  > 為什么Redis一定要用跳表來實現有序集合?

為什么Redis一定要用跳表來實現有序集合?

來源:千鋒教育
發布人:xqq
時間: 2023-10-11 04:40:06 1696970406

一、為什么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),但比上面的每兩個結點抽一個結點的索引構建方法,要減少了一半的索引結點存儲空間。

實際上,在程序開發中,我們一般不必太在意索引占用的額外空間。因為當對象比索引結點大很多時,那索引占用的額外空間就可以忽略了。

聲明:本站稿件版權均屬千鋒教育所有,未經許可不得擅自轉載。
10年以上業內強師集結,手把手帶你蛻變精英
請您保持通訊暢通,專屬學習老師24小時內將與您1V1溝通
免費領取
今日已有369人領取成功
劉同學 138****2860 剛剛成功領取
王同學 131****2015 剛剛成功領取
張同學 133****4652 剛剛成功領取
李同學 135****8607 剛剛成功領取
楊同學 132****5667 剛剛成功領取
岳同學 134****6652 剛剛成功領取
梁同學 157****2950 剛剛成功領取
劉同學 189****1015 剛剛成功領取
張同學 155****4678 剛剛成功領取
鄒同學 139****2907 剛剛成功領取
董同學 138****2867 剛剛成功領取
周同學 136****3602 剛剛成功領取
相關推薦HOT