一、哈希介紹
1.1 哈希概念
順序結(jié)構(gòu)中（數(shù)組）查找一個(gè)元素需要遍歷整個(gè)數(shù)組，時(shí)間復(fù)雜度為O(N)；樹(shù)形結(jié)構(gòu)中（二叉搜索樹(shù)）查找一個(gè)元素，時(shí)間復(fù)雜度最多為樹(shù)的高度次logN。理想的搜索方法：可以不經(jīng)過(guò)任何比較，一次直接從表中得到要搜索的元素。 構(gòu)造一種存儲(chǔ)結(jié)構(gòu)，通過(guò)某種函數(shù)使元素的存儲(chǔ)位置與它的關(guān)鍵碼之間能夠建立一一映射的關(guān)系，那么在查找時(shí)通過(guò)該函數(shù)可以很快找到該元素。
主要有3種操作：
- 插入——根據(jù)待插入元素的關(guān)鍵碼，以此函數(shù)計(jì)算出該元素的存儲(chǔ)位置并按此位置進(jìn)行存放
- 查找——根據(jù)要搜索的元素的關(guān)鍵碼，用函數(shù)計(jì)算出存儲(chǔ)位置，取該位置的元素關(guān)鍵碼進(jìn)行比較，如果相等，查找成功
- 刪除——根據(jù)待刪除元素的關(guān)鍵碼計(jì)算出該元素的存儲(chǔ)位置，如果改元素存在，則進(jìn)行刪除
該方式即為哈希(散列)方法，哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希(散列)函數(shù)，構(gòu)造出來(lái)的結(jié)構(gòu)稱為哈希表(Hash Table)(或者稱散列表)
哈希函數(shù)設(shè)置為：hash(key) = key % capacity; capacity為存儲(chǔ)元素底層空間總的大小。
用該方法進(jìn)行搜索不必進(jìn)行多次關(guān)鍵碼的比較，因此搜索的速度比較快
如果在上面的例子中插入元素44會(huì)怎樣？44%10也是4，與原來(lái)元素4的位置沖突了。那么這個(gè)新插入的44應(yīng)該如何放置呢？
1.2 哈希沖突解決
首先要知道哈希沖突的原因——哈希函數(shù)設(shè)計(jì)不夠合理
哈希函數(shù)設(shè)計(jì)原則：
- 哈希函數(shù)的定義域必須包括需要存儲(chǔ)的全部關(guān)鍵碼，而如果散列表允許有m個(gè)地址時(shí)，其值域必須在0到m-1之間
- 哈希函數(shù)計(jì)算出來(lái)的地址能均勻分布在整個(gè)空間中
- 哈希函數(shù)應(yīng)該比較簡(jiǎn)單
注意：哈希函數(shù)設(shè)計(jì)的越精妙，產(chǎn)生哈希沖突的可能性就越低，但是無(wú)法避免哈希沖突
下面介紹兩種常見(jiàn)的哈希函數(shù)：
- 閉散列
- 開(kāi)散列
1.2.1 閉散列
閉散列：也叫開(kāi)放定址法，當(dāng)發(fā)生哈希沖突時(shí)，如果哈希表未被裝滿，說(shuō)明在哈希表中必然還有空位置，那么可以把key存放到?jīng)_突位置中的“下一個(gè)” 空位置中去，這里的下一個(gè)可能也有元素，所以可能繼續(xù)重復(fù)前面的操作，直到遇到空位置。
線性探測(cè)：
從發(fā)生沖突的位置開(kāi)始，依次向后探測(cè)，直到尋找到下一個(gè)空位置為止。
44%4=4，與元素4的位置沖突，到它的下一個(gè)位置，位置5也有元素，繼續(xù)下一個(gè)，直到位置8沒(méi)有存儲(chǔ)元素，就把44存儲(chǔ)到位置8中。
1.2.2 開(kāi)散列
開(kāi)散列法又叫鏈地址法(開(kāi)鏈法)，首先對(duì)關(guān)鍵碼集合用散列函數(shù)計(jì)算散列地址，具有相同地址的關(guān)鍵碼歸于同一子集合，每一個(gè)子集合稱為一個(gè)桶，各個(gè)桶中的元素通過(guò)一個(gè)單鏈表鏈接起來(lái)，各鏈表的頭結(jié)點(diǎn)存儲(chǔ)在哈希表中。
開(kāi)散列中每個(gè)桶中放的都是發(fā)生哈希沖突的元素。
二、哈希桶
2.1 實(shí)現(xiàn)哈希桶
2.1.1 構(gòu)造節(jié)點(diǎn)和聲明成員變量
哈希表的每個(gè)位置是一個(gè)桶，這個(gè)桶的結(jié)構(gòu)是單鏈表，單鏈表由每個(gè)節(jié)點(diǎn)組成。節(jié)點(diǎn)有數(shù)據(jù)域和指針域，指針域是用來(lái)連接下一個(gè)節(jié)點(diǎn)的，數(shù)據(jù)域存放的是節(jié)點(diǎn)的值。節(jié)點(diǎn)的數(shù)據(jù)域有兩種：k模型和kv模型。這里實(shí)現(xiàn)哈希桶的是數(shù)據(jù)域是kv模型。
template<class K, class V>
struct HashNode
{
HashNode<K, V>* _next;
pair<K, V> _kv;
HashNode(const pair<K,V>& kv)
:_kv(kv)
, _next(nullptr)
{}
};
成員變量有存放的數(shù)據(jù)個(gè)數(shù)和哈希表的每個(gè)位置，即每個(gè)桶，用頭指針進(jìn)行連接，所以哈希表的每個(gè)位置是單鏈表的頭指針。
vector<Node*> _table;//哈希表的每個(gè)位置-桶-單鏈表
size_t _n = 0;//存儲(chǔ)的元素個(gè)數(shù)
2.1.2 構(gòu)造與析構(gòu)
1??構(gòu)造
剛開(kāi)始給哈希表一定的空間大小，每個(gè)位置初始化為空指針。
HashTable(size_t n = 5)
{
_table.resize(n, nullptr);
}
2??析構(gòu)
哈希表的結(jié)構(gòu)是STL庫(kù)中的vector，當(dāng)程序結(jié)束時(shí)，vector會(huì)自動(dòng)調(diào)用它的析構(gòu)來(lái)清理哈希表，但是表中的每個(gè)位置是單鏈表，單鏈表的每個(gè)節(jié)點(diǎn)是動(dòng)態(tài)開(kāi)辟出來(lái)的，vector的析構(gòu)不能清理它們。所以要自己寫析構(gòu)函數(shù)來(lái)清理這些節(jié)點(diǎn)。
~HashTable()
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
2.1.3 仿函數(shù)
哈希函數(shù)的計(jì)算公式：hash(key) = key % capacity，capacity就是表的空間大小，key必須是整數(shù)，但是key值是不確定的，有可能是整形、浮點(diǎn)型或者是字符串，所以要對(duì)key值作一些處理，使其變成整數(shù)才能進(jìn)行取模操作。
1??key不是字符串
返回值都轉(zhuǎn)化成無(wú)符號(hào)整數(shù)
template<class K>
struct HashFind
{
size_t operator()(const K& key)
{
return key;
}
};
2??key是字符串
因?yàn)閭鬟^(guò)來(lái)的參數(shù)固定就是字符串(string類型)，不像前面，可能是int、double等，所以這里可以直接特化處理。定義一個(gè)臨時(shí)變量為無(wú)符號(hào)整數(shù)作為返回值，遍歷每個(gè)字符加到臨時(shí)變量里，每個(gè)字符會(huì)自動(dòng)轉(zhuǎn)換成ASCII碼值，然后再乘上權(quán)值131（在《The C Programming Language》書(shū)中有解釋），保證不會(huì)出現(xiàn)year和raey相同的場(chǎng)景。
template<>
struct HashFind<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto& e : s)
{
hash += e;
hash *= 131;
}
return hash;
}
};
在后面的操作中使用到哈希函數(shù)：hash(key) = key % capacity，都要通過(guò)調(diào)用仿函數(shù)來(lái)實(shí)現(xiàn)。
2.1.4 查找
查找一個(gè)元素是否存在，首先要計(jì)算出該元素的位置。假設(shè)該元素存在，但是它在某個(gè)位置的桶中，通過(guò)遍歷單鏈表找到該元素，然后返回它在鏈表中的節(jié)點(diǎn)位置。不存在，返回nullptr
Node* Find(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _table.size();//表中的位置
Node* cur = _table[hashi];//得到當(dāng)前位置頭節(jié)點(diǎn)
while (cur)
{
if (cur->_kv.first == key)//找到了
{
return cur;
}
cur = cur->_next;
}
//cur為空，不存在這個(gè)數(shù)據(jù)
return nullptr;
}
2.1.5 插入
- 插入新的元素，不能有重復(fù)的，所以先對(duì)要插入的值進(jìn)行查找，如果找到了，說(shuō)明是重復(fù)元素，不能插入，返回失敗。
- 插入新的數(shù)據(jù)不是重復(fù)元素，計(jì)算該元素在哈希表的映射位置，創(chuàng)建一個(gè)新節(jié)點(diǎn)，用頭插法插入。
- 如果要插入數(shù)據(jù)前，哈希表的元素個(gè)數(shù)與哈希表的空間大小相等，就要擴(kuò)容。創(chuàng)建一個(gè)新的哈希表，擴(kuò)容的大小可以給原來(lái)的兩倍，初始化為空。遍歷舊表，將舊表的節(jié)點(diǎn)移動(dòng)到新表中。注意，移動(dòng)的過(guò)程中節(jié)點(diǎn)在舊表中的位置與新表可能是不對(duì)應(yīng)的，所以還要用哈希函數(shù)得到節(jié)點(diǎn)在新表的位置，然后插入的話還是頭插法。舊表中的每個(gè)位置即每個(gè)桶移動(dòng)完成，，就將舊表的該位置置空。最后全部轉(zhuǎn)移完，把舊表和新表進(jìn)行交換，后面使用的就是新表了。
bool Insert(const pair<K,V>& kv)
{
//重復(fù)元素不能插入
if (Find(kv.first))
{
return false;
}
Hash hs;
//擴(kuò)容
if (_n == _table.size())
{
vector<Node*> newTable(2 * _table.size(), nullptr);//新的空間
//將舊表的節(jié)點(diǎn)移到新表中，再交換
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
size_t hashi = hs(_table[i]->_kv.first) % newTable.size();
Node* next = cur->_next;
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
//插入數(shù)據(jù)
size_t hashi = hs(kv.first) % _table.size();//表中的位置
Node* newNode = new Node(kv);//新節(jié)點(diǎn)
//頭插法
newNode->_next = _table[hashi];
_table[hashi] = newNode;
++_n;
return true;
}
2.1.6 刪除
刪除某個(gè)元素，首先得查找該元素是否存在。如果不存在返回false；存在，通過(guò)哈希函數(shù)計(jì)算該元素的位置（是哪個(gè)桶的），得到該位置的頭指針（第一個(gè)節(jié)點(diǎn)），然后遍歷單鏈表，找到后刪除。
遍歷的過(guò)程中要注意兩種可能：
- 要?jiǎng)h除的節(jié)點(diǎn)是第一個(gè)節(jié)點(diǎn)
- 要?jiǎng)h除的節(jié)點(diǎn)是中間某個(gè)節(jié)點(diǎn)或者最后一個(gè)節(jié)點(diǎn)
bool Erase(const K& key)
{
Hash hs;
Node* ret = Find(key);
if (ret)
{
size_t hashi = hs(ret->_kv.first) % _table.size();//先找到表的位置
Node* cur = _table[hashi];//得到該位置的頭節(jié)點(diǎn)
Node* prev = nullptr;//前面的節(jié)點(diǎn)連接
while (cur)
{
if (cur->_kv.first == key)
{
if (prev)//第一個(gè)節(jié)點(diǎn)不是要?jiǎng)h除的
{
prev->_next = cur->_next;
}
else
{
_table[hashi] = cur->_next;
}
delete cur;
break;//找到具體節(jié)點(diǎn)刪除后跳出
}
prev = cur;
cur = cur->_next;
}
return true;
}
else//找不到，刪除失敗
{
return false;
}
}
2.2 kv模型哈希桶源代碼
#include <iostream>
#include <vector>
#include <string>
using namespace std;
//仿函數(shù)
template<class K>
struct HashFind
{
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct HashFind<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto& e : s)
{
hash += e;
hash *= 131;
}
return hash;
}
};
//節(jié)點(diǎn)
template<class K, class V>
struct HashNode
{
HashNode<K, V>* _next;
pair<K, V> _kv;
HashNode(const pair<K,V>& kv)
:_kv(kv)
, _next(nullptr)
{}
};
template<class K, class V, class Hash = HashFind<K>>
class HashTable
{
typedef HashNode<K,V> Node;
public:
//構(gòu)造
HashTable(size_t n = 5)
{
_table.resize(n, nullptr);
}
//析構(gòu)
~HashTable()
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
//查找
Node* Find(const K& key)
{
Hash hs;
size_t hashi = hs(key) % _table.size();//表中的位置
Node* cur = _table[hashi];//得到當(dāng)前位置頭節(jié)點(diǎn)
while (cur)
{
if (cur->_kv.first == key)//找到了
{
return cur;
}
cur = cur->_next;
}
//cur為空，不存在這個(gè)數(shù)據(jù)
return nullptr;
}
//插入
bool Insert(const pair<K,V>& kv)
{
//重復(fù)元素不能插入
if (Find(kv.first))
{
return false;
}
Hash hs;
//擴(kuò)容
if (_n == _table.size())
{
vector<Node*> newTable(2 * _table.size(), nullptr);//新的空間
//將舊表的節(jié)點(diǎn)移到新表中，再交換
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
size_t hashi = hs(_table[i]->_kv.first) % newTable.size();
Node* next = cur->_next;
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
//插入數(shù)據(jù)
size_t hashi = hs(kv.first) % _table.size();//表中的位置
Node* newNode = new Node(kv);//新節(jié)點(diǎn)
//頭插法
newNode->_next = _table[hashi];
_table[hashi] = newNode;
++_n;
return true;
}
//刪除
bool Erase(const K& key)
{
Hash hs;
Node* ret = Find(key);
if (ret)
{
size_t hashi = hs(ret->_kv.first) % _table.size();//先找到表的位置
Node* cur = _table[hashi];//得到該位置的頭節(jié)點(diǎn)
Node* prev = nullptr;//前面的節(jié)點(diǎn)連接
while (cur)
{
if (cur->_kv.first == key)
{
if (prev)//第一個(gè)節(jié)點(diǎn)不是要?jiǎng)h除的
{
prev->_next = cur->_next;
}
else
{
_table[hashi] = cur->_next;
}
delete cur;
break;//找到具體節(jié)點(diǎn)刪除后跳出
}
prev = cur;
cur = cur->_next;
}
return true;
}
else//找不到，刪除失敗
{
return false;
}
}
private:
vector<Node*> _table;
size_t _n = 0;
};
三、改造哈希桶
前面的哈希桶的數(shù)據(jù)類型是固定的kv模型，為了后面方便模擬實(shí)現(xiàn)unordered_set和unordered_map，將數(shù)據(jù)類型改成T，這個(gè)T可以是key，也可以是kv。到底是哪個(gè)取決于使用的是unordered_set還是unordered_map，用的是unordered_set，模板就用unordered_set的仿函數(shù)，另一個(gè)同理。
template<class T>
struct HashNode
{
HashNode<T>* _next;
T _data;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
Find的返回值修改為迭代器，Insert的返回值修改為pair< iterator, bool>
3.1 begin+end
1??begin
遍歷哈希表，一旦遇到有節(jié)點(diǎn)的位置，返回該位置的迭代器。迭代器需要傳兩個(gè)參數(shù)，該位置的頭指針和當(dāng)前哈希表（與后面實(shí)現(xiàn)迭代器類中的成員變量對(duì)應(yīng)）
iterator begin()
{
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i])
{
return iterator(_table[i], this);
}
}
return end();
}
2??end
返回的是最后一個(gè)節(jié)點(diǎn)的下一個(gè)位置，單鏈表的最后一個(gè)節(jié)點(diǎn)的下一個(gè)是空指針，所以返回迭代器，參數(shù)傳的是空指針和當(dāng)前哈希表。
iterator end()
{
return iterator(nullptr, this);
}
3.2 迭代器
雖然哈希表的結(jié)構(gòu)用的是vector，但是每個(gè)位置是單鏈表，++操作不能像數(shù)組一樣就行，所以要對(duì)每個(gè)節(jié)點(diǎn)的迭代器進(jìn)行封裝，方便++找到下一個(gè)節(jié)點(diǎn)。
注意：每個(gè)位置的桶是單鏈表，所以沒(méi)有前置- -
模板參數(shù)有KeyOfT和Hash是因?yàn)榍爸?+需要數(shù)據(jù)類型的仿函數(shù)和轉(zhuǎn)換為無(wú)符號(hào)整數(shù)的仿函數(shù)，這里先說(shuō)明一下。迭代器的成員有節(jié)點(diǎn)應(yīng)該就可以了，為什么還要哈希表類變量？因?yàn)榈葧?huì)前置++的代碼中要通過(guò)哈希函數(shù)計(jì)算節(jié)點(diǎn)數(shù)據(jù)的位置，哈希函數(shù)要有哈希表的空間大小，沒(méi)有哈希表類成員，怎么得到哈希表的空間大小。
其他的與之前一樣，不作重復(fù)敘述了
template<class K, class T, class KeyOfT, class Hash>
struct HashIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> Ht;
typedef HashIterator< K, T, KeyOfT, Hash> Self;
Node* _node;
Ht* _ht;
HashIterator(Node* node, Ht* ht)
:_node(node)
,_ht(ht)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
Self& operator++()
{
//....
}
bool operator==(const Self& s)
{
return _node == s._node;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
3.2.1 前置++
分為兩種情況：
- 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)不為空
- 當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)為空
1??情況一：
直接到下一個(gè)節(jié)點(diǎn)即可。
2??情況二：
下一個(gè)節(jié)點(diǎn)為空，先計(jì)算當(dāng)前節(jié)點(diǎn)在哈希表的位置（具體哪個(gè)桶），然后在該位置往后開(kāi)始找，只要遇到有節(jié)點(diǎn)的位置，下一個(gè)節(jié)點(diǎn)就是它；如果后面都沒(méi)有節(jié)點(diǎn)，下一個(gè)節(jié)點(diǎn)就是空。
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(kot(_node->_data)) % _ht->_table.size();
hashi++;
while (hashi < _ht->_table.size())
{
if (_ht->_table[hashi])
{
_node = _ht->_table[hashi];
break;
}
hashi++;
}
if (_ht->_table.size() == hashi)
{
_node = nullptr;
}
}
return *this;
}
3.3 改造后哈希桶與迭代器源代碼
#include <iostream>
#include <vector>
#include <string>
using namespace std;
//仿函數(shù)
template<class K>
struct HashFind
{
size_t operator()(const K& key)
{
return key;
}
};
template<>
struct HashFind<string>
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (auto& e : s)
{
hash += e;
hash *= 131;
}
return hash;
}
};
//節(jié)點(diǎn)
template<class T>
struct HashNode
{
HashNode<T>* _next;
T _data;
HashNode(const T& data)
:_data(data)
, _next(nullptr)
{}
};
//前置聲明
template<class K, class T, class KeyOfT, class Hash>
class HashTable;
//正向迭代器
template<class K, class T, class KeyOfT, class Hash>
struct HashIterator
{
typedef HashNode<T> Node;
typedef HashTable<K, T, KeyOfT, Hash> Ht;
typedef HashIterator< K, T, KeyOfT, Hash> Self;
Node* _node;
Ht* _ht;
HashIterator(Node* node, Ht* ht)
:_node(node)
,_ht(ht)
{}
T& operator*()
{
return _node->_data;
}
T* operator->()
{
return &_node->_data;
}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(kot(_node->_data)) % _ht->_table.size();
hashi++;
while (hashi < _ht->_table.size())
{
if (_ht->_table[hashi])
{
_node = _ht->_table[hashi];
break;
}
hashi++;
}
if (_ht->_table.size() == hashi)
{
_node = nullptr;
}
}
return *this;
}
bool operator==(const Self& s)
{
return _node == s._node;
}
bool operator!=(const Self& s)
{
return _node != s._node;
}
};
template<class K, class T, class KeyOfT, class Hash>
class HashTable
{
template<class K, class T, class KeyOfT, class Hash>
friend struct HashIterator;
typedef HashNode<T> Node;
public:
typedef HashIterator <K, T, KeyOfT, Hash> iterator;
//迭代器
iterator begin()
{
for (size_t i = 0; i < _table.size(); i++)
{
if (_table[i])
{
return iterator(_table[i], this);
}
}
return end();
}
iterator end()
{
return iterator(nullptr, this);
}
//構(gòu)造
HashTable(size_t n = 5)
{
_table.resize(n, nullptr);
}
//析構(gòu)
~HashTable()
{
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
delete cur;
cur = next;
}
_table[i] = nullptr;
}
}
//查找
iterator Find(const K& key)
{
Hash hs;
KeyOfT kot;
size_t hashi = hs(key) % _table.size();//表中的位置
Node* cur = _table[hashi];//得到當(dāng)前位置頭節(jié)點(diǎn)
while (cur)
{
if (kot(cur->_data) == key)//找到了
{
return iterator(cur, this);
}
cur = cur->_next;
}
//cur為空，不存在這個(gè)數(shù)據(jù)
return end();
}
//插入
pair<iterator, bool> Insert(const T& data)
{
KeyOfT kot;
//重復(fù)元素不能插入
iterator pos = Find(kot(data));
if (pos != end())
{
return make_pair(pos, false);
}
Hash hs;
//擴(kuò)容
if (_n == _table.size())
{
vector<Node*> newTable(2 * _table.size(), nullptr);//新的空間
//將舊表的節(jié)點(diǎn)移到新表中，再交換
for (size_t i = 0; i < _table.size(); i++)
{
Node* cur = _table[i];
while (cur)
{
size_t hashi = hs(kot(_table[i]->_data)) % newTable.size();
Node* next = cur->_next;
cur->_next = newTable[hashi];
newTable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newTable);
}
//插入數(shù)據(jù)
size_t hashi = hs(kot(data)) % _table.size();//表中的位置
Node* newNode = new Node(data);//新節(jié)點(diǎn)
//頭插法
newNode->_next = _table[hashi];
_table[hashi] = newNode;
++_n;
return make_pair(iterator(newNode, this), true);
}
//刪除
bool Erase(const K& key)
{
Hash hs;
KeyOfT kot;
iterator ret = Find(key);
if (ret != end())
{
size_t hashi = hs(kot(ret._node->_data)) % _table.size();//先找到表的位置
Node* cur = _table[hashi];//得到該位置的頭節(jié)點(diǎn)
Node* prev = nullptr;//前面的節(jié)點(diǎn)連接
while (cur)
{
if (kot(cur->_data) == key)
{
if (prev)//第一個(gè)節(jié)點(diǎn)不是要?jiǎng)h除的
{
prev->_next = cur->_next;
}
else
{
_table[hashi] = cur->_next;
}
delete cur;
break;//找到具體節(jié)點(diǎn)刪除后跳出
}
prev = cur;
cur = cur->_next;
}
return true;
}
else//找不到，刪除失敗
{
return false;
}
}
private:
vector<Node*> _table;
size_t _n = 0;
};
四、模擬實(shí)現(xiàn)unordered_set
unordered_set是k模型，它的仿函數(shù)就返回key。模板參數(shù)有key和Hash，Hash是用來(lái)轉(zhuǎn)換key變成無(wú)符號(hào)整數(shù)的。其他接口調(diào)用哈希桶的即可。
#include "HashTable.h"
namespace yss
{
template <class K, class Hash = HashFind<K>>
class unordered_set
{
//仿函數(shù)
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename HashTable<K, const K, SetKeyOfT, HashFind<K>>::iterator iterator;
//迭代器
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
//插入
pair<iterator, bool> Insert(const K& key)
{
return _ht.Insert(key);
}
//查找
iterator Find(const K& key)
{
return _ht.Find(key);
}
//刪除
bool Erase(const K& key)
{
return _ht.Erase(key);
}
private:
HashTable<K, const K, SetKeyOfT, Hash> _ht;
};
}
typename的作用是把HashTable<K, const K, SetKeyOfT, HashFind< K >>::iterator當(dāng)做一個(gè)類型，而不是變量。typedef就是重命名。文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-847574.html
五、模擬實(shí)現(xiàn)unordered_map
unordered_map是kv模型，仿函數(shù)傳的是kv中的key。除了查找、插入、刪除外，還有operator[]，可以進(jìn)行統(tǒng)計(jì)元素等操作文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-847574.html
#include "HashTable.h"
namespace yss
{
template <class K, class V, class Hash = HashFind<K>>
class unordered_map
{
//仿函數(shù)
struct MapKeyOfT
{
const K& operator()(const pair<K,V>& kv)
{
return kv.first;
}
};
public:
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, HashFind<K>>::iterator iterator;
//迭代器
iterator begin()
{
return _ht.begin();
}
iterator end()
{
return _ht.end();
}
//插入
pair<iterator, bool> Insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
//查找
iterator Find(const K& key)
{
return _ht.Find(key);
}
//刪除
bool Erase(const K& key)
{
return _ht.Erase(key);
}
//operator[]
V& operator[](const K& key)
{
pair<iterator, bool> ret = Insert(make_pair(key, V()));
return ret.first->second;
}
private:
HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
};
}
到了這里，關(guān)于【C++】用哈希桶模擬實(shí)現(xiàn)unordered_set和unordered_map的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![【C++入門到精通】哈希 (STL) _ unordered_map _ unordered_set [ C++入門 ]](https://imgs.yssmx.com/Uploads/2024/02/714971-1.jpeg)
