哈希封装“unordered_set·map“

本文与对set·map的封装高度相似，可以参考我之前的对set·map封装的文章：

链接：（没看过的话就点点我吧😚😚😚😚😚😚😚😚😚）https://blog.csdn.net/Small_entreprene/article/details/143026089?fromshare=blogdetail&sharetype=blogdetail&sharerId=143026089&sharerefer=PC&sharesource=Small_entreprene&sharefrom=from_link正片开始：

源码及框架分析

由于源码整体来说比较复杂，我们截取框架部分：

// 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(); }
};
// 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;
};
// 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命名，可⻅⼤佬有时写代码也不规范，乱弹琴。下⾯我们模拟⼀份⾃⼰的出来，就按⾃⼰的⻛格⾛了。

模拟实现unordered_set·map 

复用哈希表的框架的实现

复用的哈希表泛型化：

• 参考源码框架，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⽐较相等，具体细节参考如下代码实现：

框架（仿函数：这里实现XXXKeyofT）（后面会增添HashImitFunc仿函数等接口）

unordered_set：

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

unordered_map：

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

支持iterator的实现

iterator核⼼源代码

template <class Value, class Key, class HashFcn,class ExtractKey, class EqualKey, class Alloc>
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_OPERATORpointer operator->() const { return &(operator*()); }
#endif /* __SGI_STL_NO_ARROW_OPERATOR */iterator& operator++();iterator operator++(int);bool operator==(const iterator& it) const { return cur == it.cur; }bool operator!=(const iterator& it) const { return cur != it.cur; }
};
template <class V, class K, class HF, class ExK, class EqK, class A>
__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;
• ⽀持完整的迭代器还有很多细节需要修改，具体参考下⾯题的代码：

// 前置声明：HTIterator会向前查找HashTable：因为相互依赖
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;//iterator的内容Node* _node;const HT* _ht;//const权限可以缩小，为了实现const迭代器HTIterator(Node* node, const HT* ht):_node(node), _ht(ht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}Self& operator++(){if (_node->_next){// 当前桶还有数据，走到当前桶下一个节点_node = _node->_next;}else{// 当前桶走完了，找下一个不为空的桶KeyOfT kot;Hash hash;size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();//_tables为私有成员，需要友元声明++hashi;while (hashi < _ht->_tables.size()){_node = _ht->_tables[hashi];if (_node)break;else++hashi;//记得++，不然就死循环了}// 所有桶都走完了，end()给的空标识的_nodeif (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}
};

 map⽀持[]的实现

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

V& operator[](const K& key)
{pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));return ret.first->second;
}

整体的代码实现：

HashTable.h

#pragma once
#include<iostream>
#include<vector>
#include<string>
using namespace std;namespace open_address
{enum State{EXIST,//存在EMPTY,//停止DELETE//继续往后找，避免删除冲突之后，与其冲突的值找不到了，造成误判};template<class K, class V>struct HashData{pair<K, V> _kv;State _state = EMPTY;};//哈希仿函数template<class K>struct HashImitFunc{size_t operator()(const K& key){return (size_t)key;//对于自定义类型，string等就不行了}};//特化//偏特化template < >struct HashImitFunc < string>{// 参考：BKDR_Hash// 字符串转换成整形，可以把字符ascii码相加即可// 但是直接相加的话，类似"abcd"和"bcad"这样的字符串计算出是相同的// 这⾥我们使⽤BKDR哈希的思路，⽤上次的计算结果去乘以⼀个质数再加上下一个字符的ASCLL码值，这个质数⼀般是131等效果会⽐较好// 为了还是为了减少哈希冲突size_t operator()(const string& key){size_t hash = 0;for (auto e : key){hash *= 131;hash += e;}return hash;}};template<class K, class V, class Hash = HashImitFunc<K>>//加一个仿函数Hash，实现泛型编程，解决float等的取模问题class HashTable{public:HashTable():_tables(__stl_next_prime(0)), _n(0){}//实现更好的扩容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;}//插入bool Insert(const pair<K, V>& kv){//实现不冗余if (Find(kv.first)){return false;}//负载因子>=0.7进行扩容操作//这里要注意一下整数/整数是向下取整，应该将其中一个强制类型转换成浮点数//也可以前一个数*10，0.7改成7if (_n * 10 / _tables.size() >= 7){//vector<HashData<K, V>> newtables(_tables.size() * 2);//for (auto& data : _tables)//{//	//旧表的数据映射到新表//	if (data._state == EXIST)//	{//		size_t hash0 = data.first % _tables.size();//		//......//	}//}//_tables.swap(newtables);//下面我们使用一个比较妙的扩容逻辑HashTable<K, V, Hash> newht;//sgi版本//要+1，不然有坑，会造成扩容失败newht._tables.resize(__stl_next_prime(_tables.size() + 1));//Jave版本/*++_m;newht._tables.resize(pow(2, _m));*/for (auto& data : _tables){//旧表的数据映射到新表if (data._state == EXIST){newht.Insert(data._kv);//这样线性探测，二次探测等的执行就可以一体化了,就是一种复用的思想}}_tables.swap(newht._tables);//赋值也可以，但是赋值是一种深拷贝，消耗比较高}Hash hash;size_t hash0 = hash(kv.first) % _tables.size();size_t hashi = hash0;size_t i = 1;//但是如果这个表满了，就会造成死循环，所以进行了以上的扩容while (_tables[hashi]._state == EXIST){//线性探测hashi = (hash0 + i) % _tables.size();++i;}_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n;return true;}//查找HashData<K, V>* Find(const K& key){Hash hash;size_t hash0 = hash(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 = (hash0 + i) % _tables.size();++i;}return nullptr;}//删除bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){ret->_state = DELETE;return true;}else{return false;}}private:vector<HashData<K, V>> _tables;//其实本质就是vector<pair<K, V>> _table;  这看起来可行，但是实际上在对于删除操作后的查找操作可能会造成查找失败，需要再存一个状态标识size_t _n = 0;//记录数据个数//从这体会：//为什么哈希也叫散列？//因为数据是由于哈希函数造成的分散状态的存放，vector的size()并不能真正代表数据的个数};
}namespace hash_bucket
{template<class K>struct HashImitFunc{size_t operator()(const K& key){return (size_t)key;}};template<>struct HashImitFunc<string>{size_t operator()(const string& s){// BKDRsize_t hash = 0;for (auto ch : s){hash += ch;hash *= 131;}return hash;}};template<class T>//表下挂节点struct HashNode{T _data;//可以使用双向链表，也可以使用单链表，这里我们和库里面一样使用单链表//这也是为什么unordered_map的迭代器是单向迭代器HashNode* _next;HashNode(const T& data):_data(data), _next(nullptr){}};// 前置声明：HTIterator会向前查找HashTable：因为相互依赖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;//iterator的内容Node* _node;const HT* _ht;//const权限可以缩小，为了实现const迭代器HTIterator(Node* node, const HT* ht):_node(node), _ht(ht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}Self& operator++(){if (_node->_next){// 当前桶还有数据，走到当前桶下一个节点_node = _node->_next;}else{// 当前桶走完了，找下一个不为空的桶KeyOfT kot;Hash hash;size_t hashi = hash(kot(_node->_data)) % _ht->_tables.size();//_tables为私有成员，需要友元声明++hashi;while (hashi < _ht->_tables.size()){_node = _ht->_tables[hashi];if (_node)break;else++hashi;//记得++，不然就死循环了}// 所有桶都走完了，end()给的空标识的_nodeif (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}};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++){Node* cur = _tables[i];if (cur){return Iterator(cur, 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++){Node* cur = _tables[i];if (cur){return ConstIterator(cur, this);}}return End();}ConstIterator End() const{return ConstIterator(nullptr, this);}HashTable():_tables(__stl_next_prime(0)), _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;}}//实现更好的扩容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){KeyOfT kot;Iterator it = Find(kot(data));if (it != End())return make_pair(it, false);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 = new Node(data);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(Iterator(newnode, this), true);}//查找Iterator Find(const K& key){KeyOfT kot;Hash hash;size_t hashi = hash(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){KeyOfT kot;size_t hashi = 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;--_n;return true;}else{prev = cur;cur = cur->_next;}}return false;}private:vector<Node*> _tables;//指针数组//vector<list<pair<K,V>>> _tables//其实也可以这样，但是实现对应的迭代器就很复杂size_t _n = 0;//表中存储数据得个数 };
}

Unordered_set.h

#pragma once
#include"HashTable.h"
using namespace hash_bucket;
namespace rose
{template<class K, class Hash = HashImitFunc<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"
using namespace hash_bucket;
namespace rose
{template<class K, class V, class Hash = HashImitFunc<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);}bool Erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};
}

测试用例

#include<iostream>
#include"Unordered_Set.h"
#include"Unordered_Map.h"using namespace std;
void test_set()
{rose::unordered_set<int> s;int a[] = { 4, 2, 6, 1, 3, 5, 15, 7, 16, 14, 3,3,15 };for (auto e : a){s.insert(e);}for (auto e : s){cout << e << " ";}cout << endl;rose::unordered_set<int>::iterator it = s.begin();while (it != s.end()){// 不⽀持修改//*it += 1;cout << *it << " ";++it;}cout << endl;
}
void test_map()
{rose::unordered_map<string, string> dict;dict.insert({ "sort", "排序" });dict.insert({ "left", "左边" });dict.insert({ "right", "右边" });dict["left"] = "左边，剩余";dict["insert"] = "插入";dict["string"];rose::unordered_map<string, string>::iterator it = dict.begin();while (it != dict.end()){// 不能修改first，可以修改second//it->first += 'x';it->second += 'x';cout << it->first << ":" << it->second << endl;++it;}cout << endl;
}
int main()
{//test_set();test_map();return 0;
}