溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
著名數據專家沃斯曾說：算法+數據結構=程序
今天我們就來講講數據結構
數組（Array）是一種 線性表數據結構。它用一組 連續的內存空間，來存儲一組具有 相同類型的數據。具有的特性：
數組為什么下標從0開始
容器能否完全替代數組？
例如Java的ArrayList，ArrayList 最大的優勢就是可以將很多數組操作的細節封裝起來。比如前面提到的數組插入、刪除數據時需要搬移其他數據等。另外，它還有一個優勢，就是支持動態擴容。
那么，作為高級語言編程者，是不是數組就無用武之地了呢？當然不是，有些時候，用數組會更合適些，總的來說，對于業務開發，直接使用容器就足夠了，省時省力。畢竟損耗一丟丟性能，完全不會影響到系統整體的性能。但如果你是做一些非常底層的開發，比如開發網絡框架，性能的優化需要做到極致，這個時候數組就會優于容器，成為首選。
不需要一塊連續的內存空間，它通過“指針”將一組零散的內存塊串聯起來使用。
幾種常見的鏈表形式： 1\. 單鏈表 2\. 循環鏈表 3\. 雙向鏈表 （空間換時間思想） 4\. 雙向循環列表
與數組的對比：
不過，數組和鏈表的對比，并不能局限于時間復雜度。而且，在實際的軟件開發中，不能僅僅利用復雜度分析就決定使用哪個數據結構來存儲數據。
寫鏈表代碼的幾個技巧： 1\. 理解指針或引用的含義、警惕指針丟失和內存泄漏 2\. 利用哨兵簡化實現難度 3\. 重點留意邊界條件處理 4\. 舉例畫圖、輔助思考 復制代碼
寫鏈表代碼是最考驗邏輯思維能力的。因為，鏈表代碼到處都是指針的操作、邊界條件的處理，稍有不慎就容易產生 Bug。鏈表代碼寫得好壞，可以看出一個人寫代碼是否夠細心，考慮問題是否全面，思維是否縝密。所以，這也是很多面試官喜歡讓人手寫鏈表代碼的原因。所以，這一節講到的東西，你一定要自己寫代碼實現一下，才有效果。
應用：
特點：先進先出
隊列拓展：
我們知道，數組支持快速的隨機訪問，而鏈表不支持，這樣的話，就不能用二分查找法來對鏈表進行快速查找。實際上，我們只需要對鏈表稍加改造，就可以支持類似“二分”的查找算法。我們把改造之后的數據結構叫作跳表（Skip list）。
跳表，其實就是對 有序鏈表建立多級“索引”，每兩個（也可以是其他數量）結點提取一個結點到上一級，我們把抽出來的那一級叫作索引或索引層。你可以看我畫的圖。圖中的 down 表示 down 指針，指向下一級結點。
如果我們現在要查找某個結點，比如 16。我們可以先在索引層遍歷，當遍歷到索引層中值為 13 的結點時，我們發現下一個結點是 17，那要查找的結點 16 肯定就在這兩個結點之間。然后我們通過索引層結點的 down 指針，下降到原始鏈表這一層，繼續遍歷。這個時候，我們只需要再遍歷 2 個結點，就可以找到值等于 16 的這個結點了。這樣，原來如果要查找 16，需要遍歷 10 個結點，現在只需要遍歷 7 個結點。
我舉的例子數據量不大，查找效率的提升也并不明顯。為了讓你能真切地感受索引提升查詢效率。我畫了一個包含 64 個結點的鏈表，按照前面講的這種思路，建立了五級索引。
從圖中我們可以看出，原來沒有索引的時候，查找 62 需要遍歷 62 個結點，現在只需要遍歷 11 個結點，速度是不是提高了很多？所以，當鏈表的長度 n 比較大時，比如 1000、10000 的時候，在構建索引之后，查找效率的提升就會非常明顯。
時間復雜度：
跳表查詢某個數據的時間復雜度是多少呢？
按照我們剛才講的，每兩個結點會抽出一個結點作為上一級索引的結點，那第一級索引的結點個數大約就是 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。
所以在跳表中查詢任意數據的時間復雜度就是 O(logn)。這個查找的時間復雜度跟二分查找是一樣的。換句話說，我們其實是基于單鏈表實現了二分查找，是不是很神奇？不過，天下沒有免費的午餐，這種查詢效率的提升，前提是建立了很多級索引，也就是我們在第 6 節講過的空間換時間的設計思路。
空間復雜度：
跳表是不是很浪費內存？比起單純的單鏈表，跳表需要存儲多級索引，肯定要消耗更多的存儲空間。那到底需要消耗多少額外的存儲空間呢？我們來分析一下跳表的空間復雜度。
跳表的空間復雜度分析并不難，我在前面說了，假設原始鏈表大小為 n，那第一級索引大約有 n/2 個結點，第二級索引大約有 n/4 個結點，以此類推，每上升一級就減少一半，直到剩下 2 個結點。如果我們把每層索引的結點數寫出來，就是一個等比數列。
這幾級索引的結點總和就是 n/2+n/4+n/8…+8+4+2=n-2。所以，跳表的空間復雜度是 O(n)。也就是說，如果將包含 n 個結點的單鏈表構造成跳表，我們需要額外再用接近 n 個結點的存儲空間。那我們有沒有辦法降低索引占用的內存空間呢？
我們前面都是每兩個結點抽一個結點到上級索引，如果我們每三個結點或五個結點，抽一個結點到上級索引，是不是就不用那么多索引結點了呢？
第一級索引需要大約 n/3 個結點，第二級索引需要大約 n/9 個結點。每往上一級，索引結點個數都除以 3。為了方便計算，我們假設最高一級的索引結點個數是 1。我們把每級索引的結點個數都寫下來，也是一個等比數列。
通過等比數列求和公式，總的索引結點大約就是 n/3+n/9+n/27+…+9+3+1=n/2。盡管空間復雜度還是 O(n)，但比上面的每兩個結點抽一個結點的索引構建方法，要減少了一半的索引結點存儲空間。
實際上，在軟件開發中，我們不必太在意索引占用的額外空間。在講數據結構和算法時，我們習慣性地把要處理的數據看成整數，但是在實際的軟件開發中，原始鏈表中存儲的有可能是很大的對象，而索引結點只需要存儲關鍵值和幾個指針，并不需要存儲對象， 所以當對象比索引結點大很多時，那索引占用的額外空間就可以忽略了。
跳表索引動態更新
當我們不停地往跳表中插入數據時，如果我們不更新索引，就有可能出現某 2 個索引結點之間數據非常多的情況。極端情況下，跳表還會退化成單鏈表。
作為一種動態數據結構，我們需要某種手段來維護索引與原始鏈表大小之間的平衡，也就是說，如果鏈表中結點多了，索引結點就相應地增加一些，避免復雜度退化，以及查找、插入、刪除操作性能下降。
當我們往跳表中插入數據的時候，我們可以選擇同時將這個數據插入到部分索引層中。如何選擇加入哪些索引層呢？
我們通過一個隨機函數，來決定將這個結點插入到哪幾級索引中，比如隨機函數生成了值 K，那我們就將這個結點添加到第一級到第 K 級這 K 級索引中。
隨機函數的選擇很有講究，從概率上來講，能夠保證跳表的索引大小和數據大小平衡性，不至于性能過度退化。
跳表特點：
特性：
散列沖突：
工業級水平的散列表：
最終要求：
具體設計方向：
散列表和鏈表的組合應用
LRU 緩存淘汰算法
借助散列表和鏈表，我們可以把 LRU 緩存淘汰算法的時間復雜度降低為 O(1)。
利用散列表，可以讓在鏈表里查找某個數據的時間復雜度為O(1)，而鏈表本身的刪除和插入操作時間復雜度為O(1)。
Redis 有序集合
舉個例子，比如用戶積分排行榜有這樣一個功能：我們可以通過用戶的 ID 來查找積分信息，也可以通過積分區間來查找用戶 ID 或者姓名信息。這里包含 ID、姓名和積分的用戶信息，就是成員對象，用戶 ID 就是 key，積分就是 score。
所以，如果我們細化一下 Redis 有序集合的操作，那就是下面這樣：
如果我們僅僅按照分值將成員對象組織成跳表的結構，那按照鍵值來刪除、查詢成員對象就會很慢，解決方法與 LRU 緩存淘汰算法的解決方法類似。我們可以再按照鍵值構建一個散列表，這樣按照 key 來刪除、查找一個成員對象的時間復雜度就變成了 O(1)。同時，借助跳表結構，其他操作也非常高效。
Java LinkedHashMap
如果你熟悉 Java，那你幾乎天天會用到這個容器。我們之前講過，HashMap 底層是通過散列表這種數據結構實現的。而 LinkedHashMap 前面比 HashMap 多了一個“Linked”，這里的“Linked”是不是說，LinkedHashMap 是一個通過鏈表法解決散列沖突的散列表呢？
實際上，LinkedHashMap 并沒有這么簡單，其中的“Linked”也并不僅僅代表它是通過鏈表法解決散列沖突的。
你可能已經猜到了，LinkedHashMap 也是通過散列表和鏈表組合在一起實現的。我們先看下面這段代碼：
// 10是初始大小，0.75是裝載因子，true是表示按照訪問時間排序HashMap<Integer, Integer> m = new LinkedHashMap<>(10, 0.75f, true);
m.put(3, 11);
m.put(1, 12);
m.put(5, 23);
m.put(2, 22);
m.put(3, 26);
m.get(5);for (Map.Entry e : m.entrySet()) {
System.out.println(e.getKey());
}
這段代碼打印的結果是 1，2，3，5。
其實，按照訪問時間排序的 LinkedHashMap 本身就是一個支持 LRU 緩存淘汰策略的緩存系統？實際上，它們兩個的實現原理也是一模一樣的。
總結一下，實際上， LinkedHashMap 是通過雙向鏈表和散列表這兩種數據結構組合實現的。LinkedHashMap 中的“Linked”實際上是指的是雙向鏈表，并非指用鏈表法解決散列沖突。
為什么散列表和鏈表經常一塊使用？
散列表這種數據結構雖然支持非常高效的數據插入、刪除、查找操作，但是散列表中的數據都是通過散列函數打亂之后無規律存儲的。也就說，它無法支持按照某種順序快速地遍歷數據。如果希望按照順序遍歷散列表中的數據，那我們需要將散列表中的數據拷貝到數組中，然后排序，再遍歷。
因為散列表是動態數據結構，不停地有數據的插入、刪除，所以每當我們希望按順序遍歷散列表中的數據的時候，都需要先排序，那效率勢必會很低。為了解決這個問題，我們將散列表和鏈表（或者跳表）結合在一起使用。
如果需要看視頻學習，可以看：
https://zhuanlan.zhihu.com/p/96130186
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
