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

unordered系列關(guān)聯(lián)式容器是從C++11開(kāi)始，STL提供的。它的查詢(xún)效率要更優(yōu)于set/map類(lèi)型關(guān)聯(lián)式容器。
unordered系列容器的名字是從功能角度來(lái)取定的。set/map這類(lèi)容器，其遍歷是有序的，而unordered系列容器的遍歷則是無(wú)序的。
從底層角度來(lái)看，set/map類(lèi)容器底層采用紅黑樹(shù)實(shí)現(xiàn)，而unordered系列容器則是采用的哈希結(jié)構(gòu)。同時(shí)，map/set的迭代器是雙向的，而unordered系列容器是單向的。
unordered系列容器的使用可以參考set/map的使用【C++】set & map的使用，它們的使用方式大多是類(lèi)似的。

哈希結(jié)構(gòu)

哈希，也叫散列，是一種值與存儲(chǔ)位置之間建立映射關(guān)聯(lián)的結(jié)構(gòu)。
哈希結(jié)構(gòu)通過(guò)哈希函數(shù)(Hash)使元素的關(guān)鍵碼與存儲(chǔ)位置之間建立一一映射的關(guān)系。當(dāng)插入元素時(shí)，由元素的關(guān)鍵碼，根據(jù)哈希函數(shù)計(jì)算出元素的存儲(chǔ)位置進(jìn)行存放；當(dāng)查找刪除元素時(shí)，也是同樣的計(jì)算過(guò)程。

除留余數(shù)法

哈希函數(shù)有很多種，本文中使用的哈希函數(shù)為除留余數(shù)法。
設(shè)哈希表中允許存放的位置個(gè)數(shù)為n，取一個(gè)小于等于n的最大質(zhì)數(shù)p作為除數(shù)，按照哈希函數(shù)：Hash(key) = key % p，通過(guò)計(jì)算將關(guān)鍵碼轉(zhuǎn)換成哈希表中對(duì)應(yīng)的地址。

哈希沖突

當(dāng)哈希表中存放的數(shù)據(jù)越來(lái)越多，必然會(huì)出現(xiàn)不同的key通過(guò)相同哈希函數(shù)的計(jì)算，出現(xiàn)相同地址的情況，即哈希沖突，或哈希碰撞。
哈希沖突的解決有兩種常見(jiàn)方式：閉散列和開(kāi)散列。

閉散列

閉散列，也叫開(kāi)放定址法。當(dāng)發(fā)生哈希沖突時(shí)，如果哈希表未被填滿(mǎn)，也就是還存在空位置，那么可以把關(guān)鍵碼key的元素存放到?jīng)_突位置的“下一個(gè)”空位置去。

線(xiàn)性探測(cè)

線(xiàn)性探測(cè)：從發(fā)生沖突的位置開(kāi)始，依次向后探測(cè)，直到找到一個(gè)空位置為止。
線(xiàn)性探測(cè)的插入分兩種情況：

1. 通過(guò)哈希函數(shù)計(jì)算待插入元素的位置，如果該位置沒(méi)有元素，即直接插入新元素；
2. 如果該位置有元素，發(fā)生哈希沖突，使用線(xiàn)性探測(cè)找到空位置，再插入新元素。

線(xiàn)性探測(cè)的查找和刪除的處理需要額外引入對(duì)元素delete的狀態(tài)標(biāo)記。

enum State{EMPTY, EXIST, DELETE};

假如哈希表中存在發(fā)生哈希沖突的兩個(gè)元素，這兩個(gè)元素位置一前一后，狀態(tài)都為EXIST。如果在前面的元素被刪除了，該位置狀態(tài)直接被置為EMPTY，此時(shí)再去找位于后面的元素，就會(huì)發(fā)生找不到的情況。因?yàn)閷ふ业慕K止條件就是遇到空EMPTY結(jié)束。所以，通過(guò)DELETE標(biāo)記的引入，使得前面元素的刪除不會(huì)影響到后面的元素。
線(xiàn)性探測(cè)實(shí)現(xiàn)起來(lái)會(huì)比較簡(jiǎn)單。但是一旦發(fā)生哈希沖突，可能會(huì)相互作用，不斷擴(kuò)大沖突的范圍，使得找一個(gè)關(guān)鍵碼的位置需要比較很多次，從而導(dǎo)致效率的下降。

二次探測(cè)

二次探測(cè)是對(duì)線(xiàn)性探測(cè)缺陷的一種改進(jìn)，但本質(zhì)上還是沒(méi)有完全解決哈希沖突問(wèn)題。
如果說(shuō)線(xiàn)性探測(cè)的“下一個(gè)”位置可以用$Hash(key)+i(i>=0)$表示，那么在二次探測(cè)中，“下一個(gè)”位置的表示就是$Hash(key)+i^2$ 或者 $Hash(key)?i^2$。

負(fù)載因子

其實(shí)還可以通過(guò)擴(kuò)容來(lái)降低哈希沖突發(fā)生的概率。
哈希表的負(fù)載因子 $\alpha =\frac{填入表中的元素個(gè)數(shù)}{哈希表的長(zhǎng)度(地址個(gè)數(shù))}$。
$\alpha$是哈希表填充程度的衡量因子。因?yàn)楸黹L(zhǎng)是定值，所以$\alpha$與“填入表中的元素個(gè)數(shù)”成正比。所以，$\alpha$越大，表明填入表中的元素越多，沖突概率也越大；反之，$\alpha$越小，表明填入表中的元素越少，沖突概率也越小。對(duì)于閉散列(開(kāi)放定址法)，應(yīng)嚴(yán)格限制$\alpha$在0.7 - 0.8。
閉散列最大的缺陷就是空間利用率比較低了，這同時(shí)也是哈希的缺陷。

開(kāi)散列

開(kāi)散列，也叫拉鏈法。首先同樣是通過(guò)哈希函數(shù)計(jì)算關(guān)鍵碼的地址，不同的地方是它將具有相同地址的關(guān)鍵碼元素歸于同一子集合，每一個(gè)子集合稱(chēng)為一個(gè)桶，各個(gè)桶中的元素通過(guò)一個(gè)單鏈表連接起來(lái)，哈希表中存儲(chǔ)各鏈表的頭節(jié)點(diǎn)指針。
所以，開(kāi)散列中每個(gè)桶存放的都是發(fā)生哈希沖突的元素。

開(kāi)散列增容

開(kāi)散列最好的情況是：每個(gè)哈希桶中剛好掛一個(gè)節(jié)點(diǎn)。然后再繼續(xù)插入元素時(shí)，每一次都會(huì)發(fā)生哈希沖突。
因此，在元素個(gè)數(shù)剛好等于桶的個(gè)數(shù)，再插入時(shí)，可以給哈希表增容。

閉散列 VS 開(kāi)散列

使用開(kāi)散列處理哈希沖突，需要增設(shè)鏈接指針，似乎增加了存儲(chǔ)開(kāi)銷(xiāo)。而閉散列需要預(yù)留大量的空閑空間來(lái)確保效率，一般表項(xiàng)所占空間有比指針大的多，所以使用開(kāi)散列反而會(huì)比閉散列節(jié)省空間。

字符串哈希算法

如果關(guān)鍵碼key不為整型，比如為字符串類(lèi)型，又該如何映射其地址呢？
首先當(dāng)然是將字符串轉(zhuǎn)為整形再做運(yùn)算，對(duì)于如何轉(zhuǎn)換的問(wèn)題可以參考BYVoid大佬的這篇關(guān)于字符串哈希算法的文章各種字符串Hash函數(shù)比較，里面給出了各種哈希算法的源碼實(shí)現(xiàn)，并對(duì)各種算法的性能做了分?jǐn)?shù)排名。

Hash函數(shù)	數(shù)據(jù)1	數(shù)據(jù)2	數(shù)據(jù)3	數(shù)據(jù)4	數(shù)據(jù)1得分	數(shù)據(jù)2得分	數(shù)據(jù)3得分	數(shù)據(jù)4得分	平均分
BKDRHash	2	0	4774	481	96.55	100	90.95	82.05	92.64
APHash	2	3	4754	493	96.55	88.46	100	51.28	86.28
DJBHash	2	2	4975	474	96.55	92.31	0	100	83.43
JSHash	1	4	4761	506	100	84.62	96.83	17.95	81.94
RSHash	1	0	4861	505	100	100	51.58	20.51	75.96
SDBMHash	3	2	4849	504	93.1	92.31	57.01	23.08	72.41
PJWHash	30	26	4878	513	0	0	43.89	0	21.95
ELFHash	30	26	4878	513	0	0	43.89	0	21.95

線(xiàn)性探測(cè) & 二次探測(cè)實(shí)現(xiàn)

template<class K>
class Hash
{
public:// 整形直接返回size_t operator()(const K& key){return (size_t)key;}
};template<>
class Hash<string>
{
public:// string類(lèi)型 -- BKDRHashsize_t operator()(const string& key){size_t hash = 0;for (char c : key){hash *= 131;hash += c;}// 裝成整形返回return hash;}
};

// 閉散列
namespace CloseHash
{// 標(biāo)記哈希表表項(xiàng)的狀態(tài)enum State{EMPTY,EXIST,DELETE};// 哈希表表項(xiàng)的類(lèi)型template<class K, class V>class HashNode{public:pair<K, V> _kv; // 要存儲(chǔ)的元素State _state = EMPTY;};// 哈希表的實(shí)現(xiàn)template<class K, class V, class Hash = Hash<K>>class HashTable{public:// 插入bool Insert(const pair<K, V>& kv){// 找到了，返回false，插入失敗if (Find(kv.first))return false;// 先檢查擴(kuò)容 -- 負(fù)載因子到0.7就擴(kuò)容if (_table.size() == 0 || 10 * _size / _table.size() >= 7){size_t newSize = _table.size() == 0 ? 10 : _table.size() * 2;HashTable<K, V, Hash> newHT;newHT._table.resize(newSize);// 舊表數(shù)據(jù)映射到新表for (auto e : _table){if (e._state == EXIST){// 復(fù)用Insert()newHT.Insert(e._kv);}}// 交換_table.swap(newHT._table);}// 線(xiàn)性探測(cè)Hash hash;// key轉(zhuǎn)整形 -> 除留余數(shù)法size_t hashi = hash(kv.first) % _table.size();while (_table[hashi]._state == EXIST){++hashi;hashi %= _table.size();}_table[hashi]._kv = kv;_table[hashi]._state = EXIST;++_size;return true;}// 刪除bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){// 將狀態(tài)標(biāo)記成DELETE即可ret->_state = DELETE;--_size;return true;}return false;}// 查找HashData<K, V>* Find(const K& key){if (_table.empty()){return nullptr;}Hash hash;size_t start = hash(key) % _table.size();size_t hashi = start;while (_table[hashi]._state != EMPTY){if (_table[hashi]._kv.first == key && _table[hashi]._state != DELETE){return &_table[hashi];}++hashi;hashi %= _table.size();if (hashi == start){break;}}return nullptr;}private:vector<HashNode<K, V>>  _table;size_t _size = 0; // 存儲(chǔ)有效數(shù)據(jù)的個(gè)數(shù)};
}

// 二次探測(cè)
// 只需要將Insert()中的線(xiàn)性探測(cè)部分替換成下面的二次探測(cè)即可
Hash hash;
size_t start = hash(kv.first) % _table.size();
size_t i = 0;
size_t hashi = start;
while (_table[hashi]._state == EXIST)
{++i;hashi = start + i * i;hashi %= _table.size();
}_table[hashi]._kv = kv;
_table[hashi]._state = EXIST;
++_size;

拉鏈法實(shí)現(xiàn)

// 開(kāi)散列
//namespace OpenHash
namespace HashBucket
{// 哈希節(jié)點(diǎn)的類(lèi)型template<class K, class V>class HashNode{public:HashNode(const pair<K, V>& kv): _kv(kv), _next(nullptr){}pair<K, V> _kv; // 要存儲(chǔ)的元素HashNode<K, V>* _next;};template<class K, class V, class Hash = Hash<K>>class HashTable{private:typedef HashNode<K, V> Node;public:// 析構(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;}}// 引用STL源碼略做修改// 使哈希表每次擴(kuò)容的大小為素?cái)?shù)inline size_t __stl_next_prime(size_t n){static const size_t __stl_num_primes = 28;static const size_t __stl_prime_list[__stl_num_primes] ={53,         97,         193,       389,       769,1543,       3079,       6151,      12289,     24593,49157,      98317,      196613,    393241,    786433,1572869,    3145739,    6291469,   12582917,  25165843,50331653,   100663319,  201326611, 402653189, 805306457,1610612741, 3221225473, 4294967291};for (size_t i = 0; i < __stl_num_primes; ++i){if (__stl_prime_list[i] > n){return __stl_prime_list[i];}}return 0; // 表示出錯(cuò)了}bool Insert(const pair<K, V>& kv){if (Find(kv.first)){return false;}Hash hash;// 檢查擴(kuò)容if (_size == _table.size()){vector<Node*> newTable;newTable.resize(__stl_next_prime(_table.size()), nullptr);// 舊表中的節(jié)點(diǎn) 移動(dòng) 映射到新表for (size_t i = 0; i < _table.size(); ++i){Node* cur = _table[i];while (cur){Node* next = cur->_next;// 鏈接到新表size_t hashi = hash(cur->_kv.first) % newTable.size();cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}_table[i] = nullptr;}// 交換_table.swap(newTable);}size_t hashi = hash(kv.first) % _table.size();// 頭插Node* newnode = new Node(kv);newnode->_next = _table[hashi];_table[hashi] = newnode;++_size;return true;}bool Erase(const K& key){if (_table.empty()){return false;}Hash hash;size_t hashi = hash(key) % _table.size();Node* prev = nullptr;Node* cur = _table[hashi];while (cur){if (key == cur->_kv.first){// 頭刪if (prev == nullptr){_table[hashi] = cur->_next;}else // 其他位置刪除{prev->_next = cur->_next;}delete cur;--_size;return true;}prev = cur;cur = cur->_next;}return false;}Node* Find(const K& key){if (_table.empty()){return nullptr;}Hash hash;size_t hashi = hash(key) % _table.size();Node* cur = _table[hashi];// 去桶里面找while (cur){if (key == cur->_kv.first){return cur;}cur = cur->_next;}return nullptr;}// 返回有效數(shù)據(jù)個(gè)數(shù)size_t Size(){return _size;}// 表的長(zhǎng)度(地址個(gè)數(shù))size_t TableSize(){return _table.size();}// 桶的個(gè)數(shù)size_t BucketNum(){size_t num = 0;for (size_t i = 0; i < _table.size(); ++i){if (_table[i]){++num;}}return num;}// 最大桶的節(jié)點(diǎn)個(gè)數(shù)size_t MaxBucket(){size_t maxLen = 0;for (size_t i = 0; i < _table.size(); ++i){size_t len = 0;Node* cur = _table[i];while (cur){++len;cur = cur->_next;}if (len > maxLen){maxLen = len;}}return maxLen;}private:vector<Node*> _table; // 哈希表存哈希節(jié)點(diǎn)的指針size_t _size = 0; // 存儲(chǔ)有效數(shù)據(jù)的個(gè)數(shù)};
}