⑴ 數據結構與演算法是學什麼的
這個學科學習的內容有數據結構、演算法。
1、數據結構：數據結構主要關注數據的存儲和組織方式。涉及線性結構如數組和鏈表，非線性結構如樹和圖等。通過理解這些結構，能更有效地處理和操作數據。
2、演算法：演算法關註解決特定問題的方法和步驟。涵蓋排序、查找、哈希演算法等多種類型，旨在提高計算效率。學習演算法有助於編寫出更優化、更高效的代碼。
⑵ 數據結構與演算法-基礎（十八）哈希表
上期使用 紅黑樹 實現映射結構，這樣的結構滿足 Key 必須具備可比性，元素有順序地分布 這兩個特點。在實際的應用場景中，存在結構中的 元素是不需要有序的，並且 Key 也不具備可比較性 ，哈希表完全滿足這樣的應用場景。
比如設計一個公司的通訊錄，存放所有員工的通訊信息，就可以拿手機號作為 index，員工的名稱、職位等作為 value。用哈希表的方式可以將添加、刪除和搜索的時間復雜度控制在 O(1)。
這時創建一個數組，手機號作為 index，然後存放 value。這樣能將復雜度控制在 O(1)，但是這種 空間換時間 的方式也造成了一些其他問題，比如空間復雜度大（需要更多的空間），空間使用率極其低，非常浪費內存空間。
哈希表 就是空間換時間的處理方式，但是做了優化，在空間和時間兩個緯度中達到適當的平衡。
哈希表也叫做散列表，整體結構就是一個數組 ，哈希表會將 key 用哈希函數處理之後返回 hash（哈希值），hash 就是哈希表中的 index這樣的處理方式就可以滿足搜索時間是 O(1)，這樣的處理方式就可以滿足搜索時間是 O(1)。因為哈希表中的 key 可能不具備可比較性，所以要做哈希處理。
在執行哈希函數之後返回的 hash，可能會出現相同的情況 ，這樣的情況就是 哈希沖突 。解決哈希沖突常見的方法有這三種：
JDK1.8 解決哈希沖突的方式就是使用鏈地址法，其中的鏈表就是通過鏈表+紅黑樹的組合來實現 。比如當哈希表中的容量大於等於 64，並且單向鏈表的節點數大於 8 時，轉換為紅黑樹，不滿足這個條件時就使用單向鏈表。
哈希函數 是生成哈希值的實現方法，哈希函數的實現步驟大致分為兩步：
hash_code 是生成哈希值的函數，也可以直接用 JAVA 中的標准函數 hashCode() 。
這里可以用 & 位運算替換 % 運算，來提高效率。因為 & 位運算是二進制運算，所以在設計數組的時候，需要將數組的長度設計為 2 的冪次方。
一個良好的哈希函數，可以讓生成的哈希值分布更加均勻，減少哈希沖突的次數，最終可以提升哈希表的性能。
Key 的常見類型可能有證書、浮點數、字元串或者自定義對象，不同的類型生成哈希值的方式也會不一樣，但是目標是一致的，就是 盡量讓每個 Key 的哈希值唯一，盡量讓 Key 中的所有信息參與運算 。
比如在 Java 中， Long 的哈希值實現如下代碼：
這里的 >>> 和 ^ 就是將高 32 bit 和低 32 bit 混合計算出 32 bit 的哈希值。
在計算字元串的哈希值時，可以將字元串拆解成若干個字元，比如 jack，將它拆解成 j、a、c、k（字元的本質就是一個整數，所以 jack 的哈希值可以表示為 j * n3 + a * n2 + c * n1 + k * n0，表達式也可以寫成 [(j * n + a) * n + c] * n + k，代碼實現如下：
看上面代碼時，可以發現，表達式中的 n 使用的是 31 這個數字，那麼為什麼用 31 呢？
因為 31 不僅符合 22 - 1 , 而且它還是個奇素數（既是技術，又是素數，還是質數），素數和其他數相乘的結果比其他方式更容易產生唯一性，減少哈希沖突。
JDK 中，乘數 n 也是用 31，31 也是經過觀測分布結果後的選擇，關於 31 的變體可以有以下幾種：
31 * i = (25 - 1) * i = i * 25 - i = (i << 5) - i