unordered_map和unordered_set的模拟实现

目录

1.哈希表模板参数的控制

2.哈希表的默认成员函数

2.1 构造函数

2.2 拷贝构造函数

2.3 赋值运算符重载

2.4 析构函数

3.哈希表正向迭代器的实现

4.封装后的代码

HashTable.h

unordered_map.h

unordered_set.h

---

1.哈希表模板参数的控制

unordered_set是K模型的容器，而unordered_map是KV模型的容器，

要想只用一份哈希表代码同时封装出K模型和KV模型的容器，我们必定要对哈希表的模板参数进行控制。

为了与原哈希表的模板参数进行区分，这里将哈希表的第二个模板参数的名字改为T。

现在由于我们在哈希结点当中存储的数据类型是T，这个T可能就是一个键值，也可能是一个键值对，对于底层的哈希表来说，它并不知道哈希结点当中存储的数据究竟是什么类型，因此需要由上层容器提供一个仿函数，用于获取T类型数据当中的键值。

因此，unordered_map容器需要向底层哈希表提供一个仿函数，该仿函数返回键值对当中的键值。

虽然unordered_set容器传入哈希表的T就是键值，但是底层哈希表并不知道上层容器的种类，底层哈希表在获取键值时会统一通过传入的仿函数进行获取，因此unordered_set容器也需要向底层哈希表提供一个仿函数。 

这里我们给一个仿函数 KeyOFT.

template<class K, class T,class KeyOFT,class Hash = HashFunc<K>> class HashTable

 如果上层使用的是unordered_set容器，那么传入哈希表的模板参数就是key和key,仿函数则是返回一个key.

template <class K,class K> class unordered_set { struct SetKeyOFT { const K& operator(const K& key) { return key; } }; public: //..... private: hash_bucket::HashTable<K, K, SetKeyOFT> _ht; };

 但如果上层使用的是unordered_map容器，那么传入哈希表的模板参数就是key以及key和value构成的键值对，仿函数则返回pair当中的first。

template<class K,class V> class unordered_map { struct MapKeyOfT { const K& operator()(const pair<K, V> kv) { return kv.first; } }; public: //.... private: hash_bucket::Hashtable<K, pair<K, V>, MapKeyOft> _ht; };

也就是说，哈希表中的模板参数T的类型到底是什么，完全却决于上层所使用容器的种类。 

而哈希结点的模板参数也应该由原来的K、V变为T：

上层容器是unordered_set时，传入的T是键值，哈希结点中存储的就是键值。上层容器是unordered_map时，传入的T是键值对，哈希结点中存储的就是键值对。

 更改模板参数后，哈希结点的定义如下：

template<class T> struct HashNode { T _data; HashNode<T>* _next; HashNode(const T& data) :_data(data) , _next(nullptr) {} };

 而我们上面给了仿函数，那么我们的下层就会调用仿函数，凡是需要辨析数据是unordered_map和unordered_set的，我们都需要使用仿函数。

后面会附加全部代码，这里举几个例子，可以自己手动改一下，比如：

KeyOFT kot; if (Find(kot(data)))//这个data需要用仿函数判断是什么数据 return false; //双层仿函数，kot判断数据类型,hs转整型 size_t hashi =hs(kot(cur->_data)) % newSize; if (kot(cur->_data) == key) 2.哈希表的默认成员函数 2.1 构造函数

哈希表中有两个成员变量，当我们实例化一个对象时：

_table会自动调用vector的默认构造函数进行初始化。_n会根据我们所给的缺省值被设置为0。 vector<Node*> _tables; // 指针数组 size_t _n = 0; // 表中存储数据个数

构造函数和上一篇博客基本类似，我们只需要设置好哈希表的大小即可。

HashTable()//构造函数 { _tables.resize(__stl_next_prime(1), nullptr); } 2.2 拷贝构造函数

哈希表在拷贝时需要进行深拷贝，否则拷贝出来的哈希表和原哈希表中存储的都是同一批结点。

哈希表的拷贝构造函数实现逻辑如下：

将哈希表的大小调整为ht._table的大小。将ht._table每个桶当中的结点一个个拷贝到自己的哈希表中。更改哈希表当中的有效数据个数。 //拷贝构造函数 HashTable(const HashTable& ht) { //1、将哈希表的大小调整为ht._table的大小 _tables.resize(ht._tables.size()); //2、将ht._table每个桶当中的结点一个个拷贝到自己的哈希表中（深拷贝） for (size_t i = 0; i < ht._tables.size(); i++) { if (ht._tables[i]) //桶不为空 { Node* cur = ht._tables[i]; while (cur) //将该桶的结点取完为止 { Node* copy = new Node(cur->_data); //创建拷贝结点 //将拷贝结点头插到当前桶 copy->_next = _tables[i]; _tables[i] = copy; cur = cur->_next; //取下一个待拷贝结点 } } } //3、更改哈希表当中的有效数据个数 _n = ht._n; } 2.3 赋值运算符重载

实现赋值运算符重载函数时，可以通过参数间接调用拷贝构造函数，之后将拷贝构造出来的哈希表和当前哈希表的两个成员变量分别进行交换即可，当赋值运算符重载函数调用结束后，拷贝构造出来的哈希表会因为出了作用域而被自动析构，此时原哈希表之前的数据也就顺势被释放了。

//赋值运算符重载函数 HashTable& operator=(HashTable ht) { //交换哈希表中两个成员变量的数据 _tables.swap(ht._tables); swap(_n, ht._n); return *this; //支持连续赋值 } 2.4 析构函数

因为哈希表当中存储的结点都是new出来的，因此在哈希表被析构时必须进行结点的释放。在析构哈希表时我们只需要依次取出非空的哈希桶，遍历哈希桶当中的结点并进行释放即可。

~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;//将桶置空 } } 3.哈希表正向迭代器的实现

哈希表的正向迭代器实际上就是对哈希结点指针进行了封装，但是由于在实现++运算符重载时，可能需要在哈希表中去寻找下一个非空哈希桶，因此每一个正向迭代器中都应该存储哈希表的地址。

 有前面迭代器实现的基础，底层结构基本都类似，只有++需要自己去实现。++运算符重载函数的实现逻辑并不是很难，我们只需要知道如何找到当前结点的下一个结点即可。

若当前结点不是当前哈希桶中的最后一个结点，则++后走到当前哈希桶的下一个结点。若当前结点是当前哈希桶的最后一个结点，则++后走到下一个非空哈希桶的第一个结点。

迭代器代码如下：

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; const HT* _ht; Node* _node; __HTIterator(Node* node, const HT* ht) :_node(node) , _ht(ht) {} Ref operator*() { return _node->_data; } Ptr 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; } 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; } };

注意： 哈希表的迭代器类型是单向迭代器，没有反向迭代器，即没有实现–运算符的重载，若是想让哈希表支持双向遍历，可以考虑将哈希桶中存储的单链表结构换为双链表结构。

4.封装后的代码

正向迭代器实现后，我们需要在哈希表的实现当中进行如下操作：

进行正向迭代器类型的typedef，需要注意的是，为了让外部能够使用typedef后的正向迭代器类型iterator，我们需要在public区域进行typedef。

由于正向迭代器中++运算符重载函数在寻找下一个结点时，会访问哈希表中的成员变量_table，而_table成员变量是哈希表的私有成员，因此我们需要将正向迭代器类声明为哈希表类的友元。

将哈希表中查找函数返回的结点指针，改为返回由结点指针和哈希表地址构成的正向迭代器。

将哈希表中插入函数的返回值类型，改为由正向迭代器类型和布尔类型所构成的键值对。

在使用迭代器时，编译器会向上查找，但我们在迭代器中定义了一个哈希表类，编译器查不到，所以我们这里会给一个前置声明。

注意：模拟实现进行编译时极有可能会出现大范围的模板报错，这时及其正常的，调整好心态，寻找bug，模拟实现unordered_map和unordered_ser的思想并不难，但写出来可能会有一堆报错，刚开始运用模板编程的途中会出现一些极小的Bug，我也找了好久，可能只是一个const的权限放的或者缩小，或者是迭代器的返回参数不匹配，模板不匹配，这些都是常有的，需要在运用中解决错误，提高大家模板编程的能力，接下来，我会附加全部代码，当下代码是可以运行的，可能也有一些小问题，欢迎大家评论区指出，一起学习。

HashTable.h #pragma once #include<unordered_set> #include<unordered_map> #include<set> #include<map> #include<string> #include<iostream> #include<vector> using namespace std; template<class K> class HashFunc { public: size_t operator()(const K& key) { return (size_t)key; } }; // 特化 template<> class HashFunc<string> { public: size_t operator()(const string& key) { size_t hash = 0; for (auto ch : key) { hash += ch; hash *= 131; } return hash; } }; //class stringHashFunc //{ //public: // size_t operator()(const string& s) // { // size_t hash = 0; // for (auto ch : s) // { // hash += ch; // hash *= 131; // } // // return hash; // } //}; namespace hash_bucket { 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 = HashFunc<K>> 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; const HT* _ht; Node* _node; __HTIterator(Node* node, const HT* ht) :_node(node) , _ht(ht) {} Ref operator*() { return _node->_data; } Ptr 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; } 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; } }; template<class K, class T,class KeyOfT,class Hash> class HashTable { template<class K, class T, class Ref, class Ptr, class KeyOfT, class Hash> friend struct __HTIterator; typedef HashNode<T> Node; public: typedef __HTIterator<K, T,T&,T*, KeyOfT, Hash> Iterator; typedef __HTIterator<K, T,const T&,const T*, KeyOfT, Hash> ConstIterator; KeyOfT kot; Hash hs; 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); } ConstIterator Begin() const { for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; if (cur) { return ConstIterator(cur, this); } } return End(); } ConstIterator End() const//const HashTable* { return ConstIterator(nullptr, this); } HashTable()//构造函数 { _tables.resize(__stl_next_prime(1), nullptr); } //拷贝构造函数 HashTable(const HashTable& ht) { //1、将哈希表的大小调整为ht._table的大小 _tables.resize(ht._tables.size()); //2、将ht._table每个桶当中的结点一个个拷贝到自己的哈希表中（深拷贝） for (size_t i = 0; i < ht._tables.size(); i++) { if (ht._tables[i]) //桶不为空 { Node* cur = ht._tables[i]; while (cur) //将该桶的结点取完为止 { Node* copy = new Node(cur->_data); //创建拷贝结点 //将拷贝结点头插到当前桶 copy->_next = _tables[i]; _tables[i] = copy; cur = cur->_next; //取下一个待拷贝结点 } } } //3、更改哈希表当中的有效数据个数 _n = ht._n; } //赋值运算符重载函数 HashTable& operator=(HashTable ht) { //交换哈希表中两个成员变量的数据 _tables.swap(ht._tables); swap(_n, ht._n); return *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;//将桶置空 } } inline unsigned long __stl_next_prime(unsigned long n) { // Note: assumes long is at least 32 bits. 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 }; const unsigned long* first = __stl_prime_list; const unsigned long* last = __stl_prime_list + __stl_num_primes; const unsigned long* pos = lower_bound(first, last, n); return pos == last ? *(last - 1) : *pos; } pair<Iterator,bool> Insert(const T& data) { Iterator it = Find(kot(data)); if (it != End()) return { it, false }; // 负载因子到1就扩容 if (_n == _tables.size()) { size_t newSize = __stl_next_prime(_tables.size() + 1); vector<Node*> newtables(newSize, nullptr); // 遍历旧表，把旧表的节点挪动到新表 for (size_t i = 0; i < _tables.size(); i++) { Node* cur = _tables[i]; while (cur) { Node* next = cur->_next; // cur头插到新表 size_t hashi = hs(kot(cur->_data)) % newSize; cur->_next = newtables[hashi]; 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 {Iterator(newnode,this),true}; } Iterator Find(const K& key) { size_t hashi =hs(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) { size_t hashi = hs(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; } prev = cur; cur = cur->_next; } return false; } private: //vector<list<pair<K, V>>> _tables; vector<Node*> _tables; // 指针数组 size_t _n = 0; // 表中存储数据个数 }; } unordered_map.h #pragma once #include "HashTable.h" namespace my_unmap { 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 = _ht.Insert(make_pair( key,V())); return ret.first->second; } iterator find(const K& key) { return _ht.Find(key); } void erase(const K& key) { _ht.Erase(key); } private: hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT,Hash> _ht; }; void Print(const unordered_map<string, string>& dict) { unordered_map<string, string>::const_iterator it = dict.begin(); while (it != dict.end()) { //it->first += 'x'; //it->second += 'x'; cout << it->first << " " << it->second; ++it; } cout << endl; } void test_map1() { //unordered_map<string, string> dict; //unordered_map<string, string>::iterator it = dict.begin(); //while (it != dict.end()) //{ // //it->first += 'x'; // it->second += 'x'; // cout << it->first << " " << it->second; // ++it; //} //cout << endl; string arr[] = { "西瓜", "榴莲","苹果", "苹果", "榴莲", "西瓜", "西瓜", "西瓜", "西瓜", "香蕉", "香蕉", "香蕉" }; unordered_map<string, int> countMap; for (const auto& str : arr) { countMap[str]++; } for (const auto& e : countMap) { cout << e.first << ":" << e.second << endl; } cout << endl; countMap.erase("西瓜");//删除所有西瓜 for (const auto& e : countMap) { cout << e.first << ":" << e.second << endl; } cout << endl; } } unordered_set.h #pragma once #include "HashTable.h" namespace my_unset { 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); } iterator find(const K& key) { return _ht.Find(key); } void erase(const K& key) { _ht.Erase(key); } private: hash_bucket::HashTable<K,const K,SetKeyOfT,Hash> _ht; }; void Print(const unordered_set<int>& s) { unordered_set<int>::const_iterator it = s.begin(); while (it != s.end()) { // *it += 1; cout << *it << " "; ++it; } cout << endl; } void test_set1() { unordered_set<int> s; s.insert(1); s.insert(12); s.insert(54); s.insert(107); unordered_set<int>::iterator it = s.begin(); while (it != s.end()) { // *it += 1; cout << *it << " "; ++it; } cout << endl; /*for (auto e : s) { cout << *e << " "; }*/ } }

---

本篇博客到此结束，欢迎大家评论区留言~