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> { // BKDR size_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); //扩容，负载因子为1 if (_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);//这里不要加kot newNode->_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); } };
好了，这样封装基本上大致框架也就完成了。
如果该文对你有帮助的话能不能一键三连支持博主呢？💘💘💘
