前言

這篇文章是基于個人學習體會整理而來，主要分享 Map 和 Set 并深入 HashMap 和 HashSet 底層所依賴的關鍵數據結構——哈希表，去理解它的工作原理，完成一個簡單的實現。如果內容有不足之處，非常歡迎大家一起指正和交流！

1. 搜索樹

在正式開始學習 Map 和 Set 之前，有必要先了解一種非常基礎且重要的數據結構——搜索樹。許多高效的集合類，比如 TreeMap 和 TreeSet，它們的底層實現就完全離不開搜索樹。

1.1 什么是搜索樹

提到搜索樹，最常接觸到的就是二叉搜索樹（Binary Search Tree），它也經常被稱為二叉排序樹（Binary Sort Tree）。

那么，什么樣的二叉樹才能算作一棵二叉搜索樹呢？它可以是一棵空樹，如果不是，就必須滿足以下幾條性質：

• 左子樹不“大”：若左子樹不為空，則左子樹上所有節點的值均小于其根節點的值。
• 右子樹不“小”：若右子樹不為空，則右子樹上所有節點的值均大于其根節點的值。
• “子孫”也守規矩：它的左、右子樹也分別為二叉搜索樹。

這三條規則確保了樹中的數據總是有序的，為高效查找打下了堅實的基礎。

上圖就是一棵典型的二叉搜索樹，根節點是 8。可以驗證一下它是否滿足上述所有規則。

1.2 查找

理解了二叉搜索樹的定義后，其查找操作的思路就變得非常直觀了。整個過程好比在一個有序的字典里找單詞，每一次比較都能排除掉一半的可能性。

若要在樹中尋找一個特定的 key，查找過程可以這樣描述：

• 從根節點開始： 查找總是從樹的頂端——根節點——出發。
• 比較節點值：
  • 如果當前節點的 key 正好等于要找的 key，說明已經找到了目標。
  • 如果要找的 key 小于當前節點的 key，根據二叉搜索樹的性質，只需要在當前節點的左子樹中繼續查找。
  • 如果要找的 key 大于當前節點的 key，同理，就轉向右子樹繼續查找。
• 持續進行： 這個過程會一直持續下去，直到找到匹配的節點，或者遇到一個空節點（null），后者意味著整個樹里都沒有要找的 key。

這個查找邏輯充分利用了二叉搜索樹的有序性，使得每一次比較都能有效地縮小查找范圍。

參考實現代碼：

       /*** 在二叉搜索樹中查找指定的鍵。* 查找操作的時間復雜度分析：*          - 最好情況：O(logN)，當樹為一棵完全二叉樹時。*          - 最壞情況：O(N)，當樹退化為單支樹時。* @param key 要查找的鍵* @return 找到的節點，未找到則返回 null*/public TreeNode search(int key) {TreeNode cur = root; // 從根節點開始查找while (cur != null) { // 循環直到找到節點或遍歷到空鏈接if (cur.val == key) {return cur; // 找到了，返回當前節點} else if (cur.val > key) {cur = cur.left; // 當前節點值太大，去左子樹找} else {cur = cur.right; // 當前節點值太小，去右子樹找}}return null; // 遍歷完整棵樹都沒找到}

1.3 插入

向二叉搜索樹中插入一個新節點，其過程和查找非常相似。首先要做的，就是找到這個新節點應該被安放的“空位”，以確保插入后，整棵樹的性質不被破壞。

插入操作的步驟可以分解為：

1. 空樹處理： 如果樹是空的（即 root 為 null），那么新節點就直接成為根節點。
2. 尋找插入位置： 如果樹不為空，從根節點開始，像執行查找操作一樣，根據新節點的 key 與當前節點的 key 的大小關系，決定是向左走還是向右走。
3. 找到“父”節點： 這個過程會一直持續，直到找到了一個 null 鏈接。這個 null 鏈接所連接的“父”節點，就是新節點將要被掛載的地方。
4. 完成插入： 將新節點鏈接到“父”節點的左邊或右邊，具體取決于新節點的 key 是小于還是大于“父”節點的 key。

值得注意的是，在很多二叉搜索樹的實現中，通常不允許插入鍵值重復的節點。如果在尋找插入位置的過程中，發現樹中已存在一個相同 key 的節點，插入操作就會直接終止。

我們可以用下面這個流程圖來更清晰地展示整個插入過程：

參考實現代碼：

        private TreeNode root;/*** 向二叉搜索樹中插入一個新鍵。* @param key 要插入的鍵*/public void insert(int key) {// 1. 如果是空樹，新節點直接成為根節點if (root == null) {root = new TreeNode(key);return;}// 2. 尋找插入位置，同時記錄父節點TreeNode cur = root;TreeNode parent = null; // 用于記錄cur的父節點while (cur != null) {if (cur.val < key) {parent = cur;cur = cur.right; // 向右走} else if (cur.val > key) {parent = cur;cur = cur.left; // 向左走} else {// 樹中已存在相同的值，不允許插入，直接返回return;}}// 3. 循環結束，cur為null，parent為待插入位置的父節點TreeNode node = new TreeNode(key);if (parent.val > key) {// 如果新鍵小于父節點，鏈接到左邊parent.left = node;} else {// 如果新鍵大于父節點，鏈接到右邊parent.right = node;}}

1.4 刪除

相比查找和插入，刪除操作是二叉搜索樹中最復雜的一個環節。因為它需要處理多種不同的情況，同時還要保證刪除節點后，樹的結構依然滿足二叉搜索樹的性質。

刪除操作通常根據待刪除節點 cur 的子節點數量分為三種情況來討論：

情況一：cur 沒有子節點（即為葉子節點）

這是最簡單的情況。直接將其父節點 parent 指向 cur 的鏈接斷開（設置為 null）即可。

情況二：cur 只有一個子節點（只有左子樹或右子樹）

處理起來也比較直觀。將 cur 的父節點 parent 直接鏈接到 cur 的那個唯一的子節點上，就相當于“跳過”了 cur 節點，從而完成了刪除。

情況三：cur 有兩個子節點（左右子樹都存在）

這是最復雜的情況。不能簡單地刪除 cur，因為這會留下兩個“孤兒”子樹，破壞整體結構。

這里的核心思想是替換法：

1. 在 cur 的子樹中，找到一個合適的節點來“頂替” cur 的位置。這個“頂替者”必須滿足：比 cur 左子樹的所有節點都大，同時比 cur 右子樹的所有其他節點都小。
2. 滿足這個條件的節點有兩個選擇：
   • cur 左子樹中的最大值節點（即左子樹中最右邊的節點）。
   • cur 右子樹中的最小值節點（即右子樹中最左邊的節點）。
3. 通常選擇后者，即在 cur 的右子樹中尋找值最小的節點（我們稱之為 target）。
4. 將 target 的值賦給 cur。
5. 現在問題就轉化成了刪除 target 節點。因為 target 是其所在子樹中最小的節點，所以它一定沒有左子節點，最多只有一個右子節點。這樣，刪除 target 的問題就退化成了更簡單的情況一或情況二。

參考實現代碼：

       /*** 從二叉搜索樹中刪除指定的鍵。* @param key 要刪除的鍵*/public void remove(int key) {TreeNode cur = root;TreeNode parent = null;// 1. 首先，找到要刪除的節點(cur)及其父節點(parent)while (cur != null) {if (cur.val < key) {parent = cur;cur = cur.right;} else if (cur.val > key) {parent = cur;cur = cur.left;} else {// 找到了！調用輔助方法執行刪除removeNode(parent, cur);return;}}}/*** 真正執行刪除操作的輔助方法。* @param parent 要刪除節點(cur)的父節點* @param cur 要刪除的節點*/private void removeNode(TreeNode parent, TreeNode cur) {// 情況一：待刪除節點沒有左孩子 (包含葉子節點和只有右孩子兩種子情況)if (cur.left == null) {if (cur == root) { // 如果刪除的是根節點root = cur.right;} else if (cur == parent.left) { // 如果cur是其父節點的左孩子parent.left = cur.right;} else { // 如果cur是其父節點的右孩子parent.right = cur.right;}// 情況二：待刪除節點沒有右孩子} else if (cur.right == null) {if (cur == root) { // 如果刪除的是根節點root = cur.left;} else if (cur == parent.left) { // 如果cur是其父節點的左孩子parent.left = cur.left;} else { // 如果cur是其父節點的右孩子parent.right = cur.left;}// 情況三：待刪除節點左右孩子都存在} else {// 采用“替換法”：在右子樹中找到最小的節點(target)來替換curTreeNode targetParent = cur;TreeNode target = cur.right;while (target.left != null) {targetParent = target;target = target.left;}// 將target的值賦給cur，相當于替換了curcur.val = target.val;// 問題轉化為刪除target節點（target最多只有一個右孩子）if (target == targetParent.left) {targetParent.left = target.right;} else {targetParent.right = target.right;}}}

1.5 基礎代碼框架

具體的 search, insert, remove 方法上文已經介紹了，這里簡要搭建起二叉搜索樹的基本骨架。這主要包括兩個部分：樹本身 BinarySearchTree 類，以及構成樹的基石——節點 TreeNode 類。

TreeNode 通常會作為一個內部類，因為它和樹緊密相關。每個節點需要包含三個核心信息：

1. 存儲的數據值（val）。
2. 指向左子節點的引用（left）。
3. 指向右子節點的引用（right）。

下面是一個基礎的實現框架，所有操作都將在這個框架內展開：

public class BinarySearchTree {// 樹的節點定義static class TreeNode {public int val;       // 節點存儲的值private TreeNode left;  // 指向左子樹private TreeNode right; // 指向右子樹// 構造方法private TreeNode(int val) {this.val = val;}}// 樹的根節點private TreeNode root = null;// 此處將添加 search, insert, remove 等方法...
}

1.6 二叉搜索樹的性能分析

之所以選擇二叉搜索樹，就是看中了它高效的查找性能。理論上，插入、刪除和查找操作的效率都取決于樹的高度。

對于一個包含 N 個節點的樹：

• 最優情況： 當樹的形態接近于一棵完全二叉樹時，它的高度大約是 log?N。在這種結構下，每次操作都能排除大約一半的節點，因此時間復雜度為 O(logN)。這是最理想的狀態。

• 最壞情況： 然而，二叉搜索樹的形態與節點的插入順序密切相關。如果插入的序列本身就是有序的（例如，依次插入 1, 2, 3, 4, 5），那么樹就會退化成一個“單鏈表”，或者說是一棵“單支樹”。

  

  在這種極端情況下，樹的高度變成了 N。此時再進行查找，就跟遍歷一個普通鏈表沒什么區別了，時間復雜度會飆升到 O(N)。這顯然違背了使用二叉搜索樹的初衷。

這就引出了一個關鍵問題：有沒有辦法避免這種最壞情況的發生，讓樹無論在何種插入順序下都能維持一個相對平衡的“好身材”，從而保證 O(logN) 的高效性能呢？

答案是肯定的。為了解決這個問題，計算機科學家們設計出了更高級的自平衡二叉搜索樹，比如 AVL樹 和 紅黑樹（TreeMap 和 TreeSet 的底層就是紅黑樹）。它們通過在插入和刪除后進行一些巧妙的“旋轉”操作，來時刻保持樹的平衡，避免退化。

不過，AVL 樹和紅黑樹的實現相對復雜，在這里先埋下一個伏筆，等對基礎的二叉搜索樹有了扎實的理解后，再去探索它們會更有收獲。

2. Map和Set

2.1 概念

Map和Set是一類專門用于搜索的容器或數據結構，其搜索效率與其具體的實現類密切相關。回顧一下常見的搜索方式：

1. 直接遍歷：時間復雜度為O(N)，當元素較多時效率低下。
2. 二分查找：時間復雜度為O(logN)，但前提是序列必須有序。

這兩種方法更適合靜態數據的查找，即數據集合不經常發生插入和刪除操作的場景。例如：

• 根據姓名查詢固定的考試成績。
• 在通訊錄中根據姓名查詢聯系方式。
• 檢查一個單詞是否在某個固定的詞典中。

然而，當需要頻繁地進行插入和刪除，即動態查找時，上述兩種方式就不太適用了。因此，Map 和 Set 作為專為動態查找設計的集合容器，就顯得尤為重要。

2.2 模型

一般把用于搜索的數據稱為關鍵字（Key），與關鍵字對應的值稱為（Value），它們共同構成了一個Key-Value鍵值對。基于此，搜索模型可以分為兩種：

1. 純Key模型： 只關心Key本身是否存在。
   • 快速查找一個單詞是否在詞典中。
   • 快速查找某個名字是否在通訊錄中。
2. Key-Value模型： 關心與Key關聯的Value。
   • 統計文件中每個單詞出現的次數：<單詞, 出現次數>。
   • 身份證系統：<身份證號, 公民信息>。

在Java中，Map 存儲的就是Key-Value鍵值對，而 Set 則只存儲Key，并保證其唯一性。

3. Map 接口的核心用法

了解了底層的搜索樹之后，讓我們回到 Java 集合框架，正式開始探索 Map 這個強大的接口。

3.1 什么是 Map

首先需要明確，Map 是一個接口，它和 Collection 接口處于同一層級，二者之間沒有繼承關系。

Map 的核心思想是存儲鍵值對（Key-Value Pair）。可以把它想象成一本字典，每個“單詞”（Key）都對應著一個“釋義”（Value）。在 Map 中，Key 是唯一的，不允許重復，但 Value 可以重復。

因為 Map 是接口，所以不能直接 new Map()，而是需要實例化它的實現類，最常用的就是 HashMap 和 TreeMap。

3.2 Map 的常用方法

Map 接口定義了一系列非常實用的方法，下面是一些最核心的用法：

方法簽名	方法說明
V put(K key, V value)	將一個鍵值對放入 Map 中。如果 key 已存在，則會用新的 value 覆蓋舊的，并返回舊的 value。
V get(Object key)	根據 key 獲取對應的 value。如果 key 不存在，則返回 null。
V getOrDefault(Object key, V defaultValue)	get 方法的安全版。如果 key 不存在，它會返回一個指定的默認值。
V remove(Object key)	根據 key 刪除對應的鍵值對，并返回被刪除的 value。
boolean containsKey(Object key)	檢查 Map 中是否包含指定的 key。
boolean containsValue(Object value)	檢查 Map 中是否包含指定的 value。
int size()	返回 Map 中鍵值對的數量。
boolean isEmpty()	判斷 Map 是否為空。
Set<K> keySet()	獲取 Map 中所有 key 組成的 Set 集合。
Collection<V> values()	獲取 Map 中所有 value 組成的 Collection。
Set<Map.Entry<K, V>> entrySet()	獲取 Map 中所有鍵值對 (Entry) 組成的 Set 集合。這是遍歷 Map 的最高效方式。

代碼演示

通過一個簡單的例子來看看這些方法如何使用。這里選用 TreeMap，它能保證 key 是有序的。

import java.util.Map;
import java.util.Set;
import java.util.TreeMap;public class MapExample {public static void main(String[] args) {// 1. 創建一個 TreeMap 實例Map<String, String> map = new TreeMap<>();// 2. 使用 put 添加鍵值對map.put("作者", "adam");map.put("主題", "Map和Set");map.put("類型", "筆記");System.out.println("初始Map: " + map);// 3. put 一個已存在的 key，會覆蓋舊的 valueString oldValue = map.put("類型", "博客");System.out.println("更新后的Map: " + map);System.out.println("被覆蓋的舊值: " + oldValue);// 4. 使用 get 獲取 valueString author = map.get("作者");System.out.println("作者是: " + author);// 5. 使用 getOrDefault 獲取一個不存在的 keyString status = map.getOrDefault("狀態", "更新中");System.out.println("文章狀態: " + status);// 6. 檢查 key/value 是否存在System.out.println("是否包含 key '主題': " + map.containsKey("主題"));System.out.println("是否包含 value '博客': " + map.containsValue("博客"));// 7. 高效遍歷 Map (推薦方式)System.out.println("\n--- 使用 entrySet 遍歷 ---");Set<Map.Entry<String, String>> entries = map.entrySet();for (Map.Entry<String, String> entry : entries) {System.out.println("Key: " + entry.getKey() + ", Value: " + entry.getValue());}}
}

3.3 深入 Map.Entry<K, V>

在遍歷 Map 時，我們接觸到了 Map.Entry。這是 Map 接口內部定義的一個靜態內部接口，它代表了 Map 中的一個獨立的“條目”，也就是一個鍵值對。

entrySet() 之所以是最高效的遍歷方式，是因為它一次性就把每個鍵值對（Entry 對象）都拿到了，避免了像 keySet() 那樣需要先拿 key 再通過 get() 去找 value 的額外開銷。

Map.Entry 接口提供了幾個有用的方法：

方法簽名	說明
K getKey()	獲取這個條目的 key。
V getValue()	獲取這個條目的 value。
V setValue(V value)	修改這個條目的 value，并返回舊的 value。

請注意： Map.Entry 只允許修改 value，而不允許修改 key。這是因為 key 在 Map 的結構中起著定位作用（比如在哈希表中計算位置，或在樹中進行比較），一旦修改，會破壞 Map 的內部結構。如果確實需要修改 key，正確的做法是先 remove 舊的鍵值對，再 put 一個新的。

3.4 TreeMap vs HashMap

最后，總結一下 Map 兩個最重要的實現類 TreeMap 和 HashMap 的核心區別，這在面試中經常被問到。

特性	TreeMap	HashMap
底層數據結構	紅黑樹（一種自平衡的二叉搜索樹）	哈希表（數組 + 鏈表/紅黑樹）
排序性	有序。key 按照自然順序或者指定的比較器順序排列。	無序。元素的存儲和迭代順序不固定。
性能	增、刪、查、改的時間復雜度穩定在 O(logN)。	理想情況下，增、刪、查、改的時間復雜度為 O(1)；最壞情況（哈希嚴重沖突）為 O(N)。
對 Key 的要求	key 必須是可比較的。要么 key 的類實現了 Comparable 接口，要么在創建 TreeMap 時提供一個 Comparator。	key 的類必須正確地重寫 hashCode() 和 equals() 方法。
null 支持	key 不允許為 null。value 可以為 null。	key 和 value 都允許為 null（但 key 只能有一個 null）。
適用場景	需要一個有序的 Map 時，比如按 key 排序輸出。	追求極致的性能，且不關心 key 的順序時，HashMap 是首選。

4. Set 接口的核心用法

學習了 Map 之后，再來看 Set 就會感覺非常親切。可以把 Set 理解成一種特殊的 Map，它只關心 key，而不關心 value。Set 的核心價值在于保證集合中元素的唯一性。

在 Java 的集合框架中，Set 接口繼承自 Collection 接口。

一個非常巧妙的設計是，許多 Set 的實現類（如 HashSet、TreeSet）的底層就是用對應的 Map（HashMap、TreeMap）來實現的。它們將要存入 Set 的元素作為 Map 的 key，而 value 則存一個固定的、無意義的占位對象。這樣一來，就天然地利用了 Map 中 key 唯一的特性，來實現 Set 中元素的唯一性。

4.1 Set 的常用方法

由于 Set 繼承自 Collection，它包含了 add, remove, contains, size 等常用方法。這里重點關注 add 方法的行為。

方法簽名	說明
boolean add(E e)	嘗試將元素 e 添加到 Set 中。如果 e 不存在，則添加成功，返回 true；如果 e 已存在，則添加失敗，Set 不變，返回 false。
boolean contains(Object o)	判斷 Set 中是否包含指定的元素。
boolean remove(Object o)	如果 Set 中存在指定元素，則將其刪除。
int size()	返回 Set 中元素的數量。
Iterator<E> iterator()	返回一個可以用于遍歷 Set 中元素的迭代器。

Set 最強大的功能之一就是集合去重。例如，可以非常方便地利用 addAll 方法將一個 List 中的所有元素添加到一個 Set 中，從而快速得到一個不含重復元素的新集合。

4.2 TreeSet vs HashSet

和 Map 類似，Set 最常用的兩個實現類是 TreeSet 和 HashSet。它們之間的區別也和 TreeMap 與 HashMap 的區別一一對應。

特性	TreeSet	HashSet
底層數據結構	TreeMap (紅黑樹)	HashMap (哈希表)
排序性	有序。元素按照自然順序或者指定的比較器順序排列。	無序。元素的存儲和迭代順序不固定。
性能	增、刪、查的復雜度穩定在 O(logN)。	理想情況下，增、刪、查的復雜度為 O(1)。
對元素的要求	元素必須是可比較的 (實現 Comparable 或提供 Comparator)。	元素的類必須正確地重寫 hashCode() 和 equals() 方法。
null 支持	不允許添加 null 元素。	允許添加一個 null 元素。
適用場景	需要一個能自動排序且元素唯一的集合。	追求高性能，且不關心元素順序的去重場景。

4.3 TreeSet 使用案例

來看一個 TreeSet 的具體例子，直觀地感受它的唯一性和有序性。

import java.util.Set;
import java.util.TreeSet;
import java.util.Iterator;public class SetExample {public static void main(String[] args) {// 1. 創建一個 TreeSet 實例Set<Integer> numberSet = new TreeSet<>();// 2. 添加元素numberSet.add(50);numberSet.add(20);numberSet.add(80);numberSet.add(20); // 嘗試添加重復元素// 3. 打印 Set，觀察其唯一性和有序性// 重復的 20 不會被添加進去，且輸出結果是排序好的System.out.println("TreeSet中的元素: " + numberSet); // 輸出: [20, 50, 80]// 4. 檢查是否包含某個元素System.out.println("是否包含 80: " + numberSet.contains(80)); // 輸出: trueSystem.out.println("是否包含 99: " + numberSet.contains(99)); // 輸出: false// 5. 刪除元素numberSet.remove(50);System.out.println("刪除 50 后的Set: " + numberSet); // 輸出: [20, 80]// 6. 使用迭代器遍歷 SetSystem.out.println("\n--- 使用迭代器遍歷 ---");Iterator<Integer> iterator = numberSet.iterator();while (iterator.hasNext()) {System.out.print(iterator.next() + " "); // 輸出: 20 80 }System.out.println();}
}

5. 深入哈希表 (Hash Table)

前面我們學習了基于紅黑樹的 TreeMap 和 TreeSet，它們的各項操作性能穩定在 O(logN)。但我們還提到，HashMap 和 HashSet 在理想情況下的性能可以達到驚人的 O(1)。這背后就是數據結構——哈希表。

5.1 哈希表的核心思想

回顧一下，在數組和鏈表中查找元素，需要從頭到尾一個個比較，時間復雜度是 O(N)；在平衡二叉搜索樹中，利用元素的有序性，每次比較都能排除一半的元素，時間復雜度是 O(logN)。

那么，能不能做得更極致一點，不經過任何比較，一次就定位到元素的位置？

哈希表的思想正是如此。它試圖建立一種從 key 到其存儲位置（數組下標）的直接映射關系。這個映射關系通過一個特殊的函數——哈希函數（Hash Function） 來實現。

• 插入時：用哈希函數計算出 key 對應的數組下標，然后直接把元素存到這個位置。
• 查找時：再次用哈希函數計算出 key 對應的數組下標，然后直接去那個位置取元素。

如果一切順利，整個過程只需要一次計算和一次數組訪問，時間復雜度就是 O(1)，效率極高。

5.2 哈希沖突 (Hash Collision)

理想很豐滿，但現實是，我們不可能讓每一個 key 都完美地映射到一個獨一無二的數組下標。原因很簡單：key 的取值范圍（比如所有可能的字符串）是近乎無限的，而我們的數組容量是有限的。

這就必然導致一個問題：兩個不同的 key，通過哈希函數計算后，可能會得到相同的數組下標。這種情況，就稱之為哈希沖突或哈希碰撞。

5.3 如何降低哈希沖突

雖然哈希沖突無法完全避免，但可以通過精心的設計來顯著降低沖突的概率。主要有兩個抓手：設計一個好的哈希函數，以及維持一個合理的負載因子。

5.3.1 設計優秀的哈希函數

一個好的哈希函數，應該能將 key 盡可能均勻地散布到數組的各個位置。常見的哈希函數設計方法有：

• 除留余數法：這是最常用的一種方法。hash(key) = key的整數表示 % 數組長度。為了讓分布更均勻，這里的“數組長度”通常會選擇一個質數。
• 直接定址法：hash(key) = A * key + B。這種方法簡單，但只適用于 key 的分布比較連續且范圍不大的情況。
• 其他方法：還有平方取中法、折疊法等，適用于特定場景。

Java 中的 String、Integer 等類都精心設計并重寫了 hashCode() 方法，來保證產生的哈希碼有很好的散列效果。

5.3.2 調節負載因子 (Load Factor)

負載因子是衡量哈希表“擁擠程度”的一個關鍵指標。

負載因子 = 已存入的元素個數 / 哈希表的總容量

可以把哈希表想象成一個停車場。如果停車場（總容量）很大，但只停了幾輛車（元素個數），那新來的車很容易就能找到車位，沖突就少。但如果停車場快滿了，新來的車想找個車位就得轉悠半天，沖突概率大大增加。

因此，當負載因子過高時，沖突會急劇增加，哈希表的性能會嚴重下降。為了解決這個問題，HashMap 等實現會在負載因子達到某個閾值（默認為 0.75）時，進行擴容（Rehashing）——創建一個更大的新數組，并把所有舊元素重新計算哈希值后放入新數組中。這雖然會帶來一時的開銷，但保證了后續操作的長期高效。

5.4 如何解決哈希沖突

即便我們盡了最大努力，沖突依然會發生。當沖突真的發生時，該怎么辦呢？解決沖突的主流方案有兩種：閉散列和開散列。

5.4.1 閉散列 (Closed Hashing)

閉散列，也叫開放定址法。它的核心思想是：如果這個位置被人占了，那就再找一個空位置存進去。所有元素都存儲在哈希表這個數組內部，不會有外部的存儲結構。

尋找“下一個”空位置主要有兩種探測方法：

1. 線性探測 (Linear Probing)
   最樸素的想法：如果位置 i 被占了，就去看看 i+1；如果 i+1 也被占了，就看 i+2，以此類推，直到找到一個空位。

   • 優點：實現簡單。
   • 缺點：容易造成“聚集”現象。即一旦發生沖突，后面的元素也很可能繼續沖突，大家擠在一起，形成一長串連續的占位，嚴重影響后續的查找效率。
   • 刪除問題：不能直接刪除元素，否則會“斷開”探測路徑。通常采用懶刪除（標記刪除），即給被刪除的位置打上一個“已刪除”的標記。

2. 二次探測 (Quadratic Probing)
   為了緩解線性探測的聚集問題，二次探測在尋找下一個位置時，不再是簡單地 +1，而是按照 +12, -12, +22, -22… 的步長來跳躍式地探測。
   $$H_i=(H_0\pm i^2)(\mathrm{mod}m)$$

   • 優點：能有效減輕線性探測的聚集問題。
   • 缺點：實現更復雜，且對負載因子有更嚴格的要求（通常不能超過 0.5），否則可能找不到空位。

5.4.2 開散列 (Open Hashing)

開散列，也叫拉鏈法或鏈地址法 (Separate Chaining)。這是 Java HashMap 采用的解決方式，也是目前最主流、最重要的方法。

它的核心思想是：數組的每個位置不直接存儲元素，而是存儲一個容器（比如鏈表）的頭節點。

• 當一個新元素通過哈希函數定位到某個位置時，不關心這個位置是否“有人”，而是直接將這個新元素插入到該位置對應的鏈表中。
• 如果后續還有其他元素也映射到這個位置，它們會繼續被添加到這個鏈表的末尾。

這樣一來，所有沖突的元素都被串在同一個鏈條上，查找時只需先定位到數組下標，再遍歷這個短鏈表即可。

為了防止鏈表過長導致性能退化，Java 8 的 HashMap 做了一個重要的優化：當某個位置的鏈表長度超過一個閾值（默認為 8）時，這個鏈表會自動轉化為一棵紅黑樹，從而將該位置的查找時間復雜度從 O(N) 穩定到 O(logN)。這種設計兼顧了空間和時間效率，是哈希表工程實踐中的典范。

開散列法可以看作是把一個在大集合中的搜索問題，巧妙地轉化為了在多個小集合中進行搜索。

5.5 代碼實現

下面是一個基于拉鏈法實現的哈希表示例。

基本類型版本

/*** 基于拉鏈法的哈希桶實現 (處理哈希沖突)* 數組的每個元素都是一個單鏈表*/
public class HashBuck {/*** 內部節點類，用于存儲鍵值對*/static class Node {public int key;public int val;public Node next;public Node(int key, int val) {this.key = key;this.val = val;}}// 底層數組，每個元素是一個鏈表的頭節點public Node[] array = new Node[10];// 當前哈希表中存儲的鍵值對數量public int usedSize;// 默認的負載因子閾值，當達到此值時觸發擴容public static final double DEFAULT_LOAD_FACTOR = 0.75;/*** 添加或更新鍵值對* @param key 鍵* @param val 值*/public void push(int key, int val) {// 1. 根據 key 計算哈希桶的索引int index = key % array.length;// 2. 遍歷當前桶的鏈表，查找 key 是否已存在Node cur = array[index];while (cur != null) {if (cur.key == key) {// 如果 key 已存在，更新其值并直接返回cur.val = val;return;}cur = cur.next;}// 3. 如果 key 不存在，則創建一個新節點并使用頭插法插入到鏈表中Node node = new Node(key, val);node.next = array[index];array[index] = node;usedSize++;// 4. 檢查是否需要擴容if (getLoadFactor() >= DEFAULT_LOAD_FACTOR) {resize();}}/*** 對哈希表進行擴容，通常是擴大為原來的兩倍*/private void resize() {// 創建一個容量為原來兩倍的新數組Node[] newArray = new Node[2 * array.length];// 遍歷舊數組的每個桶，將節點重新散列到新數組for (int i = 0; i < array.length; i++) {Node cur = array[i];while (cur != null) {Node curNext = cur.next; // 保存下一個節點int newIndex = cur.key % newArray.length;// 使用頭插法將節點插入到新數組的對應桶中cur.next = newArray[newIndex];newArray[newIndex] = cur;cur = curNext; // 繼續處理下一個節點}}// 將舊數組引用指向新數組array = newArray;}/*** 計算當前哈希表的負載因子* @return 負載因子*/private double getLoadFactor() {return usedSize * 1.0 / array.length;}/*** 根據 key 獲取對應的 value* @param key 鍵* @return 如果找到則返回對應的 value，否則返回 -1*/public int getVal(int key) {int index = key % array.length;Node cur = array[index];while (cur != null) {if (cur.key == key) {return cur.val;}cur = cur.next;}return -1; // 未找到 key}
}

泛型版本

/*** 泛型版本的哈希桶實現* 基于拉鏈法處理哈希沖突，支持泛型鍵值對* @param <K> 鍵的類型* @param <V> 值的類型*/
public class HashBuck2<K, V> {static class Node<K, V> {public K key;public V val;public Node<K, V> next;public Node(K key, V val) {this.key = key;this.val = val;}}public Node<K, V>[] array = (Node<K, V>[]) new Node[10];public int usedSize;public static final double DEFAULT_LOAD_FACTOR = 0.75;/*** 添加或更新鍵值對* @param key 鍵* @param val 值*/public void push(K key, V val) {// 1. 使用 key 的 hashCode() 方法計算哈希值int hashCode = key.hashCode();// 2. 計算在數組中的索引int index = hashCode % array.length;// 3. 遍歷鏈表查找 keyNode<K, V> cur = array[index];while (cur != null) {// 對于引用類型，必須使用 equals() 方法比較是否相等if (cur.key.equals(key)) {cur.val = val;return;}cur = cur.next;}// 4. key 不存在，創建新節點并頭插到鏈表Node<K, V> node = new Node<>(key, val);node.next = array[index];array[index] = node;usedSize++;// 5. 檢查負載因子，判斷是否需要擴容if (getLoadFactor() >= DEFAULT_LOAD_FACTOR) {resize();}}private void resize() {Node<K, V>[] newArray = (Node<K, V>[]) new Node[2 * array.length];for (int i = 0; i < array.length; i++) {Node<K, V> cur = array[i];while (cur != null) {Node<K, V> curNext = cur.next;int hashCode = cur.key.hashCode();int newIndex = hashCode % newArray.length;cur.next = newArray[newIndex];newArray[newIndex] = cur;cur = curNext;}}array = newArray;}private double getLoadFactor() {return usedSize * 1.0 / array.length;}/*** 根據 key 獲取對應的 value* @param key 鍵* @return 如果找到則返回對應的 value，否則返回 null*/public V getVal(K key) {int hashCode = key.hashCode();int index = hashCode % array.length;Node<K, V> cur = array[index];while (cur != null) {if (cur.key.equals(key)) {return cur.val;}cur = cur.next;}return null; // 未找到 key}
}

5.6 性能分析

雖然哈希表一直在和沖突做斗爭，但在設計良好（哈希函數均勻、負載因子合理）的情況下，可以認為哈希表的沖突率是可控的，即每個桶中的鏈表長度是一個常數。因此，通常意義下，哈希表的插入、刪除、查找時間復雜度可以認為是O(1)。

5.7 和 Java 集合框架的關系

1. HashMap 和 HashSet 就是 Java 中利用哈希表實現的 Map 和 Set。
2. Java 中的 HashMap 正是采用**哈希桶（拉鏈法）**方式來解決沖突的。
3. 當沖突鏈表的長度大于某個閾值（8）時，Java 會將鏈表轉化為紅黑樹以優化該桶的查詢性能。
4. Java 中計算哈希值實際上是調用對象的 hashCode() 方法，而進行 key 的相等性比較是調用 key 的 equals() 方法。因此，如果要用自定義類作為 HashMap 的 key 或 HashSet 的元素，必須正確地重寫 hashCode() 和 equals() 方法，并保證 equals() 相等的對象，其 hashCode() 一定相等。