（1）修改原哈希表

和红黑树封装一样的逻辑，unordered_map/set公用一张哈希表，所以改的时候两个容器都要一块取考虑，因为需要通过泛型去设计，要有复用思想。

这里一部分就简单说一下，比如第二个参数是K就是K，为什么要传第一个模板参数，它要和map复用，因为map也需要用到key，第一个模板参数拿到K的类型，因为查找，删除等接口的参数是K，第二个模板参数决定了树的节点存什么，是K还是KV。

我们一步一步加并修改原来哈希表的内容，这里就不叫V，自己写的时候这叫T，把节点结构体里面的pair类型改成T，构造函数里面用data初始化_data。以及后面涉及到pair<K,V>&kv的全都改成T&data。unordered_map就通过第二个模板参数控制node里面的data，同理unordered_set也一样。

之前是kv现在要改为_data，把kv.first改为_data,但是这里的第二个_data并不是我们想要的，因为这里的data到底是什么并不知道，上一层加了一层泛型。这需要用仿函数解决Key。原来哈希表里面涉及到hash(cur->kv.first) 需要成hash(kot(cur->_data))，表示通过指针获取节点的_data数据，我们并不知道这是什么类型需要再用仿函数Key创建的对象kot调用()来获取具体的数据，最后通过hash()来获取键值所对应的存储位置。

（2）迭代器

如上图，对于++it怎么走，大致思路是这样的，如果node不等于空继续往下走，如果为空，就需要找下一个桶，
这里写迭代器的时候因为++需要用到哈希表，就需要前置声明，这里存在互相引用的问题，迭代器需要哈希表，哈希表需要迭代器，就要把哈希表定义在前面，其他的一样的老套路，只不过里面多了一个哈希表指针，构造的时候需要初始化，另外另一个构造函数一会实现，主要这里先把迭代器++实现出来，因为它的迭代器只支持单向，没有减减。
实现迭代器加加解析：
如果node的下一个指针不为空，就继续往下走更新_node,如果为空，可能走到尾部了，就需要找下一个桶，下一个不为空的桶在哪我们不知道，先算自己在哪，先把_data里面的key取出来，再用哈希的仿函数获得整数，模上表的大小找到映射位置，算出来hashi加加一下，就去找不为空的桶，如果hashi小于数据个数，就进如循环，再判断如果下一个位置不为空，就把表的第一个节点指针给_node，否则++hashi，就过走完了整个表，没有找到下一个位置，就用空取替带_node。最后返回this指针。如下图代码：

Self& operator++(){if (_node->_next != nullptr){_node = _node->_next;}else{Key kot;Hash hash;size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();++hashi;while (hashi < _ht->_tables.size()){if (_ht->_tables[hashi]){_node = _ht->_tables[hashi];break;}else{++hashi;}if (hashi == _ht->_tables.size()){_node = nullptr;}}}return *this;}

我们实现begin和end，begin：要返回第一个桶的第一个数据，这个begin不是直接构建的，需要遍历去找第一个不为空的桶，找到之后就构建迭代器，但是除了传找到的这个节点，还得传哈希表，我们直接可以用this指针，就是指向哈希表对象本身。
end：就直接拿空就构造就可以
同理const_begin和const_end同理

            iterator begin(){Node* cur = nullptr;for (size_t i = 0; i < _tables.size(); ++i){cur = _tables[i];if (cur){break;}}return iterator(cur, this);}

上面需要一些细节，迭代器需要访问_table的私有，就让我们这个哈希表这个类提供一个get.size和get.table,也可以写一个友元函数，因为是模板还得需要加上模板参数，如图：

我们继续在unordered_map增加迭代器参数，同理unordered_set也一样，在哈希表类里里面曾加一个普通迭代器和const迭代器，如图下图：
注意这里的unordered_set两个普通迭代器底层用的都是const迭代器，unordered_map普通迭代器用的普通迭代器，因为它需要修改它的Value，它的K不能修改是通过paie里面的constkey达到的，而unordered_set只有K，K是不是能修改的。

但是直接用会报错，因为unordered_set调用begin的时候，普通对象调用的普通begin，返回的是普通迭代器，但这里是const迭代器，这里就不具体演示了，和红黑树封装一样的逻辑。具体原因是我们迭代器里没有写对应的构造，需要一个支持普通到const迭代器的构造，我们在里面单独加一个普通迭代器Iterator，构造里它的参数前面加一个const，具体就不说了可以看红黑树封装。其实就是权限的缩小。这里还有一个细节，如果调用const_iterator会有问题，因为begin是const，返回时，迭代器里的this指针就是const的，这时候要要把迭代器构造的哈希表对象指针改成const的。因为迭代器里面不会修改这里的哈希表，需要取遍历它，传普通传const都可以接收，因为权限可以缩小。

（3）最后一步

我们在unordered_map里面提供一个[]，它要去访问第二个V值也就是pair的second，如果它没有就插入，如果有就返回key所在节点的迭代器，因为里面调用的是insert，这样就不仅能查找对应的value值，并有修改功能并可以插入新的键值对,insert返回值得个是个pair类型。而且并把有关的insert返回值，如果返回成功就返回新插入节点的构造的迭代器加一个true即make_pair(iterator(newnode, this), true)，同样unordered_set的insert也一样改为pair<iterator,bool>,里面是是一个迭代器和布尔值。
总之，insert返回值是个pair类型，find返回的是一个迭代器，erase返回bool值，unordered_set除了不提供[]，其他都一样。
另外，我们的key还可以支持自定义类型，但是需要要满足支持转换成取模的仿函数，和等于比较和等于比较，调用unordered_map/set需要显示传HashDate仿函数如图：

如下图我们进行的测试和结果：

（4）关于key是自定义类型的额外补充(面试题)

1、一个类型要做unordered哈希系列的key：要满足支持转换成取模的仿函数和等于比较，如上。
2、一个类型要做map系列的key：要满足支持<比较。
在STL源码库中，map默认的第三个参数为less<_Key>，就是将key按照从小到大的顺序排列，其内部实现很简单，就是直接比较两个key的类型返回。但是如果是自定义类型的时候，直接用默认的less比较的话会报错，因为编译器不知道怎么处理，即不知道如何比较他们的大小，它能应对内置类型比如int等，比如复合类型string。如何解决？2种方法：
第一种方法：继续使用第三个模板参数，因为第三个模板参数内部是直接比较key的类型大小，我们可以在自定义的类型里实现重载<运算符，让它知道如何比较这两个key，因为默认参数是less，所以只需要重载<运算符就可以了，如果参数是greater，那么就需要重载>运算符。

struct nza {nza(int n1 = 0, int n2 = 1):_n1(n1), _n2(n2) {}bool operator<(const nza& Data) const{return _n1+_n2  < Data._n1 + Data._n2;}int _n1;int _n2;
};int main() {map<nza, int> myMap;}

第二种方法就是：自己实现一个仿函数。

struct nza {nza(int n1 = 0, int n2 = 1):_n1(n1), _n2(n2) {}int _n1;int _n2;
};
template<class T>
struct RLcmp {bool operator()(const T& Data1, const T& Data2)const {return Data1._n1 + Data1._n2< Data1._n1 + Data2._n2;}
};int main() 
{map<nza, int, RLcmp<nza> > myMap;
}

（5）源代码

OpenHash.h

#pragma once
#include<utility>
#include<vector>
#include<string>
#include<iostream>
using namespace std;template<class K>
struct HashFunc
{size_t operator()(const K& key){return key;}};
template<>
struct HashFunc<string>
{size_t operator()(const string& str){size_t hash = 0;for (auto& e : str){hash += e;hash *= 131;}return hash;}};template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_next(nullptr), _data(data){}};template<class K, class T, class Key, class Hash>class HashTable;template<class K, class T, class Ref, class Ptr, class Key, class Hash>struct _HashIterator{typedef  HashNode<T> Node;typedef HashTable<K, T, Key, Hash> HT;typedef _HashIterator<K, T, Ref, Ptr, Key, Hash> Self;typedef _HashIterator<K, T, T&, T*, Key, Hash> Iterator;Node* _node;const HT* _ht;_HashIterator(Node* node, const HT* ht):_node(node), _ht(ht){}_HashIterator(const Iterator& it):_node(it._node), _ht(it._ht){}Ptr operator->(){return &_node->_data;}Ref operator*(){return _node->_data;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s) const{return _node == s._node;}Self& operator++(){if (_node->_next != nullptr){_node = _node->_next;}else{Key kot;Hash hash;size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();++hashi;while (hashi < _ht->_tables.size()){if (_ht->_tables[hashi]){_node = _ht->_tables[hashi];break;}else{++hashi;}if (hashi == _ht->_tables.size()){_node = nullptr;}}}return *this;}};template<class K, class T, class Key, class Hash>class HashTable{template<class K, class T, class Ref, class Ptr, class Key, class Hash>friend struct _HashIterator;typedef HashNode<T> Node;public:typedef _HashIterator<K, T, T&, T*, Key, Hash> iterator;typedef _HashIterator<K, T, const T&, const T*, Key, Hash> const_iterator;iterator begin(){Node* cur = nullptr;for (size_t i = 0; i < _tables.size(); ++i){cur = _tables[i];if (cur){break;}}return iterator(cur, this);}iterator end(){return iterator(nullptr, this);}const_iterator begin()const{Node* cur = nullptr;for (size_t i = 0; i < _tables.size(); ++i){cur = _tables[i];if (cur){break;}}return const_iterator(cur, this);}const_iterator end()const{return const_iterator(nullptr, this);}~HashTable(){for (auto& cur : _tables){while (cur){Node* next = cur->_next;delete cur;cur = next;}cur = nullptr;}}pair<iterator, bool> Insert(const T& data){Key kot;iterator it = Find(kot(data));if (it != end()){return make_pair(it, false);}Hash hash;if (_n == _tables.size()){/*size_t newsize = _tables.size() == 0 ? 10 : _tables.size() * 2;*/size_t newsize = GetNextPrime(_tables.size());vector<Node*> newtables(newsize, nullptr);for (auto& cur : _tables){while (cur){Node* next = cur->_next;;size_t hashi = hash(kot(cur->_data)) % newtables.size();cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}}_tables.swap(newtables);}size_t hashi = hash(kot(data)) % _tables.size();Node* newnode = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(iterator(newnode, this), true);}iterator Find(const K& key){Key kot;if (_tables.size() == 0)return end();Hash hash;size_t hashi = hash(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){Key kot;Hash hash;size_t hashi = hash(key) % _tables.size();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;}else{prev = cur;cur = cur->_next;}}return false;}size_t GetNextPrime(size_t prime){static const int __stl_num_primes = 28;static const unsigned long __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};size_t i = 0;for (; i < __stl_num_primes; ++i){if (__stl_prime_list[i] > prime)return __stl_prime_list[i];}return __stl_prime_list[i];}private:vector<Node*> _tables;size_t _n = 0;};

unordered_Map.h

#pragma once
#include"OpenHash.h"
namespace nza
{template<class K, class V,class Hash=HashFunc<K>>class unordered_Map{public:struct MapKey{const K& operator()(const pair<K,V>& kv){return kv.first;}};public:typedef  typename HashTable<K, pair<const K,V>, MapKey,Hash>::iterator iterator;typedef  typename HashTable<K, pair<const K,V>, MapKey,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();}V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}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);}private:HashTable<K,pair<const K, V>, MapKey,Hash> _ht;};class Date{friend struct HashDate;public:Date(int year = 2000, int month = 12, int day = 23): _year(year), _month(month), _day(day){}bool operator<(const Date& d)const{return (_year < d._year) ||(_year == d._year && _month < d._month) ||(_year == d._year && _month == d._month && _day < d._day);}bool operator>(const Date& d)const{return (_year > d._year) ||(_year == d._year && _month > d._month) ||(_year == d._year && _month == d._month && _day > d._day);}bool operator==(const Date& d) const{return _year == d._year&& _month == d._month&& _day == d._day;}friend ostream& operator<<(ostream& _cout, const Date& d);private:int _year;int _month;int _day;};ostream& operator<<(ostream& _cout, const Date& d){_cout << d._year << "-" << d._month << "-" << d._day;return _cout;}struct HashDate{size_t operator()(const Date& d){size_t hash = 0;hash += d._year;hash *= 31;hash += d._month;hash *= 31;hash += d._day;hash *= 31;return hash;}};void TestM1(){unordered_Map<int, int> m;m.insert(make_pair(66, 66));m.insert(make_pair(77, 77));m.insert(make_pair(160, 160));unordered_Map<int, int>::iterator it = m.begin();while (it != m.end()){cout << it->first << ":" << it->second << endl;++it;}cout << endl;}void TestM2(){Date d1(2016, 3, 15);Date d2(2016, 3, 15);Date d3(2016, 3, 12);Date d4(2016, 3, 11);Date d5(2023, 3, 12);Date d6(2023, 3, 13);Date a[] = { d1, d2, d3, d4, d5, d6 };unordered_Map<Date, int, HashDate> cm;for (auto e : a){cm[e]++;}for (auto& kv : cm){cout << kv.first << ":" << kv.second << endl;}cout << endl;}
}

unordered_Set.h

#pragma once
#include"OpenHash.h"
namespace nza
{template<class K,class Hash=HashFunc<K>>class unordered_Set{public:struct SetKey{const K& operator()(const K& key){return key;}};public:typedef typename  HashTable< K, K, SetKey,Hash>::const_iterator iterator;typedef typename  HashTable< K, K, SetKey,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<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, K, SetKey,Hash> _ht;};void TestS1(){int a[] = { 1, 6, 4, 66, 160, 32, 44 };unordered_Set<int> s;for (auto e : a){s.insert(e);}s.insert(35);s.insert(117);unordered_Set<int>::iterator it = s.begin();while (it != s.end()){cout << *it << " ";++it;}cout << endl;for (auto e : s){cout << e << " ";}cout << endl;}
}

test.cpp

#include"OpenHash.h"
#include"unordered_Set.h"
#include"unordered_Map.h"int main()
{nza::TestM1();nza::TestM2();nza::TestS1();}