1. unordered系列的容器封装
在C++11中，增加了unordered系列的容器，其底层就是哈希原理。在之前的博客内容中，我们实现了哈希的代码部分，包括闭散列和开散列两种。由于闭散列的局限性，所以C++11标准库是采用开散列的方式封装了unordered系列容器，接下来我们将使用之前实现的**哈希桶(开散列)**代码对unordered系列的容器进行改写与封装。
1.1 改造1:模版参数类型的改造
1.1.1 HashNode改造
//改造前 template<class K, class V> struct HashNode { std::pair<K, V> _kv; HashNode* _next; HashNode(const std::pair<K, V>& kv) :_kv(kv) ,_next(nullptr) {} };
由于unordered_set是K模型，而unordered_map是KV模型，为了让底层的哈希桶能够同时支持两种不同的模型，所以这里需要对哈希节点进行改造，改造后的结果如下:
//改造后 template<class T>//将模板参数变成T，对于K模型来说，传入的类型就是<Key,Key>键值对，对于KV模型来说，传入的就是<Key,Value>键值对 struct HashNode { T _data; HashNode* _next; HashNode(const T& data) :_data(data) ,_next(nullptr) {} };
1.1.2 HashTable改造
//改造前 template<class K, class V, class Hash = HashFunc<K>> class HashTable { typedef HashNode<K, V> Node; public： bool Insert(const std::pair<K,V>& kv); bool Erase(const K& key); Node* Find(const K& key); private: std::vector<Node*> _tables; size_t _n = 0; }
这里由于节点的模板类型已经更改，所以之前的KV也需要进行更改，同时传入仿函数KeyOfT用来从键值对T中提取出key。
//修改后 template<class K, class T, class KeyOfT, class Hash = HashFunc<K>> class HashTable { typedef HashNode<T> Node;//这里节点传入的类型是T public: HashTable() :_n(0) { _tables.resize(10); } bool Insert(const T& data); bool Erase(const K& key); Node* Find(const K& key); private: std::vector<Node*> _tables; size_t _n = 0; };
1.2 改造2:迭代器的增加与封装
在之前使用红黑树封装map&set的时候已经说明，我们对于map&set的迭代器的处理，使用的是红黑树实现的迭代器。所以这里同样的，使用的是哈希桶封装的迭代器，那么我们首先就改写哈希桶
1.2.1 迭代器类的实现
和红黑树的迭代器一样，原生指针不能支持迭代器行为，所以我们需要自己手动实现一个迭代器类，然后进行一些运算符重载。
在迭代器类的实现中，最重要的一个运算符就是++运算符的重载。
template<class _K, class _T, class _KeyOfT, class _Hash = HashFunc<_K>> class HashTable;//由于在迭代器类里面使用了HashTable，同时在HashTable中也使用了迭代器类，所以需要进行提前声明类模板 template<class K, class T, class KeyOfT, class Hash = HashFunc<K>> struct __HTIterator { typedef HashTable<K, T, KeyOfT, Hash> HT; typedef __HTIterator<K,T,KeyOfT,Hash> Self; typedef HashNode<T> Node; Node* _node; HT* _ht; __HTIterator(Node* node, HT* ht) :_node(node) ,_ht(ht) {} //这里的思路是按照table的顺序遍历哈希桶，在哈希桶里面单向遍历桶内的每个数据 Self& operator++() { if(_node->_next)//当前桶还有元素 { _node = _node->_next; } else//当前桶走完了，找下一个桶 { size_t hashi = Hash()(KeyOfT()(_node->_data)) % _ht->_tables.size();//找到当前桶的哈希地址 //找到下一个有元素的哈希桶对应的哈希地址，并将其第一个元素赋值给node ++hashi; while(hashi < _ht->_tables.size()) { if(_ht->_tables[hashi]) { _node = _ht->_tables[hashi]; break; } else { ++hashi; } } //后面没有桶了 if(hashi == _ht->_tables.size()) _node = nullptr; } return *this; } //其他的重载在之前的文章中有详细说明，这里道理是一样的，就不再赘述了 T& operator*() { return _node->_data; } T* operator->() { return &_node->_data; } bool operator!=(const Self& s) { return _node != s._node; } bool operator== (const Self& s) { return _node==s._node; } };
注：
类模板的声明方法：template<class type_name> class class_name;
同时，这里需要调用HashTable中的私有成员，所以需要给出友元类。
友元类的声明方法：template<class type_name> friend class class_name
这里有一个点需要注意：
由于在clang下，使用同一个模版参数名会出现报错：Declaration of '模版参数名' shadows template parameter，所以本次实现时在迭代器类的模版参数前加上_以示区分(详细代码见后文)。
1.2.2 迭代器的封装
实现了迭代器类之后，就可以在HashTable中封装迭代器接口
typedef __HTIterator<K, T, KeyOfT, Hash> iterator; //迭代器 iterator begin() { //遍历，找到第一个有元素的桶 for(size_t i = 0; i < _tables.size(); ++i) { if(_tables[i]) { return iterator(_tables[i], this); } } return iterator(nullptr, this); } //这里采用空指针当作最后一个节点的下一个元素指针 iterator end() { return iterator(nullptr, this); }
1.3 改造3:insert的改写封装
//改造前 bool Insert(const std::pair<K,V>& kv) { if(Find(kv.first)) return false; if(_n == _tables.size()) { std::vector<Node*> newTables; newTables.resize(2* _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 = Hash()(cur->_kv.first) % newTables.size(); cur->_next = newTables[hashi]; newTables[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newTables); } size_t hashi = Hash()(kv.first) % _tables.size(); Node* newnode = new Node(kv); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_n; return true; }
为了实现[]重载，所以这里和之前的map&set一样，需要对底层数据结构的insert进行改写，这里需要让返回值变成一个pair，其中的第一个成员是迭代器，第二个成员是原来的bool类型，所以代码如下
//改造后代码 std::pair<iterator, bool> Insert(const T& data)//这里将返回值修改为std::pair类型 { iterator it = Find(KeyOfT()(data));//使用仿函数从data中提取到key if(it != end()) return make_pair(it, false);//如果当前对应的key存在，那么就返回当前key的迭代器类型和false组成的pair if(_n == _tables.size()) { std::vector<Node*> newTables; newTables.resize(2* _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 = Hash()(KeyOfT()(cur->_data)) % newTables.size();//使用仿函数从data中提取到key cur->_next = newTables[hashi]; newTables[hashi] = cur; cur = next; } _tables[i] = nullptr; } _tables.swap(newTables); } size_t hashi = Hash()(KeyOfT()(data)) % _tables.size();//使用仿函数从data中提取到key Node* newnode = new Node(data); newnode->_next = _tables[hashi]; _tables[hashi] = newnode; ++_n; return make_pair(iterator(newnode, this), true);//使用newnode和this构造一个迭代器，将这个迭代器和插入情况构造成一个pair返回。 }
1.4 析构函数的实现
由于在构造或者插入的过程中使用new创建节点了，所以需要对new的资源进行手动释放，所以为了避免内存泄漏，需要进行析构函数的实现。
析构函数的实现原理就是：遍历哈希桶，依次释放节点。
所以代码就显而易见了：
~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;//将当前桶的指针置空，防止出现野指针的情况 } }
