哈希及其封装实现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=16
return 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;//我们不希望可以更改数据而打乱我们的映射 所以const
HashIterator(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()来标识_node
if (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迭代器 我们的数据都不允许更改 所以都加上const
typedef 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 所以传入的只有first
struct 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;
};
}在我们对哈希的使用进行升级之后，大多数的操作只需要把我们设计好的参数准备好就可以直接复用，从而达成封装，所以封装其实并不困难，难的点在于对哈希升级的同时兼顾到封装的逻辑。