C++ - 哈希

? ?在順序結構以及平衡樹中，由于元素關鍵碼與其存儲位置之間沒有對應的關系，因此在查找一個元素時，必須要經過關鍵碼的多次比較；比如順序表中需要從表頭開始依次往后比對尋找，查找時間復雜度為 O(N)，平衡樹中需要從第一層開始逐層往下比對尋找，查找時間復雜度為 O(logN)；即搜索的效率取決于搜索過程中元素的比較次數。

? ?盡管平衡樹的查找方式已經很快了，但我們仍然認為該方法不夠極致，我們最理想的查找方式：不像二叉樹那樣經過層層比較，能夠用O(1)的時間復雜度直接查詢到我們需要的元素。

? 如果構造一種存儲結構，通過某種函數(hashFunc)使元素的存儲位置與它的關鍵碼之間能夠建立一一映射的關系，那么在查找時通過該函數可以很快找到該元素。

一.哈希思想

?1.1 哈希思想的概念?

? ? 構造一種存儲結構，我們通過某種方法使元素的存儲位置與其查找的元素建立某種映射關系，從而利用O（1）的時間復雜度一次性查找到我們需要的元素，這就是哈希思想。

? ?當向該結構中：

插入元素時：根據待插入元素的特性，提取出一個關鍵碼，以此通過轉換函數計算出該元素的存儲位置并按此位置進行插入。
搜索元素時：對元素的關鍵碼進行同樣的計算，把求得的函數值當做元素的存儲位置，在結構中按此位置取元素比較，若關鍵碼相等，則搜索成功。

? 該方法即為哈希 (散列) 方法，哈希方法中使用的轉換函數稱為哈希 (散列) 函數，構造出來的結構稱為哈希表 (Hash Table) (或者稱散列表)。

? ps：我們上面提到的不管是順序搜索、平衡樹搜索還是哈希搜索，其 key 值都是唯一的，也就是說，搜索樹中不允許出現相同 key 值的節點，哈希表中也不允許出現相同 key 值的元素，我們下文所進行的所有操作也都是在這前提之上進行的。

假設? 數據集合?{1?，?7?，?6?，?4?，?5?，?9}?；存儲空間為10

哈希函數設置為：?hash(key)? ?= key % capacity?;

capacity?為存儲元素底層空間總的大小。

我們通過查找元素與下標關系構建一個數組，當我們查找1 時，可以直接定位到下標1這個位置，實現O（1）時間內的查找。?

?1.2 哈希函數

哈希函數有如下設計原則：

哈希函數應該要滿足待插入的所有元素使用，其值域如果在0到m-1之間，那么他就必須有m個空間。
哈希函數計算出來的地址要盡量能均勻分布在整個空間中；
哈希函數應該比較簡單

我們有幾個比較常見的哈希函數：
1.2.1 直接定址法?

直接定址法是最簡單的哈希函數，顧名思義，直接定址就是根據 key 值直接得到存儲位置，最多再進行一個簡單的常數之間的轉換，其定義如下：

Hash（Key）= A*Key + B (A B 均為常數)

?這個如果不懂，假設A=0,B=0，Key為常數，即根據Key值直接確定存儲位置。

優點：簡單、均勻

缺點：需要事先知道關鍵字的分布情況

使用場景：適合查找比較小且連續的情況

直接定址法不適用于數據范圍分散的情況，因為這樣會導致哈希表的空間利用率很低，會浪費很多空間?

比如：int arr[] = { 123, 126, 125, 138, 122331, 1}; 假設A,B都為0

?Hash(1)= 1;

Hash（12231）=12231；

那么我們根據哈希函數的定義，至少要用12231個int大小的數組來建立哈希表，那么它就會占用很多存儲空間。

1.2.2?除留余數法 (最常用)

? 為了應對數據范圍分散的情況，有人設計出了除留余數法 – 設哈希表中允許的地址數為m，取一個不大于m，但最接近或者等于m的素數p作為除數。

Hash(key) = key % p (p<=m)

? 簡單來說就是用 key 值除以哈希表的大小得到的余數作為哈希映射的地址，將 key 保存到該地址中；除留余數的優點是可以處理數據范圍分散的數據，缺點是會引發哈希沖突（下文會提及）.

例如對于數據集合 {1，7，6，4，5，9}，存儲空間為10 ，它的哈希表如下：

ps：接下來我們在文章中如果提到哈希函數，默認為除留余數法。?

1.3 哈希沖突

? 如何有兩個元素 x！=y，但是 hash（x）==hash（y），這種明明不同的元素，但是經過哈希函數計算后得到的結果一致，我們就將這種情況稱為哈希沖突。

哈希沖突有兩種常見的解決辦法：

? 閉散列 (開放定址法)：當發生哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那么可以把 key 存放到沖突位置中的 “下一個” 空位置中去；

??
? 開散列 (鏈地址法)：首先對關鍵碼集合用散列函數計算散列地址，具有相同地址的關鍵碼 (哈希沖突) 歸于同一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單鏈表鏈接起來，各鏈表的頭結點存儲在哈希表中；也就是說，當發生哈希沖突時，把 key 直接鏈接在該位置的下面。

假設我們在插入一個11和21 ：

二、閉散列法的哈希表

? 閉散列也叫開放定址法，當發生哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那么可以把 key 存放到沖突位置中的 “下一個” 空位置中去；那如何尋找下一個空位置呢？有兩種方法 – 線性探測法（常用）和二次探測法。

2.1線性探測法

? 線性探測法是指從發生沖突的位置開始，依次向后探測，直到尋找到下一個空位置為止；

插入11和21后：?

2.2 哈希表的基本框架

//通過空和存在判斷插入，通過刪除狀態判斷查找
enum State {EXIST,EMPTY,DELETE
};template<class K,class V>
struct HashData {pair<K, V> _kv; //每個節點存儲KV結構State _state = EMPTY;  //默認為空
};template<class K, class V>
class HashTable {typedef HashData<K, V> Data;HashTable(): _n(0){//將哈希表的大小默認給為10_tables.resize(10);}
private://把哈希函數封裝一下size_t Hashifunction(const K& key){//這里我們采用除留余數法return key% _tables.size();}
private:vector<Data> _tables;size_t _n;  //記錄表中有效數據的個數
};

? 如上，為了方便，在哈希表中我們使用了 vector 來存儲數據，并增加了一個變量 n 來記錄表中有效數據的個數，這是我們哈希表的底層實現。

?同時，我們在哈希表的每個位置的數據中還增加了一個 state 變量來記錄該位置的狀態，但為什么要有三個變量呢？我們不是只需要存在或者不存在不就足夠了嗎？這是為了以后哈希表的查找做基礎。

2.3 哈希表的插入

插入：通過哈希函數得到余數即數組下標，如果該下標的狀態為刪除或為空則插入，如果為存在則向后尋找下一個狀態為刪除/空的位置進行插入。（擴容一會單獨講）

	bool Insert(const pair<K,V> & kv){if (find(kv.first)){//先判斷是否查找到，因為不能存儲相同的結構，如果查找到返回falsereturn false;}//根據除留余數法判斷該插入數組的哪個位置size_t hashi = Hashifunction(kv.first);while (_tables[hashi]._state == EXIST) {++hashi;hashi = hashi % _tables.size();  //如果探測到末尾則從頭開始重新探測}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}

2.4 哈希表的查找

? 查找：通過哈希函數得到余數即數組下標，取出小標位置的key與目標key進行比較，相等就返回該位置的地址，不相等就繼續往后查找，如果查找到狀態為空的下標位置就返回 nullptr；注意：這里有三個細節：

? 當遇到狀態為空的下標位置才返回 nullptr，而不是遇到狀態為刪除的位置就返回 nullptr，因為你要查找的數據可能在已刪除位置的后面，這也是我們需要添加一個刪除狀態的原因，如果你把一個位置的元素刪除并設置為EMPTY狀態，那么我們該如何進行查找呢？我們插入時，其元素可能在刪除元素后面，例如：
??

如果是這樣，那么你該如何查找呢？?

??
? 將查找函數返回值定義為 Data*，而不是 bool，這樣可以方便我們進行刪除和修改 (修改 key 對應的 value) – 查找到之后直接通過指針解引用來修改 value 與 state；

? 哈希表經過不斷插入刪除，最終可能會出現一種極端情況 – 哈希表中元素的狀態全為 EXIST 和 DELETE，此時如果我們找空就會造成死循環，所以我們需要對這種情況單獨進行處理.

	Data* find(const K& key) {size_t hashi = Hashifunction(key);//增加一個數字 如果查找一周 返回falsesize_t start = hashi;while (_tables[hashi]._state!= EMPTY)//如果不為空則繼續查找{if (_tables[hashi]._state==EXIST&&_tables[hashi]._kv.first == key){return &_tables[hashi];}hashi++;//此時已經查找了一圈，退出循環if (hashi == start) {break;}hashi %= _tables.size();}//為空查找失敗return nullptr;}

?2.5 哈希表的刪除

?刪除：這里直接復用查找函數，查找到就通過查找函數的返回值將小標位置數據的狀態置為刪除，找不到就返回 false。

? 這里采用偽刪除法，將狀態改為DELETE就好，畢竟我們重新插入時也是只看位置的狀態，偽刪除法還減少了刪除消耗。

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

2.6 哈希表的擴容

? ?哈希表的擴容和順序表的不同，它并不是存儲空間滿了的時候才開始擴容，而是依據負載因子。

?其本質原因就是因為有哈希沖突的存在，當我們插入時，如果發生了哈希沖突，那么我們的插入，查找，刪除效率最低都可以達到O（n)級別，那就將我們哈希表的各種優勢都變得很微弱，甚至是變成劣勢（相比紅黑樹等來說，有可能退化為順序表）。

? 因此，我們引入了負載因子這一概念，其本質為一個閾值，定義為：

負載因子=散列表中的元素個數/散列表的長度

??? 這里我們定義我們的負載因子為0.7，并且當負載因子每次超過這個值時，我們都將其容量擴大為2倍。

? 同時，注意我在代碼區編寫的注意事項

代碼如下:

	void HashExpansion(const size_t& fac){//開始擴容if (fac >= 7){//我們直接采用老板思維，創建一個長度為2*n的新表，然后一個個插入，最后直接交換//因為擴容后，數組長度發生變化，哈希函數也會變化，哈希表對應的位置也會變化//因此不能單純的把數組長度變為2倍，需要一個個借助新表的插入函數，重新建立映射關系HashTable<K, V> newData;newData._tables.resize(_tables.size() * 2);for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST){newData.Insert(_tables[i]._kv);}}_tables.swap(newData._tables);}}

更改后的insert代碼：

	bool Insert(const pair<K,V> & kv){if (find(kv.first)){//先判斷是否查找到，因為不能存儲相同的結構，如果查找到返回falsereturn false;}//根據除留余數法判斷該插入數組的哪個位置size_t hashi = Hashifunction(kv.first);//這里我們通過一點小學知識將0.7 化為整數7HashExpansion(_n * 10 / _tables.size());while (_tables[hashi]._state == EXIST) {++hashi;hashi = hashi % _tables.size();  //如果探測到末尾則從頭開始重新探測}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}

2.7 哈希表的仿函數

?我們的哈希表就已經完成的差不多了，還有很多細節問題，比如說，我們如果key類型是一個string類型的對象，我們該如何經過除留余數法，得到我們應該對應的下標呢？

?我們這里建議創建幾個仿函數，分別對應不同的類型，得到不同的求解方法。

?關于整形，我們的仿函數模板如下，直接放回其對應的整形值：

template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};

關于其它類型，我們先將其轉化為整形，然后再將其返回，如字符串類型：

template<>
struct HashFunc<string>
{size_t operator()(const string& key){// BKDR轉換方法size_t hash = 0;for (auto e : key){hash *= 31;hash += e;}//cout << key << ":" << hash << endl;return hash;}
};

? 但是請注意，其他類型，不同的值可能會經過轉換的結果是相同的，這是因為int或者其它整形一共就幾十個bit位，而string等等類型我只能說無窮無盡也。

? 因此，建議用一些專用的轉換方法，這些是專業string轉換整形方法的鏈接：各種字符串Hash函數 - clq - 博客園

模板更改和函數更改：?

2.8 測試代碼?

?打印函數：

	void Print(){for (size_t i = 0; i < _tables.size(); i++){if(_tables[i]._state==EXIST){//cout << "[" << i << "]->" << _tables[i]._kv.first << ":" << _tables[i]._kv.second << endl;printf("_tables._state[%d] == ", i);cout << _tables[i]._kv.first <<"-> "<< _tables[i]._kv.second<< endl;}else if (_tables[i]._state == DELETE) {printf("_tables._state[%d] == DELETE\n", i);}else {printf("_tables._state[%d] == EMPTY\n", i);}}cout << endl << endl;}

測試代碼1：
?


void TestHT1()
{HashTable<int, int> ht;int a[] = { 4,14,24,34,5,7,1 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(3, 3));ht.Insert(make_pair(-3, -3));ht.Print();ht.Erase(3);ht.Print();if (ht.find(3)){cout << "3存在" << endl;}else{cout << "3不存在" << endl;}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(23, 3));ht.Print();
}

結果為：
?

測試代碼2：
?

void TestHT2()
{string arr[] = { "香蕉", "甜瓜","蘋果", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" };//HashTable<string, int, HashFuncString> ht;HashTable<string, int> ht;for (auto& e : arr){//auto ret = ht.Find(e);HashData<string, int>* ret = ht.find(e);if (ret){ret->_kv.second++;}else{ht.Insert(make_pair(e, 1));}}ht.Print();ht.Insert(make_pair("apple", 1));ht.Insert(make_pair("sort", 1));ht.Insert(make_pair("abc", 1));ht.Insert(make_pair("acb", 1));ht.Insert(make_pair("aad", 1));ht.Print();
}

代碼結果為：

2.9 完整代碼?

#pragma once
#include<iostream>
#include<vector>
using namespace std;template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};// 11:46繼續
//HashFunc<string>
template<>
struct HashFunc<string>
{size_t operator()(const string& key){// BKDRsize_t hash = 0;for (auto e : key){hash *= 31;hash += e;}//cout << key << ":" << hash << endl;return hash;}
};//通過空和存在判斷插入，通過刪除狀態判斷查找
enum State {EXIST,EMPTY,DELETE
};template<class K,class V>
struct HashData {pair<K, V> _kv; //每個節點存儲KV結構State _state = EMPTY;  //默認為空
};//template<class K, class V>
template<class K, class V, class Hash = HashFunc<K>>
class HashTable {typedef HashData<K, V> Data;
public:HashTable(): _n(0){//將哈希表的大小默認給為10_tables.resize(10);}bool Insert(const pair<K,V> & kv){if (find(kv.first)){//先判斷是否查找到，因為不能存儲相同的結構，如果查找到返回falsereturn false;}//根據除留余數法判斷該插入數組的哪個位置size_t hashi = Hashifunction(kv.first);//這里我們通過一點小學知識將0.7 化為整數7HashExpansion(_n * 10 / _tables.size());while (_tables[hashi]._state == EXIST) {++hashi;hashi = hashi % _tables.size();  //如果探測到末尾則從頭開始重新探測}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}Data* find(const K& key) {size_t hashi = Hashifunction(key);//增加一個數字 如果查找一周 返回falsesize_t start = hashi;while (_tables[hashi]._state!= EMPTY)//如果不為空則繼續查找{if (_tables[hashi]._state==EXIST&&_tables[hashi]._kv.first == key){return &_tables[hashi];}hashi++;//此時已經查找了一圈，退出循環if (hashi == start) {break;}hashi %= _tables.size();}//為空查找失敗return nullptr;}bool Erase(const K& key){HashData<K, V>* ret = find(key);if(ret){ret->_state = DELETE;--_n;return true;}else {return false;}}void HashExpansion(const size_t& fac){//開始擴容if (fac >= 7){//我們直接采用老板思維，創建一個長度為2*n的新表，然后一個個插入，最后直接交換//因為擴容后，數組長度發生變化，哈希函數也會變化，哈希表對應的位置也會變化//因此不能單純的把數組長度變為2倍，需要一個個借助新表的插入函數，重新建立映射關系HashTable<K, V> newData;newData._tables.resize(_tables.size() * 2);for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._state == EXIST){newData.Insert(_tables[i]._kv);}}_tables.swap(newData._tables);}}void Print(){for (size_t i = 0; i < _tables.size(); i++){if(_tables[i]._state==EXIST){//cout << "[" << i << "]->" << _tables[i]._kv.first << ":" << _tables[i]._kv.second << endl;printf("_tables._state[%d] == ", i);cout << _tables[i]._kv.first <<"-> "<< _tables[i]._kv.second<< endl;}else if (_tables[i]._state == DELETE) {printf("_tables._state[%d] == DELETE\n", i);}else {printf("_tables._state[%d] == EMPTY\n", i);}}cout << endl << endl;}private://把哈希函數封裝一下size_t Hashifunction(const K& key){//這里我們采用除留余數法Hash kot;return kot(key)% _tables.size();}
private:vector<Data> _tables;size_t _n;  //記錄表中有效數據的個數
};void TestHT1()
{HashTable<int, int> ht;int a[] = { 4,14,24,34,5,7,1 };for (auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(3, 3));ht.Insert(make_pair(-3, -3));ht.Print();ht.Erase(3);ht.Print();if (ht.find(3)){cout << "3存在" << endl;}else{cout << "3不存在" << endl;}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(23, 3));ht.Print();
}void TestHT2()
{string arr[] = { "香蕉", "甜瓜","蘋果", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" };//HashTable<string, int, HashFuncString> ht;HashTable<string, int> ht;for (auto& e : arr){//auto ret = ht.Find(e);HashData<string, int>* ret = ht.find(e);if (ret){ret->_kv.second++;}else{ht.Insert(make_pair(e, 1));}}ht.Print();ht.Insert(make_pair("apple", 1));ht.Insert(make_pair("sort", 1));ht.Insert(make_pair("abc", 1));ht.Insert(make_pair("acb", 1));ht.Insert(make_pair("aad", 1));ht.Print();
}

三. 開散列表法的哈希表

? 開散列法又叫鏈地址法 (開鏈法)，首先對關鍵碼集合用散列函數計算散列地址，即 key 映射的下標位置，具有相同地址的關鍵碼 (哈希沖突) 歸于同一子集合，每一個子集合稱為一個桶 (哈希桶)，各個桶中的元素通過一個單鏈表鏈接起來，各鏈表的頭結點存儲在哈希表中；也就是說，當發生哈希沖突時，把 key 作為一個節點直接鏈接到通過哈希函數轉換后對應下標的哈希桶中。

3.1 哈希表的基本框架

//兩個仿函數，直接CV
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};//HashFunc<string>
template<>
struct HashFunc<string>
{size_t operator()(const string& key){// BKDRsize_t hash = 0;for (auto e : key){hash *= 31;hash += e;}//cout << key << ":" << hash << endl;return hash;}
};//這里就不用狀態表示了，因為我們無論節點是否存在，都可以進行插入
/*enum State {EXIST,EMPTY,DELETE
};*///節點定義
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 Hash = HashFunc<K>>
class HashTable {typedef HashNode<K, V> Node;
private://把哈希函數封裝一下size_t Hashifunction(const K& key) {//這里我們采用除留余數法Hash kot;return kot(key) % _tables.size();}
private:vector<Node*> _tables;  //指針數組size_t _n;  //表中有效數據的個數
};

3.2 哈希表的插入函數

? 開散列插入的前部分和閉散列一樣，根據哈希函數得到映射的下標位置，與閉散列不同的是，由于哈希表中每個下標位置都是一個哈希桶，即一個單鏈表，那么對于發現哈希沖突的元素我們只需要將其鏈接到哈希桶中即可，這里一共有兩種鏈接方式：

? 將元素鏈接到單鏈表的末尾，即尾插；
? 將元素鏈接到單鏈表的開頭，即頭插。

這里顯然是選擇元素進行頭插，因為尾插還需要找尾，會導致效率降低，插入部分代碼如下：
?

	bool Insert(const pair<K, V>& kv) {if (find(kv.first)) {return false;}//這里待會需要補一個擴容size_t hashi = Hashifunction(kv.first);//哈希桶頭插Node* newnode = new Node(kv);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return true;}

?3.3 開散列的查找

? 開散列的查找也很簡單，根據哈希函數找到下標，由于下標位置存儲的是鏈表首元素地址，所以我們只需要取出首元素地址，然后順序遍歷單鏈表即可：

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

3.4 開散列的刪除

? 開散列的刪除不能單純的依靠查找函數來進行直接刪除，因為在刪除函數中，我們不僅要對本應查找到的節點進行刪除，還要改變其父節點的指向，讓他指向刪除節點的下一個節點。

	bool erase(const K& key) {size_t  hashi = Hashifunction(key);Node* cur = _tables[hashi];//記錄上一個節點的父節點Node* prev = nullptr;while (cur) {if (cur->_kv.first == key) {if (cur == _tables[hashi]) {_tables[hashi] = cur->_next;}else {prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}

3.5 開散列的擴容

開散列的擴容可以和閉散列的擴容一樣借用insert函數，但是我們有更好的方法。

方法一：
? 借用insert函數。

方法二：

? ?將原本鏈表挨個頭插入新的哈希表。?

	if (fac > 7) {//這里我們有兩種方法//一是借用 以前我們開散列中的insert插入方法//此種實現比較簡單，但相比第二種有其對應的缺點//實現/*	HashTable<K, V> newTable;newTable._tables.resize(_tables.size() * 2,nullptr);for (int i = 0; i < _tables.size(); i++) {Node* cur = _tables[i];while (cur) {newTable.Insert(cur);cur = cur->_next;}}_tables.swap(newTable._tables);}*///二是直接把原先的哈希表中的每個單鏈表 按照新的哈希函數//直接頭插進新鏈表//這個方法我們可以看出，少借用insert的一部分//也就是說，我們沒有創建節點的消耗。//是真正的空間轉移 因此，效率比第一種方法高很多，我們以后用這個方法vector<Node*> newtable;newtable.resize(_tables.size() * 2, nullptr);for (int i = 0; i < _tables.size(); i++) {Node* cur = _tables[i];while (cur) {Node* next = cur->_next;size_t hashi = Hashifunction(cur->_kv.first, newtable);cur->_next = newtable[hashi];newtable[hashi] = newtable;cur = next;}_tables[i] = nullptr;}_tables.swap(newtable);}
}

?3.6 開散列的測試代碼

print函數和以前也要有所不同。

void Print() {for (int i = 0; i < _tables.size(); i++) {Node* cur = _tables[i];cout << i << ":";while (cur) {cout << "[" << cur->_kv.first << "-> " << cur->_kv.second << "]" << "    ";cur = cur->_next;}cout << endl;}cout << endl;}

兩段測試代碼：?

	void TestHT1(){HashTable<int, int> ht;int a[] = { 4,14,24,34,5,7,1 };for(auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(3, 3));ht.Insert(make_pair(-3, -3));ht.Print();ht.erase(3);ht.Print();if (ht.find(3)){cout << "3存在" << endl;}else{cout << "3不存在" << endl;}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(23, 3));ht.Print();
}void TestHT2()
{string arr[] = { "香蕉", "甜瓜","蘋果", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" };//HashTable<string, int, HashFuncString> ht;HashTable<string, int> ht;for (auto& e : arr){//auto ret = ht.Find(e);HashNode<string, int>* ret = ht.find(e);if (ret){ret->_kv.second++;}else{ht.Insert(make_pair(e, 1));}}ht.Print();ht.Insert(make_pair("apple", 1));ht.Insert(make_pair("sort", 1));ht.Insert(make_pair("abc", 1));ht.Insert(make_pair("acb", 1));ht.Insert(make_pair("aad", 1));ht.Print();
}

代碼一結果：

測試代碼二結果：

3.7 完整代碼?

#pragma once
#include<iostream>
#include<vector>
using namespace std;namespace BucketHash {//兩個仿函數，直接CVtemplate<class K>struct HashFunc{size_t operator()(const K& key){return (size_t)key;}};//HashFunc<string>template<>struct HashFunc<string>{size_t operator()(const string& key){// BKDRsize_t hash = 0;for (auto e : key){hash *= 31;hash += e;}//cout << key << ":" << hash << endl;return hash;}};//這里就不用狀態表示了，因為我們無論節點是否存在，都可以進行插入/*enum State {EXIST,EMPTY,DELETE};*///節點定義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 Hash = HashFunc<K>>class HashTable {typedef HashNode<K, V> Node;public:HashTable():_n(0){_tables.resize(10, nullptr);}bool Insert(const pair<K, V>& kv) {if (find(kv.first)) {return false;}HashExpansion(_n * 10 / _tables.size());//這里待會需要補一個擴容size_t hashi = Hashifunction(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 = Hashifunction(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 = Hashifunction(key,_tables.size());Node* cur = _tables[hashi];//記錄上一個節點的父節點Node* prev = nullptr;while (cur) {if (cur->_kv.first == key) {if (cur == _tables[hashi]) {_tables[hashi] = cur->_next;}else {prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}void HashExpansion(const size_t& fac){if (fac > 7) {//這里我們有兩種方法//一是借用 以前我們開散列中的insert插入方法//此種實現比較簡單，但相比第二種有其對應的缺點//實現/*	HashTable<K, V> newTable;newTable._tables.resize(_tables.size() * 2,nullptr);for (int i = 0; i < _tables.size(); i++) {Node* cur = _tables[i];while (cur) {newTable.Insert(cur);cur = cur->_next;}}_tables.swap(newTable._tables);}*///二是直接把原先的哈希表中的每個單鏈表 按照新的哈希函數//直接頭插進新鏈表//這個方法我們可以看出，少借用insert的一部分//也就是說，我們沒有創建節點的消耗。//是真正的空間轉移 因此，效率比第一種方法高很多，我們以后用這個方法//但是哈希函數就不好處理了，這里我建議直接把哈希函數改一下，直接傳入表的長度vector<Node*> newtable;newtable.resize(_tables.size() * 2, nullptr);for (int i = 0; i < _tables.size(); i++) {Node* cur = _tables[i];while (cur) {Node* next = cur->_next;size_t hashi = Hashifunction(cur->_kv.first, newtable.size());cur->_next = newtable[hashi];newtable[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtable);}}void Print() {for (int i = 0; i < _tables.size(); i++) {Node* cur = _tables[i];cout << i << ":";while (cur) {cout << "[" << cur->_kv.first << "-> " << cur->_kv.second << "]" << "    ";cur = cur->_next;}cout << endl;}cout << endl;}private://把哈希函數封裝一下size_t Hashifunction(const K& key,size_t size) {//這里我們采用除留余數法Hash kot;return kot(key) % size;}private:vector<Node*> _tables;  //指針數組size_t _n;  //表中有效數據的個數};void TestHT1(){HashTable<int, int> ht;int a[] = { 4,14,24,34,5,7,1 };for(auto e : a){ht.Insert(make_pair(e, e));}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(3, 3));ht.Insert(make_pair(-3, -3));ht.Print();ht.erase(3);ht.Print();if (ht.find(3)){cout << "3存在" << endl;}else{cout << "3不存在" << endl;}ht.Insert(make_pair(3, 3));ht.Insert(make_pair(23, 3));ht.Print();
}void TestHT2()
{string arr[] = { "香蕉", "甜瓜","蘋果", "西瓜", "蘋果", "西瓜", "蘋果", "蘋果", "西瓜", "蘋果", "香蕉", "蘋果", "香蕉" };//HashTable<string, int, HashFuncString> ht;HashTable<string, int> ht;for (auto& e : arr){//auto ret = ht.Find(e);HashNode<string, int>* ret = ht.find(e);if (ret){ret->_kv.second++;}else{ht.Insert(make_pair(e, 1));}}ht.Print();ht.Insert(make_pair("apple", 1));ht.Insert(make_pair("sort", 1));ht.Insert(make_pair("abc", 1));ht.Insert(make_pair("acb", 1));ht.Insert(make_pair("aad", 1));ht.Print();
}
}