【C++】开散列实现unordered_map与unordered_set的封装

本文主要介绍unordered_map与unordered_set的封装，此次封装主要用上文所说到的开散列,通过开散列的一些改造来实现unordered_map与unordered_set的封装

一、模板参数

由于unordered_set 是 K 模型的容器，而 unordered_map 是 KV 模型的容器,所以需要对结点的参数进行改造，unordered_set可以使用，unordered_map也可以使用,改为T _data即可

	template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}};

T模板参数可能是键值Key，也可能是Key和Value构成的键值对。如果是unordered_map容器，那么它传入底层哈希表的模板参数就是Key和Key和Value构成的键值对，如果是unordered_set容器，那么它传入底层哈希表的模板参数就是Key和Key

	template<class K,class V,class Hash=HashFunc<K>>class unordered_map{private:buckethash::HashTable<K, pair<const K, V>, Hash, MapKeyOfT> _ht;};

	template<class K,class Hash = HashFunc<K>>class unordered_set{private: buckethash::HashTable<K, K, Hash, SetKeyOfT> _ht;};

如此就可以实现泛型了，如果是unordered_set，结点当中存储的是键值Key；如果是unordered_map，结点当中存储的就是<Key, Value>键值对：

哈希表仿函数的支持：KeyOfT👇

我们通过哈希计算出对应的哈希地址：但是插入的时候就不能直接用data去进行比较了

对于unordered_set:data是key是可以比较的，对于unordered_map:data是键值对,我们需要取出键值对的first。而data既可以是unordered_set的，也可以是unordered_map的，所以我们需要仿函数来实现不同容器所对应的需求，然后传入：

unordered_map返回kv.first

template<class K,class V,class Hash=HashFunc<K>>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<const K, V>& kv){return kv.first;}};}private:buckethash::HashTable<K, pair<const K, V>, Hash, MapKeyOfT> _ht;};

unordered_set返回key:

template<class K,class Hash = HashFunc<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};private: buckethash::HashTable<K, K, Hash, SetKeyOfT> _ht;};

这也就是Hashtable需要KeyOfT的原因所在。

二、string的特化

字符串无法取模，在这里重新写一遍，字符串无法取模的问题写库的大神们早就想到了

预留一个模板参数，无论上层容器是unordered_set还是unordered_map，我们都能够通过上层容器提供的仿函数获取到元素的键值

template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};
//特化
template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash *= 131;//顺序？abc，cbahash += ch;}return hash;}
};

string的特化：符合string类型的优先走string类型

template<class K,class V,class Hash=HashFunc<K>>
class unordered_map
template<class K,class Hash = HashFunc<K>>
class unordered_set

---

三、正向迭代器

哈希表的正向迭代器对哈希表指针和结点指针进行了封装，++运算符重载，可以访问下一个非空的桶，所以每个正向迭代器里面存的是哈希表地址。

template<class K, class T, class Hash, class KeyOfT>
class HashTable;template<class K,class T,class Hash,class KeyOfT>struct __HTIterator{typedef HashNode<T> Node;typedef __HTIterator<K, T, Hash, KeyOfT> Self;typedef HashTable<K, T, Hash, KeyOfT> HT;Node* _node;HT* _ht;}

所以我们构造迭代器的时候需要知道节点的地址和哈希表的地址

	__HTIterator(Node*node,HT*ht):_node(node),_ht(ht){}

++运算符重载的实现：如果当前的桶还有节点，那么++就是当前桶下一个节点，如果当前元素是所在的桶的最后一个元素，那么++就是下一个非空的桶了

如何去找下一个非空桶：其实很简单，通过当前节点的值算出当前桶的hashi，然后++hashi就是下一个桶了，找到下一个非空桶即可

		T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}bool operator !=(const Self& s) const{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();//当前桶的哈希地址++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;}};

–问题：哈希表中的迭代器是单向迭代器，并没有反向迭代器，所以没有实现–-运算符的重载，若是想让哈希表支持双向遍历，可以考虑将哈希桶中存储的单链表结构换为双链表结构。

存在的小细节：👇

	template<class K,class T,class Hash,class KeyOfT>class HashTable{typedef HashNode<T> Node;template<class K,class T,class Hash,class KeyOfT>friend struct __HTIterator;public:typedef __HTIterator<K, T, Hash, KeyOfT> 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);}private:vector<Node*> _tables;size_t _n = 0;};

++运算符重载去寻找下一个结点时，会访问_tables,而_tables是哈希表中的私有成员，所以我们需要把迭代器__HTIterator声明为哈希表的友元

正向迭代器__HTIterator的typedef放在了public,这是为了外部能够使用我们的typedef之后的正向迭代器

还需要注意的是，哈希表的 const 迭代器不能复用普通迭代器的代码，我们查看源码：

这与我们之前所复用的不同，上面stl源码中可以看到并没有用以前的复用：

这是因为如果使用const版本，那么_tables使用[]返回的就是const版本，那么Node*就相当于是const Node*,就会导致权限放大，无法构造;如果改成const HT* _ht; const Node* _node;，又会导致[]不能修改的问题:

四、构造与析构

默认构造

HashTable():_n(0){_tables.resize(__stl_next_prime(0));}

析构函数

哈希表当中存储的结点都是new出来的，所以哈希表被析构时必须delete。在析构哈希表时我们只需要遍历取出非空的哈希桶，遍历哈希桶当中的结点并进行释放即可👇

		~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;}}

五、[]的实现

要想实现[]，我们需要先把Insert的返回值修改成pair<iterator,bool>,最后的返回值也要一起修改

如果有重复的元素就返回这个找到it迭代器
没有重复的就返回newnode迭代器

		pair<iterator, bool> Insert(const T&data){KeyOfT kot;iterator it = Find(kot(data));if (it != end()){return make_pair(it, false);}if (_tables.size() == _n){vector<Node*> newTables;newTables.resize(__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 = 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);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(iterator(newnode,this),true);}

六、unordered_map的实现

#pragma once#include "HashTable.h"
namespace hwc
{template<class K,class V,class Hash=HashFunc<K>>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<const K, V>& kv){return kv.first;}};public:typedef typename buckethash::HashTable<K, pair<const K, V>, Hash, MapKeyOfT>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator, bool> insert(const pair<K, V> data){return _ht.Insert(data);}V& operator[](const K& key){pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));return ret.first->second;}private:buckethash::HashTable<K, pair<const K, V>, Hash, MapKeyOfT> _ht;};void test_unordered_map(){string arr[] = { "苹果","香蕉","苹果","西瓜","哈密瓜"};unordered_map<string, int> countMap;for (auto& e : arr){countMap[e]++;}for (const auto& kv : countMap){cout << kv.first << ":" << kv.second << endl;}}
}

七、unordered_set的实现

#pragma once#include "HashTable.h"namespace hwc
{template<class K,class Hash = HashFunc<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename buckethash::HashTable<K, K, Hash, SetKeyOfT>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator, bool> insert(const K& key){return _ht.Insert(key);}private: buckethash::HashTable<K, K, Hash, SetKeyOfT> _ht;};void test_unordered_set(){unordered_set<int> us;us.insert(13);us.insert(3);us.insert(23);us.insert(5);us.insert(5);us.insert(6);us.insert(15);us.insert(223342);us.insert(22);unordered_set<int>::iterator it = us.begin();while (it != us.end()){cout << *it << " ";++it;}cout << endl;for (auto e : us){cout << e << " ";}cout << endl;}
}

八、哈希表代码

#pragma once
#pragma once#include <iostream>
#include <string>
#include <vector>
using namespace std;
template<class K>
struct HashFunc
{size_t operator()(const K& key){return (size_t)key;}
};
//特化
template<>
struct HashFunc<string>
{size_t operator()(const string& key){size_t hash = 0;for (auto ch : key){hash *= 131;//顺序？abc，cbahash += ch;}return hash;}
};//开散列
namespace buckethash
{template<class T>struct HashNode{T _data;HashNode<T>* _next;HashNode(const T& data):_data(data), _next(nullptr){}};template<class K, class T, class Hash, class KeyOfT>class HashTable;template<class K,class T,class Hash,class KeyOfT>struct __HTIterator{typedef HashNode<T> Node;typedef __HTIterator<K, T, Hash, KeyOfT> Self;typedef HashTable<K, T, Hash, KeyOfT> HT;Node* _node;HT* _ht;__HTIterator(Node*node,HT*ht):_node(node),_ht(ht){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}bool operator !=(const Self& s) const{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();++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;}};template<class K,class T,class Hash,class KeyOfT>class HashTable{typedef HashNode<T> Node;template<class K,class T,class Hash,class KeyOfT>friend struct __HTIterator;public:typedef __HTIterator<K, T, Hash, KeyOfT> 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);}HashTable():_n(0){_tables.resize(__stl_next_prime(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 make_pair(it, false);}if (_tables.size() == _n){vector<Node*> newTables;newTables.resize(__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 = 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);newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(iterator(newnode,this),true);}iterator Find(const K& key){KeyOfT kot;size_t hashi = Hash()(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return iterator(cur, this);}else{cur = cur->_next;}}return end();}bool Erase(const K& key){size_t hashi = Hash()(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (cur->_kv.first == key){if (cur == _tables[hashi]){_tables[hashi] = cur->_next;}else{prev->_next = cur->_next;}delete cur;--_n;return true;}else{prev = cur;cur = cur->_next;}}return false;}inline unsigned long __stl_next_prime(unsigned long n){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};for (int i = 0; i < __stl_num_primes; ++i){if (__stl_prime_list[i] > n){return __stl_prime_list[i];}}return __stl_prime_list[__stl_num_primes - 1];}private:vector<Node*> _tables;size_t _n = 0;};
}

本篇到此结束…