哈希封装unordered_map和unordered_set的模拟实现

（一）认识unordered_map和unordered_set

unordered_map和unordered_set这两个容器是C++11之后才更新的。unordered_map的底层复用了哈希表来实现key/value的结构，而unordered_set的底层也是复用了哈希表，但实现的是key的结构。这两个容器的使用其实跟map和set的使用是一致的，只是map和set的底层复用的是红黑树，unordered_set和unordered_map这两个容器的使用如下代码：

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
#include <map>
#include <set>
#include <unordered_map>
#include <unordered_set>using namespace std;int main()
{//unordered_mapunordered_map<int, int> myunmap = { {4,4},{2,2},{8,8},{11,11},{2,2} };for (auto& e : myunmap){cout << e.first  << ":" << e.second << endl;}//unordered_setunordered_set<int> myunset = { 3,4,2,1,7,0,5,6,9,8,3,3 };for (auto& e : myunset){cout << e << " ";}cout << endl << endl;//mapmap<int, int> mymap = { {4,4},{2,2},{8,8},{11,11},{2,2} };for (auto& e : mymap){cout << e.first << ":" << e.second << endl;}//setset<int> myset = { 3,4,2,1,7,0,5,6,9,8,3,3 };for (auto& e : myset){cout << e << " ";}cout << endl;return 0;
}

打印结果：

从代码和打印结果来看，unordered_map和unordered_set这两个容器跟map、set一样都支持initializer_list初始化，但是从打印结果来看，unordered_map和unordered_set支持去重+不排序，而map和set支持去重+排序，这就是它们底层复用的封装不同所导致的，map和set的底层是红黑树，迭代器在遍历时走中序遍历，所以打印出来的数据是有序的，而unordered_map和unordered_set底层是哈希表，哈希表是通过哈希桶来将值一个个存储进去的，迭代器遍历时是遍历一个个哈希桶，所以底层复用的不同，实现出来的效果也略有不同，但是这几个容器的使用方式完全是类似的。

（二）模拟实现unordered_map和unordered_set

2.1 实现出复用哈希表的框架

• 首先我们得知道，哈希表既能被unordered_map复用又能被unordered_set复用，而unordered_map的数据结构是pair<key,value>，而unordered_set的数据结构就是一个key，由于这两个容器的存储的数据结构不同，所以哈希表在实现时应该使用泛型参数T来接收unordered_map和unordered_set传过来的数据结构的类型，才能实例化出不同的哈希表，提供给这两个容器使用
• 哈希表在实现时还需要使用一个K参数来接收unordered_map和unordered_set的关键字，因为这两个容器的find/erase等一些接口都是通过关键字来实现的。unordered_set传给泛型T的就是关键字，但还是需要再传一遍，就是为了要与unordered_map保持兼容，unordered_map传给泛型T的是一堆pair值，实现find/erase等接口时就不方便，所以为了保持兼容，哈希表在实现时还需要使用一个K参数来接收unordered_map和unordered_set的关键字
• 因为哈希表实现了泛型T，不知道传过来的数据是k，还是pair<k,v>，那么insert内部进行插入时要用k对象转换成整型取模和比较相等，因为pair的value不参与计算取模，且默认支持的是key和value一起比较相等，所以在任何时候只需要比较k对象，那么我们就需要在unordered_map和unordered_set层分别实现一个MapOfKey和SetOfKey的仿函数来传给哈希表中的KeyOfT，然后在哈希表中通过KeyOfT仿函数取出T类型对象中的k对象，再转换成整型取模和k比较相等

代码实现如下：
步骤1：实现哈希表

#pragma once
#include <iostream>
#include <vector>
using namespace std;//将关键字转成可以取模，如string本身取不了模，利用ASCII码值即可，用仿函数实现
template<class K>
class HashFunc
{
public://全部转成无符号的整型，这样才能取模const size_t operator()(const K& key){return (size_t)key;}
};
//使用库里面的unordered_map和unordered_set时，我们不用给string的取模进行仿函数的实现，因为库里面为string的仿函数进行了特化
template<>
class HashFunc<string>
{
public:size_t operator()(const string& str){size_t ret = 0;for (auto& s : str){ret += s;ret *= 131;}return ret;}
};namespace li //模拟实现时防止与库里面的冲突，用了命名空间
{template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data),_next(nullptr){ }};template<class K,class T,class KeyOfT,class Hash>class HashTable{typedef HashNode<T> Node;public:inline unsigned long _stl_next_prime(unsigned long n){static const int _stl_num_primes = 28;static const unsigned long _stl_primes_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};const unsigned long* first = _stl_primes_list;const unsigned long* last = _stl_primes_list + _stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);//lower_bound()在迭代器的范围内取>=n的最小值return pos == last ? *(pos - 1) : *(pos);}HashTable(){//提前开好第一个质数大小的空间_tables.resize(_stl_next_prime(1),nullptr);}~HashTable(){for (int i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}bool insert(const T& data){Hash hs;KeyOfT kot;if(find(kot(data)))return false;//负载因子为1就扩容if (_n == _tables.size()){unsigned long newsize = _stl_next_prime(_tables.size() + 1);vector<Node*> newtables(newsize, nullptr);for (int i = 0; i < _tables.size(); i++){//遍历旧表，将数据挪到新表Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = hs(kot(cur->_data)) % newtables.size();cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtables);}//算出key在哈希表中映射的存储空间size_t hashi = hs(kot(data)) % _tables.size();//头插Node* cur = new Node(data);cur->_next = _tables[hashi];_tables[hashi] = cur;++_n;return true;}bool find(const K& key){Hash hs;KeyOfT kot;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (hs(kot(cur->_data)) == hs(key)){return true;}cur = cur->_next;}return false;}bool erase(const K& key){Hash hs;KeyOfT kot;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];Node* prev = nullptr;while (cur){if (hs(kot(cur->_data)) == hs(key)){if (prev == nullptr){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _tables;size_t _n = 0;};
}

步骤2：封装unordered_map和unordered_set的框架，解决获取关键字(KeyOfT)的问题

//unordered_map.h
#pragma once
#include "HashTable.h"
namespace Unordered_map
{template<class K, class V,class Hash = HashFunc<K>>class unordered_map{struct MapOfKey{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:bool insert(const pair<K, V>& kv){return _hash.insert(kv);}bool find(const K& key){return _hash.find(key);}bool erase(const K& key){return _hash.erase(key);}private:li::HashTable<K, pair<const K, V>,MapOfKey,Hash> _hash;};
}

//unordered_set.h
#pragma once
#include "HashTable.h"
namespace Unordered_set
{template<class K,class Hash = HashFunc<K>>class unordered_set{struct SetOfKey{const K& operator()(const K& key){return key;}};public:bool insert(const K& key){return _hash.insert(key);}bool find(const K& key){return _hash.find(key);}bool erase(const K& key){return _hash.erase(key);}private:li::HashTable<K,const K,SetOfKey,Hash> _hash;};
}

2.2 迭代器iterator的实现思路分析

• iterator的实现就是用一个类型去封装结点的哈希结点的指针，再通过重载运算符实现迭代器像指针一样访问的行为，这里哈希表的迭代器是一个单项迭代器
• 重载运算符中，operator++如何实现呢，iterator中有一个结点的指针，该指针指向哈希桶里的一个结点，若桶下面还有结点，则将迭代器指向下一个结点即可。若桶的下面没有结点，则需要找到哈希桶，为了能找到下一个桶，我们需要在迭代器中增加一个哈希表指针，让该指针指向哈希表，这样的话若当前桶走完了，要找到下一个桶就方便了，直接用key值计算出当前桶的位置，依次往后找不为空的桶即可，若往后找到的桶都为空，遍历到哈希尾，就可返回一个nullptr

代码如下：
步骤1：实现哈希表的迭代器，重载运算符

template<class K, class T, class KeyOfT, class Hash>
class HashTable;template<class K, class T, class KeyOfT, class Hash>
struct HashTableIterator
{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> ht;typedef HashTableIterator<K, T, KeyOfT, Hash> Self;Node* _node; //结点的指针const ht* _ht; //哈希表指针HashTableIterator(Node* node,const ht* ht):_node(node),_ht(ht){ }T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}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++;}}if (hashi == _ht->_tables.size()){//没有不为空的桶_node = nullptr;}}return *this;}bool operator!=(const Self& s){return _node != s._node;}bool operator==(const Self& s){return _node == s._node;}
};

步骤2：begin()返回第一个桶中第一个结点指针构造的迭代器，end()返回的迭代器可以用空来表示

template<class K,class T,class KeyOfT,class Hash>
class HashTable
{typedef HashNode<T> Node;template<class K, class T, class KeyOfT, class Hash>friend struct HashTableIterator; //友元声明，方便迭代器访问哈希表中的私有成员public:typedef HashTableIterator<K, T, KeyOfT, Hash> Iterator;Iterator Begin(){for (int i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){return Iterator(cur, this);}}return End();}Iterator End(){return Iterator(nullptr, this);}
};

上面两个步骤实现的迭代器是可以修改的，我们知道unordered_map和unordered_set的关键字是不可以被修改的，所以我们需要把unordered_set的第二个模板参数改成const K，unordered_map的第二个模板参数改成pair<const K,V>，代码如下：

步骤3：封装哈希迭代器实现unordered_map和unordered_set的迭代器

//unordered_map.h
template<class K, class V,class Hash = HashFunc<K>>
class unordered_map
{
public:typedef typename li::HashTable<K, pair<const K, V>, MapOfKey, Hash>::Iterator iterator;iterator begin(){return _hash.Begin();}iterator end(){return _hash.End();}
private:li::HashTable<K, pair<const K, V>,MapOfKey,Hash> _hash;
};

//unordered_set.h
template<class K,class Hash = HashFunc<K>>
class unordered_set
{
public:typedef typename li::HashTable<K,const K, SetOfKey, Hash>::Iterator iterator;iterator begin(){return _hash.Begin();}iterator end(){return _hash.End();}
private:li::HashTable<K,const K,SetOfKey,Hash> _hash;
};

li::HashTable<K, pair<const K, V>,MapOfKey,Hash> _hash; //unordered_map
li::HashTable<K,const K,SetOfKey,Hash> _hash; // unordered_set

步骤4：实现const迭代器
增加迭代器的模板参数

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 HashTableIterator
{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> ht;typedef HashTableIterator<K, T, Ref, Ptr, KeyOfT, Hash> Self;Node* _node; //结点的指针const ht* _ht; //哈希表指针HashTableIterator(Node* node,const ht* ht):_node(node),_ht(ht){ }Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}
};

步骤5：实现const Begin()和const End()

template<class K,class T,class KeyOfT,class Hash>
class HashTable
{typedef HashNode<T> Node;template<class K, class T, class KeyOfT, class Hash>friend struct HashTableIterator; //友元声明，方便迭代器访问哈希表中的私有成员public:typedef HashTableIterator<K, T, T&, T*, KeyOfT, Hash> Iterator;typedef HashTableIterator<K, T, const T&, const T*, KeyOfT, Hash> ConstIterator;ConstIterator Begin() const{for (int i = 0; i < _tables.size(); i++){Node* cur = _tables[i];if (cur){return ConstIterator(cur, this);}}return End();}ConstIterator End() const{return ConstIterator(nullptr, this);}
};

步骤6：封装哈希const_iterator实现unordered_map和unordered_set的const_iterator

//unordered_map.h
template<class K, class V,class Hash = HashFunc<K>>
class unordered_map
{
public:typedef typename li::HashTable<K, pair<const K, V>, MapOfKey, Hash>::ConstIterator const_iterator;const_iterator begin() const{return _hash.Begin();}const_iterator end() const{return _hash.End();}
private:li::HashTable<K, pair<const K, V>,MapOfKey,Hash> _hash;
};

//unordered_set.h
template<class K,class Hash = HashFunc<K>>
class unordered_set
{
public:typedef typename li::HashTable<K,const K, SetOfKey, Hash>::ConstIterator const_iterator;const_iterator begin() const{return _hash.Begin();}const_iterator end() const{return _hash.End();}
private:li::HashTable<K,const K,SetOfKey,Hash> _hash;
};

2.3 unordered_map支持[]

unordered_map要支持[]主要需要修改insert返回值支持，修改HashTable中insert的返回值为pair<Iterator,bool> insert(const T& data)，有了insert支持unordered_map的[]就很好实现了

代码如下：

pair<Iterator,bool> insert(const T& data)
{Hash hs;KeyOfT kot;Iterator it = find(kot(data)); //find函数的返回值也要进行修改，修改成Iteratorif (it != End())return { it,false };//负载因子为1就扩容if (_n == _tables.size()){unsigned long newsize = _stl_next_prime(_tables.size() + 1);vector<Node*> newtables(newsize, nullptr);for (int i = 0; i < _tables.size(); i++){//遍历旧表，将数据挪到新表Node* cur = _tables[i];while (cur){Node* next = cur->_next;size_t hashi = hs(kot(cur->_data)) % newtables.size();cur->_next = newtables[hashi];newtables[hashi] = cur;cur = next;}_tables[i] = nullptr;}_tables.swap(newtables);}

//unordered_map.h
V& operator[](const K& key)
{pair<iterator, bool> ret = _hash.insert(make_pair(key, V()));return ret.first->second;
}

既然哈希表中的inser的返回值修改了，那么对应的unordered_map和unordered_set的insert函数的返回值也要进行修改

（三）结束语

用哈希表来模拟实现这两个容器，就得先学习底层的哈希表，不了解哈希表的友友可以看我的上一篇文章https://blog.csdn.net/muzi_liii/article/details/147519118?spm=1001.2014.3001.5501。该模拟实现简易的unordered_map和unordered_set就完成了。一起学习吧！