- 测试代码：
void TestHashTable1() { HashTable<int, int> ht; int a[] = { 4, 44, 14, 5, 2, 22, 12, 5, 8, 10, 15 }; for (auto e : a) { ht.Insert(make_pair(e, e)); } ht.Insert(make_pair(11, 11)); cout << ht.Find(44) << endl; ht.Erase(44); cout << ht.Find(44) << endl; ht.Erase(2); } void TestHashTable2() { //HashTable<string, string, HashFuncString> dict; HashTable<string, string> dict; dict.Insert(make_pair("sort", "排序")); dict.Insert(make_pair("insert", "插入")); dict.Insert(make_pair("erase", "删除")); } void TestHashTable3() { HashTable<int, int> ht1; int a[] = { 4, 44, 14, 5, 2, 22, 12, 5, 8, 10, 15 }; for (auto e : a) { ht1.Insert(make_pair(e, e)); } ht1.Insert(make_pair(11, 11)); HashTable<int, int> ht2(ht1); HashTable<int, int> ht; ht = ht2; for (size_t i = 0; i < 53; ++i) { ht.Insert(make_pair(rand(), i)); } ht.Insert(make_pair(rand(), 0)); }
- 开散列与闭散列比较：
应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上： 由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a <= 0.7，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间
三、哈希封装实现unordered_map/unordered_set
这里使用哈希桶来封装实现map和set，哈希桶相对于哈希表来说没有哈希冲突，并且效率也十分好
使用哈希封装map/set和使用红黑树来封装的思维具有很多相似的地方
1、哈希桶的改装
注意：
存储节点的数据类型对于set的K模型以及map的KV模型的兼容
示例代码：
//哈希储存的数据类型 template<class T> struct HashNode { T _data;//对于不同的上层可以存对应的K类型以及pair<K,V> HashNode* _next; HashNode(const T& data) :_data(data) , _next(nullptr) {} };
解释：
封装上层是set的话，则给底层哈希桶传入K类型，通过哈希桶再给底层的节点储存类型传入K类型
封装上层是map的话，则给底层哈希桶传入pair<K,V>，通过哈希桶再给底层的节点储存类型传入pair<K,V>
储存节点在不同封装的使用下进行对应的取出数据的key进行比较
示例代码：
//set上层 struct SetOfKey { const K& operator()(const K& key)const { return key; } }; typedef HashNode<K> Node; typedef HashTable<K, K, Hash, SetOfKey> HT; //map上层 struct MapOfKey { const K& operator()(const pair<K,V>& kv)const { return kv.first; } }; typedef HashNode<pair<K, V>> Node; typedef HashTable<K, pair<K, V>, Hash, MapOfKey> HT;
- 解释：
上层封装中实现仿函数，给对应底层哈希传入对应使用的仿函数，便于进行使用对应的函数将储存数据的key继续取出比较
- 哈希桶的迭代器如何实现，对于当前位置的迭代器怎么找到下个位置
- 示例代码：
template<class K, class T, class Hash, class KeyOfT> struct HTIterator { typedef HashNode<T> Node; typedef HashTable<K, T, Hash, KeyOfT> HT; typedef HTIterator<K, T, Hash, KeyOfT> Self; HT* _ht; Node* _node; HTIterator(Node* node, HT* ht)//不能加const，与成员变量不匹配 :_ht(ht) , _node(node) {} bool operator==(const Self& s) const; bool operator!=(const Self& s) const; T& operator*(); T* operator->(); Self& operator++() { if (_node->_next)//存在下个节点 _node = _node->_next; else//找下一个桶 { Hash hf; KeyOfT kot; size_t index = hf(kot(_node->_data)) % _ht->_table.size(); //kot仿函数为了取出储存类型数据的key，hf仿函数是实现对key类型的取整值，便于进行取模 int i=index+1; for (; i < _ht->_table.size(); i++) { if (_ht->_table[i]) { _node = _ht->_table[i]; break; } } if (i == _ht->_table.size())//走到最后* _node = nullptr; } return *this; } }; template<class K, class T, class Hash, class KeyOfT> class HashTable { typedef HashNode<T> Node; friend struct HTIterator<K, T, Hash, KeyOfT>;//* public: typedef HashTable<K, T, Hash, KeyOfT> HT; typedef HTIterator<K, T, Hash, KeyOfT> Iterator; //... }
注：对于哈希桶来说只有正向迭代器（单向），主要是底层是一个单向的链表，找上个节点地址比较麻烦，对于反向并不是很强求
解释：
迭代器底层为哈希桶节点地址，同时还需要指向该哈希桶的指针，用来进行查找对应桶的下个节点地址，这里需要使用哈希的私有成员，所以我们需要让迭代器成为哈希桶的友元类，便于访问成员
在实现的时候，我们发现，实现的迭代器包含了哈希桶类型，而哈希桶也包含了迭代器类型，两个类型互相去查找对方类型，这里就需要进行前置声明，避免有一方找不到对方类型
示例代码：
//前置声明 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 HashTable<K, T, Hash, KeyOfT> HT; typedef HTIterator<K, T, Hash, KeyOfT> Self; HT* _ht; Node* _node; //... Self& operator++(); }; template<class K, class T, class Hash, class KeyOfT> class HashTable { typedef HashNode<T> Node; friend struct HTIterator<K, T, Hash, KeyOfT>;//* public: typedef HashTable<K, T, Hash, KeyOfT> HT; typedef HTIterator<K, T, Hash, KeyOfT> Iterator; Iterator begin() { for (int i = 0; i < _table.size(); i++) { if (_table[i]) return Iterator(_table[i], this); } return Iterator(nullptr, this); } Iterator end() { return Iterator(nullptr, this); } //... }
- 哈希桶改装后完整代码：
#include<iostream> #include<vector> #include<string> using namespace std; //哈希储存的数据类型 template<class T> struct HashNode { T _data;//对于不同的上层可以存对应的K类型以及pair<K,V> HashNode* _next; HashNode(const T& data) :_data(data) , _next(nullptr) {} }; //取值比较仿函数及其特化 template<class K> struct HashFunc { size_t operator()(const K& key) { return key; } }; template<> struct HashFunc<string> { size_t operator()(const string& str) { size_t hash = 0; for (int i = 0; i < str.size(); i++) { hash = hash * 131 + str[i]; } return hash; } }; //获取下一个质数（接近二倍开辟） size_t GetNextPrime(size_t prime) { const int PRIMECOUNT = 28; static const size_t primeList[PRIMECOUNT] = { 53ul, 97ul, 193ul, 389ul, 769ul, 1543ul, 3079ul, 6151ul, 12289ul, 24593ul, 49157ul, 98317ul, 196613ul, 393241ul, 786433ul, 1572869ul, 3145739ul, 6291469ul, 12582917ul, 25165843ul, 50331653ul, 100663319ul, 201326611ul, 402653189ul, 805306457ul, 1610612741ul, 3221225473ul, 4294967291ul }; size_t i = 0; for (; i < PRIMECOUNT; ++i) { if (primeList[i] > prime) return primeList[i]; } return primeList[i]; } //前置声明 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 HashTable<K, T, Hash, KeyOfT> HT; typedef HTIterator<K, T, Hash, KeyOfT> Self; HT* _ht; Node* _node; HTIterator(Node* node, HT* ht)//不能加const，与成员变量不匹配 :_ht(ht) , _node(node) {} bool operator==(const Self& s) const { return _node == s._node; } bool operator!=(const Self& s) const { return _node != s._node; } T& operator*() { return _node->_data; } T* operator->() { return &_node->_data; } Self& operator++() { if (_node->_next) _node = _node->_next; else//找下一个桶 { Hash hf; KeyOfT kot; size_t index = hf(kot(_node->_data)) % _ht->_table.size(); int i=index+1; for (; i < _ht->_table.size(); i++) { if (_ht->_table[i]) { _node = _ht->_table[i]; break; } } if (i == _ht->_table.size())//走到最后* _node = nullptr; } return *this; } }; template<class K, class T, class Hash, class KeyOfT> class HashTable { typedef HashNode<T> Node; friend struct HTIterator<K, T, Hash, KeyOfT>;//* public: typedef HashTable<K, T, Hash, KeyOfT> HT; typedef HTIterator<K, T, Hash, KeyOfT> Iterator; HashTable() :_n(0) {} Iterator begin() { for (int i = 0; i < _table.size(); i++) { if (_table[i]) return Iterator(_table[i], this); } return Iterator(nullptr, this); } Iterator end() { return Iterator(nullptr, this); } HashTable(const HT& ht)//拷贝构造 :_n(ht._n) { if (ht._table.size() == 0) return; KeyOfT kot; _table.resize(ht._table.size(), nullptr); for (int i = 0; i < ht._table.size(); i++) { Node* cur = ht._table[i]; while (cur) { Node* newnode = new Node(cur->_kv); newnode->_next = _table[i]; _table[i] = newnode; cur = cur->_next; } } } HT& operator=(const HT& ht) { if (&ht != this) { HT temp(ht); _table.swap(temp._table); _n = ht._n; } return *this; } ~HashTable() { for (int i = 0; i < _table.size(); i++) { Node* cur = _table[i]; while (cur) { Node* next = cur->_next; delete cur; cur = next; } _table[i] = nullptr;//置空 } _n = 0; } pair<Iterator,bool> Insert(const T& data) { Hash hf; KeyOfT kot; //空哈希或者负载因子达到1 if (_table.size() == _n) { size_t newsize = _table.size() == 0 ? 10 : _table.size() * 2; //size_t newsize = GetNextPrime(_table.size());//获取新大小 vector<Node*> newdata; newdata.resize(newsize, nullptr);//开新的数组并扩容 //将原数组中的节点重新插入到新数组 for (size_t i = 0; i < _table.size(); ++i) { Node* cur = _table[i];//遍历数组 while (cur)//挂有节点 { Node* next = cur->_next;//记录下一个节点 size_t index = hf(kot(cur->_data)) % newsize;//重新计算下标 //头插到新位置 cur->_next = newdata[index]; newdata[index] = cur; cur = next;//移动 } _table[i] = nullptr; } _table.swap(newdata); } //遍历查找 size_t index = hf(kot(data)) % _table.size(); Node* cur = _table[index]; while (cur) { if (kot(cur->_data) == kot(data)) return make_pair(Iterator(cur,this),false); else cur = cur->_next; } //头插 Node* newnode = new Node(data); newnode->_next = _table[index]; _table[index] = newnode; ++_n; return make_pair(Iterator(newnode,this),true); } Node* Find(const K& key) { //空哈希 if (_table.size() == 0) return nullptr; Hash hf; KeyOfT kot; size_t index = hf(key) % _table.size(); Node* cur = _table[index]; while (cur) { if (kot(cur->_data) == key) return cur; else cur = cur->_next; } return nullptr; } bool Erase(const K& key) { //空哈希 if (_table.size() == 0) return false; Hash hf; KeyOfT kot; size_t index = hf(key) % _table.size(); Node* cur = _table[index]; Node* parent = nullptr; while (cur) { if (kot(cur->_data) == key) { if (parent == nullptr)//头结点 _table[index] = cur->_next; else parent->_next = cur->_next; delete cur; --_n; return true; } else { parent = cur; cur = cur->_next; } } return false; } private: vector<Node*> _table; size_t _n=0; };
