一、unordered 系列關(guān)聯(lián)式容器
在 C++98 中，STL 提供了底層為紅黑樹結(jié)構(gòu)的一些列關(guān)聯(lián)式容器，在查詢時(shí)效率可以達(dá)到 O ( l o g 2 N ) O(log2^N) O(log2N)，即最差情況下需要比較紅黑樹高度次，當(dāng)樹中的結(jié)點(diǎn)非常多的時(shí)候，查詢效率也不理想。最好的查詢是，進(jìn)行很少的比較次數(shù)就能夠?qū)⒃卣业?，因此?C++11 中，STL 又提供了4個(gè) unordered 系列的關(guān)聯(lián)式容器，這四個(gè)容器與紅黑樹結(jié)構(gòu)的關(guān)聯(lián)式容器使用方法基本類似，只是其底層結(jié)構(gòu)不同，本文中只對(duì) unordered_map 和 unordered_set 進(jìn)行介紹，unordered_multimap 和 unordered_multiset 感興趣的小伙伴可以自行查閱文檔。
二、unordered_map
1.1 unordered_map 介紹
-
unordered_map 是存儲(chǔ) <key，value> 鍵值對(duì)的關(guān)聯(lián)式容器，其允許通過(guò) key 快速的索引到與其對(duì)應(yīng)的 value。
-
在 unordered_map 中，鍵值通常用于唯一的標(biāo)識(shí)元素，而映射值是一個(gè)對(duì)象，其內(nèi)容與此鍵值關(guān)聯(lián)。鍵和映射值的類型可能不同。
-
在內(nèi)部，unordered_map 沒(méi)有對(duì) <key，value> 按照任何特定的順序排序，為了能在常數(shù)范圍內(nèi)找到 key 所對(duì)應(yīng)的 value，unordered_map 將相同哈希值的鍵值放在相同的桶中。
-
unordered_map 容器通過(guò) key 訪問(wèn)單個(gè)元素要比 map 快，但它通常在遍歷元素子集的范圍迭代方面效率較低。
-
unordered_map 實(shí)現(xiàn)了直接訪問(wèn)操作符（operator[ ]），它允許使用 key 作為參數(shù)直接訪問(wèn) value。
-
它的迭代器至少是前向迭代器（單向迭代器）。
1.2 unordered_map 的接口說(shuō)明
1.2.1 unordered_map 的構(gòu)造
| 函數(shù)聲明 | 功能介紹 |
|---|---|
| unordered_map | 構(gòu)造不同格式的 unordered_map 對(duì)象 |
1.2.2 unordered_map 的容量
| 函數(shù)聲明 | 功能介紹 |
|---|---|
| bool empty() const | 檢測(cè) unordered_map 是否為空 |
| size_t size() const | 獲取 unordered_map 有效元素的個(gè)數(shù) |
1.2.3 unordered_map 的迭代器
| 函數(shù)聲明 | 功能介紹 |
|---|---|
| begin() | 返回 unordered_map 第一個(gè)元素的迭代器 |
| end() | 返回 unordered_map 最后一個(gè)元素下一個(gè)位置的迭代器 |
| cbegin() | 返回 unordered_map 第一個(gè)元素的 const 迭代器 |
| cend() | 返回 unordered_map 最后一個(gè)元素下一個(gè)位置的 const 迭代器 |
1.2.4 unordered_map 的元素訪問(wèn)
| 函數(shù)聲明 | 功能介紹 |
|---|---|
| operator[ ] | 返回與 key 對(duì)應(yīng)的 value，沒(méi)有一個(gè)默認(rèn)值 |
小Tips：該函數(shù)中實(shí)際調(diào)用哈希桶的插入操作，用參數(shù) key 與 V() 構(gòu)造一個(gè)默認(rèn)值往底層哈希桶中插入，如果 key 不在哈希桶中，插入成功，返回 V()。插入失敗，說(shuō)明 key 已經(jīng)在哈希桶中，將 key 對(duì)應(yīng)的 value 返回。
1.2.5 unordered_map 的查詢
| 函數(shù)聲明 | 功能介紹 |
|---|---|
| iterator find(const K& key) | 返回 key 在哈希桶中的位置 |
| size_t count(const K& key) | 返回哈希桶中關(guān)鍵碼為 key 的鍵值對(duì)的個(gè)數(shù) |
小Tips：unordered_map 中 key 是不能重復(fù)的，因此 count 函數(shù)的返回值最大為1。
1.2.6 unordered_map 的修改操作
| 函數(shù)聲明 | 功能介紹 |
|---|---|
| insert | 向容器中插入鍵值對(duì) |
| erase | 刪除容器中的鍵值對(duì) |
| void clear() | 清空容器中有效元素個(gè)數(shù) |
| void swap(unordered_map& ump) | 交換兩個(gè)容器中的元素 |
1.2.7 unordered_map 的桶操作
| 函數(shù)聲明 | 功能介紹 |
|---|---|
| size_t bucket_count() const | 返回哈希桶中桶的總個(gè)數(shù) |
| size_t bucket_size(size_t n) const | 返回 n 號(hào)桶中有效元素的總個(gè)數(shù) |
| size_t bucket(const K& key) | 返回元素 key 所在的桶號(hào) |
三、底層結(jié)構(gòu)
unordered 系列的關(guān)聯(lián)式容器之所以效率比較高，是因?yàn)槠涞讓邮褂昧斯＝Y(jié)構(gòu)。
3.1 哈希概念
順序結(jié)構(gòu)以及平衡樹中，元素關(guān)鍵碼與其存儲(chǔ)位置之間沒(méi)有對(duì)應(yīng)的關(guān)系，因此在查找一個(gè)元素時(shí)，必須要經(jīng)過(guò)關(guān)鍵碼的多次比較。順序查找時(shí)間復(fù)雜度為 O ( N ) O(N) O(N)，平衡樹中為樹的高度，即 O ( l o g 2 N ) O(log2^N) O(log2N)，搜索的效率取決于搜索過(guò)程中關(guān)鍵碼的比較次數(shù)。
理想的搜索方法：可以在不經(jīng)過(guò)任何比較，一次直接從表中得到要搜索的元素。如果構(gòu)造一種存儲(chǔ)結(jié)構(gòu)，通過(guò)某種函數(shù)（hashFunc）使元素的存儲(chǔ)位置與它的關(guān)鍵碼之間能夠建立一一映射的關(guān)系，那么在查找時(shí)通過(guò)該函數(shù)可以很快找到該元素。在結(jié)構(gòu)中：
-
插入元素：根據(jù)待插入元素的關(guān)鍵碼，以此函數(shù)計(jì)算出該元素的存儲(chǔ)位置并按此位置進(jìn)行存放。
-
搜索元素：對(duì)元素的關(guān)鍵碼進(jìn)行相同的計(jì)算，把求得的函數(shù)值當(dāng)做元素的存儲(chǔ)位置，在結(jié)構(gòu)中按此位置取元素比較，若關(guān)鍵碼相等，則搜素成功。
該方式即為哈希（散列）方法，哈希方法中使用的轉(zhuǎn)換函數(shù)稱為哈希（散列）函數(shù)，構(gòu)造出來(lái)的結(jié)構(gòu)稱為哈希表（Hash Table）（或者散列表）
小Tips：用該方法進(jìn)行搜索不必進(jìn)行多次關(guān)鍵碼的比較，因此搜索的速度比較快。但是也會(huì)出現(xiàn)問(wèn)題，以上圖為例，再向集合中插入44，計(jì)算出來(lái)的哈希函數(shù)值是4，但是下標(biāo)為4的位置已經(jīng)存儲(chǔ)的有值了。
3.2 哈希沖突
對(duì)于兩個(gè)數(shù)據(jù)元素的關(guān)鍵字 k_i 和 k_j （i != j），有 k_i != k_j，但有：Hash(k_i) == Hash(k_j)，即：不同的關(guān)鍵字通過(guò)相同的哈希函數(shù)計(jì)算出相同的哈希值，該種現(xiàn)象稱為哈希沖突或哈希碰撞。把具有不同關(guān)鍵碼而具有相同哈希地址的數(shù)據(jù)元素稱為“同義詞”。
3.3 哈希函數(shù)
引起哈希沖突的一個(gè)原因可能是：哈希函數(shù)設(shè)計(jì)不夠合理。設(shè)計(jì)哈希函數(shù)應(yīng)該遵循以下原則：
-
哈希函數(shù)的定義域必須包括需要存儲(chǔ)的全部關(guān)鍵碼，而如果散列表允許有 m 個(gè)地址時(shí)，其值域必須在 0~m-1 之間。
-
哈希函數(shù)計(jì)算出來(lái)的地址能均勻分布在整個(gè)空間中。
-
哈希函數(shù)應(yīng)該比較簡(jiǎn)單。
下面給大家列舉一些常見(jiàn)的哈希函數(shù)。
3.3.1 直接定值法----(常用)
取關(guān)鍵字的某個(gè)線性函數(shù)為散列地址：
H
a
s
h
(
K
e
y
)
=
A
?
K
e
y
+
B
Hash(Key) = A*Key +B
Hash(Key)=A?Key+B
小Tips：此方法的優(yōu)點(diǎn)是簡(jiǎn)單、均勻。但是需要事先知道關(guān)鍵字的分布情況。適合查找比較小且連續(xù)的情況。
3.3.2 除留余數(shù)法----(常用)
設(shè)散列表中允許的地址數(shù)為 m，取一個(gè)不大于 m，但最接近或者等于 m 的質(zhì)數(shù) p 作為除數(shù)，按照哈希函數(shù)：
H
a
s
h
(
K
e
y
)
=
K
e
y
%
p
(
p
<
=
m
)
Hash(Key) = Key \% p(p <= m)
Hash(Key)=Key%p(p<=m)
3.3.3 平方取中法----(了解)
假設(shè)關(guān)鍵字為1234，對(duì)它平方就是1522756，抽取中間的3位227作為哈希地址；再比如關(guān)鍵字為4321，對(duì)它的平方就是18671041，抽取中間的3位671（或710）作為哈希地址。平方取中法適合于不知道關(guān)鍵字的分布，而位數(shù)又不是很大的情況。
3.3.4 折疊法----(了解）
折疊法是將關(guān)鍵字從左到右分割成位數(shù)相等的幾部分（最后一部分位數(shù)可以短一些），然后將這幾部分疊加求和，并按散列表表長(zhǎng)，取后幾位作為散列地址。
3.3.5 隨機(jī)數(shù)法----(了解)
選擇一個(gè)隨機(jī)數(shù)，取關(guān)鍵字的隨機(jī)函數(shù)值為它的哈希地址，即：
H
a
s
h
(
K
e
y
)
=
r
a
n
d
o
m
(
k
e
y
)
Hash(Key) = random(key)
Hash(Key)=random(key)
小Tips：其中 random 為隨機(jī)數(shù)函數(shù)。
3.3.6 數(shù)學(xué)分析法----(了解)
設(shè)有 n 個(gè)d 位數(shù)，每一位可能有 r 種不同的符號(hào)在各個(gè)位上出現(xiàn)的頻率不一定相同，可能在某些位上分布比較均勻，每種符號(hào)出現(xiàn)的機(jī)會(huì)均等，在某些位上分布不均勻只有幾種符號(hào)經(jīng)常出現(xiàn)?？筛鶕?jù)散列表的大小，選擇其中各種符號(hào)分布均勻的若干位作為散列地址。例如：
假設(shè)要存儲(chǔ)某家公司員工登記表，如果用手機(jī)號(hào)作為關(guān)鍵字，那么極有可能前7位都是 相同的，那么我們可以選擇后面的四位作為散列地址，如果這樣的抽取工作還容易出現(xiàn) 沖突，還可以對(duì)抽取出來(lái)的數(shù)字進(jìn)行反轉(zhuǎn)(如1234改成4321)、右環(huán)位移(如1234改成4123)、左環(huán)移位、前兩數(shù)與后兩數(shù)疊加(如1234改成12+34=46)等方法。
小Tips：數(shù)學(xué)分析法通常適合處理關(guān)鍵字位數(shù)比較大的情況，如果事先知道關(guān)鍵字的分布且關(guān)鍵字的若干位分布較均勻的情況。
注意：哈希函數(shù)設(shè)計(jì)的越精妙，產(chǎn)生哈希沖突的可能性就越低，但是無(wú)法避免哈希沖突。
3.4 哈希沖突解決
解決哈希沖突的兩種常見(jiàn)方法是：閉散列和開散列。
3.4.1 閉散列
閉散列也叫開放定址法，當(dāng)發(fā)生哈希沖突時(shí)，如果哈希表未被填滿，說(shuō)明在哈希函數(shù)表中必然還有空位置，那么可以把 Key 對(duì)應(yīng)的元素存放到?jīng)_突位置中的下一個(gè)空位置中去。那如何尋找下一個(gè)空位置呢？
3.4.1.1 線性探測(cè)
從發(fā)生沖突的位置開始，依次向后探測(cè)，直到尋找到下一個(gè)空位置為止。
插入：
-
通過(guò)哈希函數(shù)獲取待插入元素在哈希表中的位置。
-
如果該位置中沒(méi)有元素則直接插入新元素，如果該位置中有元素發(fā)生哈希沖突，使用線性探測(cè)找到下一個(gè)空位置，插入新元素。
查找：
-
通過(guò)哈希函數(shù)獲取待查找元素在哈希表中的位置。
-
看該位置的值是否是我們要查找的值，如果不是，從當(dāng)前位置依次往后進(jìn)行比較，找到就結(jié)束，如果遇到空還沒(méi)有找到，說(shuō)明當(dāng)前待查找的元素不在哈希表中。
小Tips：這里簡(jiǎn)介反映出哈希表中的元素不能太滿了，如果太滿，那么它的查找效率有可能就變成了 O ( N ) O(N) O(N)。
刪除：采用閉散列處理哈希沖突時(shí)，不能隨便物理刪除哈希表中已有的元素，若直接刪除元素會(huì)影響其它元素的搜索。比如上圖中，刪除元素24，如果直接刪掉，54查找起來(lái)可能會(huì)受影響。因此線性探測(cè)采用標(biāo)記的偽刪除法來(lái)刪除一個(gè)元素。
擴(kuò)容：散列表的載荷因子定義為：
α
=
填
入
表
中
的
元
素
個(gè)
數(shù)
/
散
列
表
的
長(zhǎng)
度
α = 填入表中的元素個(gè)數(shù) / 散列表的長(zhǎng)度
α=填入表中的元素個(gè)數(shù)/散列表的長(zhǎng)度
α α α 是散列表裝滿成都的標(biāo)志因子。由于表長(zhǎng)是定值， α α α 與“填入表中的元素個(gè)數(shù)”成正比，所以， α α α 越大，表明填入表中的元素越多，產(chǎn)生沖突的可能性就越大，但是空間利用率越高；反之， α α α 越小，表明填入表中的元素越少，產(chǎn)生沖突的可能性就越小，但是空間浪費(fèi)會(huì)比較多。實(shí)際上，散列表的平均查找長(zhǎng)度是載荷因子 α α α 的函數(shù)，只是不同處理沖突的方式有不同的函數(shù)。
對(duì)于閉散列（開放定址法），載荷因子是特別重要的因素，應(yīng)嚴(yán)格限制在 0.7 ? 0.8 0.7-0.8 0.7?0.8以下。超過(guò) 0.8 0.8 0.8，查表時(shí)的 CPU 緩存不命中按照指數(shù)曲線上升。因此，一些曹勇開放定址法的 hash 庫(kù)，如 Java 的系統(tǒng)庫(kù)限制了載荷因子為 0.75，超過(guò)此值將 resize 散列表。
小Tips：擴(kuò)容后，元素的映射關(guān)系會(huì)發(fā)生變化，所以我們需要重新建立映射，即重新計(jì)算元素對(duì)應(yīng)的存儲(chǔ)位置。原來(lái)沖突的，現(xiàn)在不一定沖突了，原來(lái)不沖突的，現(xiàn)在可能沖突了，因此擴(kuò)容后需要對(duì)原來(lái)表中的元素重新走一遍插入邏輯。
3.4.1.2 閉散列（開放定址法）模擬實(shí)現(xiàn)
enum STATE
{
EXIST,
EMPTY,
DELETE
};
//存儲(chǔ)元素的結(jié)點(diǎn)
template<class K, class V>
struct HashData
{
pair<K, V> _kv;
STATE _state = EMPTY;
};
//哈希表
template<class K, class V>
class HashTable
{
public:
HashTable()
{
_table.resize(10);
}
bool Insert(const pair<K, V>& kv)
{
//檢查負(fù)載因子，擴(kuò)容
/*if ((double)_n / _table.size() >= 0.7)
{
}*/
if (_n * 10 / _table.size() >= 7)
{
size_t newsize = _table.size() * 2;
//重新建立映射關(guān)系
//vector<HashData<K, V>> tmp;
//tmp.resize(newsize);
//for (const auto& e : _table)
//{
// if (e._state == EXIST)
// {
// size_t hashi = e._kv.first % tmp.size();
// while (tmp[hashi]._state == EXIST)
// {
// ++hashi;
// //當(dāng)hashi == size 的時(shí)候要讓它從 0 開始繼續(xù)找。
// /*if (hashi >= _table.size())
// {
// hashi = 0;
// }*/
// hashi %= _table.size();
// }
// tmp[hashi] = e;
// }
//
//}
//std::swap(tmp, _table);
HashTable<K, V> newHT;
newHT._table.resize(newsize);
//遍歷舊表的數(shù)據(jù)插入到新表即可
for (size_t i = 0; i < _table.size(); ++i)
{
if (_table[i]._state == EXIST)
{
newHT.Insert(_table[i]._kv);
}
}
_table.swap(newHT._table);
}
//線性探測(cè)
size_t hashi = kv.first % _table.size();//注意這里
//如果下標(biāo)為hashi的地方?jīng)]有存元素，那么就可以直接在hashi進(jìn)行插入
//如果下標(biāo)為hashi的地方存的有元素，就需要進(jìn)行線性探測(cè)
//EMPTY、DELETE都可存儲(chǔ)元素
while (_table[hashi]._state == EXIST)
{
++hashi;
//當(dāng)hashi == size 的時(shí)候要讓它從 0 開始繼續(xù)找。
/*if (hashi >= _table.size())
{
hashi = 0;
}*/
hashi %= _table.size();
}
//注意方括號(hào)訪問(wèn)，底層會(huì)去斷言，下標(biāo)必須小于size，所以上面模的是size。
_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
++_n;
return true;
}
HashData<const K, V>* Find(const K& key)
{
//線性探測(cè)
size_t hashi = key % _table.size();//注意這里
//如果下標(biāo)為hashi的地方?jīng)]有存元素，那么就可以直接在hashi進(jìn)行插入
//如果下標(biāo)為hashi的地方存的有元素，就需要進(jìn)行線性探測(cè)
//EMPTY、DELETE都可存儲(chǔ)元素
while (_table[hashi]._state != EMPTY)
{
if (_table[hashi]._state == EXIST && _table[hashi]._kv.first == key)
{
return (HashData<const K, V>*)&_table[hashi];//這里會(huì)涉及類型轉(zhuǎn)化，有的編譯器可能不支持，所以這里最好自己強(qiáng)轉(zhuǎn)一下
}
++hashi;
hashi %= _table.size();
}
return nullptr;
}
bool Erase(const K& key)
{
HashData<const K, V>* ret = Find(key);
if (ret)
{
ret->_state = DELETE;
--_n;
return true;
}
return false;
}
private:
vector<HashData<K, V>> _table;
size_t _n = 0;//因?yàn)閿?shù)據(jù)是分散存儲(chǔ)的，所以不能用vector中的size去計(jì)算哈希表中元素的數(shù)量，這個(gè)_n存儲(chǔ)的就是哈希表中有效數(shù)據(jù)的個(gè)數(shù)
};
小Tips：線性探測(cè)的優(yōu)點(diǎn)是：實(shí)現(xiàn)起來(lái)非常簡(jiǎn)單。缺點(diǎn)是：一旦發(fā)生哈希沖突，所有的沖突連在一起，容易產(chǎn)生數(shù)據(jù)“堆積”，即：不同關(guān)鍵碼占據(jù)了可利用的空位置，使得尋找某關(guān)鍵碼的位置需要許多次比較，導(dǎo)致搜索效率降低?？梢岳孟旅娴亩翁綔y(cè)來(lái)解決該問(wèn)題。
3.4.1.3 二次探測(cè)
線性探測(cè)的缺陷是產(chǎn)生沖突的數(shù)據(jù)堆積在一塊，這與其找下一個(gè)空位置有關(guān)，因?yàn)檎铱瘴恢玫姆绞骄褪前ぶ笾饌€(gè)去找，因此二次探測(cè)為了避免該問(wèn)題，找下一個(gè)空位置的方法為： H i H_i Hi? = ( H 0 H_0 H0? + i 2 i^2 i2 )% m 或者： H i H_i Hi? = ( H 0 H_0 H0? - i 2 i^2 i2 )% m。其中：i = 1,2,3…， H 0 H_0 H0?是通過(guò)散列函數(shù) Hash(x) 對(duì)元素的關(guān)鍵碼 key 進(jìn)行計(jì)算得到的位置，m是表的大小。
研究表明：當(dāng)表的長(zhǎng)度為質(zhì)數(shù)且表裝載因子 α α α 不超過(guò) 0.5 時(shí)，新的表項(xiàng)一定能夠插入，而且任何一個(gè)位置都不會(huì)被探查兩次。因此只要表中有一半的空位置，就不會(huì)存在表滿的問(wèn)題。在搜索時(shí)可以不考慮表滿的情況，但在插入時(shí)必須確保表的裝載因子 α α α 不超過(guò) 0.5，如果超出，必須考慮增容。因此，閉散列最大的缺陷局勢(shì)空間利用率比較低，這也是哈希的缺陷。
3.4.2 開散列
開散列又叫拉鏈法，首先對(duì)關(guān)鍵碼集合用散列函數(shù)計(jì)算散列地址，具有相同地址的關(guān)鍵碼歸于同一子集合，每一個(gè)子集合稱為一個(gè)桶，各個(gè)桶中的元素通過(guò)一個(gè)單鏈表鏈接起來(lái)，各鏈表的頭結(jié)點(diǎn)存儲(chǔ)在哈希表中。
小Tips：從上圖中可以看出，開散列中每個(gè)桶中放的都是發(fā)生哈希沖突的元素。
3.4.2.1 開散列模擬實(shí)現(xiàn)
template<class K, class V>
struct HashNode
{
pair<K, V> _kv;
HashNode<K, V>* _next;
HashNode(const pair<K, V>& kv = pair<K, V>())
:_kv(kv)
,_next(nullptr)
{}
};
template<class K, class V, class HashFunc = DefaultHasFunc<K>>
class HashTable
{
typedef HashNode<K, V> Node;
private:
void swap(HashTable<K, V, HashFunc>& hbt)
{
std::swap(hbt._table, this->_table);
std::swap(hbt._n, this->_n);
}
public:
HashTable(size_t size = 10)
{
_table.resize(size, nullptr);
}
//拷貝構(gòu)造
HashTable(const HashTable<K, V, HashFunc>& htb)
{
_table.resize(htb._table.size());
for (size_t i = 0; i < htb._table.size(); ++i)
{
Node* cur = htb._table[i];
while (cur)
{
Insert(cur->_kv);
cur = cur->_next;
}
}
/* HashTable<K, V, HashFunc> tmp;
tmp._table = htb._table;//這里現(xiàn)代寫法行不通，因?yàn)開table里面存的是指針，屬于內(nèi)置類型，進(jìn)行的是淺拷貝。
tmp._n = htb._n;
swap(tmp);*/
}
bool Insert(const pair<K, V>& kv)
{
//HashFunc hf;
//先檢查哈希桶中是否有這個(gè)元素，有就不能插入
if (Find(kv.first))
{
return false;
}
//不擴(kuò)容，不斷插入，某些桶會(huì)越來(lái)越長(zhǎng)，效率得不到保證
//因此還是需要進(jìn)行適當(dāng)?shù)臄U(kuò)容
//這里一般把負(fù)載因子控制在1
//這樣，在理想狀態(tài)下，平均每個(gè)桶一個(gè)數(shù)據(jù)
if (_n == _table.size())
{
//擴(kuò)容 方法一：會(huì)去創(chuàng)建新節(jié)點(diǎn)，然后還要把舊結(jié)點(diǎn)釋放，效率低下
/*HashTable<K, V, HashFunc> newTable(_table.size() * 2);
for (size_t i = 0; i < _table.size(); ++i)
{
if (_table[i] != nullptr)
{
Node* cur = _table[i];
while (cur)
{
newTable.Insert(cur->_kv);
cur = cur->_next;
}
}
}
_table.swap(newTable._table);*/
//擴(kuò)容 方法二：
vector<Node*> newtable;
newtable.resize(_table.size() * 2, nullptr);
for (size_t i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = hf(cur->_kv.first) % newtable.size();
cur->_next = newtable[hashi];
newtable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newtable);
}
size_t hashi = hf(kv.first) % _table.size();
//檢查當(dāng)前桶里面是否已經(jīng)有該元素
Node* cur = _table[hashi];
while (cur)
{
if (cur->_kv.first == kv.first)
{
return false;
}
cur = cur->_next;
}
//到這里說(shuō)明當(dāng)前桶里沒(méi)有該元素，可以插入
Node* newnode = new Node(kv);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return true;
}
//打印哈希桶
void Print()
{
for (size_t i = 0; i < _table.size(); ++i)
{
printf("Hash[%d]:", i);
Node* cur = _table[i];
while (cur)
{
cout << cur->_kv.first << ':' << cur->_kv.second << "--->";
cur = cur->_next;
}
cout << "nullptr" << endl;
}
}
//查找
Node* Find(const K& key)
{
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
while (cur)
{
if (cur->_kv.first == key)
{
return cur;
}
cur = cur->_next;
}
return nullptr;
}
//刪除
bool erase(const K& key)
{
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
Node* prev = nullptr;
while (cur)
{
if (cur->_kv.first == key)
{
if (prev == nullptr)
{
_table[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
cur = nullptr;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
~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;
}
}
private:
vector<Node*> _table;//指針數(shù)組
//這里的_table屬于自定義類型，如果我們不寫析構(gòu)函數(shù)，編譯器會(huì)去調(diào)用vector自己的析構(gòu)函數(shù)
//對(duì)于vector的析構(gòu)函數(shù)來(lái)說(shuō)，Node* 是一個(gè)指針，屬于內(nèi)置類型
//因此vector的析構(gòu)函數(shù)不會(huì)對(duì) Node* 做任何處理
//因此這里我們需要自己寫析構(gòu)函數(shù)，去釋放哈希桶中的結(jié)點(diǎn)
size_t _n = 0;//記錄存儲(chǔ)的有效數(shù)據(jù)個(gè)數(shù)
HashFunc hf;
};
四、模擬實(shí)現(xiàn) unordered_set 和 unordered_map
4.1 哈希表的改造
這里我們使用開散列的方法來(lái)實(shí)現(xiàn) unordered_set 和 unordered_map。
4.1.1 模板參數(shù)列表的改造
//哈希表
template<class K, class T, class KeyOfT, class HashFunc = DefaultHasFunc<K>>//K的作用是為了方便查找和刪除
class HashTable
小Tips：
-
K：關(guān)鍵碼類型。
-
T：不同容器 T 的類型不同，如果是
unordered_map，T 代表一個(gè)鍵值對(duì)，如果是unordered_set，V 為 K。 -
KeyOfT：因?yàn)?T 的類型不同，通過(guò) value 取 key 的方式就不同，詳細(xì)代碼參考下面
unordered_set/map的實(shí)現(xiàn)。 -
HashFunc：哈希函數(shù)仿函數(shù)對(duì)象類型，哈希函數(shù)使用除留余數(shù)法，需要將 key 轉(zhuǎn)換為整形數(shù)字才能取模。
4.1.2 增加迭代器操作
//HashTable.h
//哈希桶的迭代器
template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
struct HTIterator
{
typedef HashNode<T> Node;
typedef HTIterator<K, T, Ptr, Ref, KeyOfT, HashFunc> Self;
typedef HashTable<K, T, KeyOfT, HashFunc> Ht;
typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
Node* _node;
const Ht* _pht;
HTIterator(Node* node = nullptr, const Ht* pht = nullptr)
:_node(node)
,_pht(pht)
{}
HTIterator(const iterator& it)//如果是普通迭代器，這里就是拷貝構(gòu)造函數(shù)
:_node(it._node) //如果是 const 迭代器，這里就是用一個(gè)普通迭代器來(lái)構(gòu)造一個(gè) const 迭代器。
, _pht(it._pht)
{}
Self& operator++()
{
if (_node->_next)
{
_node = _node->_next;
}
else
{
//如果_node->_next == nullptr
//說(shuō)明要到下一個(gè)桶去，因此迭代器類里面需要一個(gè)哈希表的指針，指向當(dāng)前迭代器維護(hù)的哈希表
//這樣才能找到下一個(gè)桶
//先找到我當(dāng)前在那個(gè)桶
KeyOfT kot;
HashFunc hf;
size_t hashi = hf(kot(_node->_data)) % _pht->_table.size();
//從下一個(gè)位置開始查找下一個(gè)不為空的桶
++hashi;
while (hashi < _pht->_table.size())
{
if (_pht->_table[hashi])
{
_node = _pht->_table[hashi];
return *this;
}
else
{
++hashi;
}
}
_node = nullptr;
}
return *this;
}
bool operator != (const Self& s) const
{
return _node != s._node;
}
Ref operator*() const
{
return _node->_data;
}
Ptr operator->() const
{
return &(_node->_data);
}
};
小Tips：因?yàn)楣１肀举|(zhì)上是由一個(gè)個(gè)哈希桶組成，迭代器走完當(dāng)前桶，需要跳到下一個(gè)桶，迭代器要能指向下一個(gè)哈希桶，最簡(jiǎn)單的做法就是在迭代器里面存一份哈希表。實(shí)際代碼中我們?cè)诘髦性黾恿艘粋€(gè)哈希表類型的指針，指向當(dāng)前迭代器維護(hù)的哈希表，又因?yàn)樵撝羔槙?huì)去訪問(wèn)哈希表里面的成員變量數(shù)組，所以該迭代器類必須是哈希表的友元類，關(guān)于友元類的具體聲明參考下面修改后的哈希表。這里還有一個(gè)問(wèn)題，迭代器里面使用了哈希表類型，哈希表里面又實(shí)用的迭代器類型，這里就會(huì)涉及到誰(shuí)先誰(shuí)后的問(wèn)題，我這里的解決方法是將迭代器類定義在哈希表的前面，然后在迭代器的前面對(duì)哈希表的類做一個(gè)前置聲明。其次，因?yàn)楣Ｍ霸诘讓邮菃捂湵斫Y(jié)構(gòu)，所以哈希桶的迭代器不需要 - - 操作。
4.1.3 修改后的哈希表
//HashTable.h
//哈希表
template<class K, class T, class KeyOfT, class HashFunc = DefaultHasFunc<K>>//K的作用是為了方便查找和刪除
class HashTable
{
//模板的友元
template<class K, class T, class Ptr, class Ref, class KeyOfT, class HashFunc>
friend struct HTIterator;
typedef HashNode<T> Node;
private:
void swap(HashTable<K, T, HashFunc>& hbt)
{
std::swap(hbt._table, this->_table);
std::swap(hbt._n, this->_n);
}
public:
typedef HTIterator<K, T, T*, T&, KeyOfT, HashFunc> iterator;
typedef HTIterator<K, T, const T*, const T&, KeyOfT, HashFunc> const_iterator;
iterator begin()
{
//找第一個(gè)桶
for (size_t i = 0; i < _table.size(); ++i)
{
if (_table[i])
{
return iterator(_table[i], this);
}
}
return iterator(nullptr, this);
}
iterator end()
{
return iterator(nullptr, this);
}
const_iterator begin() const
{
//找第一個(gè)桶
for (size_t i = 0; i < _table.size(); ++i)
{
if (_table[i])
{
return const_iterator(_table[i], this);
}
}
return const_iterator(nullptr, this);
}
const_iterator end() const
{
return const_iterator(nullptr, this);
}
HashTable(size_t size = 10)
{
_table.resize(size, nullptr);
}
//拷貝構(gòu)造
HashTable(const HashTable<K, T, HashFunc>& htb)
{
_table.resize(htb._table.size());
for (size_t i = 0; i < htb._table.size(); ++i)
{
Node* cur = htb._table[i];
while (cur)
{
Insert(cur->_data);
cur = cur->_next;
}
}
/* HashTable<K, T, HashFunc> tmp;
tmp._table = htb._table;//這里現(xiàn)代寫法行不通，因?yàn)開table里面存的是指針，屬于內(nèi)置類型，進(jìn)行的是淺拷貝。
tmp._n = htb._n;
swap(tmp);*/
}
pair<iterator, bool> Insert(const T& data)
{
HashFunc hf;
KeyOfT kt;
//HashFunc hf;
//先檢查哈希桶中是否有這個(gè)元素，有就不能插入
if (Find(kt(data)) != end())
{
return make_pair(Find(kt(data)), false);
}
//擴(kuò)容
if (_n == _table.size())
{
vector<Node*> newtable;
newtable.resize(_table.size() * 2, nullptr);
for (size_t i = 0; i < _table.size(); ++i)
{
Node* cur = _table[i];
while (cur)
{
Node* next = cur->_next;
size_t hashi = hf(kt(cur->_data)) % newtable.size();
cur->_next = newtable[hashi];
newtable[hashi] = cur;
cur = next;
}
_table[i] = nullptr;
}
_table.swap(newtable);
}
size_t hashi = hf(kt(data)) % _table.size();
//到這里說(shuō)明當(dāng)前桶里沒(méi)有該元素，可以插入
Node* newnode = new Node(data);
newnode->_next = _table[hashi];
_table[hashi] = newnode;
++_n;
return make_pair(iterator(newnode, this), true);
}
//查找
iterator Find(const K& key)const
{
HashFunc hf;
KeyOfT kt;
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
while (cur)
{
if (kt(cur->_data) == key)
{
return iterator(cur, this);
}
cur = cur->_next;
}
return iterator(nullptr, this);
}
//刪除
bool erase(const K& key)
{
HashFunc hf;
KeyOfT kt;
size_t hashi = hf(key) % _table.size();
Node* cur = _table[hashi];
Node* prev = nullptr;
while (cur)
{
if (kt(cur->_data) == key)
{
if (prev == nullptr)
{
_table[hashi] = cur->_next;
}
else
{
prev->_next = cur->_next;
}
delete cur;
cur = nullptr;
--_n;
return true;
}
prev = cur;
cur = cur->_next;
}
return false;
}
~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;
}
}
private:
vector<Node*> _table;//指針數(shù)組
//這里的_table屬于自定義類型，如果我們不寫析構(gòu)函數(shù)，編譯器會(huì)去調(diào)用vector自己的析構(gòu)函數(shù)
//對(duì)于vector的析構(gòu)函數(shù)來(lái)說(shuō)，Node* 是一個(gè)指針，屬于內(nèi)置類型
//因此vector的析構(gòu)函數(shù)不會(huì)對(duì) Node* 做任何處理
//因此這里我們需要自己寫析構(gòu)函數(shù)，去釋放哈希桶中的結(jié)點(diǎn)
size_t _n = 0;//記錄存儲(chǔ)的有效數(shù)據(jù)個(gè)數(shù)
};
小Tips：哈希表的修改主要體現(xiàn)在增加通過(guò) key 獲取 value 的操作。
4.2 unordered_set 模擬實(shí)現(xiàn)
//unorderedset.h
#include "HashTable.h"
template<class K, class HashFunc = DefaultHasFunc<K>>
class unordered_set
{
private:
struct SetKeyOfT
{
const K& operator()(const K& key)
{
return key;
}
};
public:
typedef typename HashTable<K, K, SetKeyOfT, HashFunc>::const_iterator iterator;
typedef typename HashTable<K, K, SetKeyOfT, HashFunc>::const_iterator const_iterator;
iterator begin() const
{
return _ht.begin();
}
iterator end() const
{
return _ht.end();
}
pair<iterator, bool> insert(const K& key)
{
/*pair<typename HashTable<K, K, SetKeyOfT, HashFunc>::iterator, bool> ret = _ht.Insert(key);
return make_pair(iterator(ret.first._node, ret.first._pht), ret.second);*/
return _ht.Insert(key);//這種寫法如果編譯器檢查的嚴(yán)格可能過(guò)不了
//上面兩種插入方法都可以，這一塊是精華，好好品味
}
K& operator[](const K& key)
{
pair<typename HashTable<K, K, SetKeyOfT, HashFunc>::iterator, bool> ret = _ht.Insert(key);
return *(ret.first);
}
private:
HashTable<K, K, SetKeyOfT, HashFunc> _ht;
};
小Tips：unordered_set 是一種 key 結(jié)構(gòu)，所以它的普通迭代器和 const 迭代器都是不允許被修改的。因此 unordered_set 中的普通迭代器本質(zhì)上還是 HashTable 中的 const 迭代器。此時(shí)就會(huì)出現(xiàn)一個(gè)問(wèn)題，插入調(diào)用的是 HashTable 中的 Insert，其返回值是一個(gè) pair，其中 first 是一個(gè)普通迭代器，而在 unordered_set 這一層，insert 的返回值也是一個(gè) pair，它的 first 看起來(lái)是一個(gè)普通迭代器，但本質(zhì)上是用 HashTable 中的 const 迭代器進(jìn)行封裝的，因此這里涉及到從普通迭代器轉(zhuǎn)換成 const 迭代器，隨然普通迭代器和 const 迭代器共用同一個(gè)類模板，但是它們的模板參數(shù)不同，所以普通迭代器和 const 迭代器本質(zhì)上屬于兩種不同類型。因此要將一個(gè)普通迭代器轉(zhuǎn)化成 const 迭代器本質(zhì)上涉及類型轉(zhuǎn)換。要用一個(gè) A 類型的對(duì)象去創(chuàng)建一個(gè) B 類型的對(duì)象 ，可以在 A 類里面增加一個(gè)構(gòu)造函數(shù)，該構(gòu)造函數(shù)的參數(shù)是 B 類型。因此，這里我們需要在迭代器類里面增加一個(gè)用普通迭代器構(gòu)造 const 迭代器的構(gòu)造函數(shù)。除了這種方法外，上面我還提供了一種方法，即先用 HashTable 中的普通迭代器創(chuàng)建一個(gè) pair 對(duì)象 ret 接收 HashTable 中 Insert 的返回值，然后再去取出 pair 里面迭代器中的成員變量，用取出來(lái)的成員變量去構(gòu)造一個(gè) const 迭代器，然后再用這個(gè) const 迭代器去構(gòu)建一個(gè) pair，最后返回這個(gè) pair。這種方法的前提是迭代器類中的成員變量是 public，否則就不能再迭代器類的外面拿到其成員變量。
4.3 unordered_map 模擬實(shí)現(xiàn)
template<class K, class V, class HashFunc = DefaultHasFunc<K>>
class unordered_map
{
private:
struct MapKeyOfT
{
const K& operator()(const pair<K, V>& kv)
{
return kv.first;
}
};
public:
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, HashFunc>::iterator iterator;
typedef typename HashTable<K, pair<const K, V>, MapKeyOfT, HashFunc>::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<iterator, bool> insert(const pair<K, V>& kv)
{
return _ht.Insert(kv);
}
V& operator[](const K& key)
{
pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));
return ret.first->second;
}
private:
HashTable<K, pair<const K, V>, MapKeyOfT, HashFunc> _ht;
};
小Tips：對(duì) unordered_map 結(jié)構(gòu)來(lái)說(shuō)無(wú)論是普通迭代器還是 const 迭代器，它的 key 永遠(yuǎn)都不能被修改。這里的解決方案是在 unordered_map 中用 pair<cons K, V> 去實(shí)例化出一個(gè)哈希表的模板，此時(shí)哈希表的節(jié)點(diǎn)中存的就是 pair<const K, V> _data;，此時(shí)無(wú)論是普通迭代器還是 const 迭代器去解引用該結(jié)點(diǎn)，返回的 _data，它里面的 key 是 const K 類型，是不支持修改的，這樣以來(lái)問(wèn)題就解決了。由于這里我們是用 pair<cons K, V> 去實(shí)例化的模板，所以 unordered_map 中的哈希表本質(zhì)上存的就是 pair<cons K, V>，但是在用戶層我們插入的是 pair<K, V>，這是兩種不同的類型，和上面的普通迭代去創(chuàng)建 const 迭代器一樣，這里還是需要通過(guò)構(gòu)造函數(shù)來(lái)解決，但是這里不需要我們自己來(lái)解決，因?yàn)?pair 是庫(kù)中的內(nèi)容，庫(kù)中已經(jīng)幫我們實(shí)現(xiàn)好啦，所以這里我們無(wú)需做任何處理。這里本質(zhì)上會(huì)去調(diào)用下面這個(gè)構(gòu)造函數(shù)。
五、結(jié)語(yǔ)
今天的分享到這里就結(jié)束啦！如果覺(jué)得文章還不錯(cuò)的話，可以三連支持一下，春人的主頁(yè)還有很多有趣的文章，歡迎小伙伴們前去點(diǎn)評(píng)，您的支持就是春人前進(jìn)的動(dòng)力！文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-713996.html
文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-713996.html
到了這里，關(guān)于【C++雜貨鋪】一文帶你走進(jìn)哈希：哈希沖突 | 哈希函數(shù) | 閉散列 | 開散列的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
