哈希及其封装实现unordermap和set

哈希

直接定址法

哈希和之前的红黑树的区别就是，它是通过映射关系来找到目标的，可以把它想象成之前排序的计数排序，那其实就是哈希的一种方法，叫做直接定址法。

对于比较集中的数据，它只需要开一段区间，然后通过映射关系把数据存到对应的位置上就可以了，但是它的缺点也很明显，如果数据很分散，那它的消耗就很大并且效率也很低。同时，对于非整型的数据它还多了一个转换的过程，否则也无法存入。

除留余数法

那么，为了应对这种情况，进化出了我依旧是开一段区间M，但是我把要存入的数据进行取模M，然后把取模后的结果存入对应位置，这种方法叫做除留余数法。这样也可以以较小的代价存入数据，但是新的问题又出现了，必然会有取模M后相等的值出现，这个就叫做哈希冲突，当然这并不是无法解决的，只需要往它后面第一个空着的位置存入即可，但是同样的，这么做也有可能会挤占别的数据的空间，并且往后走的过程也是需要消耗效率的，理想的情况是不出现，但是实际上一定会出现，我们只能减少出现的次数。

使用这种情况，空出的位置越多，浪费越多，空出的位置越少，冲突的概率越高，我们需要在这两者之间取得一个平衡，所以大佬们决定，如果存入的数据达到70%就进行扩容，这样勉强在两者之间取得了一定的平衡，这就叫做负载因子。 

而对于开的空间M也有说法，对于除，我们可以理解为异或，比如M = 2^16 本质上是取后16位，

但是这就会出现如果我前16位相同第17位才不同的情况，那妥妥的哈希冲突，所以大佬们又想出一个办法， 先(M<<17) -1 ，这样后16位都是1，然后再异或，可是这样只有后16位参与进来，所以再把左移前的M>>16位，这样使得32位都参与了运算，极大程度降低了冲突的概率。

当然上面这种还挺复杂的，所以产生了另一种另辟蹊径的方法，那就是取一个质数，这样虽然无法和上面相媲美，但是多少也降了点。

哈希实现(丐版)

假如我想存入这样一组值，那么我的M取个质数就取11。

那么上面这组值取模11之后必然会出现冲突，所以就按照之前我们所说的往后找空位。

存只要没满冲突就冲突嘛，无法效率低点，可是找就不一样了，如果取模后的结果不是我要找的，那么就说明我的位置被占了，或者根本没存，所以我需要往后找，直到找到空为止，那么另一个情况出现了，如果我删除了呢，人为出现了一个空进而导致找不到。所以我们还需要一个枚举类型来定义非空、空、删除这三个状态。这样就完美解决了遇到删除要不要继续找下去的问题，还需要一个n来记录数据个数。

enum isempty
{yes,no,del
};template<class M, class N>
struct Data //节点
{pair<M, N> _kv;isempty _isempty = yes;
};
template<class M, class N>
class aaa
{
public:aaa():_tables(11),_n(0){}bool insert(const pair<M,N>& kv){if (find(kv.first)){//不允许重复值出现的版本return false;}//超过70%就扩容if (_n * 10 / _tables.size() >= 7){aaa<M, N> newht;newht._tables.resize(_tables.size() * 2);//开二倍，//这样原有数据的映射位置不会被改变for (auto& data : _tables){if (data._isempty == no){newht.insert(data._kv);}}//最后交换就大功告成了_table.swap(newht._table);}size_t hash0 = kv.first % _tables.size();size_t hashi = hash0;size_t i = 1;while(_tables[hashi]._isempty == no ){hashi = (hash0 + i) % _table.size();//遇到边界可以回绕回去i++;}_tables[hashi]._kv = kv;_tables[hashi]._isempty == no;_n++;return true;}Data<M, N>* find(const M& key){size_t hash0 = key % _tables.size();size_t hashi = hash0;size_t i = 1;while (_tables[hashi]._isempty != yes){//不为空就继续往后找if (_tables[hashi].kv.first == key){//找到了就返回return &_tables[hashi];}hashi = (hash0 + i) % _table.size();i++;}//不然就是没找到 返回空return nullptr;}bool erase(const M& key){Data<M, N>* ret = find(key);if (ret){//我们不用真的去删除，只需要改一下它的状态就好ret->_isempty = del;return true;}else{//不然就是没找到return false;}}
private:vector<Data<M, N>> _tables;size_t _n = 0;//数据个数
};

是的，丐版的哈希就完成了，就这样。但哈希的实现会因为你使用的方法不同，在实现上也会有所不同，所以接下来我们就在丐版的基础上增加一点东西。

加强部分

利用素数表扩容

比如说在开辟的空间上，大佬们创建了一个素数表，这样可以最大限度的避免冲突。

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};const unsigned long* first = __stl_prime_list;const unsigned long* last = __stl_prime_list + __stl_num_primes;const unsigned long* pos = lower_bound(first, last, n);return pos == last ? *(last - 1) : *pos;}

这样我们哈希表的大小就在这么一组数里取，除了最后一个数，其他的树基本上也是靠近二倍的增长，因为最后一个还二倍就溢出了，所以对于最后一个数如果lower_bound取到值等于last，就给

个last-1的值。

取模加强

然后我们就可以对数据取模的部分进行改进，之前  数据%表大小  的方法太原始了，所以我们专门写一个函数来进化它。

size_t HashiFunc(const K& key){size_t hashi = key & (_table.size() - 1);hashi ^= (key >> (32 - _m));//m=16return hashi; }//更新后的扩容
if (_n * 10 / _table.size() >= 7){HashiTable<K, V,Hash> newht;++_m;newht._table.resize(pow(2, _m));for (auto& data : _table){if (data._isempty == no){newht.insert(data._kv);}}_table.swap(newht._table);}

这么改完之后虽然我们的冲突会因为和所有的位取模而降低冲突率，但是大小也上来了。

对非整数类型的数据进行转换

这一步我们没法直接改，因为本身它的数据就是不确定的，所以我们增加一个模板参数，写一个仿函数，默认就用我们的HashiFunc，如果使用者的类型不对，那么由他自己设计仿函数传入。

//比如我们变成string类型
//那么外部就自己写一个仿函数传入
struct stringhashi
{size_t operator()(const string& s){size_t hashi = 0;for (auto ch : s){hashi += ch; }return hashi;}
};

链地址法

直接定址法什么都好，就是对于离散数据消耗太高，于是大佬进化了一下，它还是开一片空间，但是这次它每个节点变成了其他结构，可以是链表，数组甚至红黑树，这样避免了相同值的消耗，我们只要头插即可。

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

那么对于哈希表来说，主体是不变的，并且相比于丐版，我们还要把加强的部分加上，让它进入全盛状态。

迭代器

	template<class K,class T,class Ref,class Ptr, class KorT,class Hash>struct HashIterator{typedef HashiNode<T> Node;typedef HashiTable<K, T, KorT, Hash> HT;typedef HashIterator<K, T, Ref, Ptr, KorT, Hash> Self;Node* _node;const HT* _ht;//我们不希望可以更改数据而打乱我们的映射 所以constHashIterator(Node* node, const HT* ht):_node(node),_ht(ht){}Ref operator*(){return _node->_data;}Ptr operator&(){return &_node->_data;}bool operator!=(const Self& s){return _node != s._node;}//由于是编译器里实现的是单向迭代器 所以我们有样学样也实现单向迭代器 只往后走Self& operator++(){if (_node->_next)//如果下一个不为空就往后走一步{_node = _node->_next;}else{KorT kt;//由于我们不知道传的是pair还是别的类型 所以干脆给个模版类型来定义Hash hash;//在++之前我们得先找到它在表里映射的位置size_t hashi = hash(kt(_node->_data)) & _ht->_table.size();++hashi;//因为并不是每个位置都一定有值 while (hashi < _ht.table.size()){    //所以每次先把位置的值给_node 如果是空也无所谓//如果不是空 就说明找到了 break就好 不然就++ 继续往后走 直到不为空_node = _ht->_table[hashi];if (_node){break;}else{++hashi;}}//如果++到了size的位置就说明走完了 所以用end()来标识_nodeif (hashi == _ht->_table.size()){_node = nullptr;}}return *this;}};

哈希表主体部分

插入

	//为了配合迭代器 所以返回类型更改为pair
pair<Iterator,bool> insert(const T& data){KorT kt;//利用我们的迭代器先找到数据的映射位置 Iterator it = find(kt(data));//如果能找到 说明已经存在 所以返回那个位置的迭代器就好 if (it != End()){return { it,false };}//Hash hash;//和前面的除留余数法不一样的是 这里只要不满就可以不扩容 尤其是我们还是链地址法if (_n == _table.size()){vector<Node*> newtable(__stl_next_prime(_table.size()) + 1);for (int i = 0; i < _table.size(); i++){//因为扩容的关系 除数改变也会改变取模结果 所以我们还得一个个重新算 而不能直接改Node* cur = _table[i];while (cur){//所以再来一个循环 把数据重新计算然后再头插到新表Node* next = cur->_next;size_t hashi = hash(kt(cur->_data)) % newtable.size();cur->_next = newtable[hashi];newtable[hashi] = cur;cur = next;}_table[i] = nullptr;}_table.swap(newtable);}//如果不考虑上面的扩容，这就是一个链表的头插 就多了一个先找映射位置的过程//先判断是pair还是普通类型 然后再用仿函数转换一下以防不是整形 然后再取到映射位置size_t hashi = hash(kt(data)) % _table.size();Node* newnode = new node(data);newnode->_next = _table[hashi];_table[hashi] = newnode;++_n;return { Iterator(newnode,this),true };}

查找

		Iterator find(const K& key){Hash hash;//找到映射位置size_t hashi = hash(key) % _table.size();//遍历Node* cur = _table[hashi];while (cur){if (kt(cur->_data) == key){return Iterator(cur,this);}cur = cur->_next;}//如果没有找到就返回空return End();}

相比起插入，查找简直不要太简单。

删除

这里虽然也不复杂，但是需要分情况删除，因为我们的节点结构是链表，所以删除的如果是头节点，我们需要先记录它的下一个位置，而如果不是头结点，那么我们还需要记录它的前一个节点。

 

bool erase(const K& key){size_t hashi = key % _table.size();//头结点的前一个一定是空Node* cur = _table[hashi];Node* prev = nullptr;//然后开始分情况遍历while (cur){//如果就是删头结点 那就简单了 直接链接即可if (kt(cur->_data) == key){if (prev == nullptr){_table[hashi] = cur->_next;}//不然就是前一个和后一个链接else{prev->_next = cur->_next;}//然后删除cur即可delete cur;return true;}//否则就往后走 然后继续遍历else{prev = cur;cur = cur->_next;}}//走到这里就代表删除失败return false;}

 

封装

UnorderSet

namespace cxk
{//由于我们的哈希桶实现的很通用 所以我们把该给的参数设置好就可以直接使用了template<class K,class Hash = HashiFun<K>>class UnderedSet{//仿函数 确定我们是什么类型的数据struct SetMorS{const K& operator()(const K& key){return key;}};public://迭代器部分的参数设置的和链表一样 不过不论是不是const迭代器 我们的数据都不允许更改 所以都加上consttypedef typename hashi_bucket::HashiTable<K, const K, SetMorS,Hash>::Iterator iterator;typedef typename hashi_bucket::HashiTable<K, const K, SetMorS,Hash>::Const_Iterator const_iterator;//复用即可iterator begin(){return _ht.Begin();}iterator end(){return _ht.End();}const_iterator begin() const{return _ht.Begin();}const_iterator end() const{return _ht.End();}pair<iterator, bool> insert(const K& key){return _ht.insert(key);}iterator find(const K& key){return _ht.find(key);}bool erase(const K& key){return _ht.erase(key);}private:hashi_bucket::HashiTable<K, const K, SetMorS,Hash> _ht;};
}

UnorderMap

namespace wyf
{template<class K,class V,class Hash = HashiFun<K>>class UnderedMap{//和set不一样的地方就是这里的数据类型是pair 所以传入的只有firststruct MapMorS{const K& operator()(const pair<K, V>& kv){return kv.first;}};public://同样的迭代器和const迭代器typedef typename hashi_bucket::HashiTable<K, pair<const K, V>, MapMorS,Hash>::Iterator iterator;typedef typename hashi_bucket::HashiTable<K, pair<const K, V>, MapMorS,Hash>::Const_Iterator const_iterator;//复用iterator begin(){return _ht.Begin();}iterator end() {return _ht.End();}const_iterator begin() const{return _ht.Begin();}const_iterator end() const{return _ht.End();}V& operator[](const K& key){pair<iterator, bool> ret = insert({ key,V() });return ret.first->second;}pair<iterator, bool> insert(const pair<K, V>& kv){return _ht.insert(kv);}iterator find(const K& key){return _ht.find(key);}bool erase(const K& key){return _ht.erase(key);}private:hashi_bucket::HashiTable<K, pair<const K, V>, MapMorS<K>,Hash> _ht;};
}

在我们对哈希的使用进行升级之后，大多数的操作只需要把我们设计好的参数准备好就可以直接复用，从而达成封装，所以封装其实并不困难，难的点在于对哈希升级的同时兼顾到封装的逻辑。