往期《C++初階》回顧：

《C++初階》目錄導航

---

往期《C++進階》回顧：
/------------ 繼承多態 ------------/
【普通類/模板類的繼承 + 父類&子類的轉換 + 繼承的作用域 + 子類的默認成員函數】
【final + 繼承與友元 + 繼承與靜態成員 + 繼承模型 + 繼承和組合】
【多態：概念 + 實現 + 拓展 + 原理】
/------------ STL ------------/
【二叉搜索樹】
【AVL樹】
【紅黑樹】
【set/map 使用介紹】
【set/map 模擬實現】

前言

hi~ 小伙伴們大家好啊！?(ˊ?ˋ*)?
今天是什么節來著……嗯~ o(￣▽￣)o，今天是公元二〇二五年九月十三日，星期六，上午太陽照常從地平線升起，鼠鼠也照常“偷吃”了兩個包子(≧?≦*)ゞ，一切都正常！

今天我們要習得的是難度為S級的 【哈希表】，小伙伴們你們準備好要爆炸了嗎？
哦不對，是準備好腦袋瓜子“砰”一下了嗎？☆ﾐ(o*ｕωｕ)ﾉｼ

其實單看 “哈希表” 本身，它更偏向數據結構的范疇。但鼠鼠還是把它放進 C++ 的學習內容里，原因很簡單：因為我們學哈希表，終極目標就是親手擼出 unordered_set / unordered_map
就像之前啃完“二叉搜索樹 + AVL 樹 + 紅黑樹”是為了搞定 set/map 一樣，套路熟悉不？(????)

理論鋪墊已就位，接下來請系好安全帶，一起沖進哈希表的“O(1) 宇宙”吧！?(?ｖ?｡)

------------概念介紹------------

1. 什么是哈希？

哈希（Hash），也稱為散列：是一種將任意長度的輸入數據（通常稱為 “鍵” 或 “關鍵字”）通過特定的數學算法（稱為 “哈希函數”）映射為固定長度輸出的技術。

• 這個輸出值被稱為 “哈希值”、“散列值” 或 “哈希碼”。

• 哈希的核心目的是快速實現數據的查找、存儲和比較，廣泛應用于哈希表、密碼學、數據校驗等領域。

------------核心術語------------

一、哈希函數

哈希函數（Hash Function）：是哈希表（Hash Table）的核心組成部分，它的作用是將任意長度的輸入數據（稱為 “鍵” 或 “關鍵字”）映射到一個固定長度的輸出值（稱為 “哈希值” 或 “散列值”）

• 這個輸出值通常用于確定該鍵在哈希表中的存儲位置。

1. 哈希函數的核心特點是什么？

哈希函數的核心特點：

• 確定性：同一輸入必須始終映射到同一個哈希值。

  • 例如：輸入字符串"apple"每次通過哈希函數計算，結果都應相同

• 壓縮性：無論輸入數據的長度如何，輸出的哈希值長度是固定的。

  • 例如：常用的 MD5 哈希函數會將任意輸入映射為 128 位的哈希值，而哈希表中常用的哈希函數可能將鍵映射為0~n-1（n為哈希表長度）的整數

• 高效性：計算哈希值的過程應快速且易于實現，時間復雜度通常為$O(1)$或$O(k)$（$k$為輸入數據的長度），避免成為哈希表操作的性能瓶頸。

2. 哈希函數的設計目標是什么？

哈希函數的設計目標：

1. 均勻分布：理想情況下，哈希函數應將不同的鍵均勻地映射到哈希表的各個位置，避免大量鍵集中在少數位置（稱為 “哈希沖突”）
   • 均勻分布能保證哈希表的操作（插入、查找、刪除）效率接近$O(1)$
2. 減少沖突：由于輸入空間（可能的鍵）遠大于輸出空間（哈希表長度），哈希沖突無法完全避免，但好的哈希函數能最大限度降低沖突概率

3. 常見的哈希函數有哪些？

直接定址法

直接定址法：通過直接利用關鍵字本身或關鍵字的某個線性函數來確定哈希地址，從而實現關鍵字到存儲位置的映射。

• 直接定址法是一種簡單直觀的哈希函數構造方法。

---

核心公式和基本原理：

直接定址法的哈希函數公式通常為：

H(key) = key 或 H(key) = a × key + b

• key：是待映射的關鍵字。（需要存儲的數據的標識）
• a 和 b：是常數。（a ≠ 0，用于對關鍵字進行線性變換）
• H(key)：是計算得到的哈希地址。（即：數據在哈希表中的存儲位置）

---

優缺點與適用場景：

• 優點

  • 簡單高效：無需復雜計算，直接通過關鍵字映射地址，時間復雜度為 $O(1)$

  • 無沖突：只要關鍵字不重復，計算出的哈希地址一定唯一（因為是線性映射，不存在不同關鍵字映射到同一地址的情況）

• 缺點

  • 空間浪費大：如果關鍵字的范圍很大（例如：key 是 1000 到 1000000 的整數），哈希表需要開辟對應范圍的空間，但實際存儲的關鍵字可能很少，導致大量空間閑置

  • 關鍵字需為整數：若關鍵字是非整數（例如：字符串、浮點數），需先轉換為整數才能使用，否則無法直接映射

• 場景

  • 關鍵字的范圍較小且連續（或分布集中）

  • 關鍵字可以直接作為地址（或通過簡單線性變換后作為地址）

---

直接定址法的實際使用案例：

• 存儲學生的年齡（范圍通常在 5-25 歲），可直接用 H(age) = age，哈希表大小只需 30 左右
• 存儲月份（1-12 月），可用 H(month) = month，哈希表大小為 12 即可

除法散列法

除法散列法：核心邏輯是用關鍵字對一個整數取余，把大范圍的關鍵字映射到哈希表的有效下標區間，以此確定存儲位置。

• 除法散列法是哈希函數構造方法里的經典手段。

---

核心公式與基本原理：

除法散列法的哈希函數一般形式為：

H(key) = key % m

• key：是待映射的關鍵字。（可以是整數、經轉換后的字符串哈希值等）
• m：是哈希表的大小。（通常是數組長度，決定了哈希地址的范圍）
• H(key)：是計算出的哈希地址。（即：關鍵字在哈希表中的存儲下標）

本質：利用取余運算的 “截斷” 特性，把任意整數 key 映射到 [0, m-1] 區間，讓關鍵字適配哈希表的下標范圍

---

關鍵特性與優缺點：

優點

• 實現簡單：一行取余運算即可完成映射，編碼成本極低

• 適用性廣：只要能轉成整數（或本身是整數）的關鍵字都能用，涵蓋整數、字符串、自定義結構體（需先哈希轉整數）

• 控制范圍：通過調整 m 靈活控制哈希地址范圍，適配不同內存、性能需求

---

缺點

• 沖突概率與m強相關：若m選得不好（比如：是關鍵字的公約數），會導致大量沖突

  • 例如：關鍵字都是偶數、m=4，則哈希地址只能是 0,2，沖突概率飆升

• 依賴m的選取：m 若為合數（尤其是 2 的冪），易讓哈希地址分布不均（比如：二進制低位相同的關鍵字會扎堆）

• 不適用于動態擴容：哈希表擴容后 m 改變，所有關鍵字需重新計算哈希地址，遷移成本高

---

優化：m 的選取原則

除法散列法的效果高度依賴 m 的選擇，工程中常用以下策略優化：

---

優化策略一：選質數

優先選質數作為 m，能大幅降低沖突概率。原因是：質數的約數少，關鍵字取余后分布更均勻。

• 反例：若 m=10（合數），關鍵字 10、20、30 都會映射到 0，沖突嚴重
• 正例：若 m=11（質數），上述關鍵字會映射到 0、9、8，分布更分散

---

優化策略二： 避免 m=2^k/10^X

若 M = 2^X，key % M 等價于 “保留 key 的最后 X 位二進制數”。此時，只要不同 key 的最后 X 位二進制數相同，哈希值就會沖突。

• 取M = 16（即2^4），計算63 % 16 和 31 % 16：

  • 63 的二進制后 8 位是 00111111，取最后 4 位 1111 → 余數 15
  • 31 的二進制后 8 位是 00011111，取最后 4 位 1111 → 余數 15

• 可見，看似無關的 63 和 31，因最后 4 位相同，哈希值沖突。

若 M = 10^X，key % M 等價于 “保留 key 的最后 X 位十進制數”。此時，只要不同 key 的最后 X 位十進制數相同，哈希值就會沖突。

• 取M = 100（即10^2），計算112 % 100 和 12312 % 100
• 兩者最后 2 位都是 12 → 余數均為 12，哈希值沖突

---

優化策略三：結合關鍵字分布調整

若已知關鍵字的分布（如：都是奇數、或集中在某個區間），選 m 時盡量讓余數覆蓋更全。

• 關鍵字全是奇數，m 選奇數可避免 “余數全為奇數 / 偶數” 的極端情況。

乘法散列法

乘法散列法：

• 先將關鍵字 key 與一個在 (0, 1) 之間的常數 A 相乘，得到的結果會是一個小數
• 取這個小數的小數部分，再乘以哈希表的大小 m
• 最后對結果向下取整，就得到了哈希值

---

核心公式與基本原理：

乘法散列法的哈希函數公式可以表示為：

$h(key)=?m\times (key\times A\mathrm{mod}1)?$

• key：是要進行哈希計算的關鍵字。（它可以是整數、字符串等各種數據類型對于非整數類型，通常需要先通過其他方式將其轉換為整數）
• A：是一個常數。（取值范圍在 (0, 1) 之間，并且通常是一個無理數 ，常見的取值如 $\frac{\sqrt{5}?1}{2}$（黃金分割數，約等于 0.6180339887），這樣能讓哈希值分布得更均勻）
• m：是哈希表的大小。（即：哈希值的范圍是 [0, m - 1]）
• $\mathrm{mod}1$：表示取小數部分。（例如： $3.14\mathrm{mod}1$ 結果為 0.14）
• $??$：是向下取整符號。（例如： $?3.9?$ 結果為 3）

---

關鍵特性與優缺點：

優點

• 哈希值分布均勻：當常數 A 選擇合適時，乘法散列法能讓哈希值在哈希表中較為均勻地分布，減少哈希沖突的發生。這是因為乘法運算能充分打亂關鍵字的二進制位，使得不同關鍵字映射到相同哈希值的概率降低。

• 對哈希表大小要求靈活：不像除法散列法對哈希表大小 m 的取值有較多限制（如：盡量取質數等），乘法散列法對 m 的取值相對自由，m 可以是任意正整數。

• 計算效率較高：乘法散列法主要涉及乘法、取小數部分和取整操作，在現代計算機硬件上，這些操作都能高效執行。

---

缺點

• 常數 A 的選擇有難度：雖然理論上常數 A 只要在 (0, 1) 之間且為無理數就能工作，但要找到一個能在實際應用中讓哈希值分布最優的 A 并不容易，往往需要通過實驗和對數據特征的了解來確定。

• 實現相對復雜：相較于簡單的除法散列法，乘法散列法的計算步驟更多，實現代碼也相對復雜一些。

---

使用乘法散列法計算哈希值步驟示例：

假設要對整數關鍵字 key = 12345 進行哈希計算，哈希表大小 m = 100，常數 A 取黃金分割數 $\frac{\sqrt{5}?1}{2}$ ，計算過程如下：

1. 計算 key * A：$12345?\frac{\sqrt{5}?1}{2}\approx 12345?0.6180339887=7625.08749$
2. 取小數部分：$7625.08749\mathrm{mod}1=0.08749$
3. 乘以哈希表大小：$0.08749?100=8.749$
4. 向下取整得到哈希值：$?8.749?=8$

全域散列法

全域散列法：是一種隨機化哈希技術，通過從精心設計的哈希函數族中隨機選擇哈希函數，確保即使對于最壞情況下的輸入也能獲得良好的平均性能。

---

基本概念：

在普通的哈希函數設計中，如果哈希函數選擇不當，可能會出現一些極端情況

• 例如：對于給定的哈希函數，某些特定的關鍵字集合會導致大量的哈希沖突，使得哈希表退化為鏈表，操作時間復雜度從期望的 $O(1)$ 變為 $O(n)$

全域散列的核心思想是從一個哈希函數族中隨機選擇哈希函數，使得對于任意給定的關鍵字集合，哈希沖突的概率都被控制在一個較低的水平。

---

核心原理：

全域散列法基于一個哈希函數族 $\mathcal{H}$，這個函數族包含了多個不同的哈希函數。
在使用全域散列時，會從這個函數族中隨機選擇一個哈希函數 $h$ 來進行哈希操作。

從數學角度來說，對于任意兩個不同的關鍵字 $x$ 和 $y$，哈希函數族 $\mathcal{H}$ 滿足：

∣{h∈H:h(x)=h(y)}∣∣H∣≤1m\frac{|\{h \in \mathcal{H}: h(x) = h(y)\}|}{|\mathcal{H}|} \leq \frac{1}{m}∣H∣∣{h∈H:h(x)=h(y)}∣?≤m1?

• $|\mathcal{H}|$ ：表示哈希函數族中哈希函數的個數
• $m$ ：是哈希表的大小

也就是說，從哈希函數族中隨機選取一個哈希函數，使得兩個不同關鍵字哈希值相同（產生沖突）的概率不超過 $\frac{1}{m}$
這樣就能保證在平均情況下，哈希沖突的數量是比較少的。

---

全域散列法的實現步驟：

• 定義哈希函數族：需要先定義一個哈希函數族。

  以簡單的整數關鍵字為例，假設關鍵字 $k$ 是一個整數，哈希表大小為 $m$，可以定義哈希函數族如下：

  • 設 $p$ 是一個比任何關鍵字值都大的質數

  • 對于每個 a∈{1,2,?,p?1}a \in \{1, 2, \cdots, p - 1\}a∈{1,2,?,p?1} 和 b∈{0,1,?,p?1}b \in \{0, 1, \cdots, p - 1\}b∈{0,1,?,p?1}

  • 定義哈希函數：$h_{a,b}(k)=((ak+b)\mathrm{mod}p)\mathrm{mod}m$

  所有這樣的哈希函數構成了一個哈希函數族 $\mathcal{H}$

  假設：$P=17$，$M=6$，$a=3$，$b=4$，則 $h_{34}(8)=((3\times 8+4)\%17)\%6=5$

• 隨機選擇哈希函數：

  • 在構建哈希表時，從哈希函數族 $\mathcal{H}$ 中隨機選擇一個哈希函數 $h_{a,b}$ 來使用

  • 可以通過生成隨機數來確定參數 $a$ 和 $b$ 的值，從而確定具體的哈希函數

• 進行哈希操作：

  • 使用選定的哈希函數對關鍵字進行哈希計算，將關鍵字映射到哈希表的相應位置

  • 在插入、查找和刪除操作中，都使用這個選定的哈希函數來確定關鍵字在哈希表中的位置

二、負載因子

1. 什么是負載因子？

負載因子（Load Factor）：是哈希表設計與性能分析中的核心概念，用于衡量哈希表的 “填充程度”，直接影響哈希沖突概率和內存利用率

---

負載因子的定義： 哈希表中已存儲的元素數量 / 哈希表的總容量（桶的數量）

負載因子的計算公式：$\lambda =\frac{n}{m}$

• n：是哈希表中當前存儲的有效元素數量
• m：是哈希表的總容量（即桶數組的長度，如：vector<Node*> 的大小）

2. 負載因子對哈希表的性能有什么影響？

對哈希表性能的影響：

負載因子是哈希沖突概率和內存利用率的 “平衡器”，核心影響如下：

（1）負載因子越小 → 哈希沖突概率越低

• 當 $\lambda \to 0$（如：哈希表很空），每個桶的平均元素數少，鏈表 / 探測鏈短，插入、查找、刪除的時間復雜度接近 $O(1)$
• 但內存浪費嚴重（大量桶閑置），空間利用率低。

---

（2）負載因子越大 → 哈希沖突概率越高

• 當 $\lambda \to 1$（如：哈希表快滿），桶的平均元素數多，鏈表 / 探測鏈長，操作時間復雜度會退化到 $O(n)$（極端情況哈希表退化為鏈表）
• 內存利用率高，但性能暴跌。

3. 負載因子超過閾值時會發什么？

負載因子驅動的擴容流程：

當負載因子超過閾值時，哈希表會觸發擴容（Resize），流程如下：

1. 新建更大的桶數組：新容量通常是原容量的 2 倍（或接近的質數，依實現而定）
2. 重新映射所有元素：遍歷舊哈希表的所有元素，用新哈希函數（或新容量重新取模）將元素插入新桶
3. 釋放舊內存：銷毀舊桶數組，替換為新桶數組

三、哈希沖突

哈希沖突（Hash Collision）：是哈希表設計與實現中無法避免的核心問題，指不同的關鍵字通過哈希函數計算后，得到相同的哈希地址的情況。（即：映射到哈希表的同一個桶或位置）

• 定義：對于兩個不同的關鍵字 $ke{y}_1\ne ke{y}_2$，若它們的哈希值滿足 $h(ke{y}_1)=h(ke{y}_2)$，則稱這兩個關鍵字發生了哈希沖突。
• 本質：哈希函數是 “多對一” 的映射（輸入空間無限，輸出空間有限），根據鴿巢原理，沖突必然存在。

---

產生沖突的因素：

1. 哈希函數的 “壓縮映射” 特性

• 哈希函數將任意長度的輸入（如：字符串、整數、對象）映射到固定長度的哈希值（如：size_t 類型）

• 再通過取模等操作映射到哈希表的桶索引

• 這種 “壓縮” 必然導致不同輸入映射到同一輸出

2. 哈希表容量與關鍵字分布

• 若哈希表容量 m 過小，或關鍵字分布集中（如大量關鍵字的哈希值在同一區間），沖突概率會急劇上升
  • 示例：哈希表容量 (m=10)，若所有關鍵字的哈希值取模后都為 5，則所有數據會沖突到第 5 個桶。

四、沖突處理

方法一：開放定址法

開放定址法（Open Addressing）：開放定址法是處理哈希沖突的一種系統化方法，所有元素都存儲在哈希表數組本身中（而不是像鏈地址法那樣使用額外的數據結），通過探測序列尋找可用的空槽位。

• 它的核心思路是：當發生哈希沖突時，按照預定的探測規則在哈希表中尋找下一個空閑位置來存儲沖突的元素。

---

開放定址法的原理：

1. 假設哈希表的大小為 m，哈希函數為 h(key)，當通過哈希函數計算出的地址 h(key) 已經被占用，即發生沖突時

2. 開放定址法會使用一個探測序列 h_i(key)（i = 0, 1, 2,...）來尋找下一個空閑位置，直到找到可以插入的位置或者確定哈希表已滿

3. 探測序列的計算方式決定了開放定址法的具體類型

線性探測

線性探測（Linear Probing）：

• 探測公式：h_i(key) = (h(key) + i) % m ，其中 i = 0, 1, 2,...
  • 也就是說，在發生沖突時，從沖突位置開始，依次探測下一個位置（如果到達表尾則回到表頭）

---

示例：假設哈希表大小m = 10，哈希函數h(key) = key % 10，依次插入元素12、22、32

• 插入 12 時，h(12) = 12 % 10 = 2，位置 2 空閑，插入成功
• 插入 22 時，h(22) = 22 % 10 = 2，位置 2 已被占用，發生沖突
  • 根據線性探測，h_1(22) = (2 + 1) % 10 = 3，位置 3 空閑，插入成功
• 插入 32 時，h(32) = 32 % 10 = 2，位置 2 被占用，發生沖突
  • h_1(32) = (2 + 1) % 10 = 3，位置 3 也被占用，繼續探測
  • h_2(32) = (2 + 2) % 10 = 4，位置 4 空閑，插入成功

---

缺點：容易產生 “聚集”（或叫 “堆積”）現象。

• 即連續的若干個位置被占用，導致后續插入元素時需要探測多個位置，降低插入和查找效率。

二次探測

二次探測（Quadratic Probing）

• 探測公式：h_i(key) = (h(key) + c1 * i + c2 * i * i) % m
  • 通常取 c1 = 0，c2 = 1，即 h_i(key) = (h(key) + i * i) % m
  • 在發生沖突時，從發生沖突的位置開始，按照二次方的步長，向右進行跳躍式探測，直至找到下一個未存儲數據的位置
  • 若向右探測到哈希表尾，就回繞到哈希表頭繼續

---

示例：同樣假設哈希表大小m = 10，哈希函數h(key) = key % 10，插入元素11和21

• 插入 11 時，h(11) = 11 % 10 = 1，位置 1 空閑，插入成功
• 插入 21 時，h(21) = 21 % 10 = 1，位置 1 已被占用，發生沖突
  • 根據二次探測，h_1(21) = (1 + 1 * 1) % 10 = 2，位置 2 空閑，插入成功

---

優點：相較于線性探測，二次探測能減少聚集現象，使元素在哈希表中分布得更均勻。

缺點：不能探測到哈希表中的所有位置。

• 當 m 不滿足某些條件（如：m 不是 4 的倍數加 1 時），可能會出現有的位置永遠無法被探測到的情況

雙重散列

雙重哈希（Double Hashing）：

• 探測公式：h_i(key) = (h1(key) + i * h2(key)) % m
  • 其中 h1(key) 是主哈希函數，h2(key) 是輔助哈希函數且 h2(key) 的值不能為 0
  • 在發生沖突時，通過主哈希函數和輔助哈希函數共同計算探測位置

---

示例：假設h1(key) = key % 7，h2(key) = 1 + (key % 5)，哈希表大小m = 7，插入元素1和24

• 插入 10 時，h1(10) = 10 % 7 = 3，位置 3 空閑，插入成功
• 插入 24 時，h1(24) = 24 % 7 = 3，位置 3 已被占用，發生沖突
  • h2(24) = 1 + (24 % 5) = 1 + 4 = 5，根據雙重哈希探測，h_1(24) = (3 + 1 * 5) % 7 = 1，位置 1 空閑，插入成功

---

優點：探測序列比較均勻，能有效減少聚集，性能表現較好。

雙重哈希的核心邏輯：

• 當第一個哈希函數計算的位置發生沖突時
• 通過第二個哈希函數生成一個與 key 相關的偏移量，不斷向后探測，直到找到哈希表中未被占用的位置

---

偏移量 $h_2(key)$ 的約束：

為保證探測能覆蓋哈希表的所有位置，$h_2(key)$ 需滿足兩個條件：

• $h_2(key)<M$（偏移量不能超過哈希表大小）
• $h_2(key)$ 與 $M$ 互質$（$即：最大公約數 $\gcd (h_2(key),M)=1）$

---

$h_2(key)$ 的簡單取值方法：

根據哈希表大小 M 的類型，有兩種常用策略：

• 當 M 是 2 的整數次冪時： 從 [0, M-1] 中任選一個奇數作為 $h_2(key)$
  • 因為奇數與 2 的冪次互質，可保證探測覆蓋所有位置
• 當 M 是質數時： 直接計算：$h_2(key)=key\%(M?1)+1$
  • 此方法可確保 $h_2(key)$ 與 $M$ 互質

---

互質的必要性（關鍵原理）:

若 $h_2(key)$ 與 M 不互質（即 $\gcd (h_2(key)，M)=p>1$），探測的位置會無法覆蓋整個哈希表，導致部分空閑位置永遠無法被找到。

• 哈希表大小 $M=12$，初始沖突位置 hash0 = 1，偏移量 $h_2(key)=3（\gcd (3，12)=3>1）$
• 探測序列為：$（1+1\times 3)\%12=4(1+2\times 3)\%12=7(1+3\times 3)\%12=10(1+4\times 3)\%12=1$（循環）
• 可見，探測位置僅為 {1, 4, 7, 10}，共 $12/3=4$ 個位置，無法覆蓋整個哈希表。

---

總結：雙重哈希的價值

• 雙重哈希通過兩個哈希函數和互質約束，讓探測序列更均勻地覆蓋哈希表，避免了線性探測的 “聚集問題”。

• 相比其他探測方法（如：線性探測、二次探測），雙重哈希的沖突解決效率更高，適合對性能要求嚴格的場景。

方法二：鏈地址法

鏈地址法（Separate Chaining）（也叫拉鏈法、哈希桶法 ）：是哈希表解決哈希沖突的經典方案之一。

• 它的核心思路是：用數組 + 鏈表（或其他動態結構）的組合，讓沖突元素 “鏈” 在一起，既簡單又高效。

---

鏈地址法的原理：

哈希表底層是一個數組（稱為 “哈希桶數組” ），每個數組元素對應一個鏈表 / 動態結構（如：鏈表、紅黑樹、跳表 ）

• 插入元素時：

  • 通過哈希函數計算 key 的哈希值，確定要放入數組的哪個 “桶”（即：數組索引 ）
  • 若該桶對應的鏈表為空，直接插入
  • 若已存在元素（發生沖突 ），就把新元素追加到鏈表末尾

• 查找/刪除元素時：

  • 先通過哈希函數找到對應桶
  • 再遍歷鏈表逐個匹配 key

優缺點分析：

優點

1. 沖突處理簡單：不管沖突多頻繁，只需往鏈表追加，邏輯清晰易實現
2. 空間靈活：鏈表是動態結構，負載因子（負載因子 = 元素數 / 桶數 ）可大于 1 ，空間利用率高
3. 無聚集問題：每個桶的沖突是獨立鏈表，不會像開放定址法那樣 “連累” 其他桶

---

缺點

1. 遍歷開銷：若某個桶的鏈表過長，查找 / 刪除會退化為 O(n)（n 是鏈表長度 ）
2. 額外空間：鏈表節點需要存儲指針，有一定內存開銷（但現代優化如：用數組模擬鏈表可緩解 ）

------------基本操作------------

怎么解決鍵key不能取模的問題？

通過上面的學習我們知道了使用哈希函數要把關鍵字映射到數組的對應位置上，通常來說，關鍵字是整數的話進行映射計算會更方便。

哈哈，沒錯要是關鍵字本身不是整數， 是 string、Date 等類型時，無法直接對 key 進行取模操作的話，我們要怎么做呢？

沒錯那就得想辦法把它轉換成整數，但是這要怎么實現呢？

---

這時，我們需要為哈希表增加一個 仿函數（也叫哈希函數對象 ），該仿函數的作用是，把 key 轉換成一個可用于取模的整數。

• 若 key 本身能較方便地轉換為整數，且轉換后不易引發哈希沖突，直接使用哈希表默認的仿函數參數即可

• 若 key 無法直接轉換為整數，就需要我們自行實現一個仿函數，并傳遞給哈希表

實現這類仿函數的核心要求是：讓 key 的每個部分（字符、字段等）都參與計算，盡可能保證不同 key 轉換后的整數值互不相同。

---

由于 string 作為哈希表的 key 十分常見，我們可以針對性地對 string 類型做特化處理（即：專門為 string 設計更適配的哈希轉換邏輯 ）

/*------------------任務：定義哈希表函數的“結構體模板”------------------*/
template <class K>
struct HashFunc
{//1.重載()運算符 ---> 作用：將K類型轉化為size_t類型，用于計算哈希值size_t operator()(const K& key){return (size_t)key;  //注意：默認為直接轉換，適用于int、long等整數類型} 
};/*------------------任務：定義哈希函數的“模板特化”------------------*/
template <>
struct HashFunc<string>
{//1.實現：“()運算符的重載” ---> 作用：將string類型的變量轉化為哈希值size_t operator()(const string& s){//1.定義size_t類型變量記錄string類型的變量計算的哈希值size_t hash = 0;//2.使用范圍for循環遍歷字符串并用BKDR算法計算其哈希值for (auto it : s){//2.1：先將字符的ASCII值累加到哈希值中hash += it;//2.2：再讓哈希值乘以質數131（BKDR哈希算法認為：131可有效減少沖突）hash *= 131;}//3.返回最終計算的哈希值return hash;}
};

一、開放定址法

在實踐里，開放定址法的表現不如接下來要講的鏈地址法。

原因在于，開放定址法不管采用哪種沖突解決方式，都是占用哈希表自身的空間，這就使得各元素的存儲始終存在相互影響的問題。

所以，對于開放定址法，我們簡單選用線性探測的方式來實現即可 。

哈希結構

/*------------任務：定義哈希表中節點的三種狀態的“枚舉”------------*/
enum State
{EXIST,  //存在狀態EMPTY,  //空狀態DELETE  //刪除狀態
};/*------------任務：定義哈希表存儲的數據結構的“結構體模板”------------*/
template <class K, class V>
struct HashData
{//1.存儲鍵值對類型的數據//2.記錄存儲的節點的狀態pair<K, V> _kv;State _state = EMPTY; //節點的狀態默認為空
};/*------------任務：使用“開放地址法 - 線性探測”實現哈希表------------*/
template <class K, class V, class Hash = HashFunc<K>>
class HashTable
{
private:/*------------------成員變量------------------*///1.存儲HashData類型數據的數組//2.記錄哈希表中有效元素的變量 vector<HashData<K,V>> _tables;size_t _n;public://…………};

刪除操作

要注意的是，這里需要給每個存儲值的位置添加一個狀態標識，否則刪除某些值后，會影響后續沖突值的查找。

• 舉個例子，如下若刪除 30 ，會導致查找 20 失敗
• 但如果我們給每個位置設置 {EXIST, EMPTY, DELETE} 這樣的狀態標識，刪除 30 時，就不用真正刪除對應的值，而是把該位置狀態改為 DELETE

如此一來，查找 20 時，只有遇到 EMPTY 狀態才停止探測，就能順利找到 20 了

擴容操作

我們將哈希表的負載因子控制在 0.7 ，當負載因子達到 0.7 后，就需要對哈希表進行擴容。

擴容時我們依舊按照 2 倍的方式擴容，但同時要保證哈希表的大小始終為質數。

---

然而，初始大小是質數，擴容 2 倍后往往就不再是質數了。該如何解決這個問題呢？

一種方案是 sgi 版本哈希表所用的方式，預先提供一個近似 2 倍遞增的質數表，每次擴容時從質數表中選取合適的大小作為擴容后的哈希表大小 。

/*------------------任務：實現“獲取下一個 >=n 的質數的函數”---> “用于哈希表擴容”------------------*/
inline unsigned long _stl_next_prime(unsigned long n)
{//1.指定素數表的大小static const int __stl_num_primes = 28;//2.定義素數表覆蓋常見哈希表大小static const unsigned long _stl_prime_list[__stl_num_primes] =   //注意：這里的素數表的類型是unsigned long 類型{53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};//3.使用二分查找找到第一個 >=n 的素數//3.1：使用一個指針指向素數表中的“第一個素數”const unsigned long* first = _stl_prime_list;//3.1：使用一個指針指向素數表中的“最后一素數的下一位置”const unsigned long* last = _stl_prime_list + __stl_num_primes;//3.3：使用lower_bound()接口函數求出第一個 >=n 的素數const unsigned long* pos = lower_bound(first, last, n);//3.4：適合作為哈希表容量的質數return pos == last ? *(last - 1) : *pos;/**  說明遍歷完質數表，所有預定義的質數都比 n 小*  此時返回最大的質數 *(last - 1)，因為 last 是數組末尾的下一個位置，last - 1 指向最后一個有效質數 */
}

二、鏈地址法

在開放定址法里，所有元素都會直接存放在哈希表中。

而鏈地址法不同，數據不再直接存儲于哈希表，哈希表的每個位置存的是一個指針。

• 當沒有數據映射到該位置時，指針為空
• 若有多個數據映射到同一位置，就把這些沖突數據鏈成鏈表，掛在哈希表對應位置下。

鏈地址法也常被叫做拉鏈法或者哈希桶

哈希結構

/*------------------任務：定義“哈希表節點的結構體模板”------------------*/
template<class K, class V>
struct HashNode
{/*------------------成員變量------------------*///1.存儲的鍵值對//2.下一個節點的指針pair<K, V> _kv;HashNode<K, V>* _next;/*------------------成員函數------------------*///1.實現：哈希桶節點的“構造函數”HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}
};/*------------------任務：定義“哈希表的類模板”------------------*/
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
private:/*------------------成員變量------------------*///1.存儲Node*類型數據的數組//2.記錄哈希表中有效元素的變量 vector<HashNode<K, V>*> _tables;size_t _n;public:};

擴容操作

開放定址法的負載因子必須小于 1 ，鏈地址法的負載因子則沒有限制，可大于 1 。

• 負載因子越小，哈希沖突的概率越低，空間利用率也越低
• 負載因子越大，哈希沖突的概率越高，空間利用率也越高

STL 中的最大負載因子基本控制在 1 ，一旦大于 1 就會觸發擴容，我們后續實現也采用這種方式。

------------代碼實現------------

頭文件

哈希表：HashTable.h

#pragma once//包含需要使用的頭文件
#include <iostream>
#include <vector>
using namespace std;/*------------------任務：定義哈希表函數的“通用類模板”------------------*/
template <class K>
struct HashFunc
{//1.重載()運算符 ---> 作用：將K類型轉化為size_t類型，用于計算哈希值size_t operator()(const K& key){return (size_t)key;  //注意：默認為直接轉換，適用于int、long等整數類型} 
};/*------------------任務：定義哈希函數的“模板特化”------------------*/
template <>
struct HashFunc<string>
{//1.實現：“()運算符的重載” ---> 作用：將string類型的變量轉化為哈希值size_t operator()(const string& s){//1.定義size_t類型變量記錄string類型的變量計算的哈希值size_t hash = 0;//2.使用范圍for循環遍歷字符串并用BKDR算法計算其哈希值for (auto it : s){//2.1：先將字符的ASCII值累加到哈希值中hash += it;//2.2：再讓哈希值乘以質數131（BKDR哈希算法認為：131可有效減少沖突）hash *= 131;}//3.返回最終計算的哈希值return hash;}
};/*------------------任務：實現“獲取下一個 >=n 的質數的函數”---> “用于哈希表擴容”------------------*/
inline unsigned long _stl_next_prime(unsigned long n)
{//1.指定素數表的大小static const int __stl_num_primes = 28;//2.定義素數表覆蓋常見哈希表大小static const unsigned long _stl_prime_list[__stl_num_primes] =   //注意：這里的素數表的類型是unsigned long 類型{53, 97, 193, 389, 769,1543, 3079, 6151, 12289, 24593,49157, 98317, 196613, 393241, 786433,1572869, 3145739, 6291469, 12582917, 25165843,50331653, 100663319, 201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};//3.使用二分查找找到第一個 >=n 的素數//3.1：使用一個指針指向素數表中的“第一個素數”const unsigned long* first = _stl_prime_list;//3.1：使用一個指針指向素數表中的“最后一素數的下一位置”const unsigned long* last = _stl_prime_list + __stl_num_primes;//3.3：使用lower_bound()接口函數求出第一個 >=n 的素數const unsigned long* pos = lower_bound(first, last, n);//3.4：適合作為哈希表容量的質數return pos == last ? *(last - 1) : *pos;/**  說明遍歷完質數表，所有預定義的質數都比 n 小*  此時返回最大的質數 *(last - 1)，因為 last 是數組末尾的下一個位置，last - 1 指向最后一個有效質數 */
}

開放定址法：open_address.h

#pragma once#include "HashTable.h"namespace open_address
{/*------------任務：定義哈希表中節點的三種狀態的“枚舉”------------*/enum State{EXIST,  //存在狀態EMPTY,  //空狀態DELETE  //刪除狀態};/*------------任務：定義哈希表存儲的數據結構的“結構體模板”------------*/template <class K, class V>struct HashData{//1.存儲鍵值對類型的數據//2.記錄存儲的節點的狀態pair<K, V> _kv;State _state = EMPTY; //節點的狀態默認為空};/*------------任務：使用“開放地址法 - 線性探測”實現哈希表------------*/template <class K, class V, class Hash = HashFunc<K>>class HashTable{private:/*------------------成員變量------------------*///1.存儲HashData類型數據的數組//2.記錄哈希表中有效元素的變量 vector<HashData<K,V>> _tables;size_t _n;/*注意現在的結構的形式是：*    1.哈希表*		1.1：成員變量：容器vector*				1.1.1：鍵值對_kv*				1.1.2：枚舉：_state*			               1.1.2.1：存在*						   1.1.2.2：空*						   1.1.2.2：刪除*       1.2：成員變量：變量_n*//*------------------成員變量------------------*/public:/*------------------成員變量（公有）------------------*///1.實現：“哈希表的構造函數”HashTable():_tables(_stl_next_prime(0)), _n(0){}//2.實現：“查找操作” ----> 查找鍵對應的數據，找到返回指針，未找到返回nullptrHashData<K, V>* Find(const K& key)  //注意：傳入“鍵”返回“哈希表存儲元素的指針”{/*--------------第一步：計算初始哈希位置--------------*///1.實例化哈希函數對象Hash hash;//2.計算哈希值 + 對其取模計算初始位置size_t hash_0 = hash(key) % _tables.size(); ///注意：這里相當于調用時vector的接口函數size()//3.定義變量記錄當前的探測位置size_t hash_i = hash_0;//4.定義探測步長計數器size_t i = 1;/*--------------第二步：線性探測循環--------------*/while (_tables[hash_i]._state != EMPTY) //注意：遇到EMPTY標記時停止（EMPTY表示無數據，DELETE需繼續）{//1.如果當前位置為EXIST且鍵匹配 ---> 找到了鍵為key的元素，返回該位置的指針 if (_tables[hash_i]._state == EXIST && _tables[hash_i]._kv.first == key){return &_tables[hash_i];}//2.進行線性探測計算下一個位置hash_i = (hash_0 + i) % _tables.size();  //注意：取模防止越界//3.探測步長自增++i;}/*--------------第三步：--------------*///“如果這個位置的狀態為空 + 遇到EMPTY仍未找到” ---> 說明哈希表中并不存在鍵為key的元素return nullptr;}//3.實現：“刪除操作” ---> 刪除鍵對應的數據，成功返回true，未找到返回falsebool Erase(const K& key){//1.調用Find函數查找鍵key對應的目標的元素HashData<K, V>* ret = Find(key);  //注意：返回指向該元素的指針（存在）或nullptr（不存在）//2.判斷是否找到的目標元素//情況1：找到了鍵為key的元素if (ret){//1.將該元素的狀態設置為DELETE（刪除狀態）ret->_state = DELETE;//2. 更新有效元素的數量--_n;//3.刪除成功返回true即可return true;}//情況2：未找到鍵未key的元素else{return false;}/* 注意事項：刪除鍵為key的元素為什么是：“將這個元素的狀態設置為刪除狀態”呢？**    核心邏輯：不直接清除數據，而是標記為DELETE狀態*    原因：開放定址法中，直接刪除會破壞哈希沖突形成的探測鏈*    例如：若刪除中間元素，后續元素的查找可能提前終止*/}//4.實現：“插入操作”---> 插入鍵值對，成功返回true，鍵已存在返回falsebool Insert(const pair<K, V>& kv){/*----------------第一步：查重判斷----------------*///1.使用Find()函數先檢查鍵kv.first是否已經存在if (Find(kv.first)){return false; // 當鍵kv.first已經存在時，插入失敗}//1.進行擴容的判斷：負載因子（_n/_tables.size()）≥0.7時擴容if (_n * 10 / _tables.size() >= 7){/*----------------第二步：擴容操作----------------*///2.創建新哈希表，容量為大于當前size的最小質數（減少哈希沖突）HashTable<K, V, Hash> newHt;newHt._tables.resize(_stl_next_prime(_tables.size() + 1));/*  注意事項：**      newHt：是一個哈希表*	   _tables：是哈希表中的一個成員變量，本質上是vector；哈希表的另一個成員變量是_n，本質上是size_t類型的變量*      resize： 是vecotr容器中用來進行擴容的接口函數*///3.遍歷舊表，將所有EXIST狀態的元素重新插入新表for (auto& htData : _tables){if (htData._state == EXIST){newHt.Insert(htData._kv);  // 注意：需重新計算哈希值（因表長改變，取模結果不同）}}//4.交換新舊哈希表：舊表.swap(新表)_tables.swap(newHt._tables);   //注意：當前表指向新表，舊表由newht接管（離開作用域時自動釋放）}/*----------------第三步：初始位置----------------*///1.實例化哈希函數對象Hash hashFunc;//2.計算哈希值 + 對其取模計算初始位置size_t hash_0 = hashFunc(kv.first) % _tables.size(); ///注意：這里相當于調用時vector的接口函數size()//3.定義變量記錄當前的探測位置size_t hash_i = hash_0;//4.定義探測步長計數器size_t i = 1;/*----------------第四步：線性探測----------------*///1.使用while循環第一個非EXIST位置（EMPTY或DELETE均可，EXIST需要繼續尋找）while (_tables[hash_i]._state == EXIST){//2.進行線性探測計算下一個位置hash_i = (hash_0 + i) % _tables.size();  //注意：取模防止越界，環形探測//3.探測步長自增++i;}/* 注意事項：“查找”和“插入”使用while進行線性探測的“循環判斷條件不同”*      查找操作：while (_tables[hash_i]._state != EMPTY) ---> 查找的位置EXIST或DELETE需要繼續尋找“鍵為key的元素”**      插入操作：while (_tables[hashi]._state == EXIST) ---> 查找的位置EXIST需要繼續尋找“空位置”*//*----------------第五步：插入數據----------------*///1.將鍵值對插入該位置_tables[hash_i]._kv = kv;//2.將該位置的設置為EXIST_tables[hash_i]._state = EXIST;//3.更新哈希表中有效元素的數量++_n;//4.插入成功返回true即可return true;}};
}

鏈地址法：hash_bucket.h

#pragma once#include "HashTable.h"//任務8：使用“鏈地址法”實現哈希表
namespace hash_bucket
{/*------------------任務：定義“哈希表節點的結構體模板”------------------*/template<class K, class V>struct HashNode{/*------------------成員變量------------------*///1.存儲的鍵值對//2.下一個節點的指針pair<K, V> _kv;HashNode<K, V>* _next;/*------------------成員函數------------------*///1.實現：哈希桶節點的“構造函數”HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}};/*------------------任務：定義“哈希表的類模板”------------------*/template<class K, class V, class Hash = HashFunc<K>>class HashTable{private:/*------------------成員變量------------------*///1.存儲Node*類型數據的數組//2.記錄哈希表中有效元素的變量 vector<HashNode<K, V>*> _tables;size_t _n;/*注意現在的結構的形式是：*    1.哈希表*      1.1：成員變量：容器vector*			   1.1.1：哈希表節點類型的指針：HashNode<K,V>**					  1.1.1.1：鍵值對：_kv*					  1.1.1.2：下一個節點的指：_next*	   1.2：成員變量：變量_n*//*------------------類型別名------------------*///1.重命名哈希表節點的類型：HashNode<K,V> ---> Nodetypedef HashNode<K, V> Node;public:/*------------------成員函數------------------*///1.實現：“哈希表的構造函數”HashTable():_tables(_stl_next_prime(0)) //初始化為11個桶, _n(0){}//2.實現：“哈希表的析構函數”~HashTable(){//1.遍歷哈希表的每個桶（注：_tables 是存儲桶頭節點指針的容器）for (size_t i = 0; i < _tables.size(); ++i){//2.獲取當前桶的頭節點指針，從第一個桶開始清理Node* current = _tables[i];//3.遍歷當前桶對應的鏈表，逐個釋放節點內存while (current){//3.1：提前保存當前節點的下一個節點指針 ---> 防止刪除當前節點后丟失鏈表連接Node* next = current->_next;//3.2：釋放當前節點的內存（避免內存泄漏）delete current;//3.3：移動到下一個節點，繼續清理current = next;}//4.將當前桶的頭節點指針置空，確保析構后桶不會指向無效內存_tables[i] = nullptr;}}//3.實現：“查找操作”---> 根據鍵查找對應的節點，找到返回節點指針，未找到返回 nullptrNode* Find(const K& key){//1. 實例化哈希函數對象Hash hashFunc;/* 代碼解釋：*     1. 利用模板參數 Hash 生成哈希函數實例*     2. 若 K 是 int，使用默認的整數哈希；若 K 是 string，使用特化的字符串哈希*///2. 計算鍵的哈希值并取模，得到對應的桶索引size_t hash_i = hashFunc(key) % _tables.size();/* 代碼解釋：*      1. hashFunc(key)：調用哈希函數，將鍵轉換為 size_t 類型的哈希值*	   2. % _tables.size()：對哈希表的桶數量取模，確定節點應該落在哪個桶中*	   3.目的：將任意鍵映射到 [0, _tables.size()-1] 范圍內的桶索引*///3. 獲取對應桶的頭節點，開始遍歷鏈表Node* current = _tables[hash_i]; //注意：_tables[hash_i] 是桶的頭節點指針//4. 遍歷當前桶對應的鏈表while (current) //注意：若 current 為 nullptr，說明桶為空，直接跳過循環{//4.1 檢查當前節點的鍵是否匹配目標 keyif (current->_kv.first == key){return current;}//4.2 若不匹配，移動到鏈表的下一個節點else{current = current->_next;}}//5. 遍歷完鏈表后仍未找到匹配的鍵，返回 nullptrreturn nullptr;}//4.實現：“刪除操作”---> 根據鍵刪除哈希表中的節點，成功返回 true，失敗返回 falsebool Erase(const K& key){//1.計算鍵的哈希值，確定所在桶Hash hashFunc;size_t hash_i = hashFunc(key) % _tables.size();//2.定義一個指向桶的頭節點的指針Node* curr = _tables[hash_i];//3.定義一個指向當前節點的前驅節點的指針Node* prev = nullptr;  //作用記錄待刪除節點的前驅節點//3.遍歷當前桶的鏈表while (curr){//4.找到目標節點if (curr->_kv.first == key){//4.2：處理待刪除節點if (prev == nullptr){//情況1：待刪除節點是桶的頭節點_tables[hash_i] = curr->_next;}else{//情況2：待刪除節點在鏈表中間或末尾prev->_next = curr->_next;}//4.3：釋放節點內存delete curr;//4.4：有效元素數量減一--_n;//4.5：刪除成功return true;}//5.未找到目標節點，繼續遍歷//5.1：當前節點的前驅節點指向當前節點prev = curr;//5.2：當前節點指向下一個節點的位置curr = curr->_next;}//6.遍歷結束仍未找到目標節點，刪除失敗return false;}//5.實現：“插入操作”---> 插入鍵值對，成功返回true，鍵已存在返回falsebool Insert(const pair<K, V>& kv){/*----------------第一步：查重判斷----------------*///1.使用Find()函數判斷鍵kv.first是否已經存在if (Find(kv.first)){return false; // 當鍵kv.first已經存在時，插入失敗}/*----------------第二步：擴容操作----------------*///1.進行擴容判斷：負載因子（元素數/桶數）等于1時觸發擴容if (_n == _tables.size()) //目的：避免哈希沖突過多導致鏈表過長，影響性能{/*//////////////////方法一：創建新哈希表對象并復用Insert函數////////////////////2.創建新哈希表，容量為大于當前size的最小質數（減少哈希沖突）HashTable<K, V, Hash> newHt;newHt._tables.resize(_stl_next_prime(_tables.size() + 1));//3.使用for循環變量的舊表中的所有桶 ---> 將舊表中的所有節點重新插入到新表中for (size_t i = 0; i < _tables.size(); i++){//4.定義一個指針指向當前桶存儲的鏈表的頭節點Node* current = _tables[i];//5.遍歷鏈表 ---> 將遍歷的到的每個節點節點進行插入while (current){//5.1：將鏈表中的每個節點重新插入到新表中newht.Insert(cur->_kv);  // 復用Insert函數（會重新計算哈希值并查重）//5.2：指向當前節點的current指針向后移動一位cur = cur->_next;}}//6.交換新舊哈希表：舊表.swap(新表)_tables.swap(newHt._tables);   //注意：當前表指向新表，舊表由newht接管（離開作用域時自動釋放）*///////////////////方法二：直接操作數組進行節點遷移（優化版）////////////////////2.創建新數組，容量為大于當前size的最小質數（減少哈希沖突）//vector<Node*> newVector(_stl_next_prime(_tables.size() + 1));vector<Node*> newVector(_tables.size() * 2);//3.使用for循環變量的舊表中的所有桶 ---> 將舊表中的所有節點重新插入到新表中for (size_t i = 0; i < _tables.size(); i++){//4.定義一個指針指向當前節點的指針Node* current = _tables[i];//5.遍歷鏈表 ---> 將遍歷的到的每個節點節點進行插入while (current){//6.定義一個指針指向當前節點的下一個節點的指針 ---> 暫存下一節點避免鏈表斷裂Node* next = current->_next;//7.實例化哈希函數Hash hashFunc;  //創建哈希函數對象//8.重新計算“遍歷到節點”在新表中的桶索引 ---> 因表長變化，哈希值需重新取模size_t hash_i = hashFunc(current->_kv.first) % newVector.size();//9.使用頭插入法將當前節點插入新表對應桶的頭部//第一步：新插入的節點的下一個節點 ---> 該節點的桶索引位置的鏈表頭節點current->_next = newVector[hash_i];//第二步：將新插入的節點的指針賦值給其對應的桶newVector[hash_i] = current;//第三步：指向當前節點的current指針向后移動一位current = next;}//10.清空舊表的當前桶_tables[i] = nullptr;  //注意：當前桶在舊表中的哈希值是i，在新表中的哈希值是hash_i}//11.交換新舊哈希表：舊表.swap(新表)_tables.swap(newVector);   //注意：當前表指向新表，舊表由newht接管（離開作用域時自動釋放）}/*----------------第三步：插入數據----------------*///1.創建新節點Node* newNode = new Node(kv);//2.實例化哈希函數Hash hashFunc;//3.計算“新插入數據”的哈希值/桶索引size_t hash_i = hashFunc(kv.first) % _tables.size();//4.1：頭插第一步：newNode->_next = _tables[hash_i];//4.2：頭插第二步：_tables[hash_i] = newNode;//5.更新新表中有效元素的數量++_n;//6.插入成功返回true即可return true;}};
}

測試文件：Test.cpp

#include "HashTable.h" 
#include "open_address.h"
#include "hash_bucket.h"#include <string>
#include <iostream>
using namespace std;// 輔助函數：打印測試結果
void printTestResult(const string& testName, bool result)
{cout << (result ? "[PASS] " : "[FAIL] ") << testName << endl;
}/*-----------------------測試：開放尋址法哈希表-----------------------*/
void test_open_address()
{cout << "\n===== 測試開放尋址法哈希表 =====" << endl;/*--------------------創建哈希表--------------------*/open_address::HashTable<int, string> ht;cout << "創建哈希表成功" << endl;/*--------------------插入測試--------------------*/cout << "\n--- 插入測試 ---" << endl;bool insert1 = ht.Insert({ 1, "A" });printTestResult("插入鍵1值A", insert1);bool insert2 = ht.Insert({ 1, "B" }); // 重復鍵printTestResult("插入重復鍵1值B（期望失敗）", !insert2);bool insert3 = ht.Insert({ 2, "C" });printTestResult("插入鍵2值C", insert3);/*--------------------查找測試--------------------*/cout << "\n--- 查找測試 ---" << endl;auto node1 = ht.Find(1);printTestResult("查找鍵1", node1 != nullptr && node1->_kv.second == "A");auto node2 = ht.Find(2);printTestResult("查找鍵2", node2 != nullptr && node2->_kv.second == "C");auto node3 = ht.Find(3);printTestResult("查找不存在的鍵3", node3 == nullptr);/*--------------------刪除測試--------------------*/cout << "\n--- 刪除測試 ---" << endl;bool erase1 = ht.Erase(1);printTestResult("刪除鍵1", erase1);bool erase2 = ht.Erase(1); // 重復刪除printTestResult("重復刪除鍵1（期望失敗）", !erase2);bool erase3 = ht.Erase(3); // 刪除不存在的鍵printTestResult("刪除不存在的鍵3", !erase3);/*--------------------擴容測試--------------------*/cout << "\n--- 擴容測試 ---" << endl;cout << "開始插入大量數據以觸發擴容..." << endl;for (int i = 3; i < 100; ++i){ht.Insert({ i, to_string(i) });}cout << "插入完成，驗證數據訪問..." << endl;auto node99 = ht.Find(99);printTestResult("查找擴容后的鍵99", node99 != nullptr && node99->_kv.second == "99");cout << "開放尋址法哈希表測試完畢" << endl;
}/*-----------------------測試：鏈地址法哈希表-----------------------*/
void test_hash_bucket()
{cout << "\n===== 測試鏈地址法哈希表 =====" << endl;/*--------------------創建哈希表--------------------*/hash_bucket::HashTable<string, int> ht;cout << "創建哈希表成功" << endl;/*--------------------插入測試--------------------*/cout << "\n--- 插入測試 ---" << endl;bool insert1 = ht.Insert({ "apple", 5 });printTestResult("插入鍵apple值5", insert1);bool insert2 = ht.Insert({ "apple", 10 }); // 重復鍵printTestResult("插入重復鍵apple值10（期望失敗）", !insert2);bool insert3 = ht.Insert({ "banana", 8 });printTestResult("插入鍵banana值8", insert3);/*--------------------查找測試--------------------*/cout << "\n--- 查找測試 ---" << endl;auto node1 = ht.Find("apple");printTestResult("查找鍵apple", node1 != nullptr && node1->_kv.second == 5);auto node2 = ht.Find("banana");printTestResult("查找鍵banana", node2 != nullptr && node2->_kv.second == 8);auto node3 = ht.Find("orange");printTestResult("查找不存在的鍵orange", node3 == nullptr);/*--------------------刪除測試--------------------*/cout << "\n--- 刪除測試 ---" << endl;bool erase1 = ht.Erase("apple");printTestResult("刪除鍵apple", erase1);bool erase2 = ht.Erase("apple"); // 重復刪除printTestResult("重復刪除鍵apple（期望失敗）", !erase2);bool erase3 = ht.Erase("orange"); // 刪除不存在的鍵printTestResult("刪除不存在的鍵orange", !erase3);/*--------------------擴容測試--------------------*/cout << "\n--- 擴容測試 ---" << endl;cout << "開始插入大量數據以觸發擴容..." << endl;for (int i = 0; i < 100; ++i){string key = "key_" + to_string(i);ht.Insert({ key, i });}cout << "插入完成，驗證數據訪問..." << endl;auto node = ht.Find("key_99");printTestResult("查找擴容后的鍵key_99", node != nullptr && node->_kv.second == 99);cout << "鏈地址法哈希表測試完畢" << endl;
}//自定義日期結構體 ---> 用于測試復雜類型的哈希
struct Date
{/*-------------------成員變量-------------------*/int _year;int _month;int _day;/*-------------------成員函數-------------------*///1.實現：日期類的“構造函數”Date(int year = 1, int month = 1, int day = 1):_year(year), _month(month), _day(day){}//2.實現：“自定義相等比較”（哈希表需要判斷鍵是否相等）bool operator==(const Date& d) const{return _year == d._year&& _month == d._month&& _day == d._day;}
};//自定義日期的哈希函數（模仿BKDR算法）
struct DateHashFunc
{//1.實現：“運算符()的重載” ---> 作用：用于計算日期類對象的哈希值size_t operator()(const Date& d){//1.定義size_t類型的變量記錄日期類對象計算的哈希值size_t hash = 0;//2.分步哈希，減少沖突概率hash += d._year;hash *= 131;   // 乘以質數，增強離散性hash += d._month;hash *= 131;hash += d._day;hash *= 131;//3.返回最終計算的哈希值return hash;}
};void test01()
{/*---------------測試：字符串作為鍵的哈希表---------------*/hash_bucket::HashTable<string, string> ht1;const char* a1[] = { "abcd", "sort", "insert" };for (auto& it : a1){ht1.Insert({ it, it });  // 鍵值均為字符串}/*---------------測試：負數作為鍵的哈希表（需保證哈希函數處理負數）---------------*/hash_bucket::HashTable<int, int> ht2;const int a2[] = { -19,-30,5,36,13,20,21,12 };for (auto& it : a2){ht2.Insert({ it, it });}/*---------------測試：日期結構體作為鍵（自定義“哈希函數”和“相等比較”）---------------*/hash_bucket::HashTable<Date, int, DateHashFunc> ht3;ht3.Insert({ { 2025, 6, 29 }, 1 });  // 插入日期鍵值對ht3.Insert({ { 2025, 6, 30 }, 1 });}int main()
{test_open_address();test_hash_bucket();test01();return 0;
}

運行結果