unorder_map/set的底层实现---C++
前言
再看此篇前，建议实现看我文章前面的 “红黑树模拟实现map/set” 和 “哈希表的模拟实现”，这样再看本篇文章时会更加的好理解。
一 如何实现对unordered_map/set的管理
1.1 链地址法的概念
开放定址法中所有的元素都放到哈希表⾥，链地址法中所有的数据不再直接存储在哈希表中，哈希表中存储⼀个指针，没有数据映射这个位置时，这个指针为空，有多个数据映射到这个位置时，我们把这些冲突的数据链接成⼀个链表，挂在哈希表这个位置下⾯，链地址法也叫做拉链法或者哈希桶。
就是类似这样的，应该也是好理解的。1.2 哈希表的改造
unordered_map/set的实现是基于哈希表来实现的，那么我们就以哈希表为基础来进行改造来实现我们的unordered_map/set。
1.2.1 哈希链表结构体的定义
template<class K,class V>struct HashNode{pair<K, V> _kv;HashNode<K,V>* _next;HashNode(const pair<K,V>& kv):_kv(kv),_next(nullptr){ }};首先我们可以用pair结构来存储key对应的value值，然后再设置一个_next指针一个个往下链接，这样就能对哈希链表链接的基本实现了。
1.2.2 哈希表内的私有成员
template<class K,class V,class Hash = HashFunc<K>> class HashTable { private://vector<list<pair<K, V>>> _tables;vector<Node*> _tables; // 指针数组size_t _n = 0; };定义一个存节点的vector数组_tables和_n来记录当前哈希表存了多少的数据
1.2.3 哈希表的初始化
HashTable(size_t size = __stl_next_prime(0)):_tables(size,nullptr) { }~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;} }代码中__stl_next_prime(0)在上一节哈希表的实现已经说过了，就是用来取数据来决定给tables开多少的空间，初始默认参数给0就是size为默认的53，然后tables里面初始化是没有任何数据的，给个默认的nullptr就可以了。然后析构函数，由于在哈希桶里，数据有的是一个桶里面是挂着多个数据，有的甚至没有数据的，那么只需要做一个for循环遍历tables，里面设置一个cur，然后看cur是否为空，不为空就delete这个节点然后往后走，直到为空后再把tables这个地方设置成nullptr，这样就是完成析构了。
1.2.4 迭代器的实现
1迭代器的的结构
template<class T> struct HashNode {T _data;HashNode<T>* _next;HashNode(const T& data):_data(data),_next(nullptr){ } };首先一个类模板T，然后定义一个HashNode结构体，里面T类型的data和下一个节点的地址，这样一个迭代器结构就实现了。
2 构造
//前置声明 template<class K,class T,class KeyOfT,class Hash> class HashTable;template<class K,class T,class Ref,class Ptr,class KeyOfT, class Hash> struct HTIterator {typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef HTIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;Node* _node;const HT* _ht;HTIterator(Node* node,const HT* ht):_node(node),_ht(ht){ } };HashTable就是上一节实现的哈希表，他是写在了迭代器的后面，所以我们就得先声明才能对HashTable的使用，否则编译器会不认识它，那这时候就有人问了，为什么不把它放在HashTable的后面呢？我们要知道，HashTable改造后也是需要加入迭代器的，写在后面那不还是要声明，而且会比这样更麻烦些，所以这样就是最好的实现办法，然后再迭代器部分，我们需要的参数K(key),T(value),Ref(T&),Ptr(*),KeyOfT(仿函数),Hash(对类型处理的方法)。接着就是再迭代器内部首先定义是迭代器的节点，然后再定义一个哈希表，然后构造函数里面便是节点和哈希表的初始化。
3 * ->
Ref operator*() {return _node->_data; }Ptr operator->() {return &_node->_data; }4 ++
Self& operator++() {if (_node->_next){//当前桶向前走_node = _node->_next;}else{//找下一个桶的第一个节点KeyOfT kot;Hash hs;size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();++hashi;while (hashi < _ht->_tables.size()){if (_ht->_tables[hashi]){_node = _ht->_tables[hashi];break;}else {++hashi;}}//所有桶都走完了，nullptr去做end()if (hashi == _ht->_tables.size())_node = nullptr;}return *this; }++的实现就是先看节点的next是否为空，不为空就让node等于下一个数据就可以了，为空那就先找下一个桶的第一个节点，首先计算出当前节点的hashi，然后先++，如果还是空就继续++，不为空那就可以让node等于hashi位置的第一个数据的位置，然后break结束当前循环，如果一直没找到，走完循环了，那就直接给nullptr当最后一个节点。(这里有可能会有_ht的成员没办法访问的问题，只需要把HTIterator设置成HashTable的友元函数就可以了)
5 != ==
bool operator!=(const Self& s) {return _node != s._node; }bool operator==(const Self& s) {return _node == s._node; }!=和==没什么好说的，挺容易理解的。
1.2.5 Begin和End
Iterator Begin() {// 找第一个不为空的桶里面的第一个节点for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]){return Iterator(_tables[i], this);}}return End(); }Iterator End() {return Iterator(nullptr,this); }ConstIterator Begin() const {// 找第一个不为空的桶里面的第一个节点for (size_t i = 0; i < _tables.size(); i++){if (_tables[i]){return ConstIterator(_tables[i], this);}}return End(); }ConstIterator End() const {return ConstIterator(nullptr,this); }迭代器实现一个普通和一个const版本迭代器，这两个都没什么差别，多个const罢了，begin这里说一下，首先要找第一个数据的位置，直接写一个for循环遍历找，找到一个_tables[i]不为空，就直接返回这个迭代器，他就是第一个位置，如果一个都没找到，那就是一个空的哈希表。直接给一个nullptr就可以了。
1.2.6 插入
pair<Iterator,bool> Insert(const T& data) {KeyOfT kot;Iterator it = Find(kot(data));if (it != End())return { it,false };Hash hs;//负载因子到1，在扩容if (_n == _tables.size()){// 也可以，但是扩容新开辟节点，释放旧节点，有点浪费/*HashTable<K, V> newHT(__stl_next_prime(_tables.size() + 1));for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){newHT.Insert(cur->_kv);cur = cur->_next;}}_tables.swap(newHT._tables);*/vector<Node*> newtables(__stl_next_prime(_tables.size() + 1));for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){// 旧表的节点挪动下来// 插入到映射的新表位置Node* next = cur->_next;size_t hashi = hs(kot(cur->_data)) % _tables.size();cur->_next = newtables[hashi];//想象成newnode 头插newtables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtables);}size_t hashi = hs(kot(data)) % _tables.size();Node* newnode = new Node(data);//头插newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return { {newnode, this}, true }; }这个就是哈希表改装一下成pair类型返回值，一个迭代器一个bool类型的返回值，首先先找是不是存在，存在直接返回迭代器it，和一个false，不存在加入哈希表内，返回直接返回迭代器内是newnode,this指针，bool返回true。
1.2.7 Find，erase
Find实现直接把原先哈希表实现的Find返回值类型改成迭代器就可以了，erase变都不用变，代码直接参考上一节实现哈希表的就行。
1.3 unordered_map的封装
template<class K,class V,class Hash = HashFunc<K>> class unordered_map {struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::ConstIterator 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 = insert({ key,V() });return ret.first->second;} private:hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht; };首先再这里写一个仿函数为了给前面改造的哈希表提供数据，然后begin，end的普通，const版本迭代器封装，也没啥好说的，insert就只是对哈希表的insert的函数的封装再实现，要说一下的就是operator[]了，要访问i位置的value，直接定一个pair<iterator,bool>类型的ret，然后用insert把key传过去，value不用管，默认的都可以，这样它返回的值存到ret，其实就是两层ret，那么要返回的值直接是取第一层ret的first,然后第二层pair里的second就是key对应的value了。
1.4 unordered_set的封装
template<class K,class Hash =HashFunc<K>> class unordered_set {struct SetKeyOfT{const K& operator()(const K& key){return key;}}; public:typedef typename hash_bucket::HashTable<K,const K, SetKeyOfT, Hash>::Iterator iterator;typedef typename hash_bucket::HashTable<K,const K, SetKeyOfT, Hash>::ConstIterator 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);}private:hash_bucket::HashTable<K,const K, SetKeyOfT, Hash> _ht; };这里就更没什么好说的传参就是传给哈希表两个同样的key，然后和上面的unordered_map一样，begin和end的普通和const版本迭代器，insert一样的对哈希表的insert的封装再实现。
结语
unordered_map/set的实现就是再哈希表的基础长改装一下，然后再用这两个进行封装，这样就是先对unordered_map/set的模拟实现，当然你也可以写完以后自己测试一下是不是与库里面的相似。
好了，本节就说到这里，如果我有什么写的不好或者不对的地方，欢迎再评论里面说出来，感谢你的阅读。