【數據結構進階】哈希表

🌟🌟作者主頁：ephemerals__

🌟🌟所屬專欄：數據結構

前言

一、哈希表的概念

二、哈希函數的實現方法

1. 直接定址法

2. 除留余數法

三、哈希沖突?

1. 開放定址法（閉散列）

線性探測

二次探測

雙重探測

2. 鏈地址法（開散列）

四、裝填因子

五、哈希表的實現

1. 線性探測法實現

整形轉化的支持與字符串哈希

初始大小與擴容策略

哈希表結構定義

構造函數

析構函數

哈希表的插入

哈希表的查找

哈希表的刪除

總代碼

2. 鏈地址法實現

整形轉化支持、大小設置

哈希表結構定義

構造函數

析構函數

哈希表的插入

哈希表的查找

哈希表的刪除

總代碼

總結

前言

? ? ? ? 之前我們學習了紅黑樹，其雖然通過自平衡機制提供了高效的查找、插入和刪除操作，但其操作仍依賴于樹的高度，最壞情況下的時間復雜度為O(log n)。當我們希望能夠實現常數時間復雜度的查找操作時，哈希表便成為了一個更優的選擇。哈希表雖然不再像紅黑樹的元素一樣默認有序，但其通過 “ 哈希 ” 將數據進行映射，從而在理想情況下實現O(1)時間復雜度的操作，在某些需要高效查找的場景非常實用。本篇文章，我們將深入學習哈希表的相關知識，并嘗試實現。

一、哈希表的概念

? ? ? ? 哈希表（Hash Table），也叫做散列表，是一種特殊的數據結構。其通過一定的規則將數據進行 “ 散亂排列 ” ，并通過該規則進行快速查找。這個規則叫做 “ 哈希函數 ” ，其可以將數據轉化為一個固定的索引值，后續將該數據根據索引值存儲在數組的某個位置。當進行查找時，直接通過 “ 哈希函數 ” 求出數據的索引值，理想狀態下就能在常數時間內完成查找。

二、哈希函數的實現方法

? ? ? ? 在理想狀態下，哈希函數會將數據均勻散列分布在哈希表當中。為了盡量逼近這個理想狀態，先輩們發明了多種哈希函數的實現方法，如直接定址法、除留余數法、乘法散列法、全域散列法等。其中直接定址法和除留余數法最為常用，我們重點介紹一下。

1. 直接定址法

?????????當數據的范圍比較集中時，優先考慮使用直接定址法。例如有一組數據的范圍在0~99之間，那么我們開一個大小為100的數組，然后將數據按照數組下標來存儲。比如這組數據當中有3個“6”，那么數組下標為6處的值就是3。

? ? ? ? 那么當這組數據的下限非0呢？處理方法也很簡單。例如這組數據的范圍是26個小寫英文字母，ascii值在97~122之間。我們開一個大小為26的數組，然后每一個字母對應存儲位置的下標即為其ascii值減去'a'的ascii值，這樣就可以進行存儲了。

? ? ? ? 當然直接定址法的缺陷也很明顯：當數據比較分散且范圍很大時，會造成空間浪費。

2. 除留余數法

? ? ? ? 除留余數法（也叫做除法散列法），是哈希函數最常用的實現方式。它的核心思想是將數據對某個數（一般是表長）進行求余運算，將運算結果作為索引值，即表示該數據存放的下標位置。假設某個哈希表的大小為M，那么哈希函數為：hash(x) = x % M。

如圖所示，各個元素通過除留余數法存儲在哈希表當中：

注意以下兩點：

1. 為了盡量減少哈希沖突出現的次數，建議M取不太接近2的整數次冪的一個素數。

2. 除留余數法中，為了方便數據轉化為索引值，要求哈希表的數據元素支持轉換為整數。

三、哈希沖突?

? ? ? ? 當一個數據通過哈希函數產生了與另一個數據相同的哈希值，那么也就意味著它們需要存儲在同一個位置，顯然無法滿足。此時的情況就叫做哈希沖突（哈希碰撞）。理想情況下，數據會均勻分布在哈希表中，但是實際場景當中，哈希沖突是無法避免的。所以我們要有適當的方案處理哈希沖突。

處理哈希沖突的方法主要有開放定址法、鏈地址法、再哈希法和位圖法等，這里只介紹最常用的前兩種。

1. 開放定址法（閉散列）

? ? ? ? 開放定址法是按照某種策略將沖突的數據放置在表中的另一個空位當中。常見的策略有三種：線性探測、二次探測和雙重探測。

線性探測

? ? ? ? 線性探測指的是從沖突位置開始，依次向后一個一個查找，直到找到空位，再將沖突元素放置在當前空位。當查找到表尾還沒有找到空位，那么從表頭位置開始重新查找。

? ? ? ? 線性探測的缺點是容易造成表中的沖突數據聚集，且會占用其他元素的原本位置，從而影響效率。

二次探測

? ? ? ? 二次探測對線性探測進行了優化。它的查找方式是依次左右按照二次方跳躍式探測。例如先探測沖突位置的右邊? $1^{2}$ ?個位置，然后左邊? $1^{2}$ ?個位置，右邊? $2^{2}$ ?個位置，左邊? $2^{2}$ ?個位置......依次類推。

? ? ? ? 二次探測有效地減少了數據聚集問題。

雙重探測

? ? ? ? 雙重探測指的是使用另一個哈希函數計算探測步長，使探測序列更加分散。

2. 鏈地址法（開散列）

? ? ? ? 鏈地址法，也叫做拉鏈法，它改變了傳統的哈希表元素儲存策略。在鏈地址法當中，所有數據不再直接存儲在哈希表當中，而是將哈希表的每一個元素設置為指針，用于維護一個鏈表。此時哈希表的每一個元素就叫做哈希桶。當某個元素位置不存儲元素時，該指針為空；若有元素需要存儲在該位置，則在其維護的鏈表中添加該元素。因此，一條鏈表中存儲的元素互相之間就是發生哈希沖突的。

鏈地址法在發生沖突時，就不會占用其他元素的原本位置，相比開放定址法效率較高。但當某個位置的沖突元素過多時，鏈表過長，會使查找效率接近O(N)，此時可以考慮將鏈表換為紅黑樹。

Java8以及之后的HashMap實現當中，就采用了如上優化：當某個哈希桶維護的鏈表長度超過8時，將該鏈表換成紅黑樹，提升總體性能。

四、裝填因子

? ? ? ? 裝填因子（負載因子）是一個數值，表示已存儲元素與哈希表容量的比值。當裝填因子過大時，哈希表的空間利用率就越高，發生哈希沖突的概率就越高，哈希表的總體性能就越低。

? ? ? ? 在實際實現當中，為了保證哈希表的高效，我們將裝填因子作為哈希表是否需要擴容的標準。當裝填因子到達一定閾值時，哈希表就需要擴容。若哈希表使用開放定址法處理沖突，那么該閾值通常在0.7~0.8之間；若使用鏈地址法，則該閾值通常為1。

五、哈希表的實現

? ? ? ? 接下來我們將選用除留余數法的哈希函數，并用線性探測和鏈地址法兩種解決沖突的策略分別實現一個哈希表。至于其他方法，這里就不再一一實現。

與之前實現AVL樹和紅黑樹相同，我們的實現當中將鍵值對作為數據元素，其哈希值由鍵Key來決定。

1. 線性探測法實現

整形轉化的支持與字符串哈希

? ? ? ? 之前提到哈希表的數據元素要支持轉化為整形，所以在這里我們需要實現一個仿函數模板，用仿函數對象將內置類型進行轉化，并且對于不能轉化為整形的類型，可以用特化來支持。

代碼如下：

//支持內置類型轉化為整形的仿函數
template<class K>
class ToInt
{
public:size_t operator()(const K& key)//這里轉換為size_t類型更符合數組下標范圍{return (size_t)(key);}
};

除了內置類型，字符串（string）作為鍵值存儲在哈希表中的場景較多，我們實現一個特化版本支持字符串轉換為整形。

? ? ? ? 傳統的字符串轉整形可以將所有字符的ASCII值相加，但這種方法轉換出的整形值可能重復率較高（例如"abc"和"acb"），更容易導致沖突。所以這里我們使用BKDR哈希的思路：每一個字符累加之后，總累加值乘以一個素數（通常是131或31），這樣就能對每個字符進行加權。最后的累加值即為轉化后的整形值。

注意：當字符串過長時，多次相乘可能會導致溢出，但無需考慮溢出問題，因為我們只要確定能得到唯一的整形值即可。

代碼如下：

//針對string的特化版本
template<>
class ToInt<string>
{
public:size_t operator()(const string& s){size_t ret = 0;for (auto& c : s){ret += c;ret *= 131;}return ret;}
};

初始大小與擴容策略

? ? ? ? 使用除留余數法時，為了降低哈希沖突的概率，哈希表的大小（也就是除數M）的選擇十分重要，應取不太接近2的整數次冪的一個素數。那么應該如何設置哈希表的初始大小及其擴容后的大小呢？這里我們直接采用SGI STL哈希表源碼中的大小設置策略：

inline size_t __stl_next_prime(size_t n)
{// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const size_t __stl_prime_list[__stl_num_primes] ={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};const size_t* first = __stl_prime_list;const size_t* last = __stl_prime_list + __stl_num_primes;const size_t* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;
}

可以看到，函數創建了一個大小為28的數組，其中的數據即是哈希表每次擴容的大小（53、97、193...以此類推）。函數接收一個參數n，并返回數組中第一個不小于n的元素。而第一個元素53就可以作為我們哈希表的初始大小，接下來實現構造函數時調用該函數即可。

哈希表結構定義

? ? ? ? 接下來是線性探測法哈希表及其數據元素的結構定義：?

//元素的狀態表示
enum State
{EMPTY,//空EXIST,//存在DELETE//已刪除
};//數據元素
template<class K,class V>
struct HashData
{pair<K, V> _kv;//鍵值對State _state = EMPTY;//狀態
};//哈希表
template<class K, class V, class ToInteger = ToInt<K>>
class HashTable
{
public:
private:vector<HashData<K, V>> _tables;//使用vector表示哈希表size_t _n = 0;//記錄已有元素個數ToInteger _toi;//仿函數對象
};

結構定義當中，我們使用了vector用于存儲數據，其中元素是一個HashData，HashData包含一個鍵值對和狀態表示（空、存在和已刪除）。另外成員n和toi分別用于計算裝填因子和整形轉化。

構造函數

? ? ? ? 構造函數當中，我們只需要設置哈希表的初始大小。代碼如下：

//構造函數
HashTable()
{_tables.resize(__stl_next_prime(1));
}

傳入參數1，則函數__stl_next_prime返回不小于1的第一個數組元素，也就是53，然后用它調整vector的大小。

析構函數

? ? ? ? 析構函數不需要我們顯式實現，編譯器默認生成的析構函數會調用vector的析構，進行數據銷毀。?

哈希表的插入

? ? ? ? 哈希表插入的大致過程如下：

1. 首先判斷表中是否已有相同鍵值元素，若有則插入失敗（不允許鍵值重復）。

2. 判斷裝填因子的值是否過大（這里我們判斷是否超過0.7），若過大，哈希表需要擴容。

3. 根據哈希函數進行插入，并處理沖突。?

需要注意的是：擴容之后，哈希表的大小（即除數M）會發生變化，之后進行插入或查找操作時，根據新的M進行插入/查找原有元素就會出現問題。所以當哈希表擴容之后，需要將其中的所有元素都拿出來重新根據哈希函數插入在哈希表當中，使其符合新哈希表的除數M。（數據重排）

代碼實現：

//插入
bool Insert(const pair<K, V>& kv)
{if (Find(kv.first))//如果表中已有相同鍵，則插入失敗返回false{return false;}if ((double)_n / (double)_tables.size() >= 0.7)//當裝填因子大于0.7，則需要擴容{size_t newSize = __stl_next_prime(_tables.size() + 1);//先確定擴容后的大小//創建新的哈希表，并調整大小HashTable<K, V, ToInteger> newHT;newHT._tables.resize(newSize);//遍歷原哈希表，將有效數據插入到新哈希表中for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST)//存在說明是有效數據{//直接調用Insert函數本身進行插入//此時已經擴容，裝填因子一定不會超過閾值，不會再次走到這里newHT.Insert(_tables[i]._kv);}}//最后交換兩個哈希表的tables_tables.swap(newHT._tables);}//開始插入//除留余數法計算哈希值size_t hash0 = _toi(kv.first) % _tables.size();size_t i = 1;size_t hashi = hash0;while(_tables[hashi]._state == EXIST)//該位置已有元素，說明發生了哈希沖突，循環向后尋找{hashi = (hash0 + i) % _tables.size();//相比直接++，這樣設置能確保找到末尾還能從頭開始尋找i++;}//找到了不出現沖突的位置，進行插入_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;_n++;return true;
}

可以看到，在進行擴容時，我們巧妙地創建了一個新的哈希表，并調用Insert方法本身進行數據的重新插入，減少了代碼冗余。

哈希表的查找

? ? ? ? 查找時的邏輯與插入過程大體相同，同樣使用哈希函數求出索引值，然后用線性探測法進行查找（注意按鍵查找）。代碼如下：

HashData<K, V>* Find(const K& key)
{//除留余數法計算哈希值size_t hash0 = _toi(key) % _tables.size();size_t i = 1;size_t hashi = hash0;//沒有走到空，則一直查找while (_tables[hashi]._state != EMPTY){//存在且鍵值相同，返回if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key){return &(_tables[hashi]);}hashi = (hash0 + i) % _tables.size();i++;}//沒找到，返回空return nullptr;
}

這里需要注意：由于線性探測法一定會使得沖突的數據在表中連續排列，所以我們查找時，如果在線性探測的過程中出現了空位，說明一定查找失敗，就無需遍歷整個哈希表了。

哈希表的刪除

? ? ? ? 刪除的大致過程也很簡單（注意按鍵刪除）：

如果表中不存在該元素，則刪除失敗。

如果存在該元素，直接將元素狀態修改為DELETE，然后調整已有元素個數即可。

代碼如下：

//刪除
bool Erase(const K& key)
{//首先進行查找HashData<K, V>* ret = Find(key);//沒找到，刪除失敗if (ret == nullptr){return false;}else//找到了，刪除{ret->_state = DELETE;//修改元素狀態_n--;//修改已有元素個數return true;}
}

總代碼

哈希表線性探測版本的全部代碼如下：

#include <iostream>
#include <utility>
#include <vector>
#include <string>
using namespace std;//支持內置類型轉化為整形的仿函數
template<class K>
class ToInt
{
public:size_t operator()(const K& key)//這里轉換為size_t類型更符合數組下標范圍{return (size_t)(key);}
};//針對string的特化版本
template<>
class ToInt<string>
{
public:size_t operator()(const string& s){size_t ret = 0;for (auto& c : s){ret += c;ret *= 131;}return ret;}
};//元素的狀態表示
enum State
{EMPTY,//空EXIST,//存在DELETE//已刪除
};//數據元素
template<class K, class V>
struct HashData
{pair<K, V> _kv;//鍵值對State _state = EMPTY;//狀態
};//哈希表
template<class K, class V, class ToInteger = ToInt<K>>
class HashTable
{
public://構造函數HashTable(){_tables.resize(__stl_next_prime(1));}//插入bool Insert(const pair<K, V>& kv){if (Find(kv.first))//如果表中已有相同鍵，則插入失敗返回false{return false;}if ((double)_n / (double)_tables.size() >= 0.7)//當裝填因子大于0.7，則需要擴容{size_t newSize = __stl_next_prime(_tables.size() + 1);//先確定擴容后的大小//創建新的哈希表，并調整大小HashTable<K, V, ToInteger> newHT;newHT._tables.resize(newSize);//遍歷原哈希表，將有效數據插入到新哈希表中for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST)//存在說明是有效數據{//直接調用Insert函數本身進行插入//此時已經擴容，裝填因子一定不會超過閾值，不會再次走到這里newHT.Insert(_tables[i]._kv);}}//最后交換兩個哈希表的tables_tables.swap(newHT._tables);}//開始插入//除留余數法計算哈希值size_t hash0 = _toi(kv.first) % _tables.size();size_t i = 1;size_t hashi = hash0;while(_tables[hashi]._state == EXIST)//該位置已有元素，說明發生了哈希沖突，循環向后尋找{hashi = (hash0 + i) % _tables.size();//相比直接++，這樣設置能確保找到末尾還能從頭開始尋找i++;}//找到了不出現沖突的位置，進行插入_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;_n++;return true;}//查找HashData<K, V>* Find(const K& key){//除留余數法計算哈希值size_t hash0 = _toi(key) % _tables.size();size_t i = 1;size_t hashi = hash0;//沒有走到空，則一直查找while (_tables[hashi]._state != EMPTY){//存在且鍵值相同，返回if (_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key){return &(_tables[hashi]);}hashi = (hash0 + i) % _tables.size();i++;}//沒找到，返回空return nullptr;}//刪除bool Erase(const K& key){//首先進行查找HashData<K, V>* ret = Find(key);//沒找到，刪除失敗if (ret == nullptr){return false;}else//找到了，刪除{ret->_state = DELETE;//修改元素狀態_n--;//修改已有元素個數return true;}}
private:inline size_t __stl_next_prime(size_t n){// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const size_t __stl_prime_list[__stl_num_primes] ={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};const size_t* first = __stl_prime_list;const size_t* last = __stl_prime_list + __stl_num_primes;const size_t* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}vector<HashData<K, V>> _tables;//使用vector表示哈希表size_t _n = 0;//記錄已有元素個數ToInteger _toi;//仿函數對象
};

2. 鏈地址法實現

整形轉化支持、大小設置

? ? ? ? 對于進行整形轉化的仿函數和哈希表的初始大小設置，我們繼續沿用之前線性探測法的實現。

//支持內置類型轉化為整形的仿函數
template<class K>
class ToInt
{
public:size_t operator()(const K& key)//這里轉換為size_t類型更符合數組下標范圍{return (size_t)(key);}
};//針對string的特化版本
template<>
class ToInt<string>
{
public:size_t operator()(const string& s){size_t ret = 0;for (auto& c : s){ret += c;ret *= 131;}return ret;}
};

inline size_t __stl_next_prime(size_t n)
{// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const size_t __stl_prime_list[__stl_num_primes] ={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};const size_t* first = __stl_prime_list;const size_t* last = __stl_prime_list + __stl_num_primes;const size_t* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;
}

哈希表結構定義

? ? ? ? 接下來是鏈地址法哈希表的結構定義：

//鏈表節點
template<class K, class V>
struct HashNode
{pair<K, V> _kv;//數據域HashNode<K, V>* _next;//指針域//節點構造HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}
};//哈希表
template<class K, class V, class ToInteger = ToInt<K>>
class HashTable
{typedef HashNode<K, V> Node;
public:
private:vector<Node*> _tables;size_t _n = 0;//記錄已有元素個數ToInteger _toi;//仿函數對象
};

這里我們創建了一個指針數組，每一個指針都用于維護一個鏈表。其次，成員n與toi的作用和線性探測實現中相同。由于鏈地址法中的數據都是通過鏈表存儲，所以這里就無需對每個元素進行狀態表示。

構造函數

? ? ? ? 構造函數的實現與線性探測法相同，注意初始化時將表中的所有指針制為空。

代碼如下：

//構造函數
HashTable()
{_tables.resize(__stl_next_prime(1), nullptr);
}

析構函數

? ? ? ? 與線性探測法實現不同，由于每個哈希桶都維護一個單鏈表，所以析構時需要我們手動釋放這些鏈表所占內存。?遍歷哈希表，逐個銷毀即可。代碼如下：

//析構函數
~HashTable()
{//循環遍歷所有哈希桶for (size_t i = 0; i < _tables.size(); i++){//使cur指向當前哈希桶Node* cur = _tables[i];//循環銷毀當前鏈表中的所有節點while (cur){Node* next = cur->_next;delete cur;cur = next;}//將當前哈希桶制空_tables[i] = nullptr;}
}

哈希表的插入

? ? ? ? 鏈地址法哈希表的插入大致過程：

1. 與線性探測一樣，首先判斷是否已有相同鍵值。

2. 判斷裝填因子是否大于1，如果大于1就需要擴容。（擴容仍需注意數據重排）

3. 通過哈希函數找到對應的哈希桶，進行插入。?

需要注意兩點：

1. 這里的插入過程涉及單鏈表的插入，為了提高效率，我們將使用頭插法。?

2. 由于數據存儲在鏈表節點當中，擴容之后，進行數據重排時釋放節點再創建節點就過于麻煩，所以我們遍歷所有鏈表，將節點連接到新的哈希表中對應位置即可。

代碼實現：

//插入
bool Insert(const pair<K, V>& kv)
{if (Find(kv.first))//已有相同鍵，插入失敗{return false;}if (_n >= _tables.size())//裝填因子的值超過1，需要擴容{size_t newSize = __stl_next_prime(_tables.size() + 1);//先確定擴容后大小//創建新的vector，然后進行數據重排vector<Node*> newV(newSize, nullptr);for (size_t i = 0; i < _tables.size(); i++)//遍歷所有哈希桶{Node* cur = _tables[i];//cur指向當前哈希桶while (cur){Node* next = cur->_next;//先記錄下一個節點size_t hashi = _toi(cur->_kv.first) % newV.size();//計算當前節點在新表中的索引值//將當前節點連接到新桶中cur->_next = newV[hashi];newV[hashi] = cur;//繼續操作下一個節點cur = next;}//一個哈希桶遍歷結束后，及時制空_tables[i] = nullptr;}//重排結束，交換兩個vector_tables.swap(newV);}//進行插入size_t hashi = _toi(kv.first) % _tables.size();//計算索引值Node* newnode = new Node(kv);//創建新節點//頭插newnode->_next = _tables[hashi];_tables[hashi] = newnode;_n++;return true;
}

可以看到，與剛才的線性探測實現不同，這里我們在擴容時創建的是一個vector，相比直接創建HashTable再調用Insert方法，能夠有效地控制數據重排時節點之間的連接。

對于不同的結構實現，同一種操作所使用的方法也會有所不同，因此在實際場景中，我們應抓住問題本質，靈活運用各種方法，而非死抓一種應對措施。

哈希表的查找

? ? ? ? 相比線性探測法，鏈地址法的查找中，我們只需要確定索引值，然后順著鏈表直接查找即可，總體過程相對簡潔。代碼實現如下：

//查找
Node* Find(const K& key)
{size_t hashi = _toi(key) % _tables.size();//確定索引值Node* cur = _tables[hashi];//開始查找while (cur){if (cur->_kv.first == key)//找到了，返回當前節點{return cur;}cur = cur->_next;}return nullptr;//沒找到，返回空
}

哈希表的刪除

? ? ? ? 刪除的邏輯也比較簡單，確定哈希值之后，進行單鏈表的指定位置刪除。代碼如下：

//刪除
bool Erase(const K& key)
{size_t hashi = _toi(key) % _tables.size();Node* prev = nullptr;//記錄前驅指針Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key)//找到了，刪除{if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;_n--;return true;}prev = cur;cur = cur->_next;}return false;//沒找到，刪除失敗
}

總代碼

鏈地址法實現哈希表的全部代碼如下：

#include <iostream>
#include <utility>
#include <vector>
#include <string>
using namespace std;//支持內置類型轉化為整形的仿函數
template<class K>
class ToInt
{
public:size_t operator()(const K& key)//這里轉換為size_t類型更符合數組下標范圍{return (size_t)(key);}
};//針對string的特化版本
template<>
class ToInt<string>
{
public:size_t operator()(const string& s){size_t ret = 0;for (auto& c : s){ret += c;ret *= 131;}return ret;}
};//鏈表節點
template<class K, class V>
struct HashNode
{pair<K, V> _kv;//數據域HashNode<K, V>* _next;//指針域//節點構造HashNode(const pair<K, V>& kv):_kv(kv), _next(nullptr){}
};//哈希表
template<class K, class V, class ToInteger = ToInt<K>>
class HashTable
{typedef HashNode<K, V> Node;
public://構造函數HashTable(){_tables.resize(__stl_next_prime(1), nullptr);}//析構函數~HashTable(){//循環遍歷所有哈希桶for (size_t i = 0; i < _tables.size(); i++){//使cur指向當前哈希桶Node* cur = _tables[i];//循環銷毀當前鏈表中的所有節點while (cur){Node* next = cur->_next;delete cur;cur = next;}//將當前哈希桶制空_tables[i] = nullptr;}}//插入bool Insert(const pair<K, V>& kv){if (Find(kv.first))//已有相同鍵，插入失敗{return false;}if (_n >= _tables.size())//裝填因子的值超過1，需要擴容{size_t newSize = __stl_next_prime(_tables.size() + 1);//先確定擴容后大小//創建新的vector，然后進行數據重排vector<Node*> newV(newSize, nullptr);for (size_t i = 0; i < _tables.size(); i++)//遍歷所有哈希桶{Node* cur = _tables[i];//cur指向當前哈希桶while (cur){Node* next = cur->_next;//先記錄下一個節點size_t hashi = _toi(cur->_kv.first) % newV.size();//計算當前節點在新表中的索引值//將當前節點連接到新桶中cur->_next = newV[hashi];newV[hashi] = cur;//繼續操作下一個節點cur = next;}//一個哈希桶遍歷結束后，及時制空_tables[i] = nullptr;}//重排結束，交換兩個vector_tables.swap(newV);}//進行插入size_t hashi = _toi(kv.first) % _tables.size();//計算索引值Node* newnode = new Node(kv);//創建新節點//頭插newnode->_next = _tables[hashi];_tables[hashi] = newnode;_n++;return true;}//查找Node* Find(const K& key){size_t hashi = _toi(key) % _tables.size();//確定索引值Node* cur = _tables[hashi];//開始查找while (cur){if (cur->_kv.first == key)//找到了，返回當前節點{return cur;}cur = cur->_next;}return nullptr;//沒找到，返回空}//刪除bool Erase(const K& key){size_t hashi = _toi(key) % _tables.size();Node* prev = nullptr;//記錄前驅指針Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key)//找到了，刪除{if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;_n--;return true;}prev = cur;cur = cur->_next;}return false;//沒找到，刪除失敗}
private:inline size_t __stl_next_prime(size_t n){// Note: assumes long is at least 32 bits.static const int __stl_num_primes = 28;static const size_t __stl_prime_list[__stl_num_primes] ={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};const size_t* first = __stl_prime_list;const size_t* last = __stl_prime_list + __stl_num_primes;const size_t* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}vector<Node*> _tables;size_t _n = 0;//記錄已有元素個數ToInteger _toi;//仿函數對象
};

總結

? ? ? ? 哈希表是一種基于哈希函數的高效數據結構，其通過數據映射，支持 O(1) 級別的查找、插入和刪除操作。哈希表有多種實現方法，我們實現了開放地址法（線性探測）和鏈地址法兩種。開放地址法適用于低負載、節省空間，但處理沖突時可能導致探測成本增加；鏈地址法適用于高負載，擴展性更強，但需額外存儲指針。合理選擇哈希函數和沖突解決策略是優化哈希表性能的關鍵。如果你覺得博主講的還不錯，就請留下一個小小的贊在走哦，感謝大家的支持???