閱前：隻是一篇随手的筆記(内容參考來源：資料結構與算法、算法導論、算法精解、算法圖解等書籍)，幫助自己記錄學習過程，順便留些坑。
棧
遵循後進先出原則的有序集合。
生産：
→ +3 | 3 |
→ +2 | 2 | | 2 |
| | → +1 | 1 | | 1 | | 1 | 消費：
| 3 | → -3
| 2 | | 2 | → -2
| 1 | | 1 | | 1 | → -1 | | 隊列
遵循先進先出原則的有序集合。
→ +3 | 3 |
→ +2 | 2 | | 2 |
| | → +1 | 1 | | 1 | | 1 | | 3 |
| 2 | | 3 |
| 1 | → -1 | 2 | → -2 | 3 | → -3 | | 如果要優先隊列，在上面的結構上加入 priority ，根據 priority 排序。
// 比如 值越小優先級越高
| 1 : priority 3 |
| 2 : priority 2 |
| 3 : priority 1 | 連結清單
連結清單存儲的是一系列有序的元素集合，每一項在記憶體中可以不是連續放置的，通過目前元素的屬性引用下一個元素(或加上上一個元素的引用，成雙向連結清單)記憶體位址即可。
其結構如下：
------- ------- -------
| v : 1 | → | v : 2 | → | v : 3 |
| next | next | next | next | next |
------- ------- ------- 或者雙向連結清單：
-------- -------- --------
| v : 1 | next | v : 2 | next | v : 3 |
| next | → | next | → | next |
| return | ← | return | ← | return |
-------- return -------- return -------- 小記：又如 react hooks，或者 fiber 對象鍊(這個連結清單有點畸形)
hooks 使用代碼：
const [num, setNum] = useState(1);
const [str, setStr] = useState("a"); fiber 對象上的 memoizedState 屬性(hooks)：
--------------------
| baseState : 1 |
| baseUpdate : null |
| memoizedState : 1 |
| next |
| queue |
--------------------
next ↓
--------------------
| baseState : "a" |
| baseUpdate : null |
| memoizedState : "a"|
| next |
| queue |
--------------------
next ↓
--------------------
| baseState : null |
| baseUpdate : null |
| memoizedState |
| next : null |
| queue : null |
-------------------- 集合
表示一組裡面的項是無序且唯一的元素，由
{}
表示。
ECMAScript 6 裡的 Set：
const mySet = new Set([1, 2, 3, 3, 4, 5, 6, 7]);
// Set(7) {1, 2, 3, 4, 5, 6, 7} 并集 & 交集 & 差集 & 子集
A ∪ B : [ 1, 2, 3 ] ∪ [ 2, 3, 4 ] => [ 1, 2, 3, 4 ]
A ∩ B : [ 1, 2, 3 ] ∩ [ 2, 3, 4 ] => [ 2, 3 ]
A - B : [ 1, 2, 3 ] - [ 2, 3, 4 ] => [ 1 ]
B - A : [ 2, 3, 4 ] - [ 1, 2, 3 ] => [ 4 ]
B ⊆ A : [ 2, 3 ] ⊆ [ 1, 2, 3 ] => [ 2, 3 ] ES6 Set & WeakSet 具體的自己看
https://www.ecma-international.org/ecma-262/6.0/字典(映射)
表示一組無序且唯一的[鍵, 值]對，通過鍵來查詢值，也由
{}
ECMAScript 6 裡的 Map：
const myMap = new Map([["1", 1], [1, "1"]]);
// Map(2) {"1" => 1, 1 => "1"} ES6 Map & WeakMap 具體的自己看
散清單
在數組中，一般需要知道下标才能夠直接取到需要的值(O(1)，一次操作)，如果使用關鍵字查找，那麼最壞需要 N 次(N 是數組長度，也就是 O(n))；而散清單可以将通過關鍵字搜尋降到 O(1)，其原理是通過散列函數将關鍵字轉換成存儲資料的下标存在在散清單中，當通過關鍵字搜尋時，隻需要通過散列函數取得該下标就能得到值(當然是理想情況下的 O(1)，實際實作中大多還是 O(n)，隻不過它能夠将其搜尋範圍縮小，起碼 java 和 redis 裡的 hashMap 的對應存儲值是連結清單形式的...)。
在散清單中，通過散列函數，将搜查 key 資料的下标，結構如下：
---------------------------------------------------------
| key | hash fn | hash key | hash table |
---------------------------------------------------------
| "aa" | fn("aa") | 149 | [149] [email protected] |
---------------------------------------------------------
| "bb" | fn("bb") | 153 | [153] [email protected] |
---------------------------------------------------------
| "cc" | fn("cc") | 157 | [157] [email protected] |
--------------------------------------------------------- 這裡以取模求散列值的方法為例，用數組來存儲資料：
// 表
var table = [];
// 舉個例子，比如一個簡單的散列計算函數
var hashCode = key => {
let hash = 0;
for (let i = 0; i < key.length; i++) {
hash = hash + key.charCodeAt(i);
}
return hash;
};
// 存值
var put = (key, value) => {
var position = hashCode(key);
table[position] = value;
};
// 取值
var query = key => {
var position = hashCode(key);
return table[position];
};
put("hy", "hello yeshou");
put("ht", "hello tutu");
put("hw", "hello world");
console.log(query("hy")); // output hello yeshou
console.log(query("ht")); // output hello tutu
console.log(query("hw")); // output hello world
put("yh", "hello haha");
console.log(query("hy")); // output hello world
console.log(query("yh")); // output hello world 然而上面的代碼是有問題的，當把
hy
倒過來
yh
的時候，hash 的計算是一樣的值，于是會出現後面的現象，這就是 hash 函數計算的沖突了，更好的 hash 函數可以降低沖突率，比如網上的一些
lose lose
,
djb2
sdbm
等..
djb2
var hashCode = key => {
let hash = 5381; // 初始 hash 值
for (let i = 0; i < key.length; i++) {
hash = hash * 33 + key.charCodeAt(i); // 乘積因子 33
}
return hash % 1013; // mod 5381
};
console.log(hashCode("yh"), hashCode("hy")); // output 762 218 個人認為這種方式生成的 hashMap 空間方面會比較多的無效占用(比如上面的 hashMap length=1012)，但存的資料根據我希望的隻需要有 78 個便足夠，除非設計者本身就需要存這麼多的資料，不然的話可以根據需求去設計初始的 hash 值、乘積因子和 mod 。(保留意見，暫時對這方面研究深度不夠，僅做筆記)
除了精心設計的 hash 函數能夠降低沖突率，一些書籍(如算導、資料結構、算法精解)中還有提到一些"改進 hashMap 存儲規則的方法"來解決可能出現的沖突，如"連結法"和"開放尋址法"。這裡僅簡單提一下.
連結法：保留沖突，在沖突的項上建立是一個雙向連結清單(算導裡推薦的是雙向連結清單，操作的負責度為 O(1))，可以簡單了解為 Map+連結清單 的結合，在查找過程中可以快速定位查找範圍，節省不必要部分的檢索；
開放尋址法：保留沖突，在沖突位置根據指定的探查方式對散清單進行探查，直到探查到空槽來放置元素；元素都存在散清單裡，裝載因子 α 不會超過 1；三種常用的計算開放尋址法的探查序列：線性探查、二次探查、雙重散列。
小記：java hashMap 使用的是連結法，在 JDK-1.8 之前由 load factor = 0.75 (裝載因子 > 0.75)為界限執行擴容；1.8 後以 TREEIFY_THRESHOLD = 8 (連結清單長度 > 8)為界限執行轉換紅黑樹。(保留筆記，之後有興趣再探索擴容和轉換過程)
樹
樹是一種分層資料的抽象模型，一個樹結構包括一系列的存在父子關系的節點，每個節點(除了根節點)都有一個父節點以及零個或多個子節點。
如下結構：
(root)
10
/ \
8 9
/ / | \ \ |
1 2 4 5 7 15 二叉樹 & 二叉搜尋樹
二叉樹是每個結點最多有兩個子節點(樹)的樹結構。
二叉搜尋樹是二叉樹的一種，規則是左側子節點的值小于本身節點的值，右側節點的值大于本身節點的值(使得其操作的複雜度等于樹高)。
二叉搜尋樹結構如下：
(root)
11
/ \
7 15
/ \ / \
5 9 13 17
/ \ / \ / \ / \
4 6 8 10 12 14 16 18 二叉樹的周遊
先序周遊：以優先于後代節點的順序通路每個節點，平常的周遊操作順序就是這種。
代碼如下：
function traverse(node, callback) {
if (node !== null) {
callback(node.v);
traverse(node.left, callback);
traverse(node.right, callback);
}
} 如果拿上面的結構來說，順序是 11,7,5,4,6,9,8,10,15,13,12,14,17,16,18
中序周遊：一種以上行順序通路樹中所有節點的周遊方式，以從最小到最大的順序通路所有節點。
function traverse(node, callback) {
if (node !== null) {
traverse(node.left, callback);
callback(node.v);
traverse(node.right, callback);
}
} 如果拿上面的結構來說，順序是 4,5,6,7,8,9,10,11,12,13,14,15,16,17,18
後序周遊：先通路節點的後代節點，再通路節點本身。(應用：如計算一個目錄和其子目錄中所有檔案所占空間大小)
function traverse(node, callback) {
if (node !== null) {
traverse(node.left, callback);
traverse(node.right, callback);
callback(node.v);
}
} 如果拿上面的結構來說，順序是 4,6,4,8,10,9,7,12,14,13,16,18,17,15,11
紅黑樹
紅黑樹是一顆二叉搜尋樹，它在每個節點上增加了一個存儲位以表示節點的顔色(隻可以是紅色和黑色)，通過對任何一條從根到葉子的簡單路徑上各個節點的顔色進行限制，確定沒有一條路徑會比其他路徑長出 2 倍，因而保證此樹是近似于平衡的(主要是保持樹的平衡，可減短特殊情況下的操作路徑)。
紅黑樹滿足以下規則：
- 根節點是黑色的；
- 每個節點隻能是紅色或者黑色的；
- 每個葉子節點(nil)是黑色的；
- 如果一個節點是紅色的，則它的兩個子節點是黑色的；
- 對每個節點，從該節點到其所有後代葉節點的簡單路徑上均包含相同數目的黑色節點。
對于紅黑樹的操作，會根據規則做一些改變(樹節點的變色和旋轉)，如下案例：
樹中的 n 為 nil，黑色 ； B 為黑色 ； R 為紅色。
(root)
13(B)
/ \
8(R) 17(R)
/ \ / \
1(B) 11(B) 15(B) 23(B)
/ \ / \ / \ / \
n 6(R) n n n n 22(R) 25(R)
// 如果僅插入 14
(root)
13(B)
/ \
8(R) 17(R)
/ \ / \
1(B) 11(B) 15(B) 23(B)
/ \ / \ / \ / \
n 6(R) n n 14(R) n 22(R) 25(R)
/ \
n n
// 如果僅插入 21
(root)
17(B)
/ \
8(R) 23(R)
/ \ / \
1(B) 13(B) 22(B) 25(B)
/ \ / \ / \ / \
n 6(R) 11(R) 15(R) 21(R) n n n
/ \ / \ / \ / \
n n n n n n n n
// 如果僅删除 15
(root)
13(B)
/ \
6(R) 23(R)
/ \ / \
1(B) 8(B) 22(B) 25(B)
/ \ / \ / \ / \
n n n n n n n n B 樹 & B+樹
B 樹将任何和關鍵字相關聯的"資料指針"和關鍵字一起存放在節點中。其結構規則如下：
- 每個節點 x 具有下面屬性；
- x.n，目前存儲節點中的關鍵字個數；
- x.n 個關鍵字本身：x.key_1, x.key_2, ..., x.key_x.n，以非降序存放，使得：x.key_1 <= x.key_2 <= ... <= x.key_x.n；
- x.leaf，一個 boolean 值，如果 x 是葉節點，則是 ture；如果 x 是内部節點，則為 false；
- 每個内部節點 x 還包含 x.n+1 個指向其子節點的指針：x.c_1, x.c_2, ..., x.c_x.n+1，葉節點沒有子節點，是以其 c_i 屬性沒有定義；
- 關鍵字 x.key_1 對存儲在各個字數中的關鍵字範圍進行分割：如果 k_i 為人任意一個存儲在以 x.c_i 為根的子樹中的關鍵字，那麼：k_1 <= x.key_1 <= k2 <= x.key_2 <= ... <= x.key_x.n+1 <= k_x.n+1
- 每個葉節點具有相同是深度，即樹的高度 h；
- 每個節點所包含的關鍵字個數有上界和下界，用 B 樹的最小讀書的固定整數 t >= 2 來表示這些界；
- 除了根節點以外的每個節點必須至少有 t-1 個關鍵字，是以除了根節點以外的每個内部節點至少有 t 個子節點；如果樹非空，根節點至少有一個關鍵字；
- 每個節點至多可包含 2t-1 個關鍵字，是以一個内部節點至多可有 2t 個子節點，當一個節點恰好有 2t-1 個關鍵字時，則該節點是滿了；
B+樹将"資料指針"都存儲在葉節點中，内部節點隻存放關鍵字和子節點的指針，是以最大化了内部節點的分支因子。
小記：據說 mysql 的索引據說 B+樹實作的... 留坑，閑時再做一次對 mysql 的深度探索。
圖
如果說樹是分層的抽象，那圖就更加抽象了，針對結構的抽象模型，因為任何二進制關系都可以用圖來表示。
一個圖結構由點(節點)和線(邊)組成。
如下：
// 無(方)向圖
A - B - C - D
| | |
E F - G - H
| |
-I-
// 有(方)向圖
A → B → C → D
↓ ↓ ↓
E F → G → H
↓ ↓
→I← 搜尋：深度優先 & 廣度優先
圖的周遊可以用來尋找特定的節點或尋找兩個節點之間的路徑，檢查節點之間是否連通或者是否含有環等。
如上述圖，深度優先搜尋(Depth-First Search)的順序是：
A E
A B F G I
A B F G H I
A B C D H I 如上述圖，廣度優先搜尋(Breadth-First Search)的順序是：
A E
A B C
A B F
A B C D
A B F G
A B C D H
A B F G I
A B F G H
A B C D H I
A B F G H I 搜尋過程是拆分成每次搜尋步驟的，可能這樣描述也不是很好了解... 能了解的就了解吧，不能了解的也确實不了解...
一般情況下深度搜尋占用記憶體少但速度較慢，廣度搜尋占記憶體較多但速度較快。
深度優先和廣度優先都有對應的應用場景(個人見解，這塊還缺乏豐富的實踐經驗)：比如要搜尋單個值或特定值，那麼深搜是相對較好的方式；比如搜尋近似值或所有值，則廣搜更具"全局"的概念。
小記：深搜廣搜對于樹也是适用的。同時這塊深入進去還可以帶"記憶"的搜尋(緩存搜尋過程和結果)，動态規劃等知識... 這塊後續會有給出筆記，含分治政策等~
最後
希望自己技術水準越來越好吧 ~(･ェ･。)~ 越學越覺得自己渣...
本文内容僅做學習參考，更多詳情自行官方學習；佛系寫文，不喜勿噴。
![241 Different Ways to Add Parentheses（C代碼版）[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)