前言

哈希表的核心思想就是映射，通過將key值以某種算法映射成不大于哈希表長度的哈希值，從而實現存儲數據。上篇提到解決哈希沖突有 閉散列 和 開散列，本文將用這兩種理論思想實現哈希表。
代碼位置：哈希模擬的實現源碼

一. 開放地址法實現哈希表

1.1 閉散列結構定義

該閉散列哈希表使用vector數組，其中數組里面包含一個結構體，該結構存儲pair類型數據及當前位置的狀態，是否為空，不為空，或者有數據然后被刪除了的三個狀態，偽代碼如下：

//節點可能的三種狀態
enum State
{EXIST,EMPTY,DELETE
};//哈希表中存儲的數據
template<class K, class V>
struct HashData
{pair<K, V> _kv;//存放數據類型State _state = EMPTY;//當前位置的狀態，默認為空，即表示此位置沒有數據
};
template<class K, class V, class Hash = HashFunc<K>>
class HashTable
{
public:
private:vector<HashData<K, V>> _tables;size_t _n = 0;//表中實際存儲的數據個數
};

• 仿函數作用：

因為里面是數組，通過key值映射成哈希值后，哈希值不能超過哈希表的長度，需要取模，所以同時也要傳入仿函數，將任意類型數據不能取模轉換成整數，本來就可以進行取模運算的，就無需借助額外的仿函數，所以就可以給一個默認的仿函數，該仿函數給本來是整數去使用的。

//默認的仿函數
template<class K>
class HashFunc
{
public:size_t operator()(const K& key){return (size_t)key;}
};

1.2 構造函數

給vector數組開一定的空間，為了防止2的冪次方的數，底層給了一定合理的素數，下面給代碼即可。

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

1.3 插入（線性探測）

插入之前判斷該key值是否在存在，存在直接返回即可。對插入的key值映射成哈希值，然后進行探測，探測規則：當前位置為空，繼續向后探測，跳出循環后，將該位置插入數據并將該位置的狀態設置為存在，_n++(表示存儲的數據個數+1)，這里有一個問題：擴容？？？

• 問題：如何擴容

1.3.1 傳統寫法

創建一個數組（數組已經擴容后），將舊表中的vector數組中的數據重新進行映射成新開的數組（這里的一個優勢在于：原來在舊表中沖突的數據可能在新表中就不沖突了），也需進行探測，過程基本與插入過程一致，將舊數據完成探測之后，在新表與舊表進行交換。偽代碼如下：

bool Insert(const pair<K, V>& kv)
{if (Find(kv.first))return false;//擴容if ((double)_n / (double)_tables.size() >= 0.7){// 獲取素數表里面比當前表大的下一個素數size_t newSize = __stl_next_prime(_tables.size() + 1);vector<HashData<K, V>> newTables(newSize);//遍歷舊表，將數據都映射到新表for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST){size_t hash0 = _tables[i].kv.first % newSize;size_t i = 1;size_t hashi = hash0;while (newTables[hashi]._state == EXIST){//沖突探測hashi = (hash0 + i) % newSize;i++;}newTables[hashi]._kv = kv;newTables[hashi]._state = EXIST;//_n++;需不需要寫？？？思考一下}}_tables.swap(newTables);}Hash hs;size_t hash0 = hs(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;
}

• 細節1：

重新尋找哈希值，需要對新的哈希表的長度進行取余，不要依然對舊表中的哈希表長度進行取余，否則會導致新表中新增加的長度沒有被使用，沖突概率未減少。

• 細節2：

_n++需不需要寫？？？不需要，因為是將舊表中的數據重新映射至新表，數據并沒有增加。

注意：可以看出上述代碼有點冗余，特別是插入過程與重新建立映射關系的代碼很相似。
下面這種寫法很巧妙，且代碼量少。

1.3.2 現代寫法

思想：建立一個新表，然后給新表中的哈希表開一定足夠的空間，然后將舊表中的數據直接插入新表中即可，插入的過程同時也完成探測過程。很優雅的寫法，建議采用它。

• 偽代碼：

bool Insert(const pair<K, V>& kv)
{if (Find(kv.first))return false;//擴容if ((double)_n / (double)_tables.size() >= 0.7){size_t newSize = __stl_next_prime(_tables.size() + 1);HashTable<K, V, Hash> newHT;newHT._tables.resize(newSize);//遍歷舊表，將數據都映射到新表for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST){newHT.Insert(_tables[i]._kv);//此行為已經將舊數據映射到了新表中，同時進行線性探測和沖突探測，可能原來在舊表中的數據沖突，在新表中它就不沖突了}}_tables.swap(newHT._tables);//將新表與舊表進行交換}Hash hs;size_t hash0 = hs(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;
}

該實現是一個功能完整的線性探測哈希表，適合學習用途。

1.4 查找

查找過程很簡單，首先對要查找的key值轉化成映射后的哈希值，對應位置狀態為！EXIST，進行查詢當前位置狀態不為空，且不為刪除直接返回該指針即可，否則繼續往后探測，當探測為空，說明不存在，直接返回nullptr即可。

• 偽代碼：

HashData<K, V>* Find(const K& key)
{Hash hs;size_t hash0 = hs(key) % _tables.size();size_t hashi = hash0;size_t i = 1;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;
}

1.5 刪除

直接調用接口Find即可，接收返回值，判斷返回值是否為空，為空直接返回false；不為空將該位置的狀態設置為刪除即可，然后返回true即可。

• 偽代碼：

bool Erase(const K& key)
{HashData<K, V>* ret = Find(key);if (ret == nullptr){return false;}else{--_n;ret->_state = DELETE;return true;}
}

標記刪除操作時間復雜度為 O(1)，無數據遷移開銷。
聲明：上述做法了解一下即可，下面這個才是王炸，需重點關注及掌握。

二. 鏈地址法實現哈希表（哈希桶）

2.1 開散列結構定義

該開散列哈希表使用vector數組，其中數組里面包含一個哈希表節點，該節點存儲pair類型數據及下一個哈希表數據的指針。偽代碼如下：

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 HashTable {typedef HashNode<K, V> Node;vector<Node*> _tables;    // 哈希槽數組（存儲鏈表頭指針）size_t _n = 0;            // 當前元素總數
};

該代碼提供了鏈地址法哈希表的核心骨架。

2.2 構造函數

構造函數與上述閉散列一致。

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

2.3 插入

創建一個數組，擴容時，將舊表中的節點挪動至新表中，需重新建立映射關系，也需要進行探測，過程與插入過程一致，將舊數據完成探測之后，在新表與舊表進行交換。偽代碼如下：
**插入數據時有個問題，**進行尾插還是頭插，兩者都可以，但頭插很簡單，尾插相對較復雜，需要找尾，當前桶挪動完畢，需要將當前桶只為nullptr，本文以頭插為示例。

bool Insert(const pair<K, V>& kv)
{if (Find(kv.first))return false;if (_n == _tables.size()){size_t newSize = __stl_next_prime(_tables.size() + 1);vector<Node*> newtables(newSize, nullptr);//遍歷舊表，將舊表的節點挪動到新表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = cur->_kv.first % newSize;cur->_next = newtables[hashi];newtables[hashi] = cur;}_tables[i] = nullptr;}_tables.swap(newtables);}size_t hashi = kv.first % _tables.size();Node* newnode = new Node(kv);//頭插，尾插也行，找尾麻煩,需要找尾newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;
}

2.4 查找

查找過程很簡單，將要查找的key值轉換成哈希值，然后對該桶進行遍歷，判斷桶中的數據key值是否與要查找的key值是否相等，相等返回該節點指針即可，找到空還未找到，返回nullptr即可。

• 偽代碼如下：

Node* Find(const K& key)
{size_t hashi = key % _tables.size();Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){return cur;}cur = cur->_next;}return nullptr;
}

2.5 刪除

刪除需要前驅指針（默認為空）將刪除后的節點連接起來，刪除過程相對來說較復雜，也需要要刪除的key值轉換成哈希值，然后遍歷該桶，判斷桶中節點的數據key值與要查找的key值是否相等，相等進行刪除，返回true即可，里面有細節 -> :

• 細節一：

當刪除頭結點時，頭結點沒有前驅指針，會對空指針進1行解引用，所以需要分情況討論。

1. 前驅指針不為空，和為空兩種狀態。
2. 不相等繼續往后找，當前桶找完還未找到，返回false即可。

• 偽代碼：

		bool Erase(const K& key){size_t hashi = 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;}

代碼正確處理了鏈表節點的刪除，維護了計數器_n，但未處理重復鍵（若允許存在）。

三. 最后

本文詳述了哈希表的兩種實現方式：開放地址法（閉散列）與鏈地址法（開散列）。開放地址法通過線性探測解決沖突，采用標記刪除優化性能，擴容時重建哈希表；鏈地址法以鏈表處理沖突，頭插法簡化操作，擴容時重新映射所有節點。兩者均使用素數表優化哈希分布，核心操作包括插入、查找、刪除，適用于不同場景，是高效鍵值存儲的關鍵技術。