📖 前言

與學(xué)習(xí)紅黑樹和map、set的思路一樣，我們?cè)趯W(xué)unordered_map和unordered_set時(shí)，也是先學(xué)底層結(jié)構(gòu)，在用模擬的底層結(jié)構(gòu)來自己封裝一下該容器，動(dòng)手實(shí)踐來讓我們更好的學(xué)習(xí)和理解底層邏輯。

前情回顧：哈希桶 👉 傳送門

這里用到的封裝思路和封裝map、set的思路相同，都是更高維度的泛型編程。

思路復(fù)習(xí)：封裝map和set 👉 傳送門

---

1. 復(fù)用同一個(gè)哈希桶?

如何復(fù)用同一個(gè)哈希桶，我們就需要對(duì)哈希桶進(jìn)行改造，將哈希桶改造的更加泛型一點(diǎn)，既符合Key模型，也符合Key_Value模型。

1.1 🌀修改后結(jié)點(diǎn)的定義

所以我們這里還是和封裝map和set時(shí)一樣，無論是Key還是Key_Value，都用一個(gè)類型T來接收，這里高維度的泛型哈希表中，實(shí)現(xiàn)還是用的是Kye_Value模型，K是不能省略的，同樣的查找和刪除要用。

1.2 🌀兩個(gè)容器各自模板參數(shù)類型：

如何取到想要的數(shù)據(jù)：

• 我們給每個(gè)容器配一個(gè)仿函數(shù)
• 各傳不同的仿函數(shù)，拿到想要的不同的數(shù)據(jù)

同時(shí)我們?cè)俳o每個(gè)容器配一個(gè)哈希函數(shù)。

2. 改造之后的哈希桶?

//K --> 鍵值Key，T --> 數(shù)據(jù)
//unordered_map ->HashTable<K, pair<K, V>, MapKeyOfT> _ht;
//unordered_set ->HashTable<K, K, SetKeyOfT> _ht;
template<class K, class T, class KeyOfT, class HashFunc>
class HashTable
{template<class K, class T, class KeyOfT, class HashFunc>friend class __HTIterator;typedef HashNode<T> Node;
public:typedef __HTIterator<K, T, KeyOfT, HashFunc> iterator;iterator begin(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){return iterator(cur, this);}}return end();}iterator end(){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;}}size_t GetNextPrime(size_t prime){const int PRIMECOUNT = 28;static const size_t primeList[PRIMECOUNT] ={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};//獲取比prime大那一個(gè)素?cái)?shù)size_t i = 0;for (i = 0; i < PRIMECOUNT; i++){if (primeList[i] > prime)return primeList[i];}return primeList[i];}pair<iterator, bool> Insert(const T& data){HashFunc hf;KeyOfT kot;iterator pos = Find(kot(data));if (pos != end()){return make_pair(pos, false);}//負(fù)載因子 == 1 擴(kuò)容 -- 平均每個(gè)桶掛一個(gè)結(jié)點(diǎn)if (_tables.size() == _n){//size_t newSize = _tables.size() == 0 ? 10 : _tables.size() * 2;size_t newSize = GetNextPrime(_tables.size());if (newSize != _tables.size()){vector<Node*> newTable;newTable.resize(newSize, nullptr);//遍歷舊表for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];//再對(duì)每個(gè)桶挨個(gè)遍歷while (cur){Node* next = cur->_next;size_t hashi = hf(kot(cur->_data)) % newSize;//轉(zhuǎn)移到新的表中cur->_next = newTable[hashi];newTable[hashi] = cur;cur = next;}//將原表置空_tables[i] = nullptr;}newTable.swap(_tables);}}size_t hashi = hf(kot(data));hashi %= _tables.size();//頭插到對(duì)應(yīng)的桶即可Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;//有效數(shù)據(jù)加一_n++;return make_pair(iterator(newnode, this), true);}iterator Find(const K& key){if (_tables.size() == 0){return iterator(nullptr, this);}KeyOfT kot;HashFunc hf;size_t hashi = hf(key);//size_t hashi = HashFunc()(key);hashi %= _tables.size();Node* cur = _tables[hashi];//找到指定的桶之后，順著單鏈表挨個(gè)找while (cur){if (kot(cur->_data) == key){return iterator(cur, this);}cur = cur->_next;}//沒找到返回空return iterator(nullptr, this);}bool Erase(const K& key){if (_tables.size() == 0){return false;}HashFunc hf;KeyOfT kot;size_t hashi = hf(key);hashi %= _tables.size();//單鏈表刪除結(jié)點(diǎn)Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){//頭刪if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;return true;}prev = cur;cur = cur->_next;}return false;}
private://指針數(shù)組vector<Node*> _tables;size_t _n = 0;
};

研究表明：除留余數(shù)法，最好模一個(gè)素?cái)?shù)

• 通過查STL官方庫我們也發(fā)現(xiàn)，其提供了一個(gè)取素?cái)?shù)的函數(shù)
• 所以我們也提供了一個(gè)，直接拷貝過來
• • 這樣我們?cè)跀U(kuò)容時(shí)就可以每次給素?cái)?shù)個(gè)桶
• • 在擴(kuò)容時(shí)加了一條判斷語句是為了防止素?cái)?shù)值太大，過分?jǐn)U容容易直接把空間（堆）干崩了

---

3. 哈希桶的迭代器🔥

3.1 💥哈希桶的begin（）和 end（）的定義

• 以第一個(gè)桶中第一個(gè)不為空的結(jié)點(diǎn)為整個(gè)哈希桶的開始結(jié)點(diǎn)
• 以空結(jié)點(diǎn)為哈希桶的結(jié)束結(jié)點(diǎn)

3.2 💥 operator* 和 operator->

同之前operator->的連續(xù)優(yōu)化一樣，不再贅述……

3.3 💥 operator++

備注：

• 這里要在哈希桶的類外面訪問其私有成員
• 我們要搞一個(gè)友元類
• 迭代器類是哈希桶類的朋友
• 這樣就可以訪問了

思路：

• 判斷一個(gè)桶中的數(shù)據(jù)是否遍歷完
• • 如果所在的桶沒有遍歷完，在該桶中返回下一個(gè)結(jié)點(diǎn)指針
• • 如果所在的桶遍歷完了，進(jìn)入下一個(gè)桶
• 判斷下一個(gè)桶是否為空
• • 非空返回桶中第一個(gè)節(jié)點(diǎn)
• • 空的話就遍歷一個(gè)桶

后置++和之前一眼老套路，不贅述

注意：

• unordered_map和unordered_set是不支持反向迭代器的，從底層結(jié)構(gòu)我們也能很好的理解（單鏈表找不了前驅(qū)）
• 所以不支持實(shí)現(xiàn)迭代器的operator- -

3.4 💥 operator== 和 operator!=

template<class K, class T, class KeyOfT, class HashFunc>
class HashTable;//哈希桶的迭代器
template<class K, class T, class KeyOfT, class HashFunc>
class __HTIterator
{typedef HashNode<T> Node;typedef __HTIterator<K, T, KeyOfT, HashFunc> Self;
public:Node* _node;__HTIterator() {};//編譯器的原則是向上查找（定義必須在前面，否則必須先聲明）HashTable<K, T, KeyOfT, HashFunc>* _pht;__HTIterator(Node* node, HashTable<K, T, KeyOfT, HashFunc>* pht):_node(node), _pht(pht){}Self& operator++(){if (_node->_next){ _node = _node->_next;}else//當(dāng)前桶已經(jīng)走完了，要走下一個(gè)桶{KeyOfT kot;HashFunc hf;size_t hashi = hf(kot(_node->_data)) % _pht->_tables.size();hashi++;//找下一個(gè)不為空的桶 -- 訪問到了哈希表中私有的成員（友元）for (; hashi < _pht->_tables.size(); hashi++){if (_pht->_tables[hashi]){_node = _pht->_tables[hashi];break;}}//沒有找到不為空的桶，用nullptr去做end標(biāo)識(shí)if (hashi == _pht->_tables.size()){_node = nullptr;}}return *this;}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}bool operator!=(const Self& s) const{return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}
};

編譯器的原則是向上查找（定義必須在前面，否則必須先聲明）

---

4. 封裝unordered_map和unordered_set?

有了上面的哈希桶的改裝，我們這里的對(duì)map和set的封裝就顯得很得心應(yīng)手了。

unordered_map的封裝：

template<class K, class V, class HashFunc = DefaultHash<K>>
class unordered_map
{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};
public:typedef typename Bucket::HashTable<K, pair<K, V>, MapKeyOfT, HashFunc>::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);}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}private:Bucket::HashTable<K, pair<K, V>, MapKeyOfT, HashFunc> _ht;
};

這里unordered_map中的operator[ ]我們知道其原理之后，模擬實(shí)現(xiàn)就非常方便，直接調(diào)用插入函數(shù)，控制好參數(shù)和返回值即可。

對(duì)unordered_set的封裝：

template<class K, class HashFunc = DefaultHash<K>>
class unordered_set
{//SteKeyOfT是set專用的就用內(nèi)部類struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename Bucket::HashTable<K, K, SetKeyOfT, HashFunc>::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:Bucket::HashTable<K, K, SetKeyOfT, HashFunc> _ht;
};