【C++：哈希表封装】用哈希表封装unordered_map和unordered_set

🔥艾莉丝努力练剑：个人主页

❄专栏传送门：《C语言》、《数据结构与算法》、C/C++干货分享&学习过程记录、Linux操作系统编程详解、笔试/面试常见算法：从基础到进阶、测试开发要点全知道

⭐️为天地立心，为生民立命，为往圣继绝学，为万世开太平

🎬艾莉丝的简介：

🎬艾莉丝的C++专栏简介：

C++的两个参考文档

 老朋友（非官方文档）：cplusplus

官方文档（同步更新）：C++ 官方参考文档

set和multiset的参考文档：set、multiset

map和multimap的参考文档：map、multimap

unordered_set和unordered_multiset的参考文档：unordered_set、unordered_multiset

unordered_map和unordered_multimap的参考文档：

unordered_map、unordered_multimap

1  ~>  浅解源码和框架

1.1  浅看源码

SGI-STL30版本源代码中没有unordered_map和unordered_set，SGI-STL30版本是C++11之前的STL版本，这两个容器是C++11之后才更新的，但是SGI-STL30实现了哈希表，只容器的名字是hash_map和hash_set，他是作为非标准的容器出现的，非标准是指非C++标准规定必须实现的，

1.2  框架

源代码在hash_map/hash_set / stl_hash_map / stl_hash_set / stl_hashtable.h中hash_map和hash_set的实现结构框架核心部分截取出来如下：

1.2.1  stl_hash_set

// stl_hash_set template <class Value, class HashFcn = hash<Value>, class EqualKey = equal_to<Value>, class Alloc = alloc> class hash_set { private: typedef hashtable<Value, Value, HashFcn, identity<Value>, EqualKey, Alloc> ht; ht rep; public: typedef typename ht::key_type key_type; typedef typename ht::value_type value_type; typedef typename ht::hasher hasher; typedef typename ht::key_equal key_equal; typedef typename ht::const_iterator iterator; typedef typename ht::const_iterator const_iterator; hasher hash_funct() const { return rep.hash_funct(); } key_equal key_eq() const { return rep.key_eq(); } };

1.2.2  stl_hash_map

// stl_hash_map template <class Key, class T, class HashFcn = hash<Key>, class EqualKey = equal_to<Key>, class Alloc = alloc> class hash_map { private: typedef hashtable<pair<const Key, T>, Key, HashFcn, select1st<pair<const Key, T> >, EqualKey, Alloc> ht; ht rep; public: typedef typename ht::key_type key_type; typedef T data_type; typedef T mapped_type; typedef typename ht::value_type value_type; typedef typename ht::hasher hasher; typedef typename ht::key_equal key_equal; typedef typename ht::iterator iterator; typedef typename ht::const_iterator const_iterator; };

1.2.3  stl_hashtable.h

// stl_hashtable.h template <class Value, class Key, class HashFcn, class ExtractKey, class EqualKey, class Alloc> class hashtable { public: typedef Key key_type; typedef Value value_type; typedef HashFcn hasher; typedef EqualKey key_equal; private: hasher hash; key_equal equals; ExtractKey get_key; typedef __hashtable_node<Value> node; vector<node*, Alloc> buckets; size_type num_elements; public: typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator; pair<iterator, bool> insert_unique(const value_type& obj); const_iterator find(const key_type& key) const; }; template <class Value> struct __hashtable_node { __hashtable_node* next; Value val; };

我们这里就不画图分析了，通过源码可以看到，结构上hash_map和hash_set跟map和set的完全类似，复用同一个hashtable实现key和key / value结构，hash_set传给hash_table的是两个key，hash_map传给hash_table的是pair<const key , value>；

需要注意的是源码里面跟map / set源码类似，命名风格比较乱，并且这里比map和set还乱，hash_set模板参数居然用的Value命名，hash_map用的是Key和T命名，可见大佬有时写代码也不规范嘿嘿。下面我们会自己实现一下，就按自己的风格来喽。

2  ~>  模拟实现unordered_map和unordered_set

2.1  

2.1.1  复用哈希表的框架，并支持insert

参考源码框架，unordered_map和unordered_set复用之前我们实现的哈希表。

这里相比源码调整一下，key参数就用K，value参数就用V，哈希表中的数据类型，我们使用T。

其次跟map和set相比而言unordered_map和unordered_set的模拟实现类结构更复杂一点，但是
大框架和思路是完全类似的。因为HashTable实现了泛型不知道T参数导致是K，还是pair<K,V>，那么insert内部进行插入时要用K对象转换成整形取模和K比较相等，因为pair的value不参与计算取模，且默认支持的是key和value一起比较相等，我们需要时的任何时候只需要比较K对象，所以我们在unordered_map和unordered_set层分别实现一个MapKeyOfT和SetKeyOfT的仿函数传给
HashTable的KeyOfT，然后HashTable中通过KeyOfT仿函数取出T类型对象中的K对象，再转换成
整形取模和K比较相等。

2.1.2  实现迭代器的思路

iterator实现的大框架跟list的iterator思路一致，用一个类型封装结点的指针，再通过重载运算符实现，迭代器像指针一样访问的行为，要注意的是哈希表的迭代器是单向迭代器。

难点在于operator++的实现。iterator中有一个指向结点的指针，如果当前桶下面还有结点，则结点的指针指向下一个结点即可。如果当前桶走完了，则需要想办法计算找到下一个桶。这里的难点是反而是结构设计的问题，参考上面的源码，我们可以看到iterator中除了有结点的指针，还有哈希表对象的指针，这样当前桶走完了，要计算下一个桶就相对容易多了，用key值计算出当前桶位置，依次往后找下一个不为空的桶，实现如下——

begin()返回第一个桶中第一个节点指针构造的迭代器，这里end()返回迭代器可以用空表示。

unordered_set的迭代器也不支持修改，把unordered_set的第二个模板参数改成const K即可：

HashTable<K，const K，SetKeyOfT，Hash>_ht;

unordered_map的iterator不支持修改key但是可以修改value，我们把unordered_map的第二个
模板参数pair的第一个参数改成const K即可——

HashTable<K，pair<constK，V>，MapKeyOfT，Hash> _ht;

当然，支持完整的迭代器还有很多细节需要修改。

2.1.3  map支持[ ]

unordered_map要支持[]主要需要修改insert返回值支持，修改HashTable中的insert返回值为：

pair<Iterator，bool> Insert(const T& data)；

有了insert，支持[ ]实现就很简单了。

2.2  模拟实现

2.2.1  模拟实现unordered_set

2.2.2  模拟实现unordered_map

完整代码示例与实践演示

HashTable.h：

#pragma once #include<vector> 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 }; inline unsigned long __stl_next_prime(unsigned long n) { const unsigned long* first = __stl_prime_list; const unsigned long* last = __stl_prime_list + __stl_num_primes; // >= n const unsigned long* pos = lower_bound(first, last, n); return pos == last ? *(last - 1) : *pos; } template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; // 特化 template<> struct HashFunc<string> { size_t operator()(const string& key) { size_t hash = 0; for (auto ch : key) { 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> 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* _pht; HTIterator(Node* node, const HT* pht) :_node(node) , _pht(pht) {} 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)) % _pht->_tables.size(); ++hashi; while (hashi < _pht->_tables.size()) { if (_pht->_tables[hashi]) // 找到下一个不为空的桶 { _node = _pht->_tables[hashi]; break; } else { ++hashi; } } if (hashi == _pht->_tables.size()) // 最后一个桶走完了，要++到end()位置 { // end()中，_node是空 _node = nullptr; } } return *this; } bool operator!=(const Self & s) const { return _node != s._node; } bool operator==(const Self & s) const { return _node == s._node; } }; //Hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT> _ht; //Hash_bucket::HashTable<K, K, SetKeyOfT> _ht; 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; Iterator Begin() { if (_n == 0) { return End(); } 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 { if (_n == 0) { return End(); } 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); } ////确保KeyofT的operator()是const的 //struct SetKeyOfT //{ // const K& operator()(const K& key) const // { // return key; // } //}; ////确保KeyofT的operator()是const的 //struct MapKeyOfT //{ // const K& operator()(const pair<K, V>& kv) const // { // return key; // } //}; HashTable() :_tables(__stl_next_prime(1),nullptr) ,_n(0) { } ~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; } _n = 0; } pair<Iterator, bool> Insert(const T& data) { KeyOfT kot; if (auto it = Find(kot(data)); it != End()) return { it,false }; Hash hs; // 负载因子 == 1就开始扩容 if (_n == _tables.size()) { //HashTable<K, V> newht; //newht._tables.resize(_tables.size() * 2); //for (size_t i = 0; i < _tables.size(); i++) //{ // // 遍历旧表，旧表数据插入到newht // Node* cur = _tables[i]; // while (cur) // { // newht.Insert(cur->_kv); // cur = cur->_next; // } //} //_tables.swap(newht._tables); std::vector<Node*> newtables(__stl_next_prime(_tables.size() + 1), nullptr); 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)) % newtables.size(); 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) { KeyOfT kot; Hash hs; size_t hashi = hs(key) % _tables.size(); Node* cur = _tables[hashi]; while (cur) { if (kot(cur->_data) == key) { return { cur,this }; } cur = cur->_next; } return { nullptr,this }; } bool Erase(const K& key) { KeyOfT kot; Hash hs; 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; } --_n; // _n是有效数据个数，每次删除之后都要减减 delete cur; return true; } prev = cur; cur = cur->_next; } return false; } private: std::vector<Node*> _tables; // 指针数组 size_t _n; // 存储的有效数据个数 //std::vector<std::list<K, V>> _tables; // 不是实现不了，而是这种实现太绕了，而且比较抽象，现阶段对我们来说还是太难了 }; }

unordered_set.h：

#pragma once #include"HashTable.h" namespace jqj { 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); } bool erase(const K& key) { return _ht.Erase(key); } private: Hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht; }; }

unordered_map.h：

#pragma once #include"HashTable.h" namespace jqj { 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(pair<const K,V>& kv) 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() }); // 测试类型不匹配 pair<iterator, bool> ret = _ht.Insert(make_pair(key, V())); return ret.first->second; } iterator find(const K & key) { return _ht.Find(key); } //iterator find(pair<const K,V>& kv) //{ // return _ht.Find(key); //} bool erase(const K & key) { return _ht.Erase(key); } //bool erase(pair<const K,V>& kv) //{ // return _ht.Erase(key); //} private: //Hash_bucket::HashTable<K, const K, MapKeyOfT, Hash> _ht; Hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht; }; }

Test.cpp：

#define _CRT_SECURE_NO_WARNINGS 1 #include<iostream> #include<unordered_map> using namespace std; #include"unordered_map.h" #include"unordered_set.h" void Print(const jqj::unordered_set<int>& s) { jqj::unordered_set<int>::const_iterator it = s.begin(); while (it != s.end()) { // it* = 1; // 迭代器不能被修改 cout << *it << " "; ++it; } cout << endl; } int main() { jqj::unordered_set<int> us; us.insert(3); us.insert(1000); us.insert(2); us.insert(102); us.insert(2111); us.insert(22); jqj::unordered_set<int>::iterator it = us.begin(); while (it != us.end()) { //*it = 1; // 不能被修改 cout << *it << " "; ++it; } cout << endl; Print(us); jqj::unordered_map<string, string> dict; dict.insert({ "string","" }); dict.insert({ "string","" }); dict.insert({ "left","左边" }); dict.insert({ "right","右边" }); // 修改 dict["left"] = "左边"; // 插入 dict["insert"]; // 插入并且修改 dict["map"] = "地图"; for (auto& [k, v] : dict) { //k += 'x'; //v += 'x'; cout << k << ":" << v << endl; } return 0; }

运行结果

博主手记

这是博主的学习笔记，大家可以看看——

结尾

uu们，本文的内容到这里就全部结束了，艾莉丝再次感谢您的阅读！

往期回顾：

【C++：哈希表】从哈希冲突到负载因子：熟悉哈希表的核心机制

结语：既然都看到这里啦！请大佬不要忘记给博主来个“一键四连”哦！ 

🗡博主在这里放了一只小狗，大家看完了摸摸小狗放松一下吧！🗡

૮₍ ˶ ˊ ᴥ ˋ˶₎ა