資訊專欄INFORMATION COLUMN
摘要：跳表分析通過上面的理解，你應該知道了跳表，其實就是通過建立多級索引來提升查找效率的一種數(shù)據(jù)結(jié)構(gòu)。一般的動態(tài)數(shù)據(jù)結(jié)構(gòu)都會維持平衡，保證插入查詢操作的性能不會下降。例如在中已經(jīng)有跳表的兩個實現(xiàn)類，分別是和，并且是線程安全的。
1. 概述
前面說到了二分查找，并且它是基于順序表結(jié)構(gòu)的，即數(shù)組，如果直接用于鏈表，時間復雜度會比較的高，是 O(logn)，一般我們不會這樣做。那么有沒有基于鏈表的二分查找呢？答案就是今天說到的跳躍鏈表。
2. 跳表長什么樣子？
對于一般的鏈表，我們進行查找的話，需要遍歷整個鏈表，就像下面這樣：如果我們要找節(jié)點 9 ，需要遍歷 9 個節(jié)點。
如果我們在原始鏈表之上建立一級鏈表，會是什么樣子呢？如下圖：
新建立的一級鏈表，我們叫做索引層或是索引，那么建立了一級索引之后，再來查找節(jié)點 9，會遍歷多少節(jié)點呢？我們從第一級索引中開始查找，到了節(jié)點 9 的時候，通過向下的指針，可以找到節(jié)點 9，總共遍歷了 6 個節(jié)點，相比沒有索引，查找的效率提高了。
這樣效果其實還不是非常的明顯，如果我們再加上幾級索引，查找會不會更快呢？
如上圖，總共建立了三級索引，現(xiàn)在查找節(jié)點 9 ，只需要遍歷 5 個節(jié)點了，查找的效率再一步提升了。其實，上面我舉的例子，總共只有 10 個節(jié)點，所以看不出來性能有多大的提升，但是在實際的開發(fā)中，存儲的數(shù)據(jù)成千上萬，那么跳表的效率就更能體現(xiàn)了。
3. 跳表分析
通過上面的理解，你應該知道了跳表，其實就是通過建立多級索引來提升查找效率的一種數(shù)據(jù)結(jié)構(gòu)。跳表的查詢時間復雜度是 O(logn)，跟二分查找一樣，空間復雜度是 O(n)，因為每一級建立的索引的節(jié)點個數(shù)都是上一級的一半，總共加起來就還需要原始鏈表的空間大小。
綜合分析，其實你已經(jīng)不能看到，跳表其實利用的是空間換時間的思想。
其實跳表不只是能夠在 O(logn) 內(nèi)查詢數(shù)據(jù)，并且也可以高效的插入和刪除數(shù)據(jù)，時間復雜度還是 O(logn)。
刪除操作其實很簡單，找到之后直接刪除節(jié)點即可。
插入操作也類似，因為整個鏈表是有序的，所以查找之后，直接插入。只不過這里涉及到一個動態(tài)更新的問題。一般的動態(tài)數(shù)據(jù)結(jié)構(gòu)都會維持平衡，保證插入查詢操作的性能不會下降。
例如跳表，假如沒有動態(tài)更新，則可能會出現(xiàn)插入之后，鏈表節(jié)點特別集中的問題：
在極端的情況下，跳表還是會退化為鏈表。
所以跳表借助了隨機函數(shù)這種方式來維持整個索引的平衡性，每插入一個節(jié)點，都會生成一個隨機函數(shù) k，然后不僅是在原始鏈表中插入這個節(jié)點，還會在 1-k 層索引中插入這個節(jié)點。
4. 跳表實現(xiàn)
跳表的具體實現(xiàn)其實還是比較復雜的，代碼理解起來比較的困難，這里我就不貼出來了，大家有興趣的可以到我的 Github 上面參考借鑒。點擊進入我的 Github
只不過我們也不用死扣跳表的代碼實現(xiàn)，在實際的開發(fā)環(huán)境中，我們能夠利用已有的實現(xiàn)就很不錯了，這就是避免重復造輪子。例如在 Java 中已經(jīng)有跳表的兩個實現(xiàn)類，分別是 ConcurrentSkipListSet 和 ConcurrentSkipListMap，并且是線程安全的。
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/73914.html
摘要：同時，也提供了一個基于的實現(xiàn)類，底層基于紅黑樹設計，是一種有序的?？梢钥闯墒遣l(fā)版本的，但是和不同是，并不是基于紅黑樹實現(xiàn)的，其底層是一種類似跳表的結(jié)構(gòu)。上述所有構(gòu)造器都調(diào)用了方法方法將一些字段置初始化，然后將指針指向新創(chuàng)建的結(jié)點。 showImg(https://segmentfault.com/img/remote/1460000016201159); 本文首發(fā)于一世流云專欄：ht...
摘要：跳表全稱叫做跳躍表，簡稱跳表。跳表在原有的有序鏈表上面增加了多級索引，通過索引來實現(xiàn)快速查找。跳表不僅能提高搜索性能，同時也可以提高插入和刪除操作的性能。每個節(jié)點包含兩個指針，一個指向同一鏈表中的下一個元素，一個指向下面一層的元素。 前言 增加了向前指針的鏈表叫作跳表。跳表全稱叫做跳躍表，簡稱跳表。跳表是一個隨機化的數(shù)據(jù)結(jié)構(gòu)，實質(zhì)就是一種可以進行二分查找的有序鏈表。跳表在原有的有序鏈表...
閱讀 891·2023-04-25 19:17
閱讀 2195·2021-09-10 11:26
閱讀 1908·2019-08-30 15:54
閱讀 3429·2019-08-30 15:53
閱讀 2688·2019-08-30 11:20
閱讀 3404·2019-08-29 15:12
閱讀 1238·2019-08-29 13:16
閱讀 2395·2019-08-26 12:19
