开散列——哈希桶
这里就是数组是要给指针数组，数组里面存放单链表的地址，将冲突的值放在单链表里面就可以了。
但是如果某一个位置冲突很多，挂了很长，那么效率也会下降。
不过这里下面不一定能非要挂单链表，也可以挂红黑树等等。
哈希桶的实现
首先表中类型需要更改,并且负载因子等于1才会进行扩容。
如果当前位置没有任何值就是空，如果有就挂链表。
每一次链表插入的时候需要进行头插，这样更方便，不需要进行排序，因为不知道要先找谁。
#include<iostream> #include<cassert> #include<vector> #include<string> using namespace std; template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; template<> struct HashFunc<string>//HashFunc特化，如果是string类型的就走这里 { size_t operator()(const string& key) { size_t sum = 0; size_t count = 0; for (auto e : key) { ++count; sum += e; } return sum; } }; template<class K, class V> struct HashNode { pair<K, V> _kv; HashNode<K ,V>* next; HashNode(const pair<K, V>& kv) :_kv(kv) ,next(nullptr) { } }; template<class K, class V, class Hashc = HashFunc<K>> class Hashbucket { typedef HashNode<K, V> data; public: Hashbucket() { _hash.resize(10, nullptr); } ~Hashbucket() { for (int i = 0; i < _hash.size(); i++) { data* old = _hash[i]; while (old) { data* p = old -> next; delete old; old = p; } _hash[i] = nullptr; } } bool Insert(const pair<K, V>& kv) { if (find(kv.first)) return false; Hashc hs; if (_hash.size() == _n)//扩容 { vector<data*> new_hash;//这里必须创建Hashbucket中的vector<data*>，如果直接用Hashbucket类型会导致析构出问题 new_hash.resize(2 * _hash.size(), nullptr); for (size_t i = 0; i < _hash.size(); i++) { data* cur = _hash[i]; while (cur) { data* old = cur->next; size_t hashi = hs(cur->_kv.first) % new_hash.size();//计算重新插入的位置 cur->next = new_hash[hashi];//头插 new_hash[hashi] = cur; cur = old; } _hash[i] = nullptr; } _hash.swap(new_hash); } size_t hashi = hs(kv.first) % _hash.size(); data* newnode = new data(kv); newnode->next = _hash[hashi]; _hash[hashi] = newnode; ++_n; return true; } data* find(const K& key) { Hashc hs; size_t hashi = hs(key) % _hash.size(); data* p = _hash[hashi]; while (p) { if (p->_kv.first == key) { return p; } else { p = p -> next; } } return nullptr; } bool Erase(const K& key) { Hashc hs; size_t hashi = hs(key) % _hash.size(); data* cur = _hash[hashi]; data* old = nullptr;//指向cur的前一个结点 while (cur) { if (cur->_kv.first == key) { if (cur == _hash[hashi])//这里说明删除的是第一个结点 { _hash[hashi] = cur->next; } else { old->next = cur->next; } _n--; delete cur; return true; } else { old = cur; cur = cur->next; } } return false; } private: vector<data*> _hash; size_t _n = 0; };
模拟实现unordered_set与unordered_map
这里有一种说法，说哈希表的大小保持一个素数的大小更好。
那么看源码是怎么处理的：
这里给了一个素数表。
将素数表放进上面实现哈希桶用的代码里面，我们只需要封装成一个函数就可以了。
参数选择传当前哈希表的大小。
然后通过这个参数来比较是否需要扩容即可。
返回值也是返回容量大小，如果是表中最后一个值还要继续扩容，那么这里就返回最后一个值，不进行扩容，因为内存已经很大了。
unsigned long Prime_list(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 (n < __stl_prime_list[i]) { return __stl_prime_list[i]; } } return __stl_prime_list[__stl_num_primes - 1]; }
然后接下来进行对哈希桶改造与迭代器的封装：
首先考虑以下迭代器如何遍历整个哈希桶。
从第一个有结点的地方开始遍历，走到空之后去找表中的下一个有结点的地方再从头开始走，以此类推，遍历完整个表就可以了。
#include<iostream> #include<cassert> #include<vector> #include<string> using namespace std; template<class K> struct HashFunc { size_t operator()(const K& key) { return (size_t)key; } }; template<> struct HashFunc<string>//HashFunc特化，如果是string类型的就走这里 { size_t operator()(const string& key) { size_t hash = 0; for (auto ch : key) { hash *= 131; hash += ch; } return hash; } }; //前置声明，不然迭代器不知道有哈希桶这个类 template<class K, class T, class KeyOFT, class Hashc> class Hashbucket; template<class T> struct HashNode { T _data; HashNode<T>* next; HashNode(const T& data) :_data(data) , next(nullptr) { } }; template<class K, class T, class KeyOFT, class Hashc> struct HIterator { typedef HashNode<T> Node; typedef HIterator<K, T, KeyOFT, Hashc> Self; typedef Hashbucket<K, T, KeyOFT, Hashc> Hashbucket; Node* _node; Hashbucket* _hs; HIterator(Node* node, Hashbucket* hs) :_node(node) ,_hs(hs) {} 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; Hashc ht; size_t hashi = ht(kot(_node->_data)) % _hs->_hash.size(); hashi++; while (hashi < _hs->_hash.size())//找表中下一个不为空的结点 { if (_hs->_hash[hashi]) { _node = _hs->_hash[hashi]; break; } else { hashi++; } } if (hashi == _hs->_hash.size())//如果走到末尾了就说明结束了 _node = nullptr; } return *this; } }; template<class K, class T, class KeyOFT, class Hashc>//这里的取整数仿函数不在这里放缺省值 class Hashbucket { template<class K, class T, class KeyOFT, class Hashc> friend struct HIterator;//这里将迭代器设置友元，因为迭代器内部需要调用该类的私有成员 typedef HashNode<T> Data; public: typedef HIterator<K, T, KeyOFT, Hashc> Iterator; Iterator begin() { for (size_t i = 0; i < _hash.size(); i++) { if (_hash[i]) { return Iterator(_hash[i], this); } } return Iterator(nullptr, this); } Iterator end() { return Iterator(nullptr, this); } Hashbucket() { _hash.resize(10, nullptr); } ~Hashbucket() { for (int i = 0; i < _hash.size(); i++) { Data* old = _hash[i]; while (old) { Data* p = old->next; delete old; old = p; } _hash[i] = nullptr; } } pair<Iterator, bool> Insert(const T& data) { KeyOFT kot; Iterator it = find(kot(data)); if (it != end()) return make_pair(it, false); Hashc hs; if (_hash.size() == _n)//扩容 { vector<Data*> new_hash;//这里必须创建Hashbucket中的vector<data*>，如果直接用Hashbucket类型会导致析构出问题 new_hash.resize(2 * _hash.size(), nullptr); for (size_t i = 0; i < _hash.size(); i++) { Data* cur = _hash[i]; while (cur) { Data* old = cur->next; size_t hashi = hs(kot(cur->_data)) % new_hash.size();//计算重新插入的位置 cur->next = new_hash[hashi];//头插 new_hash[hashi] = cur; cur = old; } _hash[i] = nullptr; } _hash.swap(new_hash); } size_t hashi = hs(kot(data)) % _hash.size(); Data* newnode = new Data(data); newnode->next = _hash[hashi]; _hash[hashi] = newnode; ++_n; return make_pair(Iterator(newnode, this), true); } Iterator find(const K& key) { KeyOFT kot; Hashc hs; size_t hashi = hs(key) % _hash.size(); Data* p = _hash[hashi]; while (p) { if (kot(p->_data) == key) { return Iterator(p, this); } else { p = p->next; } } return Iterator(nullptr, this); } bool Erase(const K& key) { Hashc hs; KeyOFT kot; size_t hashi = hs(key) % _hash.size(); Data* cur = _hash[hashi]; Data* old = nullptr;//指向cur的前一个结点 while (cur) { if (kot(cur->_data) == key) { if (cur == _hash[hashi])//这里说明删除的是第一个结点 { _hash[hashi] = cur->next; } else { old->next = cur->next; } _n--; delete cur; return true; } else { old = cur; cur = cur->next; } } return false; } unsigned long Prime_list(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 (n < __stl_prime_list[i]) { return __stl_prime_list[i]; } } return __stl_prime_list[__stl_num_primes - 1]; } private: vector<Data*> _hash; size_t _n = 0; };
#include "uset与umap.h" template<class K, class Hash = HashFunc<K>> class uset { struct Setkot { const K& operator()(const K& key) { return key; } }; public: typedef typename Hashbucket<K, K, Setkot, Hash>::Iterator Iterator; Iterator begin() { return _set.begin(); } Iterator end() { return _set.end(); } pair<Iterator, bool> Insert(const K& key) { return _set.Insert(key); } Iterator Find(const K& key) { return _set.find(key); } bool Erase(const K& key) { return _set.Erase(key); } private: Hashbucket<K, K, Setkot, Hash> _set; };
#include "uset与umap.h" template<class K, class V, class Hash = HashFunc<K>> class umap { struct Mapkot { const K& operator()(const pair<const K, V>& kv) { return kv.first; } }; public: typedef typename Hashbucket<K, pair<K, V>, Mapkot, Hash>::Iterator Iterator; Iterator begin() { return _map.begin(); } Iterator end() { return _map.end(); } pair<Iterator, bool> Insert(const pair<K, V>& kv) { return _map.Insert(kv); } V& operator[](const K& key) { pair<Iterator, bool> it = Insert(make_pair(key, V())); return it.first->second; } Iterator Find(const K& key) { return _map.find(key); } bool Erase(const K& key) { return _map.Erase(key); } private: Hashbucket<K, pair<K, V>, Mapkot, Hash> _map; };
但是const版本的迭代器和非const迭代器是不能像以前一样套两个模板就能分别返回不同的const与非const类型，因为我们调用const迭代器的时候this指针也是const，那么成员：
这两个也是const类型，按照以前写begin()const，end()const：
然后取用const类型去构造，这里的迭代器构造函数是非const类型，没办法进行构造，这里属于权限放大。（严格意义上来说，hs也是一样的，传过来的是const，不能构造非const _hs）
所以我们这里就绪就要重新写一个const版本的迭代器（这里跟const迭代器什么区别）。
