【數據結構】之散列

一、定義與基本術語

（一）、定義

散列（Hash）是一種將鍵（key）通過散列函數映射到一個固定大小的數組中的技術，因為鍵值對的映射關系，散列表可以實現快速的插入、刪除和查找操作。在這里分辨一下散列表和哈希表（Hash table和Hash Map）：

散列表：可能是一個更通用的概念，不一定強調鍵值對的映射關系。
哈希表：通常強調鍵值對的映射關系，類似于?HashMap?或?Dictionary。

不過呢，散列表和哈希表在本質上是相同的，我們平時使用一般也不會做很詳細的區分。都是基于散列函數的數據結構，用于高效地存儲和查找數據。

（二）、基本術語

哈希函數（Hash Function）：也叫散列函數，將鍵映射到散列表中的索引位置的函數。

哈希函數的作用是將鍵（key）轉換為一個索引值，這個索引值用于在底層的數組（或其他數據結構）中定位存儲值（value）的位置。這個過程可以概括為以下幾個步驟：

鍵到哈希值的轉換：哈希函數接收一個鍵作為輸入，并輸出一個哈希值。這個哈希值通常是整數。

哈希值到索引的映射：哈希值通過某種映射機制（如取模運算）轉換成數組的索引。這個索引決定了鍵值對在哈希表中的具體存儲位置。

存儲和檢索：在存儲數據時，鍵值對被放置在由鍵通過哈希函數和映射機制確定的索引處。在檢索數據時，同樣的鍵通過哈希函數和映射機制計算出索引，然后直接訪問該索引處的值。

常見的散列(哈希)函數：

除留余數法：hash(key) = key % table_size。
乘留余數法：hash(key) = (key * A) % table_size，其中?A?是一個常數。
平方取中法：適用于鍵是字符串的情況。

哈希沖突（Hash Collision）：兩個不同的鍵通過散列函數映射到同一個索引位置。

由于哈希值的范圍通常遠小于鍵的總數，不同的鍵可能會經過哈希函數計算后得到相同的索引值，這種現象稱為哈希沖突。為了解決哈希沖突，常用的方法包括：

鏈地址法：在每個數組索引位置維護一個鏈表，所有映射到該索引的鍵值對都存儲在這個鏈表中。（是不是可以想到操作系統里的地址表）

開放尋址法：當發生沖突時，使用某種探測序列在數組中尋找下一個空閑位置。

再哈希法：使用另一個哈希函數計算一個新的索引值。

負載因子（Load Factor）：散列表中元素數量與表的容量的比值，衡量哈希表的空間利用率，＞0.75會引發重哈希。

如果負載因子過高，意味著更多的鍵被映射到同一個桶中，這會增加哈希沖突的概率，降低哈希表的性能；

相反，如果負載因子過低，意味著哈希表的存儲空間沒有得到充分利用，導致額外的空間浪費。

實例 1：理想的哈希函數

假設我們有一個哈希表，總桶數量為10，哈希函數設計得非常完美，將5個鍵均勻地分布在這10個桶中。

已使用的桶的數量：5
總桶的數量：10
負載因子：105?=0.5

在這種情況下，負載因子為0.5，表示哈希表的使用率為50%，沖突的概率較低，性能較好。

實例 2：不理想的哈希函數

假設我們有同樣的哈希表，總桶數量為10，但哈希函數設計得不理想，將5個鍵都映射到了前5個桶中。

已使用的桶的數量：5
總桶的數量：10
負載因子：105?=0.5

盡管負載因子仍然是0.5，但由于鍵的分布不均勻，實際上前5個桶已經滿了，而后5個桶是空的。這種情況下，雖然負載因子顯示哈希表的使用率不高，但實際上已經出現了性能問題。

實例 3：高負載因子

假設我們有一個哈希表，總桶數量為5，但存儲了8個鍵。

已使用的桶的數量：8
總桶的數量：5
負載因子：8/5?=1.6

在這種情況下，負載因子為1.6，表示哈希表的使用率超過了100%，這意味著平均每個桶中有兩個鍵，哈希沖突非常頻繁，性能會顯著下降。

實例 4：動態擴容

假設我們有一個動態擴容的哈希表，初始總桶數量為10，存儲了15個鍵。

已使用的桶的數量：15
總桶的數量：10
負載因子：15/10?=1.5

當負載因子達到一定閾值（例如1.0）時，哈希表會自動擴容，比如將桶的數量增加到20。擴容后，原有的鍵會重新通過哈希函數計算新的桶位置，從而降低負載因子，減少沖突。

擴容后的總桶的數量：20
負載因子：15/20?=0.75

通過動態擴容，負載因子降低，哈希表的性能得到改善。

二、特點

高效性：
- 平均時間復雜度為?O(1) 的插入、刪除和查找操作。
- 在最壞情況下（如所有鍵都映射到同一索引），時間復雜度為?O(n)。
靈活性：
- 可以處理任意類型的鍵（如整數、字符串等）。
- 可以通過選擇合適的散列函數和沖突解決方法優化性能。
空間利用率：
- 散列表通常需要預留一定的空間來降低沖突概率。
- 負載因子通常控制在 0.5 到 0.8 之間。

三、基本操作實現

基本操作就包括：

定義、插入，刪除，查找

1. 散列表的基本操作

class HashTable{
private:vector<int> table;int size;// 哈希函數int hashFunction(int key) {return key % size;}public:// 構造函數HashTable(int s) : size(s) {table.resize(size, -1);}// 插入元素void insert(int key) {int index = hashFunction(key);while (table[index] != -1) {index = (index + 1) % size;}table[index] = key;}// 查找元素bool search(int key) {int index = hashFunction(key);int start = index;while (table[index] != -1) {if (table[index] == key) {return true;}index = (index + 1) % size;if (index == start) {break;}}return false;}// 刪除元素void remove(int key) {int index = hashFunction(key);int start = index;while (table[index] != -1) {if (table[index] == key) {table[index] = -1;return;}index = (index + 1) % size;if (index == start) {break;}}}// 打印哈希表void printTable() {for (int i = 0; i < size; ++i) {cout << "Index " << i << ": ";if (table[i] != -1) {cout << table[i];} else {cout << "Empty";}cout << endl;}}
};int main() {HashTable hashTable(10);// 插入元素hashTable.insert(12);hashTable.insert(22);hashTable.insert(3);// 打印哈希表cout << "After insertion:" << endl;hashTable.printTable();// 查找元素cout << "\nSearching for 22: " << (hashTable.search(22) ? "Found" : "Not found") << endl;cout << "Searching for 10: " << (hashTable.search(10) ? "Found" : "Not found") << endl;// 刪除元素hashTable.remove(22);cout << "\nAfter deletion of 22:" << endl;hashTable.printTable();return 0;
}

2. 使用內置函數

以上都是為了幫助理解，在實際的代碼中，std::unordered_map?和std::unordered_set?都屬于標準庫中的哈希表實現，借助它我們可以直接運用其內置函數來完成基本操作，無需手動實現哈希表。兩者適用的問題不同：

std::unordered_map：存儲的是鍵值對（key - value），每個元素由一個鍵和一個與之關聯的值組成。鍵是唯一的，通過鍵可以快速查找對應的值。例如，我們可以用?unordered_map?來存儲學生的學號和對應的姓名，學號作為鍵，姓名作為值。Leetcode例題參考：??????
std::unordered_set：只存儲單一的元素，每個元素都是唯一的。它更側重于判斷某個元素是否存在于集合中。例如可以用?unordered_set?來存儲一組不重復的單詞。Leetcode例題參考：202. 快樂數

具體來說，常用的內置函數包括：

1. 插入元素

insert：把鍵值對插入到?unordered_map?中。若鍵已存在，則不會插入新元素。
emplace：原位構造并插入一個新元素，若鍵已存在，則不插入。
operator[]：若鍵存在，返回對應的值；若鍵不存在，則插入該鍵，并默認初始化其值。

2. 查找元素

find：查找指定鍵的元素，若找到則返回指向該元素的迭代器；若未找到，則返回?end()?迭代器。（所以我們判斷指定鍵的元素在不在表中一般用的代碼類似：if(seen.find(n)==seen.end()) ）
count：返回指定鍵的元素數量，由于?unordered_map?中鍵是唯一的，所以返回值要么是 0（鍵不存在），要么是 1（鍵存在）。

3. 刪除元素

erase：刪除指定鍵的元素，可接受鍵或迭代器作為參數。

4. 其他常用函數

size：返回表中元素的數量。
empty：判斷表是否為空。
clear：清空表中的所有元素。

在這里也給出一個應用的例子：

#include <iostream>
#include <unordered_map>
#include <unordered_set>int main() {// 使用 std::unordered_mapstd::unordered_map<int, std::string> myMap;myMap[1] = "apple";myMap[2] = "banana";auto itMap = myMap.find(1);if (itMap != myMap.end()) {std::cout << "Value for key 1 in map: " << itMap->second << std::endl;}// 使用 std::unordered_setstd::unordered_set<std::string> mySet;mySet.insert("apple");mySet.insert("banana");auto itSet = mySet.find("apple");if (itSet != mySet.end()) {std::cout << "Element 'apple' found in set." << std::endl;}return 0;
}

四、練習

1. 基本概念練習

首先明確單射、滿射的含義：
理想的單射哈希函數：每個鍵都映射到一個唯一的索引，沒有任何兩個鍵共享同一個索引。這可以完全避免哈希沖突，使得每個鍵都可以直接映射到一個唯一的桶或數組位置。

理想的滿射哈希函數：所有的桶或數組索引至少被一個鍵映射到。這確保了數組的空間被充分利用，沒有浪費的桶或索引。

但以上都屬于理想情況，在實際設計哈希函數時，目標是盡量減少沖突（接近單射），同時盡可能均勻地分布鍵到所有可用的索引（接近滿射）。

由此分析：?

A：錯誤。由于 ∣A∣<∣S∣，即地址空間小于詞條空間，不可能每個詞條都映射到一個唯一的地址，因此 h 不可能是滿射。

B：正確。從A的分析就能知道，由于 ∣A∣<∣S∣，不同的詞條必須映射到相同的地址以避免某些詞條無法映射，因此 h 不可能是單射。

C：錯誤。雖然 ∣A∣<∣S∣，但 h 仍然可以是滿射，只要每個地址都至少被一個詞條映射到。

D：錯誤。單射要求每個地址只能映射到一個詞條。在哈希表中，由于沖突的存在，一個地址可能映射到多個詞條，因此 h 不一定是單射。

我們從構造散列函數的目的進行分析，可以找出正確和錯誤的說法。

單射：在散列表的上下文中，單射并不是一個好的特性，因為不同的鍵映射到同一個索引是不可避免的，這是由于散列表的大小有限。

值域覆蓋：一個好的散列函數應該盡可能覆蓋散列表的所有地址，這樣可以提高空間利用率和減少沖突。

一致性：同一個詞條每次計算得到的哈希值應該是相同的，這樣才能保證數據的一致性。

效率：散列函數的計算應該簡單快速，以便于快速定位和檢索數據。

均勻分布：散列函數應該能夠將不同的詞條均勻地分布在散列表中，避免某些區域過于擁擠，這有助于減少沖突。

沖突幾率：一個好的散列函數應該設計得能夠最小化沖突的概率，這樣可以提高散列表的性能。

對于?h1(key)=key%12，計算每個元素的哈希值：

0%12=0

8%12=8

16%12=4

24%12=0 （與0沖突）

32%12=8 （與8沖突）

40%12=4 （與16沖突）

48%12=0 （與0, 24, 32沖突）

56%12=8 （與8, 32, 48沖突）

64%12=4 （與16, 40沖突）

不同的哈希值有：{0,4,8}，共3個不同的元素。

對于?h2(key)=key%11，計算每個元素的哈希值：

0%11=0

8%11=8

16%11=5

24%11=2

32%11=10

40%11=7

48%11=4

56%11=1

64%11=9

所有的哈希值都是不同的，因此有9個不同的元素。

A. 錯誤。獨立鏈法中，每個桶（數組的每個位置）都鏈接到一個鏈表，沖突的詞條存放在對應的鏈表中，而不是桶數組內部。

B.?正確。開放定址法中，當發生沖突時，詞條會嘗試在數組中找到下一個空閑位置存放，因此實際存放位置可能與散列函數計算出的位置不同。

C. 錯誤。開放定址法不會使用鏈表存放詞條，而是在數組中尋找下一個空閑位置。

D. 錯誤。即使散列函數設計得再好，由于散列表的大小有限，不同的鍵仍然可能映射到同一個索引，需要沖突解決策略。

h(4)=(3×4+5)%11=17%11=6

也就是說詞條4應該被放在數組索引6的位置，但是我們發現索引6處非空閑，存儲的是15，需要使用線性試探來尋找下一個空閑位置。線性試探的公式通常是 hi?=(h+i)%size，其中 i 是探測次數，從0開始。

第一次試探：h0?=6（已占用）

第二次試探：h1?=(6+1)%11=7（已被26占用）

第三次試探：h2?=(6+2)%11=8（空）

所以鍵4的實際存放位置是數組索引8的位置，即 A[8]。

開放定址法是一種處理哈希表沖突的方法，其中平方試探法是開放定址法的一種。在平方試探法中，如果發生沖突，我們按照 hi?=(h+i2)%size 的公式來探測下一個可能的空槽位。

當使用平方試探法時，為了保證哈希表中至少有一個空槽位，裝填因子load factor也就是負載因子不能超過 0.5。

這是因為在最壞的情況下，如果裝填因子超過 0.5，那么在探測過程中可能會遇到一個“循環”，即所有的槽位都被占用，沒有空槽位可以插入新的詞條。

(1) H(9)=9%11=9

所以關鍵字為9的節點應該被存儲在索引為9的位置。先對給出的散列表中元素進行插入：

給定的關鍵字已經按順序插入散列表，我們先計算它們的哈希值并確定它們的存儲位置：

15: 15%11=4 → 存儲在位置 4

31: 31%11=9 → 存儲在位置 9

27: 27%11=5 → 存儲在位置 5

14: 14%11=3 → 存儲在位置 3

10: 10%11=10 → 存儲在位置 10

16: 16%11=5 → 與關鍵字 27 沖突，線性探測到位置 6

11: 11%11=0 → 存儲在位置 0

查找后發現索引為9的位置已被占用，那就線性探測繼續找下一個空位。

位置 10 已被關鍵字 10 占用

位置 11 為空

因此，關鍵字 9 將被存儲在位置 11。

A={11,31,?,14,?,0,15,26,16,5,9,?}

(2) 平均成功查找長度

15: 直接在位置 4 找到，長度為 1

31: 直接在位置 9 找到，長度為 1

27: 直接在位置 5 找到，長度為 1

14: 直接在位置 3 找到，長度為 1

10: 直接在位置 10 找到，長度為 1

16: 在位置 5 沖突，探測到位置 6，長度為 2

11: 直接在位置 0 找到，長度為 1

9: 在位置 9 沖突，探測到位置 11，長度為 2

總長度 = 1+1+1+1+1+2+1+2=10 ,關鍵字數量 = 8

ASL(成功) =10/8 =5/4

(3) 失敗的平均查找長度

采用線性探測法處理沖突時，若該地址有元素，從該地址開始，依次探測下一個地址，直到找到空地址。將每個散列地址查找失敗的比較次數相加，再除以散列地址的個數，就能得到失敗的平均查找長度。

A={11,31,?,14,?,0,15,26,16,5,9,?}

位置0：依次探測0，1，2，在索引為2處找到空桶，比較次數3；

位置1：依次探測1，2，在索引為2處找到空桶，比較次數2；

位置2：在索引為2處找到空桶，比較次數1；

位置3：依次探測3，4，在索引為4處找到空桶，比較次數2；

位置4：在索引為4處找到空桶，比較次數1；

位置5：依次探測5，6，7，8，9，10，11，在索引為11處找到空桶，比較次數為7；

位置6：依次探測6，7，8，9，10，11，在索引為11處找到空桶，比較次數為6；

位置7：依次探測7，8，9，10，11，在索引為11處找到空桶，比較次數為5；

位置8：依次探測8，9，10，11，在索引為11處找到空桶，比較次數為4；

位置9：依次探測9，10，11，在索引為11處找到空桶，比較次數為3；

位置10：依次探測10，11，在索引為11處找到空桶，比較次數為2；

位置11：在索引為11處找到空桶，比較次數為1；

總長度 = 3+2+1+2+1+7+6+5+4+3+2+1=11 空桶數量 = 3

ASL(失敗)?= 11

五、Leetcode練習題匯總

題號	題目名稱	難度等級	關鍵詞
1	兩數之和	簡單	哈希表、數組
202	快樂數	簡單	哈希表、數學、雙指針
217	存在重復元素	簡單	哈希表、數組、排序
219	存在重復元素 II	簡單	哈希表、數組
242	有效的字母異位詞	簡單	哈希表、字符串、排序
349	兩個數組的交集	簡單	哈希表、雙指針、二分查找、排序
350	兩個數組的交集 II	簡單	哈希表、雙指針、二分查找、排序
409	最長回文串	簡單	哈希表、字符串、貪心
451	根據字符出現頻率排序	中等	哈希表、字符串、排序、堆（優先隊列）
560	和為 K 的子數組	中等	哈希表、數組、前綴和
705	設計哈希集合	簡單	哈希表、設計
706	設計哈希映射	簡單	哈希表、設計
771	寶石與石頭	簡單	哈希表、字符串
811	子域名訪問計數	簡單	哈希表、字符串
953	驗證外星語詞典	簡單	哈希表、字符串
1207	獨一無二的出現次數	簡單	哈希表、數組
1365	有多少小于當前數字的數字	簡單	哈希表、數組、排序、計數
1481	不同整數的最少數目	中等	哈希表、貪心、排序、堆（優先隊列）