柚子快報(bào)邀請(qǐng)碼778899分享：哈希算法 算法 【C++】哈希

http://yzkb.51969.com/

目錄

unordered系列關(guān)聯(lián)式容器

unordered_set

unordered_map

底層結(jié)構(gòu)

什么是哈希

哈希沖突

哈希桶的迭代器

HashTable的封裝

unordered_set封裝

unordered_set封裝

在哈希提出之前，stl的設(shè)計(jì)者認(rèn)為有紅黑樹(shù)就足夠了，但是的確在有些場(chǎng)景下，哈希的性能要優(yōu)于紅黑樹(shù)，紅黑樹(shù)和哈希的功能相似度大約是90%，主要區(qū)別有幾點(diǎn)：

1.有序 無(wú)序：哈希實(shí)現(xiàn)的map和set在C++的STL中叫做unordered map和unordered set，從名字上就能看出unordered map和unordered set是無(wú)序的，而紅黑樹(shù)實(shí)現(xiàn)的map和set是有序的。

2.性能，map和set的時(shí)間復(fù)雜度是O（logN），unordered map和unordered set的時(shí)間復(fù)雜度是O（1）。

3.底層角度區(qū)分適合場(chǎng)景

unordered系列關(guān)聯(lián)式容器

unordered_set

unordered_set和set的功能類(lèi)似，接口也很類(lèi)似

1.unordered_set的構(gòu)造

函數(shù)聲明功能介紹unordered_set構(gòu)造不同格式的unordered_set對(duì)象

2.unordered_set的容量

函數(shù)聲明功能介紹bool empty() const檢測(cè)unordered_set是否為空size_t size() const獲取unordered_set的有效元素個(gè)數(shù)

3.unordered_set的迭代器

函數(shù)聲明功能介紹begin返回unordered_set第一個(gè)元素的迭代器end返回unordered_set最后一個(gè)元素的迭代器

?和set不同的是，unordered_set的迭代器是單向的。

4.unordered_set的查詢(xún)

函數(shù)聲明功能介紹iterator find(const K& key) 返回key在哈希桶位置的迭代器 size_t count(const K& key)返回哈希桶中關(guān)鍵碼為key的元素的個(gè)數(shù)

5.unordered_set的修改操作

函數(shù)聲明功能介紹insert向容器中插入元素erase刪除容器元素clear清空容器元素

6.unordered_set的桶操作

函數(shù)聲明功能介紹size_t bucket_count()const返回哈希桶中通的個(gè)數(shù)size_t bucket_size(size_t n)const返回第n個(gè)哈希桶元素的個(gè)數(shù)size_t bucket(const K& key)返回元素key所在的桶號(hào)

unordered_map

參考unordered_map說(shuō)明文檔

底層結(jié)構(gòu)

什么是哈希

哈希是一種映射，是值和值進(jìn)行1對(duì)1或者1對(duì)多的映射，哈希表是哈希思想實(shí)現(xiàn)的數(shù)據(jù)結(jié)構(gòu)，是值和存儲(chǔ)位置建立映射關(guān)系。??但是，值和存儲(chǔ)位置建立映射關(guān)系也會(huì)存在問(wèn)題：

1.值很分散（如1,5,1000,52,18），這樣就需要很多的存儲(chǔ)位置，很多存儲(chǔ)位置沒(méi)有被使用，會(huì)被浪費(fèi)

2.有些值不好映射，如string、結(jié)構(gòu)體對(duì)象

為了解決第一個(gè)問(wèn)題，提出了除留余數(shù)法，i=key%空間的大小，這樣就做到空間和值的范圍無(wú)關(guān)，

但是這樣就會(huì)引入另外一個(gè)問(wèn)題--哈希沖突，

哈希沖突

也叫哈希碰撞，不同的值可能會(huì)映射到相同位置（如上面的10001和1），

為了解決互哈希沖突的問(wèn)題，提出了兩種解決方法：

1.閉散列：開(kāi)放定址法

當(dāng)一個(gè)元素插入時(shí)，當(dāng)它本應(yīng)該插入的位置被占用時(shí)，按照某種方法往后找空位置去插入它。

某種方法：

????????1.線性探測(cè)：從當(dāng)前位置挨著往后找一個(gè)空的位置插入，

? ? ? ? 2.二次探測(cè)：跳躍著往后找空位置

思路：我的位置被占了，我就去后面搶別人的位置用。這樣導(dǎo)致的問(wèn)題是元素間相互影響，查找的效率低下，查找時(shí)，找到空的位置才能確認(rèn)沒(méi)有這個(gè)元素。這種方式不是我們重點(diǎn)的解決方式。

雖然這種方法的效率不高，但是早期有些地方可能也會(huì)用，所以我們還是來(lái)實(shí)現(xiàn)一下：

首先第一個(gè)問(wèn)題，當(dāng)我們查找某個(gè)元素是否存在時(shí)，找到空位置就說(shuō)明這個(gè)元素不存在。那么，怎樣算空位置呢？

第二個(gè)問(wèn)題，刪除55后，再查31,會(huì)發(fā)生31存在，但是找不到的情況（尷尬￣□￣｜｜）

為了解決這樣的問(wèn)題，我們可以給每個(gè)節(jié)點(diǎn)加一個(gè)狀態(tài)標(biāo)記，

當(dāng)把某個(gè)節(jié)點(diǎn)刪除了，不是把它標(biāo)為EMPTY，而是標(biāo)為DELETE，這樣問(wèn)題就解決了。

接下來(lái)就要完成哈希表的插入，當(dāng)插入某個(gè)節(jié)點(diǎn)時(shí)，需要除留取余得到這個(gè)結(jié)點(diǎn)應(yīng)該放的位置，如果這個(gè)位置狀態(tài)是EXIST，就需要依次找下一個(gè)位置，直到找到狀態(tài)為EMPTY或DELETE的節(jié)點(diǎn)。但是，在找下一個(gè)狀態(tài)為EMPTY或DELETE的節(jié)點(diǎn)時(shí)，有可能當(dāng)前所有節(jié)點(diǎn)的狀態(tài)都是EXIST，這時(shí)的哈希表已滿(mǎn)，需要擴(kuò)容。

這里先引入負(fù)載因子的概念，就是當(dāng)前數(shù)據(jù)個(gè)數(shù)/總數(shù)據(jù)個(gè)數(shù)，取值范圍為0-1。

雖然哈希表看起來(lái)效率不錯(cuò)，但是如果負(fù)載因子越高，沖突率越高，效率就越低；負(fù)載因子越小，沖突率越低，效率就越高，但是空間利用率越低。比如，哈希表的size是10，但是已經(jīng)有8個(gè)數(shù)據(jù)了，這時(shí)候插入數(shù)據(jù)極有可能會(huì)造成哈希沖突。?

所以，并不是哈希表滿(mǎn)了再進(jìn)行擴(kuò)容，一般當(dāng)負(fù)載因子超過(guò)0.7就會(huì)擴(kuò)容。擴(kuò)容完成后，我們不能直接memcpy原來(lái)表里的內(nèi)容到新的表里，這樣會(huì)發(fā)生錯(cuò)亂（比如之前的表大小是10,12要放到下標(biāo)為2的位置處，當(dāng)表大小擴(kuò)容到20后，12就需要放在下標(biāo)為12的位置）。因此，擴(kuò)容后，原有的值不能直接拷貝，需要重新映射。實(shí)際上，擴(kuò)容這一步效率很低，因此哈希表的插入效率會(huì)呈現(xiàn)出這樣的形式，但是整體平均的效率依然很高：

看一個(gè)擴(kuò)容的示意圖：

可以看出，擴(kuò)容后數(shù)據(jù)變得更分散，沖突率就會(huì)變低。

哈希表插入的代碼如下：

bool Insert(const pair& kv)

{

//防止重復(fù)插入

if (Find(kv.first))

return false;

//負(fù)載因子>=0.7,就擴(kuò)容;不需要擔(dān)心剛開(kāi)始size是0，我們?cè)谧约簩?xiě)的默認(rèn)構(gòu)造里初始化大小為10了

if (_n * 10 / _tables.size() >= 7)

{

//現(xiàn)代寫(xiě)法，本質(zhì)上是一種復(fù)用

size_t newsize = 2 * _tables.size();

//創(chuàng)建一個(gè)新的Hash表

HashTable 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);

}

size_t hashi = kv.first % _tables.size();

//線性探測(cè)

while (_tables[hashi]._state == EXIST)

{

hashi++;

hashi %= _tables.size();

}

_tables[hashi]._kv = kv;

_tables[hashi]._state = EXIST;

++_n;

return true;

}

接著，我們來(lái)寫(xiě)一下哈希表查找的代碼，查找的思路就是從除留余數(shù)的位置開(kāi)始找，直到找到狀態(tài)為EMPTY的節(jié)點(diǎn)：

HashData* Find(const K& key)

{

size_t hashi = key % _tables.size();

while ( _tables[hashi]._state != EMPTY)

{

//_tables[hashi]._state != EMPTY這個(gè)條件很有必要，如果沒(méi)有，當(dāng)刪除某個(gè)值，再查找這個(gè)值，仍然能找到

if (_tables[hashi]._state == EXIST

&&_tables[hashi]._kv.first == key)

return &_tables[hashi];

hashi++;

}

return nullptr;

}

需要注意的是，while循環(huán)里面if語(yǔ)句的判斷條件_tables[hashi]._state == EXIST是必要的，如果沒(méi)有，當(dāng)刪除某個(gè)值后，再查找這個(gè)值，仍然能找到，這就不對(duì)了！

接著我們?cè)賮?lái)寫(xiě)一下刪除的代碼，刪除的思路就是把所刪除節(jié)點(diǎn)的狀態(tài)改為DELETE：

bool Erase(const K& key)

{

HashData* ret = Find(key);

if (ret != nullptr)

{

ret->_state = DELETE;

--_n;

return true;

}

else

return false;

}

以上解決了值很分散的問(wèn)題，但是，還存在另一個(gè)問(wèn)題，那就是值的類(lèi)型如果為string、結(jié)構(gòu)體怎么辦？

?我們可以再建立一層哈希：

我們知道，哈希就是值 --> 存儲(chǔ)位置建立映射關(guān)系，如果值是int，那么就可以直接建立映射關(guān)系；如果是string，可以把string轉(zhuǎn)換成int，然后int再和存儲(chǔ)位置建立映射。

那么如何把string轉(zhuǎn)換成int，可以考慮把string[0]的ascii碼當(dāng)成int，為了實(shí)現(xiàn)這樣的功能，需要在HashTable的模版參數(shù)中增加一個(gè)，從而在類(lèi)中可以使用仿函數(shù)：

?默認(rèn)使用HashFunc這個(gè)類(lèi)，它的實(shí)現(xiàn)：

template

struct HashFunc

{

size_t operator()(const K& key)

{

return (size_t)key;

}

};

?將這個(gè)類(lèi)作為模版參數(shù)傳入后，不管元素的值是負(fù)數(shù)、浮點(diǎn)數(shù)，都可以轉(zhuǎn)換成size_t。

如果值是string，可以構(gòu)造如下類(lèi)：

struct StringHashFunc

{

size_t operator()(const string& key)

{

return key[0];

}

};

?字符串和其首字母的ascii碼值一一對(duì)應(yīng)。

但是，這個(gè)字符串轉(zhuǎn)換成整形的方案不太好，這時(shí)只要首字母一樣，就會(huì)沖突，所以，我們可以換一種方案，遍歷string，把每個(gè)字母的ascii加起來(lái)：

struct StringHashFunc

{

size_t operator()(const string& key)

{

size_t hash = 0;

for (auto e : key)

{

hash += e;

}

return hash;

}

};

但是，這種方案也有缺陷，如abcd，acbd，aadd等的ascii值加起來(lái)是一樣的。實(shí)際上，現(xiàn)實(shí)中有很多字符串哈希算法，其中，BKDR方法效果最好：

//BKDR

struct StringHashFunc

{

size_t operator()(const string& key)

{

size_t hash = 0;

for (auto e : key)

{

hash = hash * 131 + e;

}

return hash;

}

};

那這種BKDR算法還存在沖突嗎？

仍然存在。 假設(shè)字符串長(zhǎng)度是10，共有256的10次方個(gè)，但是映射的整形size_t是42億左右，仍然存在沖突。

總結(jié)一下思路：如果key不支持強(qiáng)轉(zhuǎn)整形取模，那么就要自己提供轉(zhuǎn)換成整形的仿函數(shù)。

還有一點(diǎn)值得注意，我們?cè)谑褂胾nordered_map插入string時(shí)，并沒(méi)有使用仿函數(shù)，它其實(shí)由于string經(jīng)常作為key，所以可以給string做一個(gè)特化：

template

struct HashFunc

{

size_t operator()(const K& key)

{

return (size_t)key;

}

};

//string 特化

template<>

struct HashFunc

{

size_t operator()(const string& key)

{

size_t hash = 0;

for (auto e : key)

{

hash = hash * 131 + e;

}

return hash;

}

};

那如果把日期類(lèi)作為key呢？?那也需要自己寫(xiě)仿函數(shù)，仿函數(shù)中可以把年月日加起來(lái)。如果是Person類(lèi)作為key呢？可以把名字轉(zhuǎn)換成整形，再加年齡，依次類(lèi)推。

2.哈希桶

哈希桶，又叫拉鏈法，哈希桶的方式才是我們要重點(diǎn)學(xué)習(xí)的方式。哈希桶的思想是，當(dāng)一個(gè)元素插入時(shí)，當(dāng)它本應(yīng)該插入的位置被占用時(shí)，在這個(gè)位置下面插入一個(gè)節(jié)點(diǎn)，把這個(gè)節(jié)點(diǎn)掛起來(lái)，

這樣盡管節(jié)點(diǎn)數(shù)量很多，也不會(huì)互相影響。哈希桶的效率很高，比如我們要查找64，在原來(lái)的序列里需要查8次，但是在哈希桶只需要查3次。

那么，我們先來(lái)設(shè)置一下Hash節(jié)點(diǎn)：

template

struct HashNode

{

pair _kv;

HashNode* _next;

};

首先來(lái)實(shí)現(xiàn)一下插入：先找到元素待插入的位置，然后通過(guò)頭插插入這個(gè)位置的鏈表中。真正的問(wèn)題在于擴(kuò)容，首先最容易想到的思路是：在擴(kuò)容時(shí)，創(chuàng)建一個(gè)新的哈希表，表的大小是原來(lái)大小的2倍，遍歷原表的每一個(gè)桶的每一個(gè)節(jié)點(diǎn)，然后插入到新表里，再拿這兩個(gè)表的_tables交換。如下代碼：

bool Insert(const pair& kv)

{

//方法1，構(gòu)建一個(gè)新的哈希表，遍歷原表每一個(gè)節(jié)點(diǎn)，插入到新表上

//擴(kuò)容

//負(fù)載因子為1時(shí)擴(kuò)容，這時(shí)大概一個(gè)節(jié)點(diǎn)下面掛一個(gè)

if (_n == _tables.size())

{

size_t newsize = _tables.size() * 2;

HashTable newHT;

newHT._tables.resize(newsize);

//舊表內(nèi)容重新計(jì)算放到新表上

for (size_t i = 0; i < _tables.size(); i++)

{

Node* cur = _tables[i];

while (cur)

{

newHT.Insert(cur->_kv);

cur = cur->_next;

}

}

_tables.swap(newHT._tables);

}

size_t hashi = kv.first % _tables.size();

Node* newnode = new Node(kv);

//頭插，時(shí)間復(fù)雜度是O(1)

newnode->_next = _tables[hashi];

_tables[hashi] = newnode;

++_n;

return true;

}

上面的newHT出了作用域應(yīng)該被銷(xiāo)毀，需要調(diào)用析構(gòu)函數(shù)，_tables是vector，會(huì)自動(dòng)銷(xiāo)毀，但是其上面掛的節(jié)點(diǎn)是自定義類(lèi)型，需要自己寫(xiě)析構(gòu)函數(shù)：

~HashTable()

{

for (size_t i = 0; i < _tables.size(); i++)

{

Node* cur = _tables[i];

while (cur)

{

Node* next = cur->_next;

delete cur;

cur = next;

}

_tables[i] = nullptr;

}

}

但是這種擴(kuò)容寫(xiě)法是有改進(jìn)空間的，如果原表上掛了10000個(gè)節(jié)點(diǎn)，那么在插入時(shí)，需要?jiǎng)?chuàng)建10000個(gè)節(jié)點(diǎn)，這樣效率很低，所以，可以考慮將原表的節(jié)點(diǎn)算出來(lái)應(yīng)該掛到新表的哪個(gè)位置，然后直接掛到新表上：

bool Insert(const pair& kv)

{

if (Find(kv.first))

return false;

//方法2，創(chuàng)建一個(gè)新表，遍歷原表的每一個(gè)節(jié)點(diǎn)，將原表的節(jié)點(diǎn)算出來(lái)應(yīng)該掛到新表的哪個(gè)位置，然后直接掛到新表上

//擴(kuò)容

if (_n == _tables.size())

{

vector newTables(_tables.size() * 2, 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 % newTables.size();

cur->_next = newTables[hashi];

newTables[hashi] = cur;

cur = next;

}

_tables[i] = nullptr;

}

_tables.swap(newTables);

}

size_t hashi = kv.first % _tables.size();

Node* newnode = new Node(kv);

//頭插，時(shí)間復(fù)雜度是O(1)

newnode->_next = _tables[hashi];

_tables[hashi] = newnode;

++_n;

return true;

}

再來(lái)看一下查找，比較簡(jiǎn)單：

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;

}

剩下的還有Erase，刪除節(jié)點(diǎn)要分刪除某個(gè)桶的頭節(jié)點(diǎn)和中間節(jié)點(diǎn)兩種情況：

bool Erase(const K& key)

{

size_t hashi = key % _tables.size();

Node* cur = _tables[hashi];

Node* prev = nullptr;

while (cur)

{

if (cur->_kv.first == key)

{

//刪除的是頭節(jié)點(diǎn)

if (prev == nullptr)

{

_tables[hashi] = cur->_next;

}

//刪除的是中間節(jié)點(diǎn)

else

{

prev->_next = cur->_next;

}

delete cur;

return true;

}

else

{

prev = cur;

cur = cur->_next;

}

}

return false;

}

同樣的，為了解決值的類(lèi)型是string、結(jié)構(gòu)體等類(lèi)型，我們也需要在HashTable的模版參數(shù)中增加一個(gè)，從而在類(lèi)中可以使用仿函數(shù)，這和上面的開(kāi)放定址法很類(lèi)似，就不再重復(fù)寫(xiě)了。

和紅黑樹(shù)封裝map和set類(lèi)似，可以將哈希桶的值類(lèi)型作為模版參數(shù)：?

但是，Class Hash這個(gè)參數(shù)應(yīng)該在unordered_map和unordered_set這層，因?yàn)槲覀冊(cè)趯?shí)際用的時(shí)候，只能調(diào)用到unordered_map和unordered_set：

哈希桶的迭代器

實(shí)現(xiàn)迭代器最難的地方還是在于++的實(shí)現(xiàn)，?

當(dāng)it遍歷完當(dāng)前桶后，現(xiàn)在我們只是知道一個(gè)Node*，如何找到下一個(gè)桶呢？為此，我們還需要知道這個(gè)哈希桶的表才行，所以，在__HTIterator中，還要加上HashTable*這個(gè)模版參數(shù)：

加上HashTable*后，當(dāng)++需要跳到下一個(gè)桶時(shí)，就從當(dāng)前桶出發(fā)，找到下一個(gè)桶：

Self& operator++()

{

if (_node->_next)

{

//當(dāng)前桶沒(méi)走完，取當(dāng)前桶的下一個(gè)節(jié)點(diǎn)

//_node和_node->_next在同一個(gè)桶中

_node = _node->_next;

}

else

{

//當(dāng)前桶走完了，取下一個(gè)不為空的桶的第一個(gè)節(jié)點(diǎn)

KeyOfT kot;

Hash hs;

//先找出當(dāng)前節(jié)點(diǎn)在哪個(gè)桶中

size_t i = hs(kot(_node->_data)) % (_pht->_tables.size());

//++指向下一個(gè)位置

++i;

//從下一個(gè)位置開(kāi)始找，找到下一個(gè)桶

for (; i < _pht->_tables.size(); i++)

{

if (_pht->_tables[i])

{

_node = _pht->_tables[i];

break;

}

}

if (i == _pht->_tables.size())

{

//所有桶都走完了，最后一個(gè)的下一個(gè)用nullptr標(biāo)記

_node = nullptr;

}

}

return *this;

}

這段程序就是迭代器的精華所在！

繼續(xù)封裝operator!=、operator*、operator->，

bool operator!=(const Self& self)

{

return _node != self._node;

}

T& operator*()

{

return _node->_data;

}

T* operator->()

{

return &_node->_data;

}

我們運(yùn)行后，可能會(huì)報(bào)錯(cuò)誤，原因在于struct __HTIterator和class HashTable在實(shí)現(xiàn)時(shí)要互相依賴(lài)，在這里，我們有兩種方法可以考慮：第一種是使用內(nèi)部類(lèi)解決這個(gè)問(wèn)題，即將struct __HTIterator放在class HashTable中實(shí)現(xiàn)；第二種是在struct __HTIterator的前面加上class HashTable的前置聲明，并將struct __HTIterator聲明為class HashTable的友元。

HashTable的封裝

template

struct HashFunc

{

size_t operator()(const K& key)

{

return (size_t)key;

}

};

//string 特化

template<>

struct HashFunc

{

size_t operator()(const string& key)

{

size_t hash = 0;

for (auto e : key)

{

hash = hash * 131 + e;

}

return hash;

}

};

namespace hash_bucket

{

template

struct HashNode

{

HashNode(const T& data)

:_data(data)

,_next(nullptr)

{}

T _data;

HashNode* _next;

};

template

class HashTable

{

typedef HashNode Node;

public:

template

struct __HTIterator

{

typedef HashNode Node;

typedef __HTIterator Self;

__HTIterator(Node* node, const HashTable* pht)

:_node(node)

, _pht(pht)

{}

Self& operator++()

{

if (_node->_next)

{

//當(dāng)前桶沒(méi)走完，取當(dāng)前桶的下一個(gè)節(jié)點(diǎn)

//_node和_node->_next在同一個(gè)桶中

_node = _node->_next;

}

else

{

//當(dāng)前桶走完了，取下一個(gè)不為空的桶的第一個(gè)節(jié)點(diǎn)

KeyOfT kot;

Hash hs;

//先找出當(dāng)前節(jié)點(diǎn)在哪個(gè)桶中

size_t i = hs(kot(_node->_data)) % (_pht->_tables.size());

//++指向下一個(gè)位置

++i;

//從下一個(gè)位置開(kāi)始找，找到下一個(gè)桶

for (; i < _pht->_tables.size(); i++)

{

if (_pht->_tables[i])

{

_node = _pht->_tables[i];

break;

}

}

if (i == _pht->_tables.size())

{

//所有桶都走完了，最后一個(gè)的下一個(gè)用nullptr標(biāo)記

_node = nullptr;

}

}

return *this;

}

bool operator!=(const Self& self)

{

return _node != self._node;

}

Ref operator*()

{

return _node->_data;

}

Ptr operator->()

{

return &_node->_data;

}

Node* _node;

const HashTable* _pht;

};

typedef __HTIterator iterator;

typedef __HTIterator const_iterator;

//friend struct __HTIterator;//把struct __HTIterator聲明為這個(gè)的友元，就可以在struct __HTIterator中訪問(wèn)_tables

iterator begin()

{

for (size_t i = 0; i < _tables.size(); i++)

{

if (_tables[i])

return iterator(_tables[i], this);//this就是哈希表的指針

}

return end();

}

iterator end()

{

return iterator(nullptr, this);

}

const_iterator begin()const

{

for (size_t i = 0; i < _tables.size(); i++)

{

if (_tables[i])

return iterator(_tables[i], this);//this就是哈希表的指針

}

return end();

}

const_iterator end()const

{

//this -> const HashTable*

return iterator(nullptr, this);

}

~HashTable()

{

for (size_t i = 0; i < _tables.size(); i++)

{

Node* cur = _tables[i];

while (cur)

{

Node* next = cur->_next;

delete cur;

cur = next;

}

_tables[i] = nullptr;

}

}

HashTable()

{

_tables.resize(10, nullptr);

_n = 0;

}

pair Insert(const T& data)

{

//方法1，構(gòu)建一個(gè)新的哈希表，遍歷原表每一個(gè)節(jié)點(diǎn)，插入到新表上

//擴(kuò)容

//負(fù)載因子為1時(shí)擴(kuò)容，這時(shí)大概一個(gè)節(jié)點(diǎn)下面掛一個(gè)

//if (_n == _tables.size())

//{

// size_t newsize = _tables.size() * 2;

// HashTable newHT;

// newHT._tables.resize(newsize);

// //舊表內(nèi)容重新計(jì)算放到新表上

// for (size_t i = 0; i < _tables.size(); i++)

// {

// Node* cur = _tables[i];

// while (cur)

// {

// newHT.Insert(cur->_kv);

// cur = cur->_next;

// }

// }

// _tables.swap(newHT._tables);

//}

KeyOfT kot;

iterator it = Find(kot(data));

if (it != end())

return make_pair(it,false);

//方法2，創(chuàng)建一個(gè)新表，遍歷原表的每一個(gè)節(jié)點(diǎn)，將原表的節(jié)點(diǎn)算出來(lái)應(yīng)該掛到新表的哪個(gè)位置，然后直接掛到新表上

//擴(kuò)容

Hash hf;

if (_n == _tables.size())

{

vector newTables(_tables.size() * 2, nullptr);

for (size_t i = 0; i < _tables.size(); i++)

{

Node* cur = _tables[i];

while (cur)

{

Node* next = cur->_next;

//頭插

size_t hashi = hf(kot(cur->_data)) % newTables.size();

cur->_next = newTables[hashi];

newTables[hashi] = cur;

cur = next;

}

_tables[i] = nullptr;

}

_tables.swap(newTables);

}

size_t hashi = hf(kot(data)) % _tables.size();

Node* newnode = new Node(data);

//頭插，時(shí)間復(fù)雜度是O(1)

newnode->_next = _tables[hashi];

_tables[hashi] = newnode;

++_n;

return make_pair(iterator(newnode,this),true);

}

iterator Find(const K& key)

{

KeyOfT kot;

Hash hf;

size_t hashi = hf(key) % _tables.size();

Node* cur = _tables[hashi];

while (cur)

{

if (kot(cur->_data) == key)

{

return iterator(cur,this);

}

cur = cur->_next;

}

return end();

}

bool Erase(const K& key)

{

KeyOfT kot;

Hash hf;

size_t hashi = hf(key) % _tables.size();

Node* cur = _tables[hashi];

Node* prev = nullptr;

while (cur)

{

if (kot(cur->_data) == key)

{

//刪除的是頭節(jié)點(diǎn)

if (prev == nullptr)

{

_tables[hashi] = cur->_next;

}

//刪除的是中間節(jié)點(diǎn)

else

{

prev->_next = cur->_next;

}

delete cur;

return true;

}

else

{

prev = cur;

cur = cur->_next;

}

}

return false;

}

private:

vector _tables;

size_t _n;

};

}

unordered_set封裝

template>

class unordered_set

{

struct SetKeyOfT

{

const K& operator()(const K& key)

{

return key;

}

};

public:

typedef typename hash_bucket::HashTable::iterator iterator;

typedef typename hash_bucket::HashTable::const_iterator const_iterator;

pair insert(const K& key)

{

return _ht.Insert(key);

}

iterator begin()

{

return _ht.begin();

}

iterator end()

{

return _ht.end();

}

const_iterator begin()const

{

return _ht.begin();

}

const_iterator end()const

{

return _ht.end();

}

iterator find(const K& key)

{

return _ht.Find(key);

}

bool erase(const K& key)

{

return _ht.Erase(key);

}

private:

hash_bucket::HashTable _ht;

};

需要注意的是， HashTable的第二個(gè)模版參數(shù)要用const K，這樣可以保證key不被修改。

unordered_map封裝

template>

class unordered_map

{

struct MapKeyOfT

{

const K& operator()(const pair& kv)

{

return kv.first;

}

};

public:

typedef typename hash_bucket::HashTable, MapKeyOfT, Hash>::iterator iterator;

typedef typename hash_bucket::HashTable, MapKeyOfT, Hash>::const_iterator const_iterator;

iterator begin()

{

return _ht.begin();

}

iterator end()

{

return _ht.end();

}

const_iterator begin()const

{

return _ht.begin();

}

const_iterator end()const

{

return _ht.end();

}

pair insert(const K& key)

{

return _ht.Insert(key);

}

V& operator[](const K& key)

{

pair ret = _ht.Insert(make_pair(key, V()));

return ret.first->second;

}

iterator find(const K& key)

{

return _ht.Find(key);

}

bool erase(const K& key)

{

return _ht.Erase(key);

}

private:

hash_bucket::HashTable, MapKeyOfT,Hash> _ht;

};

}

柚子快報(bào)邀請(qǐng)碼778899分享：哈希算法 算法 【C++】哈希

http://yzkb.51969.com/

好文閱讀