系统学习C++-第二十一讲-用哈希表封装 myunordered_map 和 myunordered_set

系统学习C++-第二十一讲-用哈希表封装 myunordered_map 和 myunordered_set

• 1. 源码及框架分析
• 2. 模拟实现 unordered_map 和 unordered_set
  • 2.1 实现出复用哈希表的框架，并支持 insert
  • 2.2 支持 iterator 的实现
  • 2.3 map 支持 ` [] `
  • 2.4 unordered_map 和 unordered_set 代码实现

1. 源码及框架分析

SGI-STL30 版本源代码中没有 unordered_map 和 unordered_set ，SGI-STL30 版本是 C++11 之前的STL版本，

这两个容器是 C++11 之后才更新的。但是 SGI-STL30 实现了哈希表，只是容器的名字是 hash_map 和 hash_set ，

他是作为非标准的容器出现的，非标准是指非 C++ 标准规定必须实现的，

源代码在hash_map/hash_set/stl_hash_map/stl_hash_set/stl_hashtable.h 中

hash_map 和 hash_set 的实现结构框架核心部分截取出来如下：

// stl_hash_settemplate<classValue,classHashFcn= hash<Value>,classEqualKey= equal_to<Value>,classAlloc= alloc>classhash_set{private:typedef hashtable<Value, Value, HashFcn, identity<Value>, EqualKey, Alloc> ht; ht rep;public:typedeftypenameht::key_type key_type;typedeftypenameht::value_type value_type;typedeftypenameht::hasher hasher;typedeftypenameht::key_equal key_equal;typedeftypenameht::const_iterator iterator;typedeftypenameht::const_iterator const_iterator; hasher hash_funct()const{return rep.hash_funct();} key_equal key_eq()const{return rep.key_eq();}};// stl_hash_maptemplate<classKey,classT,classHashFcn= hash<Key>,classEqualKey= equal_to<Key>,classAlloc= alloc>classhash_map{private:typedef hashtable<pair<const Key, T>, Key, HashFcn, select1st<pair<const Key, T>>, EqualKey, Alloc> ht; ht rep;public:typedeftypenameht::key_type key_type;typedef T data_type;typedef T mapped_type;typedeftypenameht::value_type value_type;typedeftypenameht::hasher hasher;typedeftypenameht::key_equal key_equal;typedeftypenameht::iterator iterator;typedeftypenameht::const_iterator const_iterator;};// stl_hashtable.htemplate<classValue,classKey,classHashFcn,classExtractKey,classEqualKey,classAlloc>classhashtable{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<classValue>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 实现出复用哈希表的框架，并支持 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 比较相等，具体细节参考如下代码实现。

// MyUnorderedSet.hnamespace My_UnorderedSet {template<classK,classHash= HashFunc<K>>classunordered_set{structSetKeyOfT{const K&operator()(const K& key){return key;}};public:boolinsert(const K& key){return _ht.Insert(key);}private: hash_bucket::HashTable<K, K, SetKeyOfT, Hash> _ht;};}// MyUnorderedMap.hnamespace My_UnorderedMap {template<classK,classV,classHash= HashFunc<K>>classunordered_map{structMapKeyOfT{const K&operator()(const pair<K, V>& kv){return kv.first;}};public:boolinsert(const pair<K, V>& kv){return _ht.Insert(kv);}private: hash_bucket::HashTable<K, pair<K, V>, MapKeyOfT, Hash> _ht;};}// HashTable.htemplate<classK>structHashFunc{ size_t operator()(const K& key){return(size_t)key;}};namespace hash_bucket {template<classT>structHashNode{ T _data; HashNode<T>* _next;HashNode(const T& data):_data(data),_next(nullptr){}};// 实现步骤： // 1、实现哈希表 // 2、封装unordered_map和unordered_set的框架 解决KeyOfT // 3、iterator // 4、const_iterator // 5、key不⽀持修改的问题 // 6、operator[] template<classK,classT,classKeyOfT,classHash>classHashTable{typedef HashNode<T> Node;inlineunsignedlong__stl_next_prime(unsignedlong n){staticconstint __stl_num_primes =28;staticconstunsignedlong __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};constunsignedlong* first = __stl_prime_list;constunsignedlong* last = __stl_prime_list + __stl_num_primes;constunsignedlong* pos =lower_bound(first, last, n);return pos == last ?*(last -1):*pos;}public:HashTable(){ _tables.resize(__stl_next_prime(_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;}}boolInsert(const T& data){ KeyOfT kot;if(Find(kot(data)))returnfalse; Hash hs; size_t hashi =hs(kot(data))% _tables.size();// 负载因⼦==1扩容 if(_n == _tables.size()){ vector<Node*>newtables(__stl_next_prime(_tables.size()),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);}// 头插  Node* newnode =newNode(data); newnode->_next = _tables[hashi]; _tables[hashi]= newnode;++_n;returntrue;}private: vector<Node*> _tables;// 指针数组  size_t _n =0;// 表中存储数据个数 };}

2.2 支持 iterator 的实现

iterator 核心源代码：

template<classValue,classKey,classHashFcn,classExtractKey,classEqualKey,classAlloc>struct__hashtable_iterator{typedef hashtable<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> hashtable;typedef __hashtable_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> iterator;typedef __hashtable_const_iterator<Value, Key, HashFcn, ExtractKey, EqualKey, Alloc> const_iterator;typedef __hashtable_node<Value> node;typedef forward_iterator_tag iterator_category;typedef Value value_type; node* cur; hashtable* ht;__hashtable_iterator(node* n, hashtable* tab):cur(n),ht(tab){}__hashtable_iterator(){} reference operator*()const{return cur->val;}#ifndef__SGI_STL_NO_ARROW_OPERATOR pointer operator->()const{return&(operator*());}#endif/* __SGI_STL_NO_ARROW_OPERATOR */ iterator&operator++(); iterator operator++(int);booloperator==(const iterator& it)const{return cur == it.cur;}booloperator!=(const iterator& it)const{return cur != it.cur;}};template<classV,classK,classHF,classExK,classEqK,classA> __hashtable_iterator<V, K, HF, ExK, EqK, A>& __hashtable_iterator<V, K, HF, ExK, EqK, A>::operator++(){const node* old = cur; cur = cur->next;if(!cur){ size_type bucket = ht->bkt_num(old->val);while(!cur &&++bucket < ht->buckets.size()) cur = ht->buckets[bucket];}return*this;}

iterator 实现思路分析：

• iterator 实现的大框架跟 list 的 iterator 思路是一致的，用一个类型封装结点的指针，再通过重载运算符实现，迭代器像指针一样访问的行为，要注意的是哈希表的迭代器是单向迭代器。
• 这里的难点是 operator++ 的实现。iterator 中有一个指向结点的指针，如果当前桶下面还有结点，则结点的指针指向下一个结点即可。如果当前桶走完了，则需要想办法计算找到下一个桶。这里的难点是反而是结构设计的问题，参考上面的源码，我们可以看到iterator 中除了有结点的指针，还有哈希表对象的指针，这样当前桶走完了，要计算下⼀个桶就相对容易多了，用 key 值计算出当前桶位置，依次往后找下一个不为空的桶即可。
• begin() 返回第一个桶中第一个节点指针构造的迭代器，这里 end() 返回迭代器可以用空表示。
• unordered_set 的 iterator 也不支持修改，我们把 unordered_set 的第⼆个模板参数改成 const K 即可，
  HashTable<K, const K, SetKeyOfT, Hash> _ht;
• unordered_map 的 iterator 不支持修改 key 但是可以修改 value ，我们把 unordered_map 的第二个模板参数 pair 的第一个参数改成 const K 即可，HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;
• 支持完整的迭代器还有很多细节需要修改，具体参考下面题的代码。

2.3 map 支持 []

• unordered_map 要支持 [] 主要需要修改 insert 返回值支持，修改 HashTable 中的 insert 返回值为
  pair<Iterator, bool> Insert(const T& data)
• 有了 insert 支持 [] 实现就很简单了，具体参考下面代码实现

2.4 unordered_map 和 unordered_set 代码实现

//HashTable.h#pragmaonce#include<iostream>#include<vector>usingnamespace std;inlineunsignedlong__stl_next_prime(unsignedlong n){// Note: assumes long is at least 32 bits.staticconstint __stl_num_primes =28;staticconstunsignedlong __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};constunsignedlong* first = __stl_prime_list;constunsignedlong* last = __stl_prime_list + __stl_num_primes;// >=constunsignedlong* pos =lower_bound(first, last, n);return pos == last ?*(last -1):*pos;}template<classK>structHashFunc{ size_t operator()(const K& key)const{return(size_t)key;}};// 特化template<>structHashFunc<string>{ size_t operator()(const string& key)const{ size_t hash =0;for(auto ch : key){ hash += ch; hash *=131;}return hash;}};namespace open_adrress {enumState{ EXIST, EMPTY, DELETE };template<classK,classV>structHashData{ pair<K, V> _kv; State _state = EMPTY;};//struct StringHashFunc//{// size_t operator()(const string& key) const// {// size_t hash = 0;// for (auto ch : key)// {// hash += ch;// hash *= 131;// }//// return hash;// }//};template<classK,classV,classHash= HashFunc<K>>classHashTable{public:HashTable(size_t n =__stl_next_prime(0)):_tables(n),_n(0){}boolInsert(const pair<K, V>& kv){if(Find(kv.first))returnfalse;// 扩容，负载因子==0.7就扩容if((double)_n /(double)_tables.size()>=0.7){//vector<HashData<K, V>> newtables;//newtables.resize(_tables.size() * 2);//// 遍历旧表，将旧表的数据全部重新映射到新表//for (size_t i = 0; i < _tables.size(); i++)//{// if (_tables[i]._state == EXIST)// {// //...// }//}//_tables.swap(newtables);//HashTable<K, V> newht(_tables.size() * 2); HashTable<K, V, Hash>newht(__stl_next_prime(_tables.size()+1));// 遍历旧表，将旧表的数据全部重新映射到新表for(size_t i =0; i < _tables.size(); i++){if(_tables[i]._state == EXIST){ newht.Insert(_tables[i]._kv);}} _tables.swap(newht._tables);} Hash hs; size_t hash0 =hs(kv.first)% _tables.size(); size_t hashi = hash0; size_t i =1;// 线性探测while(_tables[hashi]._state == EXIST){ hashi += i * i; i++; hashi %= _tables.size();} _tables[hashi]._kv = kv; _tables[hashi]._state = EXIST;++_n;returntrue;} HashData<K, V>*Find(const K& key){ Hash hs; size_t hash0 =hs(key)% _tables.size(); size_t hashi = hash0; size_t i =1;while(_tables[hashi]._state != EMPTY){if(_tables[hashi]._state == EXIST && _tables[hashi]._kv.first == key){return&_tables[hashi];}// 线性探测 hashi += i; i++; hashi %= _tables.size();}returnnullptr;}boolErase(const K& key){ HashData<K, V>* ret =Find(key);if(ret){ ret->_state = DELETE;--_n;returntrue;}else{returnfalse;}}private: vector<HashData<K, V>> _tables; size_t _n;// 实际存储的数据个数};voidTestHashTable1(){int a[]={19,30,5,36,13,20,21,12}; HashTable<int,int> ht;for(auto e : a){ ht.Insert({ e, e });} cout << ht.Find(20)<< endl; cout << ht.Find(30)<< endl; ht.Erase(30); cout << ht.Find(20)<< endl; cout << ht.Find(30)<< endl; ht.Insert({-3,3}); ht.Insert({13,3}); ht.Insert({33,3}); ht.Insert({323,3}); ht.Insert({23,3});for(size_t i =0; i <100; i++){ ht.Insert({rand(),i });}}structpairHash{ size_t operator()(const pair<int,int>& kv)const{ size_t hash =0; hash += kv.first; hash *=131; hash += kv.second; hash *=131; cout << hash << endl;return hash;}};// 21:07voidTestHashTable2(){//HashTable<string, string, StringHashFunc> dict; HashTable<string, string> dict; dict.Insert({"sort","排序"}); dict.Insert({"left","左边"}); dict.Insert({"sort","xxx"}); unordered_map<pair<int,int>,int, pairHash> um; um.insert({{1,3},3}); um.insert({{3,1},3});/*StringHashFunc hf; cout << hf("abcd") <<endl; cout << hf("bcad") << endl; cout << hf("aadd") << endl;*/}}namespace hash_bucket {template<classT>structHashNode{ T _data; HashNode<T>* _next;HashNode(const T& data):_data(data),_next(nullptr){}};// 前置声明template<classK,classT,classKeyOfT,classHash>classHashTable;template<classK,classT,classRef,classPtr,classKeyOfT,classHash>structHTIterator{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){} Self&operator++(){if(_node->_next){// 当前桶还没走完 _node = _node->_next;}else// 21:05{// 当前桶走完了，需要找下一个不为空的桶里面的第一个节点 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;}++hashi;}if(hashi == _pht->_tables.size()){// 所有桶都走完了，置为end() _node =nullptr;}}return*this;} Ref operator*(){return _node->_data;} Ptr operator->(){return&_node->_data;}booloperator!=(const Self& s)const{return _node != s._node;}booloperator==(const Self& s)const{return _node == s._node;}};template<classK,classT,classKeyOfT,classHash>classHashTable{// 友元声明template<classK,classT,classRef,classPtr,classKeyOfT,classHash>friendstructHTIterator;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)returnEnd();for(size_t i =0; i < _tables.size(); i++){if(_tables[i]){returnIterator(_tables[i],this);}}returnEnd();} Iterator End(){returnIterator(nullptr,this);} ConstIterator Begin()const{if(_n ==0)returnEnd();for(size_t i =0; i < _tables.size(); i++){if(_tables[i]){returnConstIterator(_tables[i],this);}}returnEnd();} ConstIterator End()const{returnConstIterator(nullptr,this);}HashTable(size_t n =__stl_next_prime(0)):_tables(n,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;}} 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),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))% 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 =newNode(data); newnode->_next = _tables[hashi]; _tables[hashi]= newnode;++_n;return{Iterator(newnode,this),true};} Iterator Find(const K& key){ Hash hs; KeyOfT kot; size_t hashi =hs(key)% _tables.size(); Node* cur = _tables[hashi];while(cur){if(kot(cur->_data)== key)returnIterator(cur,this); cur = cur->_next;}returnEnd();}boolErase(const K& key){ Hash hs; size_t hashi =hs(key)% _tables.size(); KeyOfT kot; 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;delete cur;returntrue;} prev = cur; cur = cur->_next;}returnfalse;}private: vector<Node*> _tables; size_t _n;// 实际存储有效数据个数};//unordered_set.h#include"HashTable.h"namespace My_UnorderedSet {template<classK,classHash= HashFunc<K>>classunordered_set{structSetKeyOfT{const K&operator()(const K& key){return key;}};public:typedeftypenamehash_bucket::HashTable<K,const K, SetKeyOfT, Hash>::Iterator iterator;typedeftypenamehash_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);}boolerase(const K& key){return _ht.Erase(key);}private: hash_bucket::HashTable<K,const K, SetKeyOfT, Hash> _ht;};}//unordered_map.h#include"HashTable.h"namespace My_UnorderedMap {template<classK,classV,classHash= HashFunc<K>>classunordered_map{structMapKeyOfT{const K&operator()(const pair<K, V>& kv){return kv.first;}};public:typedeftypenamehash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::Iterator iterator;typedeftypenamehash_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);} iterator find(const K& key){return _ht.Find(key);}boolerase(const K& key){return _ht.Erase(key);} 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;};}