[[396177]]

今天我們來學(xué)一下數(shù)據(jù)結(jié)構(gòu)方面的知識，對扎實 Java 的基本功非常有用，學(xué)會了就會有一種自帶大佬的感覺，嘿嘿。數(shù)據(jù)結(jié)構(gòu)，也就是 Data Structure，是一種存儲數(shù)據(jù)的結(jié)構(gòu)體，數(shù)據(jù)與數(shù)據(jù)之間存在著一定的關(guān)系，這樣的關(guān)系有數(shù)據(jù)的邏輯關(guān)系、數(shù)據(jù)的存儲關(guān)系和數(shù)據(jù)的運算關(guān)系。

在 Java 中，數(shù)據(jù)結(jié)構(gòu)一般可以分為兩大類：線性數(shù)據(jù)結(jié)構(gòu)和非線性數(shù)據(jù)結(jié)構(gòu)。哈哈，這個非字很有靈魂吧？

先來說線性數(shù)據(jù)結(jié)構(gòu)吧。

1）數(shù)組

一眼看上去就知道的，像 String []、int [] 這種；還有需要看兩眼才能看透的（看源碼了），像 ArrayList，內(nèi)部對數(shù)組進行了封裝。

數(shù)組這種數(shù)據(jù)結(jié)構(gòu)最大的好處，就是可以根據(jù)下標（或者叫索引）進行操作，插入的時候可以根據(jù)下標直接插入到具體的位置，但與此同時，后面的元素就需要全部向后移動，需要移動的數(shù)據(jù)越多，就越累。

假設(shè)現(xiàn)在已經(jīng)有了一個 ArrayList 了，準備在第 4 個位置（下標為 3）上添加一個元素 55。

此時 ArrayList 中第 5 個位置以后的元素將會向后移動。

準備把 23 從 ArrayList 中移除。

此時下標為 7、8、9 的元素往前挪。

簡單總結(jié)一下 ArrayList 的時間復(fù)雜度，方便大家在學(xué)習的時候作為參考。

1、通過下標（也就是 get(int index)）訪問一個元素的時間復(fù)雜度為 O(1)，因為是直達的，無論數(shù)據(jù)增大多少倍，耗時都不變。

2、添加一個元素（也就是 add()）的時間復(fù)雜度為 O(1)，因為直接添加到末尾。

3、刪除一個元素的時間復(fù)雜度為 O(n)，因為要遍歷列表，數(shù)據(jù)量增大幾倍，耗時也增大幾倍。

4、查找一個未排序的列表時間復(fù)雜度為 O(n)，因為要遍歷列表；查找排序過的列表時間復(fù)雜度為 O(log n)，因為可以使用二分查找法，當數(shù)據(jù)增大 n 倍時，耗時增大 logn 倍（這里的 log 是以 2 為底的，每找一次排除一半的可能）。

2）鏈表

鏈表在物理存儲空間是不連續(xù)的，但每個節(jié)點要么知道它的下一個節(jié)點是誰，要么知道它的上一個節(jié)點是誰，仿佛就像我們之間隔著千山萬水，卻心有靈犀一點鏈。像 LinkedList 就是最典型的鏈表結(jié)構(gòu)，通過引用相互鏈接。

LinkedList 中的每一個元素都可以稱之為節(jié)點（Node），每一個節(jié)點都包含三個項目：其一是元素本身，其二是指向下一個元素的引用地址，其三是指向上一個元素的引用地址。

LinkedList 看起來就像下面這個樣子：

•   第一個節(jié)點由于沒有前一個節(jié)點，所以 prev 為 null；
•  最后一個節(jié)點由于沒有后一個節(jié)點，所以 next 為 null；
•  這是一個雙向鏈表，每一個節(jié)點都由三部分組成，前后節(jié)點和值。

相比 ArrayList，LinkedList 有以下優(yōu)勢：

1、LinkedList 允許內(nèi)存進行動態(tài)分配，這就意味著內(nèi)存分配是由編譯器在運行時完成的，我們無需在 LinkedList 聲明的時候指定大小。

2、LinkedList 不需要在連續(xù)的位置上存儲元素，因為節(jié)點可以通過引用指定下一個節(jié)點或者前一個節(jié)點。也就是說，LinkedList 在插入和刪除元素的時候代價很低，因為不需要移動其他元素，只需要更新前一個節(jié)點和后一個節(jié)點的引用地址即可。

3）棧

棧是一種非常有用的數(shù)據(jù)結(jié)構(gòu)，它就像一摞盤子，第一個放在最下面，第二個放在第一個上面，第三個放在第二個上面，最后一個放在最上面。棧遵循后進先出的原則，也就是“Last In First Out”（簡稱 LIFO）——最后的一個進的，最先出去。

對于棧這樣一個數(shù)據(jù)結(jié)構(gòu)來說，它有兩個常見的動作：

•  push，中文釋義有很多種，我個人更喜歡叫它“壓入”，非常形象。當我們要把一個數(shù)據(jù)放入棧的頂部，這個動作就叫做 push。
•  pop，同樣的，我個人更喜歡叫它“彈出”，帶有很強烈的動畫效果，有沒有？當我們要從棧中移除一個數(shù)據(jù)時，這個動作就叫做 pop。

4）隊列

隊列，只允許在隊尾添加數(shù)據(jù)，隊首移除數(shù)據(jù)。隊列在 Java 中的出現(xiàn)頻率非常高，有各種不同的類來滿足不同的場景需求。像優(yōu)先級隊列 PriorityQueue、延時隊列 DelayQueue 等等。隊列遵循的是 First In First Out，縮寫為 FIFO，也就是先進先出，第一個進入隊列的第一個先出來。

再來說非線性數(shù)據(jù)結(jié)構(gòu)。

1） 樹

樹是一種典型的非線性結(jié)構(gòu)，它是由 n（n>0）個有限節(jié)點組成的一個具有層次關(guān)系的集合。之所以叫“樹”，是因為這種數(shù)據(jù)結(jié)構(gòu)看起來就像是一個倒掛的樹，只不過根在上，葉在下。樹形數(shù)據(jù)結(jié)構(gòu)有以下這些特點：

•  每個節(jié)點都只有有限個子節(jié)點或無子節(jié)點；
•  沒有父節(jié)點的節(jié)點稱為根節(jié)點；
•  每一個非根節(jié)點有且只有一個父節(jié)點；
•  除了根節(jié)點外，每個子節(jié)點可以分為多個不相交的子樹。

下圖展示了樹的一些術(shù)語：

根節(jié)點是第 0 層，它的子節(jié)點是第 1 層，子節(jié)點的子節(jié)點為第 2 層，以此類推。

•  深度：對于任意節(jié)點 n，n 的深度為從根到 n 的唯一路徑長，根的深度為 0。
•  高度：對于任意節(jié)點 n，n 的高度為從 n 到一片樹葉的最長路徑長，所有樹葉的高度為 0。

樹又可以細分為下面幾種：

1、普通樹：對子節(jié)點沒有任何約束。

2、二叉樹：每個節(jié)點最多含有兩個子節(jié)點的樹。 二叉樹按照不同的表現(xiàn)形式又可以分為多種。

2.1、普通二叉樹：每個子節(jié)點的父節(jié)點不一定有兩個子節(jié)點的二叉樹。

2.2、完全二叉樹：對于一顆二叉樹，假設(shè)其深度為d（d>1）。除了第 d 層外，其它各層的節(jié)點數(shù)目均已達最大值，且第 d 層所有節(jié)點從左向右連續(xù)地緊密排列。

2.3、滿二叉樹：一顆每一層的節(jié)點數(shù)都達到了最大值的二叉樹。有兩種表現(xiàn)形式，第一種，像下圖這樣（每一層都是滿的），滿足每一層的節(jié)點數(shù)都達到了最大值 2。

3、二叉查找樹：英文名叫 Binary Search Tree，即 BST，需要滿足以下條件：

•  任意節(jié)點的左子樹不空，左子樹上所有節(jié)點的值均小于它的根節(jié)點的值；
•  任意節(jié)點的右子樹不空，右子樹上所有節(jié)點的值均大于它的根節(jié)點的值；
•  任意節(jié)點的左、右子樹也分別為二叉查找樹。

3.1、平衡二叉樹：當且僅當任何節(jié)點的兩棵子樹的高度差不大于 1 的二叉樹。由前蘇聯(lián)的數(shù)學(xué)家 Adelse-Velskil 和 Landis 在 1962 年提出的高度平衡的二叉樹，根據(jù)科學(xué)家的英文名也稱為 AVL 樹。

平衡二叉樹本質(zhì)上也是一顆二叉查找樹，不過為了限制左右子樹的高度差，避免出現(xiàn)傾斜樹等偏向于線性結(jié)構(gòu)演化的情況，所以對二叉搜索樹中每個節(jié)點的左右子樹作了限制，左右子樹的高度差稱之為平衡因子，樹中每個節(jié)點的平衡因子絕對值不大于 1。

平衡二叉樹的難點在于，當刪除或者增加節(jié)點的情況下，如何通過左旋或者右旋的方式來保持左右平衡。

紅黑樹是一種常見的平衡二叉樹，節(jié)點是紅色或者黑色，通過顏色的約束來維持著二叉樹的平衡：

•  每個節(jié)點都只能是紅色或者黑色
•  根節(jié)點是黑色
•   每個葉節(jié)點（NIL 節(jié)點，空節(jié)點）是黑色的。
•  如果一個節(jié)點是紅色的，則它兩個子節(jié)點都是黑色的。也就是說在一條路徑上不能出現(xiàn)相鄰的兩個紅色節(jié)點。
•  從任一節(jié)點到其每個葉子的所有路徑都包含相同數(shù)目的黑色節(jié)點。

4、B 樹：一種對讀寫操作進行優(yōu)化的自平衡的二叉查找樹，能夠保持數(shù)據(jù)有序，擁有多于兩個的子樹。

5、B+ 樹：B 樹的變體。

HashMap 里面的 TreeNode 就用到了紅黑樹，而 B 樹、B+ 樹在數(shù)據(jù)庫的索引原理里面有典型的應(yīng)用。

2）哈希表

哈希表（Hash Table），也叫散列表，是一種可以通過關(guān)鍵碼值（key-value）直接訪問的數(shù)據(jù)結(jié)構(gòu)，它最大的特點就是可以快速實現(xiàn)查找、插入和刪除。其中用到的算法叫做哈希，就是把任意長度的輸入，變換成固定長度的輸出，該輸出就是哈希值。像 MD5、SHA1 都用的是哈希算法。

每一個 Java 對象都會有一個哈希值，默認情況就是通過調(diào)用本地方法執(zhí)行哈希算法，計算出對象的內(nèi)存地址 + 對象的值的關(guān)鍵碼值。

數(shù)組的最大特點就是查找容易，插入和刪除困難；而鏈表正好相反，查找困難，而插入和刪除容易。哈希表很完美地結(jié)合了兩者的優(yōu)點， Java 的 HashMap 在此基礎(chǔ)上還加入了樹的優(yōu)點。

哈希表具有較快（常量級）的查詢速度，以及相對較快的增刪速度，所以很適合在海量數(shù)據(jù)的環(huán)境中使用。

對于任意兩個不同的數(shù)據(jù)塊，其哈希值相同的可能性極小，也就是說，對于一個給定的數(shù)據(jù)塊，找到和它哈希值相同的數(shù)據(jù)塊極為困難。再者，對于一個數(shù)據(jù)塊，哪怕只改動它的一個比特位，其哈希值的改動也會非常的大——這正是 Hash 存在的價值！

盡管可能性極小，但仍然會發(fā)生，如果哈希沖突了，Java 的 HashMap 會在數(shù)組的同一個位置上增加鏈表，如果鏈表的長度大于 8，將會轉(zhuǎn)化成紅黑樹進行處理——這就是所謂的拉鏈法（數(shù)組+鏈表）。

3）圖

圖是一種復(fù)雜的非線性結(jié)構(gòu)，由頂點的有窮非空集合和頂點之間邊的集合組成，通常表示為：G（V，E），其中，G 表示一個圖，V 是圖 G 中頂點的集合，E 是圖 G 中邊的集合。

上圖共有 V0，V1，V2，V3 這 4 個頂點，4 個頂點之間共有 5 條邊。

在線性結(jié)構(gòu)中，數(shù)據(jù)元素之間滿足唯一的線性關(guān)系，每個數(shù)據(jù)元素（除第一個和最后一個外）均有唯一的“前驅(qū)”和“后繼”；

在樹形結(jié)構(gòu)中，數(shù)據(jù)元素之間有著明顯的層次關(guān)系，并且每個數(shù)據(jù)元素只與上一層中的一個元素（父節(jié)點）及下一層的多個元素（子節(jié)點）相關(guān)；

而在圖形結(jié)構(gòu)中，節(jié)點之間的關(guān)系是任意的，圖中任意兩個數(shù)據(jù)元素之間都有可能相關(guān)。