該哈希表實(shí)現(xiàn)是閉散列實(shí)現(xiàn)法。

閉散列表：

????????閉散列：也叫開(kāi)放定址法，當(dāng)發(fā)生哈希沖突時(shí)，如果哈希表未被裝滿，說(shuō)明在哈希表中必然還有空位置，那么可以把key存放到?jīng)_突位置中的“下一個(gè)” 空位置中去。

????????那如何尋找下一個(gè)空位置呢？

線性探測(cè)：

????????線性探測(cè)：從發(fā)生沖突的位置開(kāi)始，依次向后探測(cè)，直到尋找到下一個(gè)空位置為止。

注意：除了線性探測(cè)，你還可以進(jìn)行二次探測(cè)等，看個(gè)人實(shí)現(xiàn)策略。

如何插入
????????通過(guò)哈希函數(shù)獲取待插入元素在哈希表中的位置
????????如果該位置中沒(méi)有元素則直接插入新元素，如果該位置中有元素發(fā)生哈希沖突，
????????使用線性探測(cè)找到下一個(gè)空位置，插入新元素

比如2.1中的場(chǎng)景，現(xiàn)在需要插入元素44，先通過(guò)哈希函數(shù)計(jì)算哈希地址，hashAddr為4，
因此44理論上應(yīng)該插在該位置，但是該位置已經(jīng)放了值為4的元素，即發(fā)生哈希沖突。

如何刪除
????????采用閉散列處理哈希沖突時(shí)，不能隨便物理刪除哈希表中已有的元素，若直接刪除元素會(huì)影響其他元素的搜索。比如刪除元素4，如果直接刪除掉，44查找起來(lái)可能會(huì)受影響。因此線性探測(cè)采用標(biāo)記的偽刪除法來(lái)刪除一個(gè)元素。?

// 哈希表每個(gè)空間給個(gè)標(biāo)記
// EMPTY此位置空， EXIST此位置已經(jīng)有元素， DELETE元素已經(jīng)刪除
enum State{EMPTY, EXIST, DELETE};

線性探測(cè)實(shí)現(xiàn)插入：

		bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;// 負(fù)載因子0.7就擴(kuò)容if (_n*10 / _tables.size() == 7){size_t newSize = _tables.size() * 2;HashTable<K, V, Hash> newHT;newHT._tables.resize(newSize);// 遍歷舊表for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._s == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}Hash hf;// 線性探測(cè)size_t hashi = hf(kv.first) % _tables.size();while (_tables[hashi]._s == EXIST){hashi++;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._s = EXIST;++_n;return true;}

什么是負(fù)載因子？

? ? ? ? 負(fù)載因子是關(guān)鍵詞key的存儲(chǔ)個(gè)數(shù)與哈希表內(nèi)存大小之比，一般取0.75左右，這樣做是為了提高存儲(chǔ)效率，（只有百分之75的內(nèi)存可以用，剩余的百分之25，是不存儲(chǔ)的）減少哈希沖突。

如何擴(kuò)展內(nèi)存？

? ? ? ? 定義一個(gè)新的對(duì)象，開(kāi)好想要的內(nèi)存，將舊表的數(shù)據(jù)重新查到新的哈希表中，舊表的數(shù)據(jù)分布與新表的數(shù)據(jù)分布不一樣，將舊表數(shù)據(jù)插入完之后，再將新表的哈希表數(shù)據(jù)與舊表的數(shù)據(jù)進(jìn)行交換。

哈希表的查找：

		HashData<K, V>* Find(const K& key){Hash hf;size_t hashi = hf(key) % _tables.size();while (_tables[hashi]._s != EMPTY){if (_tables[hashi]._s == EXIST&& _tables[hashi]._kv.first == key){return &_tables[hashi];}hashi++;hashi %= _tables.size();}return NULL;}

數(shù)據(jù)有三種狀態(tài)：存在，刪除，為空。

存在和刪除的狀態(tài)下如果沒(méi)有找到要查找的數(shù)據(jù)就要向后繼續(xù)查找，因?yàn)椴迦霑r(shí)進(jìn)行的是線性插入，只有為空和刪除的位置才進(jìn)行插入，所以有可能想要的數(shù)據(jù)會(huì)出現(xiàn)在，刪除狀態(tài)的后面。

注意：如果是二次探測(cè)就進(jìn)行二次查找

哈希表的刪除：

		// 偽刪除法bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){ret->_s = DELETE;--_n;return true;}else{return false;}}

將要?jiǎng)h除的數(shù)據(jù)狀態(tài)進(jìn)行標(biāo)記就行了，如果標(biāo)記為空，就會(huì)影響查找函數(shù)的進(jìn)行，就可能會(huì)出現(xiàn)查找錯(cuò)誤的情況。

完整代碼及其測(cè)試代碼：

#include<vector>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){// BKDRsize_t hash = 0;for (auto e : key){hash *= 31;hash += e;}//cout << key << ":" << hash << endl;return hash;}
};namespace open_address
{enum Status{EMPTY,EXIST,DELETE};template<class K, class V>struct HashData{pair<K, V> _kv;Status _s;          //狀態(tài)};template<class K, class V, class Hash = HashFunc<K>>class HashTable{public:HashTable(){_tables.resize(10);}bool Insert(const pair<K, V>& kv){if (Find(kv.first))return false;// 負(fù)載因子0.7就擴(kuò)容if (_n*10 / _tables.size() == 7){size_t newSize = _tables.size() * 2;HashTable<K, V, Hash> newHT;newHT._tables.resize(newSize);// 遍歷舊表for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._s == EXIST){newHT.Insert(_tables[i]._kv);}}_tables.swap(newHT._tables);}Hash hf;// 線性探測(cè)size_t hashi = hf(kv.first) % _tables.size();while (_tables[hashi]._s == EXIST){hashi++;hashi %= _tables.size();}_tables[hashi]._kv = kv;_tables[hashi]._s = EXIST;++_n;return true;}HashData<K, V>* Find(const K& key){Hash hf;size_t hashi = hf(key) % _tables.size();while (_tables[hashi]._s != EMPTY){if (_tables[hashi]._s == EXIST&& _tables[hashi]._kv.first == key){return &_tables[hashi];}hashi++;hashi %= _tables.size();}return NULL;}// 偽刪除法bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){ret->_s = DELETE;--_n;return true;}else{return false;}}void Print(){for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]._s == EXIST){//printf("[%d]->%d\n", i, _tables[i]._kv.first);cout << "[" << i << "]->" << _tables[i]._kv.first <<":" << _tables[i]._kv.second<< endl;}else if (_tables[i]._s == EMPTY){printf("[%d]->\n", i);}else{printf("[%d]->D\n", i);}}cout << endl;}private:vector<HashData<K, V>> _tables;size_t _n = 0; // 存儲(chǔ)的關(guān)鍵字的個(gè)數(shù)};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[] = { "香蕉", "甜瓜","蘋(píng)果", "西瓜", "蘋(píng)果", "西瓜", "蘋(píng)果", "蘋(píng)果", "西瓜", "蘋(píng)果", "香蕉", "蘋(píng)果", "香蕉" };//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();}
}