幕布總結：思維導圖總結的數據結構，方便查看

文章目錄

• 一、開篇
• 二、常用的數據結構和算法
• 三、常用概念
• • 1、線性表
  • 2、動態數據結構
  • 3、什么是查詢
• 四、數組
• • 1、數組定義
  • 2、數組的優缺點
  • 3、數組怎么根據下標隨機訪問的？
  • 4、為何數組插入和刪除低效
  • 5.用數組還是容器？
  • • 什么是動態擴容？
    • 提高刪除效率：
  • 6、為什么數組要從 0 開始編號？
• 五、鏈表
• • 一、鏈表的定義
  • 二、鏈表的優缺點
  • 三、常用鏈表：單鏈表、循環鏈表和雙向鏈表
  • • 1.單鏈表
    • 2.循環鏈表
    • 3.雙向鏈表
    • 4.雙向循環鏈表
  • 四、數組和鏈表對比
  • 五、鏈表簡易代碼
• 六、棧
• • 一、棧的定義
  • 二、為什么需要棧？
  • 三、棧的簡易代碼
  • 四、棧的數組實現
  • 五、棧的鏈表實現
  • 六、棧的應用
  • • 1、棧在表達式求值中的應用
    • 2、實現瀏覽器的前進后退功能
• 七、隊列
• • 一、隊列的定義
  • 二、隊列的應用場景
  • • 1.阻塞隊列
    • 2.并發隊列
  • 三、順序隊列的數組實現
  • 四、鏈表實現簡易隊列
• 八、散列表
• • 一、散列表的定義
  • 二、散列沖突
  • • （1）什么是散列沖突
    • （2）散列沖突解決方法
    • • 1）開放尋址法
      • 2）鏈表法（更常用）
  • 三、動態擴容
  • • （1）為什么要動態擴容
    • （2）動態擴容導致插入效率低
    • （3）如何避免低效擴容？分批擴容
    • （4）分批擴容的查詢操作
• 九、樹
• • 一、樹的常用概念
  • 二、二叉樹
  • • （1）二叉樹
    • （2）滿二叉樹
    • （3）完全二叉樹
    • （4）二叉查找樹
  • 三、二叉樹的鏈式存儲
  • 四、二叉樹的順序存儲
  • 五、二叉樹的遍歷
• 十、二叉查找樹
• • 一、二叉查找樹的定義
  • 二、二叉查找樹的查找操作
  • 三、二叉查找樹的插入操作
  • 四、二叉查找樹的刪除操作
  • 五、簡易的刪除
  • 六、支持重復數據的二叉查找樹
  • • （1）每個結點存儲多個key相同的數據
    • （2）每個節點中存儲一個數據，相同的值存放在右子節點。
  • 七、二叉查找樹的極端情況
• 十一、平衡二叉查找樹之紅黑樹
• • 一、紅黑樹的定義
  • • （1）為什么使用紅黑樹
  • 二、平衡二叉查找樹
  • （1）AVL 樹
  • （2）紅黑樹
• 十二、堆
• • 1、堆的定義
  • 2、實現堆
  • 3、往堆中插入元素
  • • （1）從下往上堆化
    • （2）刪除堆頂元素，從上往下堆化
  • 4、基于堆實現排序
  • • （1）如何建堆
    • （2）排序
• 十三、跳表
• • 一、跳表的定義
  • 二、計算跳表的時間復雜度
  • • （1）計算跳表的高度
    • （2）計算跳表的時間復雜度
    • （3）跳表的空間復雜度
  • 三、跳表插入
  • • （1）鏈表插入
    • （2）跳表插入
  • 四、跳表索引動態更新
  • 五、代碼
• 十四、圖
• • 一、圖的定義
  • • （1）帶權圖
  • 二、鄰接矩陣
  • • （1）鄰接矩陣缺點
  • 三、鄰接表存儲方法
  • • （1）鄰接矩陣和鄰接表的區別
  • 四、逆鄰接表
  • 五、存儲大數據
  • • （1）數據分片
    • （2）數據庫存儲
• 十五、Trie樹
• • 一、搜索引擎的搜索關鍵詞提示功能
  • 二、Trie 樹的定義
  • 三、Trie樹的存儲
  • 四、Trie樹的時間復雜度
  • 五、Trie樹的空間復雜度
  • 六、總結
• 十六、HashMap
• 十七、LinkedHashMap
• • 一、LinkedHashMap實現
  • 二、LRU算法
• 十八、HashMap、HashTable和ConcurrentHashMap
• • 1、Hashmap
  • 2、Hashtable
  • 3、ConcurrentHashMap
  • • 分段鎖
    • JDK1.8采用CAS

From-周鑫

一、開篇

數據結構廣義上講就是數據的存儲結構，算法是操作數據的方法。
數據結構是為算法服務的，算法只能作用在特定的數據結構之上。比如二分查找，如果我們選擇鏈表這種數據結構，就無法進行二分查找。因為鏈表不支持隨機訪問。

二、常用的數據結構和算法

常用的數據結構：數組、鏈表、棧、隊列、散列表、二叉樹、堆、跳表、圖、Trie 樹；

算法：遞歸、排序、二分查找、搜索、哈希算法、貪心算法、分治算法、回溯算法、動態規劃、字符串匹配算法。

|數據結構|簡介|
|:----|:----|:----|
|數組|數組是一種線性數據結構，它是一組連續的內存空間，數組可以存儲各種數據類型，但是一個數組中只能存儲同一種數據類型。
優點：查詢快，時間復雜度是O(1)（根據首地址和下標通過尋址方式來計算出該元素的內存地址）；
缺點：插入刪除慢，時間復雜度是O(n)。為了保證內存的連續性，我們插入或者刪除數據的時候，要進行數據遷移。
試用場景：數據規模較小，不經常變動。|
|鏈表|鏈表中的每一個內存塊被稱為節點Node。節點除了存儲數據外，還需記錄鏈上下一個節點的地址，即后繼指針next。通過next將一組零散的內存塊串聯起來的線性數據結構。
優點：插入、刪除的時間復雜度是O(1)（只需更改指針指向即可）；
缺點：
1）隨機訪問查詢效率低，時間復雜端是O(n)（需要從鏈頭進行遍歷）；
2）內存空間消耗更大，因為需要額外的空間存儲指針信息。
3）對鏈表進行頻繁的插入和刪除操作，會導致頻繁的內存申請和釋放，容易造成內存碎片，如果是Java語言，還可能會造成頻繁的GC（自動垃圾回收器）操作。
適用場景：適用于順序訪問數據，數據維護較頻繁的場合。
應用：鏈表實現 LRU 緩存淘汰算法
分類：單鏈表、循環鏈表、雙向鏈表、雙向循環鏈表|
|棧|棧是一種“操作受限”的線性表，只允許在端插入和刪除數據。先進者后出，后進者先出。
應用場景：表達式的應用、頁面的前進后退。|
|隊列|隊列是操作受限的線性表，先進者先出。支持兩個操作入隊和出隊。
應用場景：線程池。|
|散列表|散列表來源于數組，它利用的是數組支持按照下標隨機訪問元素的特性。我們把key，通過hash函數計算得到hash值，hash值作為數組的下標。然后把key和key綁定的數據（我們稱為value）存儲在hash值對應的數組下標位置。需要設計一個好的hash函數，把元素均勻分散到散列表中。
優點：散列表的插入、刪除、查找操作的時間復雜度O(1)。
缺點：
1）散列表中的數據是無序存儲的，如果要輸出有序的數據，需要先進行排序。
2）散列表有散列沖突，對散列函數要求很高。解決散列沖突：開放尋址方法和鏈表法。
3）散列表需要進行動態擴容或縮容。設置裝載因子，當裝載因子到達閾值時，先進行擴容。不進行數據遷移，當有新數據插入時，我們將新數據插入到散列表中，然后從老散列表取出一個放入到新散列表中。多次插入操作，老散列表的數據會一點點搬移到新散列表中了。查詢的時候，先查新散列表后查老散列表。
4）散列表的查找等操作的時間復雜度是常量級的，但因為哈希沖突的存在，和哈希函數的耗時，所以查找時間復雜度不穩定。
適用場景：適用于不需要順序遍歷，在海量數據中隨機訪問數據的場合。|
|跳表|為一個值有序的鏈表建立多級索引，比如每2個節點提取一個節點到上一級，我們把抽出來的那一級叫做索引或索引層。為鏈表建立多級索引的數據結構就稱為跳表。
優點：插入刪除查找都是O(logn), 并且能順序遍歷（因為基于鏈表）。
缺點：需要額外的空間來構建索引鏈表。空間復雜度
適用場景：對有序元素的快速查找、插入和刪除。|
|二叉樹|二叉樹：每個節點最多只有2個子節點的樹，這兩個節點分別是左子節點和右子節點。有滿二叉樹、完全二叉樹等。
二叉樹的鏈式存儲：每個節點由3個字段，其中一個存儲數據，另外兩個是指向左右子節點的指針。遍歷：分前中后序三種遍歷。|
|二叉查找樹|二叉查找樹要求，在樹中的任意一個節點，其左子樹中的每個節點的值，都要小于這個節點的值，而右子樹節點的值都大于這個節點的值。最大的特點就是，支持動態數據集合的快速插入、刪除、查找操作。
二叉查找樹，有兩種極端情況。分別是二叉查找樹退化成鏈表的情況和完全二叉樹。
如果輸出有序的數據，對于二叉查找樹來說，我們只需要中序遍歷，就可以在 O(n) 的時間復雜度內，輸出有序的數據序列。|
|紅黑樹|紅黑樹定義：二叉樹中任意一個節點的左右子樹的高度相差不能大于 1。并且在樹中的任意一個節點，其左子樹中的每個節點的值，都要小于這個節點的值，而右子樹節點的值都大于這個節點的值。
紅黑樹是一種平衡二叉查找樹。它是為了解決普通二叉查找樹在數據更新的過程中，復雜度退化的問題而產生的。雖然相比高度平衡的AVL樹效率有所下降，但是紅黑樹不用耗費太多精力維護平衡。紅黑樹的高度近似 log2n，所以它是近似平衡，插入、刪除、查找操作的時間復雜度都是 O(logn)，中序遍歷即是順序遍歷。相比跳表，紅黑樹除了內存占用較小，其他性能并不比跳表更優。|
|Trie樹|搜索引擎的搜索關鍵詞提示功能，當你在搜索引擎的搜索框中，輸入要搜索的文字的某一部分的時候，搜索引擎就會自動彈出下拉框，里面是各種關鍵詞提示。Trie 樹，它是一個樹形結構。它是一種專門處理字符串匹配的數據結構，用來解決在一組字符串集合中快速查找某個字符串的問題。Trie 樹不適合精確匹配查找，這種問題更適合用散列表或者紅黑樹來解決。Trie 樹比較適合的是查找前綴匹配的字符串。|
|堆|堆是一個完全二叉樹，堆中的每一個節點的值都必須大于等于（或小于等于）其子樹中每個節點的值。用數組來存儲完全二叉樹是非常節省存儲空間的。因為我們不需要存儲左右子節點的指針，單純地通過數組的下標，就可以找到一個節點的左右子節點和父節點。|
|圖|圖中的元素我們稱為頂點（vertex）。圖中的一個頂點可以與任意其他頂點建立連接關系。我們把這種建立的關系叫做邊（edge）。跟頂點相連接的邊的條數，我們稱為度（degree）。我們把邊沒有方向的圖叫做“無向圖”，有方向的叫“有向圖”。
圖最直觀的一種存儲方法就是，鄰接矩陣（Adjacency Matrix）。鄰接矩陣的底層依賴一個二維數組。鄰接矩陣比較浪費存儲空間
鄰接表：存儲起來比較節省空間，但是使用起來就比較耗時間。分鄰接表和逆鄰接表。|

三、常用概念

1、線性表

顧名思義，線性表就是數據排列成一條線一樣的結構，每個線性表的數據最多只有前和后兩個方向；

線性表有：數組、鏈表、隊列、棧等；

非線性表：二叉樹、堆、圖等；

2、動態數據結構

動態數據結構是支持動態的更新操作，里面存儲的數據是時刻在變化的，通俗一點講，它不僅僅支持查詢，還支持刪除、插入數據。而且，這些操作都非常高效。如果不高效，也就算不上是有效的動態數據結構了。
注意：動態不是指在運行時該數據結構所占的內存會擴大或縮小。

3、什么是查詢

查詢的意思：就是查找數組或鏈表中第k個元素。

數組：根據首地址和下標，通過尋址公式直接計算第k個元素對應的內存地址，然后找到內存地址對應的數據。

鏈表：需要根據指針一個結點一個結點的依次遍歷，直到找到第K個元素對應的內存地址，然后找到內存地址對應的數據。

四、數組

1、數組定義

數組（array）是一種線性數據結構，它用一組連續的內存空間，來存儲一組具有相同數據類型的數據；
重點:線性、連續的內存空間、相同的數據類型

2、數組的優缺點

優點：數組具有隨機訪問的特性，所以查詢快。

缺點：數組刪除，插入數據效率低。

3、數組怎么根據下標隨機訪問的？

計算機會給每個內存單元分配一個地址，計算機通過地址來訪問內存中的數據。
當計算機隨機訪問某個元素的時候，他會通過尋址方式來計算出該元素的內存地址。
通過尋址公式，計算出該元素存儲的內存地址：
a[i]_address = base_address + i * data_type_size
所以數組具有查詢快的優點

4、為何數組插入和刪除低效

為了保證內存的連續性，我們插入一個數據或者刪除一個數據的時候，比如我們需要將一個數據插入到數組中的第K個位置，就需要把第K個位置騰出來，給新的數據。所以就需要將K–N這部分的元素順序往后挪一位。刪除同理；

注意：
2.2.1：如果數組的元素是有序的，那我們插入元素的時候，就必須按照上面的方法對K之后的元素順序移位。
2.2.2：如果數組中的數據不是有序的，也就是無規律的情況下，可以直接把第k個位置上的數據移到最后，然后將插入的數據直接放在第k個位置上。
所以數組插入、刪除效率很低

5.用數組還是容器？

數組先指定了空間大小，容器如ArrayList可以動態擴容。
1.希望存儲基本類型數據int long，可以用數組
2.事先知道數據大小，并且操作簡單，可以用數組
3.直觀表示多維，可以用數組,更直觀。
ArrayList：最大的優勢將很多數組操作的細節封裝起來。比如插入和刪除操作。另外，它支持動態擴容。

什么是動態擴容？

ArrayList預先申請了默認大小的數組，如果存儲空間不足，它會將存儲空間自動擴容為1.5倍。那之前的數據就需要數據搬移。只有在擴容的時候，進行一次數據搬移。

提高刪除效率：

將多次刪除操作中集中在一起執行，可以先記錄已經刪除的數據，但是不進行數據遷移，而僅僅是記錄，當發現沒有更多空間存儲時，再執行真正的刪除操作。這也是 JVM 標記清除垃圾回收算法的核心思想。

6、為什么數組要從 0 開始編號？

由于數組是通過尋址公式，計算出該元素存儲的內存地址：
a[i]_address = base_address + i * data_type_size
如果數組是從 1 開始計數，那么就會變成：
a[i]_address = base_address + （i-1）* data_type_size
對于CPU來說，多了一次減法的指令。
當然，還有一定的歷史原因。

五、鏈表

一、鏈表的定義

1.和數組一樣，鏈表也是一種線性表。
2.從內存結構來看，鏈表的內存結構是不連續的內存空間，是將一組零散的內存塊串聯起來，從而進行數據存儲的數據結構。
3.鏈表中的每一個內存塊被稱為節點Node。節點除了存儲數據外，還需記錄鏈上下一個節點的地址，即后繼指針next。

二、鏈表的優缺點

1.鏈表插入、刪除數據效率高O(1)級別（只需更改指針指向即可），隨機訪問效率低O(n)級別（需要從鏈頭至鏈尾進行遍歷）。
2.和數組相比，內存空間消耗更大，因為每個存儲數據的節點都需要額外的空間存儲后繼指針。

三、常用鏈表：單鏈表、循環鏈表和雙向鏈表

1.單鏈表

1）每個節點只包含一個指針，即后繼指針。
2）單鏈表有兩個特殊的節點，即首節點和尾節點。首節點和尾節點為什么特殊？用首節點地址表示整條鏈表，尾節點的后繼指針指向空地址null。
3）性能特點：插入和刪除節點的時間復雜度為O（1），查找的時間復雜度為O(n)。

2.循環鏈表

1）除了尾節點的后繼指針指向首節點的地址外均與單鏈表一致。
2）適用于存儲有循環特點的數據，比如約瑟夫問題。

3.雙向鏈表

1）節點除了存儲數據外，還有兩個指針分別指向前一個節點地址（前驅指針prev）和下一個節點地址（后繼指針next）。
2）首節點的前驅指針prev和尾節點的后繼指針均指向空地址。
3）性能特點：
和單鏈表相比，存儲相同的數據，需要消耗更多的存儲空間。
雙向鏈表優點：
插入、刪除操作比單鏈表效率更高O(1)級別。
以刪除操作為例，刪除操作分為2種情況：
一：給定數據值刪除對應節點和給定節點地址刪除節點。對于前一種情況，單鏈表和雙向鏈表都需要從頭到尾進行遍歷從而找到對應節點進行刪除，時間復雜度為O(n)。
二：已經知道數據值了，單鏈表要找到它的上一個節點。那么單鏈表需要從頭到尾進行遍歷直到p->next = q，時間復雜度為O(n)。而雙向鏈表可以直接找到前驅節點，時間復雜度為O(1)。

對于一個有序鏈表，雙向鏈表的按值查詢效率要比單鏈表高一些。因為我們可以記錄上次查找的位置p，每一次查詢時，根據要查找的值與p的大小關系，決定是往前還是往后查找，所以平均只需要查找一半的數據。

4.雙向循環鏈表

首節點的前驅指針指向尾節點，尾節點的后繼指針指向首節點。

四、數組和鏈表對比

1.插入、刪除和隨機訪問的時間復雜度

數組：插入、刪除的時間復雜度是O(n)，隨機訪問的時間復雜度是O(1)。

鏈表：插入、刪除的時間復雜度是O(1)，隨機訪問的時間復雜端是O(n)。

2.數組缺點

1）若申請內存空間很大，比如100M，但若內存空間沒有100M的連續空間時，則會申請失敗，盡管內存可用空間超過100M。

2）大小固定，若存儲空間不足，需進行擴容，一旦擴容就要進行數據復制，而這時非常費時的。

3.鏈表缺點

1）內存空間消耗更大，因為需要額外的空間存儲指針信息。

2）對鏈表進行頻繁的插入和刪除操作，會導致頻繁的內存申請和釋放，容易造成內存碎片，如果是Java語言，還可能會造成頻繁的GC（自動垃圾回收器）操作。

4.如何選擇？

數組簡單易用，在實現上使用連續的內存空間，可以借助CPU的緩沖機制預讀數組中的數據，所以訪問效率更高，而鏈表在內存中并不是連續存儲，所以對CPU緩存不友好，沒辦法預讀。

如果代碼對內存的使用非常苛刻，那數組就更適合。

五、鏈表簡易代碼

/*** 定義一個類作為節點* 節點需要有兩個屬性：數據域、指針域*/ public class Node {//數據域public int data;//指針域，指向下一個節點public Node next;//如果是雙向鏈接，要添加上個節點。Node<E> prev;public Node() {}public Node(int data) {this.data = data;}public Node(int data, Node next) {this.data = data;this.next = next;} } //創建頭節點 Node head = new Node(value); /*** 向鏈表添加數據* 注意：為了邏輯的簡潔，咱們假設插在最后。不是插在中間位置。* @param value 要添加的數據* @param last 最后的節點，尾結點*/ public static void addData(int value, Node last) {//初始化要加入的節點Node newNode = new Node(value);//忽略很多細節操作，因為我們假設插入到尾結點//實際，要判斷這個節點的下個節點。做很多判斷。last.next = newNode; } /*** 遍歷鏈表* @param head 頭節點*/ public static void traverse(Node head) {//臨時節點，從首節點開始Node temp = head.next;while (temp != null) {System.out.println("鏈表數據：" + temp.data);//繼續下一個temp = temp.next;} }

六、棧

一、棧的定義

1.先進者后出，后進者先出，這就是典型的“棧”結構。

2.從棧的操作特性來看，是一種“操作受限”的線性表，只允許在端插入和刪除數據。

二、為什么需要棧？

1.棧是一種操作受限的數據結構，其操作特性用數組和鏈表均可實現。

2.任何數據結構都是對特定應用場景的抽象，數組和鏈表雖然使用起來更加靈活，但卻暴露了幾乎所有的操作，難免會引發錯誤操作的風險。

3.所以，當某個數據集合只涉及在某端插入和刪除數據，且滿足后進者先出，先進者后出的操作特性時，我們應該首選棧這種數據結構。

三、棧的簡易代碼

注意：代碼只是便于理解，簡化了很多。邏輯并不嚴謹。

//1.棧的API public class Stack<Item> { //壓棧 public void push(Item item){} //彈棧 public Item pop(){} //還有一些方法，比如：棧是否為空、棧中數據的size等等 }

四、棧的數組實現

/*** 為了便于理解，簡化了很多代碼* 數據類型，直接設置為String*/ public class StackOfArray {//存儲數據的數組String[] stackArray = new String[1];//記錄元素個數Nint N = 0;//添加元素public void push(String item) {//自動擴容if (N == stackArray.length){resize(2 * stackArray.length);}stackArray[N++] = item;}//刪除元素public String pop() {String item = stackArray[--N];stackArray[N] = null;//縮小數組容量if (N > 0 && N == stackArray.length / 4) resize(stackArray.length / 2);return item;}//改變數組容量private void resize(int length) {String[] temp = new String[length];for (int i = 0; i < N; i++) {temp[i] = stackArray[i];}stackArray = temp;}//、、、省略部分代碼 }

五、棧的鏈表實現

/*** 為了便于理解，簡化了很多代碼* 數據類型，直接設置為 String*/ public class StackOfLinked {//定義一個鏈表類private class Node{String value;Node next;}//棧的第一個值 private Node first;private int N;//添加public void push(String newData){Node oldfirst = first;first = new Node();first.value = newData;first.next = oldfirst;N++;}//刪除public String pop(){String value = first.value;first = first.next;N--;return value;}//、、、省略部分代碼 }

六、棧的應用

1、棧在表達式求值中的應用

棧在表達式求值中的應用（比如：34+13*9+44-12/3）

利用兩個棧，其中一個用來保存操作數，另一個用來保存運算符。我們從左向右遍歷表達式，當遇到數字，我們就直接壓入操作數棧；當遇到運算符，就與運算符棧的棧頂元素進行比較，若比運算符棧頂元素優先級高，就將當前運算符壓入棧，若比運算符棧頂元素的優先級低或者相同，從運算符棧中取出棧頂運算符，從操作數棧頂取出2個操作數，然后進行計算，把計算完的結果壓入操作數棧，繼續比較。

2、實現瀏覽器的前進后退功能

我們使用兩個棧X和Y，我們把首次瀏覽的頁面依次壓如棧X，當點擊后退按鈕時，再依次從棧X中出棧，并將出棧的數據一次放入Y棧。當點擊前進按鈕時，我們依次從棧Y中取出數據，放入棧X中。當棧X中沒有數據時，說明沒有頁面可以繼續后退瀏覽了。當Y棧沒有數據，那就說明沒有頁面可以點擊前進瀏覽了。

七、隊列

一、隊列的定義

1.先進者先出，這就是典型的“隊列”結構。

2.支持兩個操作：入隊enqueue()，放一個數據到隊尾；出隊dequeue()，從隊頭取一個元素。

3.所以，和棧一樣，隊列也是一種操作受限的線性表。

二、隊列的應用場景

1.阻塞隊列

1）在隊列的基礎上增加阻塞操作，就成了阻塞隊列。

2）阻塞隊列就是在隊列為空的時候，從隊頭取數據會被阻塞，因為此時還沒有數據可取，直到隊列中有了數據才能返回；如果隊列已經滿了，那么插入數據的操作就會被阻塞，直到隊列中有空閑位置后再插入數據，然后在返回。

3）從上面的定義可以看出這就是一個“生產者-消費者模型”。這種基于阻塞隊列實現的“生產者-消費者模型”可以有效地協調生產和消費的速度。當“生產者”生產數據的速度過快，“消費者”來不及消費時，存儲數據的隊列很快就會滿了，這時生產者就阻塞等待，直到“消費者”消費了數據，“生產者”才會被喚醒繼續生產。不僅如此，基于阻塞隊列，我們還可以通過協調“生產者”和“消費者”的個數，來提高數據處理效率，比如配置幾個消費者，來應對一個生產者。

2.并發隊列

1）在多線程的情況下，會有多個線程同時操作隊列，這時就會存在線程安全問題。能夠有效解決線程安全問題的隊列就稱為并發隊列。

2）并發隊列簡單的實現就是在enqueue()、dequeue()方法上加鎖，但是鎖粒度大并發度會比較低，同一時刻僅允許一個存或取操作。

3）實際上，基于數組的循環隊列利用CAS原子操作，可以實現非常高效的并發隊列。這也是循環隊列比鏈式隊列應用更加廣泛的原因。

3.線程池資源枯竭是的處理

在資源有限的場景，當沒有空閑資源時，基本上都可以通過“隊列”這種數據結構來實現請求排隊。

三、順序隊列的數組實現

/*** 為了便于理解，簡化了很多代碼* 數據類型，直接設置為String*/ public class ArrayQueue {//存儲數據的數組private String[] items;//記錄數組容量private int n;private int size;//head記錄隊頭索引，tail記錄隊尾索引private int head = 0;private int tail = 0;//申請一個指定容量的隊列public ArrayQueue(int capacity) {items = new String[capacity];n = capacity;}/** 入隊：* 1.堆滿的時，入隊失敗* 1.1頻繁出入隊，造成數組使用不連續* 1.2在入隊的時候，集中觸發進行數據搬移* 2.在末尾插入數據，注意tail指向隊尾元素的索引+1*/public boolean enqueue(String item) {//表示隊滿if (head == 0 && tail == n) {return false;} else if (head != 0 && tail == n) {//表示需要數據搬移for (int i = head; i < tail; i++) {items[i - head] = items[i];}head = 0;tail = tail - head;}//將數據加入隊列items[tail++] = item;size++;return true;}//出隊：1.隊空時，出隊失敗;2.出隊，head索引+1public String dequeue() {String res = null;if (head == tail) return res;res = items[head++];size--;return res;} }

四、鏈表實現簡易隊列

/*** 為了便于理解，簡化了很多代碼* 數據類型，直接設置為String*/ public class LinkedQueue {//定義一個節點類private class Node {String value;Node next;}//記錄隊列元素個數private int size = 0;//head指向隊頭結點，tail指向隊尾節點private Node head;private Node tail;//申請一個隊列public LinkedQueue() {}//入隊public boolean enqueue(String item) {Node newNode = new Node();newNode.value = item;if (size == 0) head = newNode;else tail.next = newNode;tail = newNode;size++;return true;}//出隊public String dequeue() {String res = null;if (size == 0) return res;if (size == 1) tail = null;res = head.value;head = head.next;size--;return res;} }

八、散列表

一、散列表的定義

散列表我們平時也叫它“哈希表”或者“Hash 表”。散列表來源于數組，它利用的是數組支持按照下標隨機訪問元素的特性。
我們把key，通過散列函數（hash函數）計算得到hash值，hash值作為數組的下標。
然后把key和key綁定的數據（我們稱為value）存儲在hash值對應的數組下標位置。

二、散列沖突

（1）什么是散列沖突

可以理解為把11個雞蛋放到10個籃子里，那么肯定會有一個籃子有2個雞蛋。

（2）散列沖突解決方法

常用的散列沖突解決方法有2類：開放尋址法（open addressing）和鏈表法（chaining）

1）開放尋址法

①核心思想：如果出現散列沖突，就重新探測一個空閑位置，將其插入。
②線性探測法（Linear Probing）：

插入數據：

當我們往散列表中插入數據時，如果某個數據經過散列函數之后，存儲的位置已經被占用了，我們就從當前位置開始，依次往后查找，看是否有空閑位置，直到找到為止。如果到最后也沒有位置，然后從頭開始查找。

查找數據：

我們通過散列函數求出要查找元素的鍵值對應的散列值，然后比較數組中下標為散列值的元素和要查找的元素是否相等，若相等，則說明就是我們要查找的元素；否則，就順序往后依次查找。如果遍歷到數組的空閑位置還未找到，就說明要查找的元素并沒有在散列表中。

刪除數據：

刪除操作稍微有些特別。我們不能單純地把要刪除的元素設置為空。

因為在查找的時候，一旦我們通過線性探測方法，找到一個空閑位置，我們就可以認定散列表中不存在這個數據。但是，如果這個空閑位置是我們后來刪除的，就會導致原來的查找算法失效。本來存在的數據，會被認定為不存在。

如果我們刪除數據，為了不讓查找算法失效，可以將刪除的元素特殊標記為deleted，當線性探測查找的時候，遇到標記為deleted的空間，并不是停下來，而是繼續往下探測。

缺點：當散列表中插入的數據越來越多時，散列沖突發生的可能性就會越來越大，空閑位置會越來越少，線性探測的時間就會越來越久。

2）鏈表法（更常用）

插入數據：當插入的時候，我們需要通過散列函數計算出對應的散列槽位，將其插入到對應的鏈表中即可，所以插入的時間復雜度為O(1)。

查找或刪除數據：當查找、刪除一個元素時，通過散列函數計算對應的槽，然后遍歷鏈表查找或刪除。對于散列比較均勻的散列函數，鏈表的節點個數k=n/m，其中n表示散列表中數據的個數，m表示散列表中槽的個數，所以是時間復雜度為O(k)。

三、動態擴容

裝載因子：
散列表的裝載因子=填入表中的元素個數/散列表的長度

（1）為什么要動態擴容

對于動態散列表來說，數據集合是頻繁變動的，我們事先無法預估將要加入的數據個數，所以我們也無法事先申請一個足夠大的散列表。隨著數據慢慢加入，裝載因子就會慢慢變大。當裝載因子大到一定程度之后，散列沖突就會變得不可接受。這個時候，我們就需要動態擴容。我們可以通過設置裝載因子的閾值，當裝載因子大于我們設置的閾值的時候，我們進行動態擴容。重新申請一個更大的散列表，將數據搬移到這個新散列表中。數據搬移操作比較復雜。因為散列表的大小變了，數據的存儲位置也變了，所以我們需要通過散列函數重新計算每個數據的存儲位置。

（2）動態擴容導致插入效率低

大部分情況下，動態擴容的散列表插入一個數據都很快，但是在特殊情況下，當裝載因子已經到達閾值，需要先進行擴容，進行數據搬移，然后再插入數據。這個時候，插入數據就會變得很慢，甚至會無法接受。

（3）如何避免低效擴容？分批擴容

當裝載因子觸達閾值之后，我們只申請新空間，但并不將老的數據搬移到新散列表中。當有新數據要插入時，我們將新數據插入新散列表中，并且從老的散列表中拿出一個數據放入到新散列表。每次插入一個數據到散列表，我們都重復上面的過程。經過多次插入操作之后，老的散列表中的數據就一點一點全部搬移到新散列表中了。這樣沒有了集中的一次性數據搬移，插入操作就都變得很快了。

（4）分批擴容的查詢操作

先查新散列表，再查老散列表。

九、樹

一、樹的常用概念

節點：樹中的每個元素稱為節點

父子關系：相鄰兩節點的連線，稱為父子關系

根節點：沒有父節點的節點

葉子節點：沒有子節點的節點

父節點：指向子節點的節點

子節點：被父節點指向的節點

兄弟節點：具有相同父節點的多個節點稱為兄弟節點關系

節點的高度：節點到葉子節點的最長路徑所包含的邊數

節點的深度：根節點到節點的路徑所包含的邊數

節點的層數：節點的深度+1（根節點的層數是1）

樹的高度：等于根節點的高度

二、二叉樹

（1）二叉樹

每個節點最多只有2個子節點的樹，這兩個節點分別是左子節點和右子節點。

（2）滿二叉樹

有一種二叉樹，除了葉子節點外，每個節點都有左右兩個子節點，這種二叉樹叫做滿二叉樹。

（3）完全二叉樹

有一種二叉樹，葉子節點都在最底下兩層，最后一層葉子節都靠左排列，并且除了最后一層，其他層的節點個數都要達到最大，這種二叉樹叫做完全二叉樹。

（4）二叉查找樹

三、二叉樹的鏈式存儲

每個節點由3個字段，其中一個存儲數據，另外兩個是指向左右子節點的指針。我們只要拎住根節點，就可以通過左右子節點的指針，把整棵樹都串起來。這種存儲方式比較常用，大部分二叉樹代碼都是通過這種方式實現的。

四、二叉樹的順序存儲

用數組來存儲，對于完全二叉樹，如果節點X存儲在數組中的下標為i，那么它的左子節點的存儲下標為2i，右子節點的下標為2i+1，反過來，下標i/2位置存儲的就是該節點的父節點。注意，根節點存儲在下標為1的位置。完全二叉樹用數組來存儲時最省內存的方式。

五、二叉樹的遍歷

①前序遍歷：對于樹中的任意節點來說，先打印這個節點，然后再打印它的左子樹，最后打印它的右子樹。

②中序遍歷：對于樹中的任意節點來說，先打印它的左子樹，然后再打印它的本身，最后打印它的右子樹。

③后序遍歷：對于樹中的任意節點來說，先打印它的左子樹，然后再打印它的右子樹，最后打印它本身。

十、二叉查找樹

一、二叉查找樹的定義

二叉查找樹也叫二叉搜索樹，二叉查找樹最大的特點就是，支持動態數據集合的快速插入、刪除、查找操作。

二叉查找樹要求，在樹中的任意一個節點，其左子樹中的每個節點的值，都要小于這個節點的值，而右子樹節點的值都大于這個節點的值。

二、二叉查找樹的查找操作

我們先取根節點，如果它等于我們要查找的數據，那就返回。如果要查找的數據比根節點的值小，那就在左子樹中遞歸查找；如果要查找的數據比根節點的值大，那就在右子樹中遞歸查找。

代碼：

public class BinarySearchTree {private Node tree;public Node find(int data) {Node p = tree;while (p != null) {if (data < p.data) p = p.left;else if (data > p.data) p = p.right;else return p;}return null;}public static class Node {private int data;private Node left;private Node right;public Node(int data) {this.data = data;}} }

三、二叉查找樹的插入操作

從根節點開始，依次比較要插入的數據和節點的大小關系。如果要插入的數據比節點的數據大，并且節點的右子樹為空，就將新數據直接插到右子節點的位置；如果不為空，就再遞歸遍歷右子樹，查找插入位置。如果要插入的數據比節點的數據小，同理。

代碼：

public void insert(int data) {if (tree == null) {tree = new Node(data);return;}Node p = tree;while (p != null) {if (data > p.data) {if (p.right == null) {p.right = new Node(data);return;}p = p.right;} else { // data < p.dataif (p.left == null) {p.left = new Node(data);return;}p = p.left;}} }

四、二叉查找樹的刪除操作

二叉查找樹的查找、插入操作都比較簡單易懂，但是它的刪除操作就比較復雜了 。針對要刪除節點的子節點個數的不同，我們需要分三種情況來處理。

第一種情況是，如果要刪除的節點沒有子節點，我們只需要直接將父節點中，指向要刪除節點的指針置為 null。比如圖中的刪除節點 55。

第二種情況是，如果要刪除的節點只有一個子節點（只有左子節點或者右子節點），我們只需要更新父節點中，指向要刪除節點的指針，讓它指向要刪除節點的子節點就可以了。比如圖中的刪除節點 13。

第三種情況是，如果要刪除的節點有兩個子節點，這就比較復雜了。我們需要找到這個節點的右子樹中的最小節點，把它替換到要刪除的節點上。然后再刪除掉這個最小節點，因為最小節點肯定沒有左子節點（如果有左子結點，那就不是最小節點了），所以，我們可以應用上面兩條規則來刪除這個最小節點。比如圖中的刪除節點 18。

代碼：

public void delete(int data) {Node p = tree; // p指向要刪除的節點，初始化指向根節點Node pp = null; // pp記錄的是p的父節點while (p != null && p.data != data) {pp = p;if (data > p.data) p = p.right;else p = p.left;}if (p == null) return; // 沒有找到// 要刪除的節點有兩個子節點if (p.left != null && p.right != null) { // 查找右子樹中最小節點Node minP = p.right;Node minPP = p; // minPP表示minP的父節點while (minP.left != null) {minPP = minP;minP = minP.left;}p.data = minP.data; // 將minP的數據替換到p中p = minP; // 下面就變成了刪除minP了pp = minPP;}// 刪除節點是葉子節點或者僅有一個子節點Node child; // p的子節點if (p.left != null) child = p.left;else if (p.right != null) child = p.right;else child = null;if (pp == null) tree = child; // 刪除的是根節點else if (pp.left == p) pp.left = child;else pp.right = child; }

五、簡易的刪除

關于二叉查找樹的刪除操作，還有個非常簡單、取巧的方法，就是單純將要刪除的節點標記為“已刪除”，但是并不真正從樹中將這個節點去掉。這樣原本刪除的節點還需要存儲在內存中，比較浪費內存空間，但是刪除操作就變得簡單了很多。而且，這種處理方法也并沒有增加插入、查找操作代碼實現的難度。

六、支持重復數據的二叉查找樹

很多時候，在開發中，我們在二叉查找樹中存儲的，是一個包含很多字段的對象。我們利用對象的某個字段作為鍵值（key）來構建二叉查找樹。我們把對象中的其他字段叫作衛星數據。如果存儲的兩個對象鍵值相同，這種情況該怎么處理呢？有兩種解決方法。

（1）每個結點存儲多個key相同的數據

二叉查找樹中每一個節點不僅會存儲一個數據，因此我們通過鏈表和支持動態擴容的數組等數據結構，把值相同的數據都存儲在同一個節點上。

（2）每個節點中存儲一個數據，相同的值存放在右子節點。

每個節點仍然只存儲一個數據。在查找插入位置的過程中，如果碰到一個節點的值，與要插入數據的值相同，我們就將這個要插入的數據放到這個節點的右子樹，也就是說，把這個新插入的數據當作大于這個節點的值來處理。

當要查找數據的時候，遇到值相同的節點，我們并不停止查找操作，而是繼續在右子樹中查找，直到遇到葉子節點，才停止。這樣就可以把鍵值等于要查找值的所有節點都找出來。

七、二叉查找樹的極端情況

二叉查找樹，有兩種極端情況。分別是二叉查找樹退化成鏈表的情況和完全二叉樹。

十一、平衡二叉查找樹之紅黑樹

一、紅黑樹的定義

（1）為什么使用紅黑樹

二叉查找樹是最常用的一種二叉樹，它支持快速插入、刪除、查找操作，各個操作的時間復雜度跟樹的高度成正比，理想情況下，時間復雜度是 O(logn)。不過，二叉查找樹在頻繁的動態更新過程中，可能會出現樹的高度遠大于 log2n 的情況，從而導致各個操作的效率下降。極端情況下，二叉樹會退化為鏈表，時間復雜度會退化到 O(n)。

紅黑樹是一種平衡二叉查找樹。它是為了解決普通二叉查找樹在數據更新的過程中，復雜度退化的問題而產生的。紅黑樹的高度近似 log2n，所以它是近似平衡，插入、刪除、查找操作的時間復雜度都是 O(logn)。因為紅黑樹是一種性能非常穩定的二叉查找樹，所以，在工程中，但凡是用到動態插入、刪除、查找數據的場景，都可以用到它。不過，它實現起來比較復雜，如果自己寫代碼實現，難度會有些高，這個時候，我們其實更傾向用跳表來替代它。

二、平衡二叉查找樹

平衡二叉查找樹的嚴格定義是這樣的：二叉樹中任意一個節點的左右子樹的高度相差不能大于 1。其次，是二叉查找樹。

平衡二叉樹主要有兩種，AVL 樹和紅黑樹。

（1）AVL 樹

AVL 樹是一種高度平衡的二叉樹，所以查找的效率非常高，但是，有利就有弊，AVL 樹為了維持這種高度的平衡，就要付出更多的代價。每次插入、刪除都要做調整，就比較復雜、耗時。所以，對于有頻繁的插入、刪除操作的數據集合，使用 AVL 樹的代價就有點高了。

（2）紅黑樹

紅黑樹的英文是“Red-Black Tree”，簡稱 R-B Tree。它是一種不嚴格的平衡二叉查找樹。紅黑樹只是做到了近似平衡，并不是嚴格的平衡，所以在維護平衡的成本上，要比 AVL 樹要低。

十二、堆

1、堆的定義

堆是一個完全二叉樹，堆中的每一個節點的值都必須大于等于（或小于等于）其子樹中每個節點的值。

2、實現堆

用數組來存儲完全二叉樹是非常節省存儲空間的。因為我們不需要存儲左右子節點的指針，單純地通過數組的下標，就可以找到一個節點的左右子節點和父節點。

從圖中可以看出：數組中下標為 i 的節點的左子節點，就是下標為 i?2 的節點，右子節點就是下標為 i?2+1 的節點，父節點就是下標為 2i? 的節點。

3、往堆中插入元素

往堆中插入一個元素后，我們需要繼續滿足堆的兩個特性。

我們新插入一個元素，如果我們把新插入的元素放到堆的最后，那么就不符合堆的特性了。于是，我們就需要進行調整，讓其重新滿足堆的特性，這個過程我們起了一個名字，就叫做堆化（heapify）。

堆化實際上有兩種，從下往上和從上往下。這里我先講從下往上的堆化方法。

堆化非常簡單，就是順著節點所在的路徑，向上或者向下，對比，然后交換。

現在解釋一下從下往上堆化

（1）從下往上堆化

我們把22這個元素，插入到堆中。首先我們插到最后，然后看圖

代碼：

public class Heap { private int[] a; // 數組，從下標1開始存儲數據 private int n; // 堆可以存儲的最大數據個數 private int count; // 堆中已經存儲的數據個數public Heap(int capacity) { a = new int[capacity + 1]; n = capacity; count = 0; }public void insert(int data) { if (count >= n) return; // 堆滿了 ++count; a[count] = data; int i = count; while (i/2 > 0 && a[i] > a[i/2]) { // 自下往上堆化 swap(a, i, i/2); // swap()函數作用：交換下標為i和i/2的兩個元素 i = i/2; } } }

（2）刪除堆頂元素，從上往下堆化

我們把最后一個節點放到堆頂，然后利用同樣的父子節點對比方法。對于不滿足父子節點大小關系的，互換兩個節點，并且重復進行這個過程，直到父子節點之間滿足大小關系為止。這就是從上往下的堆化方法。

我們把堆頂的33刪除。

public void removeMax() {if (count == 0) return -1; // 堆中沒有數據a[1] = a[count];--count;heapify(a, count, 1); }private void heapify(int[] a, int n, int i) { // 自上往下堆化while (true) {int maxPos = i;if (i*2 <= n && a[i] < a[i*2]) maxPos = i*2;if (i*2+1 <= n && a[maxPos] < a[i*2+1]) maxPos = i*2+1;if (maxPos == i) break;swap(a, i, maxPos);i = maxPos;} }

4、基于堆實現排序

我們借助于堆這種數據結構實現的排序算法，就叫做堆排序。這種排序方法的時間復雜度非常穩定，是 O(nlogn)，并且它還是原地排序算法。堆排序的過程大致分解成兩個大的步驟，建堆和排序。

（1）如何建堆

建堆的過程，有兩種思路。

第一種：起初堆中只包含一個數據，就是下標為 1 的數據。然后，我們調用堆的插入操作，將下標從 2 到 n 的數據依次插入到堆中。每插入一個數據，都要從下往上堆化。這樣我們就將包含 n 個數據的數組，組織成了堆。

第二種：從后往前處理數組，并且每個數據都是從上往下堆化。因為葉子節點從上往下堆化只能自己跟自己比較，所以我們直接從第一個非葉子節點開始，依次堆化就行了。

先看圖：

第一個非葉子節點：a[4]

（2）排序

建堆結束之后，數組中的數據已經是按照大頂堆的特性來組織的。數組中的第一個元素就是堆頂，也就是最大的元素。

我們把它跟最后一個元素交換，那最大元素就放到了下標為 n 的位置。這個過程有點類似上面講的“刪除堆頂元素”的操作，當堆頂元素移除之后，我們把下標為 n 的元素放到堆頂，然后再通過堆化的方法，將剩下的 n?1 個元素重新構建成堆。堆化完成之后，我們再取堆頂的元素，放到下標是 n?1 的位置，一直重復這個過程，直到最后堆中只剩下標為 1 的一個元素，排序工作就完成了。

十三、跳表

一、跳表的定義

為一個值有序的鏈表建立多級索引，比如每2個節點提取一個節點到上一級，我們把抽出來的那一級叫做索引或索引層。如下圖所示，其中down表示down指針，指向下一級節點。以此類推，對于節點數為n的鏈表，大約可以建立log2n-1級索引。

為鏈表建立多級索引的數據結構就稱為跳表。

重點：鏈表、值有序、多級索引。

二、計算跳表的時間復雜度

（1）計算跳表的高度

如果鏈表有n個節點，每2個節點抽取抽出一個節點作為上一級索引的節點，那第1級索引的節點個數大約是n/2，第2級索引的節點個數大約是n/4，依次類推，第k級索引的節點個數就是n/(2^{k)。假設索引有h級別，最高級的索引有2個節點，則有n/(2}h)=2，得出h=log2n-1，包含原始鏈表這一層，整個跳表的高度就是log2n。
注意：跳表的某個結點的層數是維護一個隨機函數，隨機生成的。

（2）計算跳表的時間復雜度

假設我們在跳表中查詢某個數據的時候，如果每一層都遍歷m個節點，那在跳表中查詢一個數據的時間復雜度就是O(m*logn)。那這個m是多少呢？如下圖所示，假設我們要查找的數據是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)。

這個查找的時間復雜度跟二分查找是一樣的。換句話說，我們其實是基于單鏈表實現了二分查找。這種查詢效率的提升，前提是建立了很多級索引，利用空間換時間的設計思路。

（3）跳表的空間復雜度

1.計算索引的節點總數

如果鏈表有n個節點，每2個節點抽取抽出一個節點作為上一級索引的節點，那每一級索引的節點數分別為：n/2，n/4，n/8，…，8，4，2，等比數列求和n/2+n/4+n/8…+8+4+2=n-2，所以跳表的空間復雜度為O(n)。

2.如何優化時間復雜度

如果鏈表有n個節點，每3或5個節點抽取抽出一個節點作為上一級索引的節點，那每一級索引的節點數分別為（以3為例）：n/3，n/9，n/27，…，27，9，3，1。

三、跳表插入

（1）鏈表插入

我們知道，在單鏈表中，一旦定位好要插入的位置，插入結點的時間復雜度是很低的，就是 O(1)。但是，這里為了保證原始鏈表中數據的有序性，我們需要先找到要插入的位置，這個查找操作就會比較耗時 O(n)。

（2）跳表插入

因為跳表的查詢是O(logn)，所以跳表的插入耗時也是O(logn)。

四、跳表索引動態更新

當我們不停地往跳表中插入數據時，如果我們不更新索引，就有可能出現某 2 個索引結點之間數據非常多的情況。極端情況下，跳表會退化成單鏈表。

作為一種動態數據結構，我們需要某種手段來維護索引與原始鏈表大小之間的平衡，也就是說，如果鏈表中結點多了，索引結點就相應地增加一些，避免復雜度退化，以及查找、插入、刪除操作性能下降。

當我們往跳表中插入數據的時候，我們可以選擇同時將這個數據插入到部分索引層中。如何選擇加入哪些索引層呢？我們通過一個隨機函數，來決定將這個結點插入到哪幾級索引中，比如隨機函數生成了值 K，那我們就將這個結點添加到第一級到第 K 級這 K 級索引中。

五、代碼

https://github.com/wangzheng0822/algo/blob/master/java/17_skiplist/SkipList2.java

十四、圖

一、圖的定義

圖中的元素我們稱為頂點（vertex）。圖中的一個頂點可以與任意其他頂點建立連接關系。我們把這種建立的關系叫做邊（edge）。跟頂點相連接的邊的條數，我們稱為度（degree）。我們把邊沒有方向的圖叫做“無向圖”，有方向的叫“有向圖”。在有向圖中，我們把度分為入度（In-degree）和出度（Out-degree）。頂點的入度，表示有多少條邊指向這個頂點；頂點的出度，表示有多少條邊是以這個頂點為起點指向其他頂點。

（1）帶權圖

QQ 有一個好友親密度功能，在帶權圖中，每條邊都有一個權重（weight），我們可以通過這個權重來表示 QQ 好友間的親密度。

二、鄰接矩陣

圖最直觀的一種存儲方法就是，鄰接矩陣（Adjacency Matrix）。

鄰接矩陣的底層依賴一個二維數組。對于無向圖來說，如果頂點 i 與頂點 j 之間有邊，我們就將 A[i][j]和 A[j][i]標記為 1；對于有向圖來說，如果頂點 i 到頂點 j 之間，有一條箭頭從頂點 i 指向頂點 j 的邊，那我們就將 A[i][j]標記為 1。同理，如果有一條箭頭從頂點 j 指向頂點 i 的邊，我們就將 A[j][i]標記為 1。對于帶權圖，數組中就存儲相應的權重。

（1）鄰接矩陣缺點

用鄰接矩陣來表示一個圖，雖然簡單、直觀，但是比較浪費存儲空間。

對于無向圖來說，如果 A[i][j]等于 1，那 A[j][i]也肯定等于 1。實際上，我們只需要存儲一個就可以了。也就是說，無向圖的二維數組中，如果我們將其用對角線劃分為上下兩部分，那我們只需要利用上面或者下面這樣一半的空間就足夠了，另外一半白白浪費掉了。

如果我們存儲的是稀疏圖（Sparse Matrix），也就是說，頂點很多，但每個頂點的邊并不多，那鄰接矩陣的存儲方法就更加浪費空間了。比如微信好友關系。

三、鄰接表存儲方法

針對鄰接矩陣存儲圖比較浪費內存空間的問題，我們來看另外一種圖的存儲方法，鄰接表（Adjacency List）。

（1）鄰接矩陣和鄰接表的區別

鄰接矩陣：鄰接矩陣存儲起來比較浪費空間，但是使用起來比較節省時間。

鄰接表：存儲起來比較節省空間，但是使用起來就比較耗時間。

鄰接矩陣和鄰接表就是采用時間和空間互換的設計思想。

鄰接表耗時間的原因：如果我們要確定，是否存在一條從頂點 2 到頂點 4 的邊，那我們就要遍歷頂點 2 對應的那條鏈表，看鏈表中是否存在頂點 4。

為了提高查詢效率，我們可以將鏈接表中的鏈表改成：平衡二叉樹、跳表、散列表等。也可以將鏈表改為有序動態數組。

四、逆鄰接表

如果存儲微博這種用戶關系，假設我們需要支持下面這樣幾個操作：

判斷用戶 A 是否關注了用戶 B；

判斷用戶 A 是否是用戶 B 的粉絲；

用戶 A 關注用戶 B；

用戶 A 取消關注用戶 B；

根據用戶名稱的首字母排序，分頁獲取用戶的粉絲列表；

根據用戶名稱的首字母排序，分頁獲取用戶的關注列表。

那么用一個鄰接表存儲有向圖是不能實現的。所以我們還需要增加一個逆鄰接表。

鄰接表可以表示用戶關注了哪些用戶，逆鄰接表就可以表示用戶被哪些用戶關注。

如圖：

五、存儲大數據

（1）數據分片

如果存儲小規模數據，比如社交關系幾萬幾十萬用戶，我們可以存儲在內存中。如果微博有上億用戶，數據規模太大。我們就無法全部存儲在內存中。所以

我們可以通過hash算法等數據分片的方式，將鄰接表存儲在不同的機器上。要查詢頂點和頂點的關系時候，我們就用同樣的hash算法，先定位頂點機器的位置。然后在響應的機器上查找。

（2）數據庫存儲

除此之外，我們還有另外一種解決思路，就是利用外部存儲（比如硬盤），因為外部存儲的存儲空間要比內存會寬裕很多。數據庫是我們經常用來持久化存儲關系數據的，所以我這里介紹一種數據庫的存儲方式。

下面是表結構

十五、Trie樹

一、搜索引擎的搜索關鍵詞提示功能

搜索引擎的搜索關鍵詞提示功能，當你在搜索引擎的搜索框中，輸入要搜索的文字的某一部分的時候，搜索引擎就會自動彈出下拉框，里面是各種關鍵詞提示。

如圖：

這個功能是如何實現的呢？接下來主角上場了-Trie樹。

二、Trie 樹的定義

Trie 樹，也叫“字典樹”。顧名思義，它是一個樹形結構。它是一種專門處理字符串匹配的數據結構，用來解決在一組字符串集合中快速查找某個字符串的問題。

舉個簡單的例子來說明一下。我們有 6 個字符串，它們分別是：how，hi，her，hello，so，see。我們希望在里面多次查找某個字符串是否存在。如果每次查找，都是拿要查找的字符串跟這 6 個字符串依次進行字符串匹配，那效率就比較低。

這個時候，我們就可以先對這 6 個字符串做一下預處理，組織成 Trie 樹的結構，之后每次查找，都是在 Trie 樹中進行匹配查找。Trie 樹的本質，就是利用字符串之間的公共前綴，將重復的前綴合并在一起。最后構造出來的就是下面這個圖中的樣子。

注意：其中，根節點不包含任何信息。每個節點表示一個字符串中的字符。

Trie 樹主要有兩個操作，一個是將字符串集合構造成 Trie 樹。這個過程分解開來的話，就是一個將字符串插入到 Trie 樹的過程。另一個是在 Trie 樹中查詢一個字符串。

三、Trie樹的存儲

假設我們的字符串中只有從 a 到 z 這 26 個小寫字母，我們在數組中下標為 0 的位置，存儲指向子節點 a 的指針，下標為 1 的位置存儲指向子節點 b 的指針，以此類推，下標為 25 的位置，存儲的是指向的子節點 z 的指針。如果某個字符的子節點不存在，我們就在對應的下標的位置存儲 null。

查找：

當我們在 Trie 樹中查找字符串的時候，我們就可以通過字符的 ASCII 碼減去“a”的 ASCII 碼，迅速找到匹配的子節點的指針。比如，d 的 ASCII 碼減去 a 的 ASCII 碼就是 3，那子節點 d 的指針就存儲在數組中下標為 3 的位置中。

上代碼：

public class Trie {public class TrieNode {public char data;public TrieNode[] children = new TrieNode[26];public boolean isEndingChar = false;public TrieNode(char data) {this.data = data;}private TrieNode root = new TrieNode('/'); // 存儲無意義字符// 往Trie樹中插入一個字符串public void insert(char[] text) {TrieNode p = root;for (int i = 0; i < text.length; ++i) {int index = text[i] - 'a';if (p.children[index] == null) {TrieNode newNode = new TrieNode(text[i]);p.children[index] = newNode;}p = p.children[index];}p.isEndingChar = true;}// 在Trie樹中查找一個字符串public boolean find(char[] pattern) {TrieNode p = root;for (int i = 0; i < pattern.length; ++i) {int index = pattern[i] - 'a';if (p.children[index] == null) {return false; // 不存在pattern}p = p.children[index];}if (p.isEndingChar == false) return false; // 不能完全匹配，只是前綴else return true; // 找到pattern} }

四、Trie樹的時間復雜度

如果要在一組字符串中，頻繁地查詢某些字符串，用 Trie 樹會非常高效。構建 Trie 樹的過程，需要掃描所有的字符串，時間復雜度是 O(n)（n 表示所有字符串的長度和）。但是一旦構建成功之后，后續的查詢操作會非常高效。

每次查詢時，如果要查詢的字符串長度是 k，那我們只需要比對大約 k 個節點，就能完成查詢操作。跟原本那組字符串的長度和個數沒有任何關系。所以說，構建好 Trie 樹后，在其中查找字符串的時間復雜度是 O(k)，k 表示要查找的字符串的長度。

五、Trie樹的空間復雜度

Trie 樹是一種非常獨特的、高效的字符串匹配方法。如果Trie樹基于數組去實現，Trie 樹是非常耗內存的，用的是一種空間換時間的思路”。

我們可以稍微犧牲一點查詢的效率，將每個節點中的數組換成其他數據結構，來存儲一個節點的子節點指針。用哪種數據結構呢？我們的選擇其實有很多，比如有序數組、跳表、散列表、紅黑樹等。

六、總結

Trie 樹只是不適合精確匹配查找，這種問題更適合用散列表或者紅黑樹來解決。Trie 樹比較適合的是查找前綴匹配的字符串，也就是類似開篇問題的那種場景。

十六、HashMap

HashMap 底層是 hash 數組和單向鏈表實現，數組中的每個元素都是鏈表，當鏈表長度超過 8 時(大于等于9)，鏈表轉換為紅黑樹。

HashMap簡易實現 1、定義Node類 static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;V value;Node<K,V> next;//next 指向鏈表的下一個結點。 } //2、定義存儲Node的數組table Node<K,V>[] table; //3、定義table的容量，初始為16，后會動態擴容。 table= (Node<K,V>[])new Node[newCap];//newCap，默認初始為1 << 4（16），之后會擴容，左移1位。 //4、插入數據 public V put(K key, V value) { //5、定義數組，tab=table。 //6、通過數組長度和key的hash值，計算當前的索引。然后把node存到數組對應的索引中。 tab[i = (n - 1) & hash]= newNode(hash, key, value, null) //注意：node是鏈表，當鏈表長度超過 8 時(大于等于9)，鏈表轉換為紅黑樹。 }

十七、LinkedHashMap

一、LinkedHashMap實現

1、LinkedHashMap是HashMap的子類，LinkedHashMap =HashMap + 雙向鏈表。通俗的說： 數組+鏈表，然后在鏈表的node之上添加了before和after。before指向當前數據的上一條數據，after指向當前數據的下一條數據。通過維護雙向鏈表的before和after保持迭代順序。定義了head結點和tail結點，表示開始的頭結點數據和尾結點數據。

在這里插入圖片描述

public class LinkedHashMap<K,V> extends HashMap<K,V>

2、LinkedHashMap采用的hash算法和HashMap相同,但是它重新定義了Entry（也就是node）。

我們先來看LinkedHashMapEntry。在HashMap.Node之上，增加了兩個指針，before 和 after，它們分別用于維護雙向鏈接列表。

static class LinkedHashMapEntry<K,V> extends HashMap.Node<K,V> {LinkedHashMapEntry<K,V> before, after;LinkedHashMapEntry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}

3、head和tail表示頭尾結點。

LinkedHashMapEntry<K,V> head;LinkedHashMapEntry<K,V> tail;

二、LRU算法

LRU全稱是Least Recently Used，最少最近使用策略。

LRU算法的設計原則是：如果一個數據在最近一段時間沒有被使用，那么在未來它被使用的概率很小。也就是說，當存儲空間滿的時候，我們應當把最久沒有被使用的數據刪除。

使用LinkedHashMap，當使用數據的時候，如果數據存在，則把該數據移到鏈表頭部。不存在，新建數據放到鏈表頭部。如果空間滿了，刪除鏈表尾部的數據。這樣就實現了Lru算法。

十八、HashMap、HashTable和ConcurrentHashMap

1、Hashmap

因為多線程環境下，使用Hashmap進行put操作是線程不安全的。

2、Hashtable

Hashtable容器使用synchronized來保證線程安全。
synchronized是悲觀鎖，當某一線程得到鎖，其他需要鎖的線程就掛起的情況就是悲觀鎖。這樣在線程競爭激烈的情況下Hashtable的效率非常低下。好處是總能獲取最實時的數據更新。

3、ConcurrentHashMap

分段鎖

ConcurrentHashMap，在 JDK 1.7 中采用 分段鎖的方式；
為了解決HashTable在多線程的情況效率低下的問題（因為HashTables是多個線競爭同一把鎖），在JDK1.7采用分段鎖的技術（ConcurrentHashMap首先將數據分成N段，然后給每一段數據配一把鎖。這樣當線程訪問不同數據段的數據的時候，就不會競爭同一把鎖）。
缺點：
讀取操作不能保證獲取到最新的數據。
例如線程A寫入大量數據，期間線程B調用get方法，那么get獲取的數據只能是已經完成插入的部分數據。

JDK1.8采用CAS

JDK1.8的拋棄了分段鎖機制，利用CAS（樂觀鎖）+Synchronized來保證并發更新的安全。
CAS操作的就是樂觀鎖，每次不加鎖,而是假設沒有沖突而去完成某項操作，如果因為沖突失敗就重試，直到成功為止。

From：周鑫

總結

以上是生活随笔為你收集整理的数据结构总结的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。