---

1 哈希表的基本改造

这里的思路与前面讲解map/set的封装思路一致，STL不喜欢直接实例化出两份几乎相同的代码，所以用了模板参数来处理，还是老规矩：set中传入的是<K,K>,map中传入的是<K,Pair<K,V>>.这样我们在哈希桶的结构中只需要用一个T类型的模板参数接受上层传入的参数即可。

基本框架的改造：

namespace BucketHash
{template<class T>struct BucketHashNode{BucketHashNode* _next;T _data;BucketHashNode(const T& data):_next(nullptr),_data(data){}};template<class K>struct HashTranfor{size_t operator()(const K& k){return (size_t)k;}};//特化一个版本出来template<>struct HashTranfor<string>{// BKDRsize_t operator()(const string& key){size_t val = 0;for (auto ch : key){val *= 131;val += ch;}return val;}};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};template<class K, class T,class Hash,class KeyOfT>//给出第一个模板参数的目的是为了Insert//时能够正确将K插入class HashTable{private:typedef BucketHashNode<T> Node;vector<Node*> _tables;size_t _size = 0;public:size_t GetCapacity(size_t sz){int i = 0;for (; i < __stl_num_primes; ++i){if (sz < __stl_prime_list[i]) break;}return __stl_prime_list[i];}~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;}}size_t Size()const{return _tables.size();}size_t BucketSize()const{int cnt = 0;for (int i = 0; i < Size(); ++i){if (_tables[i])++cnt;}return cnt;}size_t MaxBucketSize()const{int maxLen = 0;for (int i = 0; i < Size(); ++i){Node* cur = _tables[i];int len = 0;while (cur){++len;cur = cur->_next;}maxLen = max(maxLen, len);}return maxLen;}};

注意：

• 为了得到set和map比较的参数所以我们设置一个模板参数KeyOfT来获取set/map比较大小的数据。

---

2 迭代器

封装中最重要的一环就是迭代器了，那么究竟该如何设计迭代器呢？

2.1 迭代器的大致框架

首先我们来想想：迭代器究竟该有哪些成员？
由于迭代器要支持++操作（这里的迭代器不支持- -操作，因为是单向迭代器(底层用的是单链表)),所以我们得拿到整张表来方便我们遍历，我们还需要结点指针来帮助我们取数据。
所以我们就能够搭建出迭代器的大致框架了：

  //前置声明template<class K, class T, class Hash, class KeyOfT>class HashTable;//迭代器template<class K, class T, class Ref, class Ptr, class Hash, class KeyOfT>struct __TableIterator{typedef BucketHashNode<T> Node;typedef HashTable<K, T, Hash, KeyOfT> HTable;typedef __TableIterator<K, T, Ref, Ptr, Hash, KeyOfT> Self;typedef __TableIterator<K, T, T&, T*, Hash, KeyOfT> Iterator;Node* _node;//结点指针，方便取数据HTable* _ht;//找到哈希表__TableIterator(Node* node,HTable* ht):_node(node),_ht(ht){}__TableIterator(const Iterator& it):_node(it._node),_ht(it._ht){}Ref operator*(){return _node->_data;}Ptr operator->(){return &_node->_data;}bool operator==(const Self& self)const{return self._node == _node;}bool operator!=(const Self& self)const{return self._node != _node;}};

注意：迭代器的成员变量由于用到了哈希桶结构，而哈希桶的实现在迭代器的下面，所以我们要在迭代器前面加上一个前置声明。

现在的关键是如何实现出++运算符的重载。

2.2 ++运算符重载的实现

其实这个的实现也不难，我们已经拿到了哈希表，所以只需要从当前位置找到表中下一个位置即可：

		Self& operator++(){if (_node->_next)_node = _node->_next;else{Hash hash;KeyOfT kot;size_t hashi = hash(kot(_node->_data)) % _ht->Size();++hashi;for (; hashi < _ht->Size(); ++hashi){if (_ht->_tables[hashi]){_node = _ht->_tables[hashi];break;}}if (hashi == _ht->Size())_node = nullptr;}return *this;}

但是还有一个问题：我们哈希表的实现中成员变量是私有的，所以迭代器是不能够访问的，为了方便我们可以在哈希表结构中加上友元声明，当然大家自己也可以实现get接口取数据，方法有很多，大家可以自行选择。

class HashTable{private:template<class K, class T, class Ref, class Ptr, class Hash, class KeyOfT>friend struct __TableIterator;typedef BucketHashNode<T> Node};

2.3 哈希表的完善

	template<class K, class T,class Hash,class KeyOfT>//给出第一个模板参数的目的是为了Insert//时能够正确将K插入class HashTable{private:template<class K, class T, class Ref, class Ptr, class Hash, class KeyOfT>friend struct __TableIterator;typedef BucketHashNode<T> Node;vector<Node*> _tables;size_t _size = 0;public:typedef __TableIterator<K, T, T&, T*, Hash, KeyOfT> iterator;typedef __TableIterator<K, T, const T&, const T*, Hash, KeyOfT> const_iterator;iterator begin(){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);}const_iterator begin()const{for (size_t i = 0; i < _tables.size(); ++i){if (_tables[i])return const_iterator(_tables[i], this);}return end();}const_iterator end()const{return const_iterator(nullptr, this);}size_t GetCapacity(size_t sz){int i = 0;for (; i < __stl_num_primes; ++i){if (sz < __stl_prime_list[i]) break;}return __stl_prime_list[i];}~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;Hash hash;auto ret = Find(kot(data));if (ret != end())return make_pair(ret, false);//扩容，负载因子为1if (_size == _tables.size()){//int newcapacity = _tables.size() == 0 ? 10 : _tables.size() * 2;int newcapacity =GetCapacity(_tables.size());vector<Node*> newTables;//这里直接用vector的目的是可以直接用原表的结点直接链接即可//不必多拷贝结点newTables.resize(newcapacity);for (int i = 0; i < _tables.size(); ++i){Node* cur = _tables[i];//头插while (cur){Node* next = cur->_next;size_t hashi = hash(kot(cur->_data)) % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur=next;}_tables[i] = nullptr;}_tables.swap(newTables);}size_t hashi = hash(kot(data)) % _tables.size();Node* newNode = new Node(data);//这里不要加kotnewNode->_next = _tables[hashi];_tables[hashi] = newNode;++_size;return make_pair(iterator(newNode,this), true);}iterator Find(const K& k){if (_tables.size()==0)return end();KeyOfT kot;Hash hash;size_t hashi = hash(k) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == k)return iterator(cur,this);cur = cur->_next;}return end();}bool Erase(const K& k){if (Find(k) == nullptr)return false;KeyOfT kot;Hash hash;size_t hashi = hash(k) % _tables.size();if (kot(_tables[hashi]->_data) == k){Node* del = _tables[hashi];_tables[hashi] = del->_next;delete del;--_size;return true;}Node* cur = _tables[hashi];while (cur->_next && kot(cur->_next->_data) != k){cur = cur->_next;}Node* del = cur->_next;cur->_next = del->_next;delete del;--_size;return true;}size_t Size()const{return _tables.size();}size_t BucketSize()const{int cnt = 0;for (int i = 0; i < Size(); ++i){if (_tables[i])++cnt;}return cnt;}size_t MaxBucketSize()const{int maxLen = 0;for (int i = 0; i < Size(); ++i){Node* cur = _tables[i];int len = 0;while (cur){++len;cur = cur->_next;}maxLen = max(maxLen, len);}return maxLen;}};

注意：由于迭代器的构造中我们需要哈希表的指针，而恰好this就是哈希表指针，所以我们传入this即可。另外find和inset时为了与STL保持一致，我们将返回值分别修改为iterator和pair<terator,bool>。

---

3 unordered_map和unordered_set的封装

这个思路与红黑树种map/set的封装思路一致，如何实现unordered_map支持修改val，不支持修改key;而unordered_set不支持修改key也是一致的：unordered_map的pair中的参数给<const K,V>,而unordered_set的普通迭代器是用const迭代器实现的，const迭代器也是用const迭代器实现的。

但是unordered_set中这样实现就会有一些问题：我们用了普通迭代器构造了const迭代器，这样肯定是会编译报错的，所以在迭代器的中我们还得增加一个构造：

		typedef __TableIterator<K, T, Ref, Ptr, Hash, KeyOfT> Self;typedef __TableIterator<K, T, T&, T*, Hash, KeyOfT> Iterator;Node* _node;//结点指针HTable* _ht;//找到哈希表__TableIterator(const Iterator& it):_node(it._node),_ht(it._ht){}

这样如果上层传入的是普通迭代器那么就是一个拷贝构造，传入的是const迭代器的话就是用了普通迭代器构造const迭代器。这点大家一定要注意。

3.1 unordered_map

	template<class K, class V, class Hash = BucketHash::HashTranfor<K>>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<K,V>& kv){return kv.first;}};private:BucketHash::HashTable<K, pair<const K,V>, Hash, MapKeyOfT> _tab;public:typedef typename BucketHash::HashTable<K, pair<const K,V>, Hash, MapKeyOfT>::iterator iterator;//这里要加上typename 的原因是告诉编译器这里是模板的声明而不是静态成员的声明iterator begin(){return _tab.begin();}iterator end(){return _tab.end();}pair<iterator, bool> insert(const pair<K,V>& kv){return _tab.Insert(kv);}V& operator[](const K& k){auto ret = _tab.Insert(make_pair(k, V()));return ret.first->second;}};

3.2 unordered_set

	template<class K, class Hash = BucketHash::HashTranfor<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};private:BucketHash::HashTable<K, K, Hash, SetKeyOfT> _tab;public:typedef typename BucketHash::HashTable<K, K, Hash, SetKeyOfT>::const_iterator iterator;//这里要加上typename 的原因是告诉编译器这里是模板的声明而不是静态成员的声明typedef typename BucketHash::HashTable<K, K, Hash, SetKeyOfT>::const_iterator const_iterator;iterator begin(){return _tab.begin();}iterator end(){return _tab.end();}const_iterator begin()const{return _tab.begin();}const_iterator end()const{return _tab.end();}pair<iterator, bool> insert(const K& k){return _tab.Insert(k);}};

好了，这样封装基本上大致框架也就完成了。

如果该文对你有帮助的话能不能一键三连支持博主呢？💘💘💘

---