C++_哈希

1. unordered系列关联式容器

在C++98中，STL提供了底层为红黑树结构的一系列关联式容器，在查询时效率可达到$log_2 N$，即最差情况下需要比较红黑树的高度次，当树中的节点非常多时，查询效率也不理想。最好的查询是，进行很少的比较次数就能够将元素找到，因此在C++11中，STL又提供了4个 unordered系列的关联式容器，这四个容器与红黑树结构的关联式容器使用方式基本类似，只是其底层结构不同

哈希表与红黑树封装出来的容器的区别
1undered_xxx是单向迭代器
2unordered_xxx遍历出来不是有序
在用法上undered_xxx和xxx基本上没什么区别就是底层的实现一个是哈希一个是红黑树

哈希：存储的值跟存储的位置建立出一个对应的关系

2. 底层结构

2.1哈希概念

顺序结构以及平衡树中，元素关键码与其存储位置之间没有对应的关系，因此在查找一个元素时，必须要经过关键码的多次比较。顺序查找时间复杂度为O(N)，平衡树中为树的高度，即 O($log_2 N$)，搜索的效率取决于搜索过程中元素的比较次数。
理想的搜索方法：可以不经过任何比较，一次直接从表中得到要搜索的元素。如果构造一种存储结构，通过某种函数(hashFunc)使元素的存储位置与它的关键码之间能够建立一一映射的关系，那么在查找时通过该函数可以很快找到该元素。
这种函数就是哈希函数，用来求一个哈希值

2.2哈希冲突

不同关键字通过相同哈希哈数计算出相同的哈希地址，该种现象称为哈希冲突或哈希碰撞。

2.3哈希函数

引起哈希冲突的一个原因就是哈希函数设计的不够合理。

常见哈希函数
1 直接定址法
取关键字的某个线性函数为散列地址：Hash（Key）= A*Key + B
优点：简单、均匀
缺点：需要事先知道关键字的分布情况
使用场景：适合查找比较小且连续的情况
2 除留余数法
设散列表中允许的地址数为m，取一个不大于m，但最接近或者等于m的质数p作为除数，按照哈希函数：Hash(key) = key% p(p将关键码转换成哈希地址
3. 平方取中法--(了解)
4. 折叠法--(了解)
5. 随机数法--(了解)
6. 数学分析法--(了解)

注意：哈希函数设计的越精妙，产生哈希冲突的可能性就越低，但是无法避免哈希冲突

2.4哈希冲突解决

1 闭散列-开放定址法
1.线性探测
线性探测当遇到挨着的一系列值的时候，会发生拥堵
缺点就是你的位置被占用的时候最好不要取占用别人的位置
当删除的时候，不能随便删除已有元素，而是用标记法来伪删除一个元素
那么哈希表什么情况下发生扩容讷？如何扩容
线性探测的实现：
bool Insert(const pair<K, V>& kv)
{//通过载荷因子来判断是否需要扩容if ((double)_n / (double)_table.size() >= 0.7){//这时候扩容，新创建一个表， 然后将旧表的数据插入到新的表里面//最后交换新旧表的_tableHashTable<K, V, HashiFunc> newTB;size_t newsize = _table.size() * 2;newTB._table.resize(newsize);for (size_t i = 0; i < _table.size(); i++){if (_table[i]._state == EXIST){newTB.Insert(_table[i]._kv);}}_table.swap(newTB._table);}//线性探索HashiFunc hfunc;size_t Hashi = hfunc(kv.first) % _table.size();while (_table[Hashi]._state != EMPTY){Hashi++;Hashi %= _table.size();}_table[Hashi]._kv = kv;_table[Hashi]._state = EXIST;_n++;return true;
}
2.二次探测
其实就是找空位置的方法是通过另外一种算hashi值的方法去找空位
2 开散列-链地址法
开散列法又叫链地址法(开链法)，首先对关键码集合用散列函数计算散列地址，具有相同地址的关键码归于同一子集合，每一个子集合称为一个桶，各个桶中的元素通过一个单链表链接起来，各链表的头结点存储在哈希表中。
从上图可以看出，开散列中每个桶中放的都是发生哈希冲突的元素。

字符串哈希值的特殊算法：

template<class T>  
size_t BKDRHash(const T *str)  
{  register size_t hash = 0;  while (size_t ch = (size_t)*str++)  {         hash = hash * 131 + ch;         }  return hash;  
}

2.5开散列与闭散列比较

应用链地址法处理溢出，需要增设链接指针，似乎增加了存储开销。事实上：由于开地址法必须保持大量的空闲空间以确保搜索效率，如二次探查法要求装载因子a ，而表项所占空间又比指针大的多，所以使用链地址法反而比开地址法节省存储空间。

3. 模拟实现

模拟实现需要按照步骤完成

1、哈希表

注意这里传的是T,T可以位K,也可以为pair<K,V>，封装的时候再去处理

template <class T>
struct HashiNode
{T _Data;HashiNode<T>* next;HashiNode(const T& Data):_Data(Data),next(nullptr){}};

迭代器的实现

//前置声明，因为这个迭代器里面用到了
template <class K, class T, class KeyOfT, class HashiFunc>
class HashBucket;template <class K, class T,class Ptr,class Ref, class KeyOfT, class HashiFunc>
struct HTIterator
{typedef HashiNode<T> Node;typedef HTIterator<K, T,Ptr,Ref, KeyOfT, HashiFunc> Self;typedef HTIterator<K, T, T*, T&, KeyOfT, HashiFunc> Iterator;Node* _node;const HashBucket<K, T, KeyOfT, HashiFunc>* _pht;//因为这里要传一个表，在const_iterator//里面end()返回的是带const修饰的HTIterator(Node* node,const HashBucket<K, T, KeyOfT, HashiFunc>* pht):_node(node),_pht(pht){}HTIterator(const Iterator& it):_node(it._node), _pht(it._pht){}Self& operator++(){//一个桶找完了之后要找到下一个桶if (_node->next){_node = _node->next;}else{KeyOfT kot;HashiFunc hf;size_t Hashi = hf(kot(_node->_Data))%_pht->_hashtable.size();++Hashi;//查找下一个不为空的桶while (Hashi < _pht->_hashtable.size()){if (_pht->_hashtable[Hashi]){_node = _pht->_hashtable[Hashi];return *this;}else{Hashi++;}}_node =  nullptr;}return *this;}bool operator!=(const Self& s){return _node != s._node;}Ref operator*(){return _node->_Data;}Ptr operator->(){return &_node->_Data;}};

哈希表的实现（底层用桶）

template <class K,class T, class KeyOfT,class HashiFunc>
class HashBucket
{typedef HashiNode<T> Node;template <class K, class T,class Ptr,class Ref, class KeyOfT, class HashiFunc>friend struct HTIterator;
public:typedef HTIterator<K, T,T*,T&, KeyOfT, HashiFunc> iterator;typedef HTIterator<K, T,const T*,const T&, KeyOfT, HashiFunc> const_iterator;iterator begin(){//找到第一个桶for (size_t i = 0; i < _hashtable.size(); i++){if (_hashtable[i]){return iterator(_hashtable[i], this);}}return iterator(nullptr, this);}iterator end(){return iterator(nullptr, this);}const_iterator begin()const{//找到第一个桶for (size_t i = 0; i < _hashtable.size(); i++){if (_hashtable[i]){return const_iterator(_hashtable[i], this);}}return const_iterator(nullptr, this);}const_iterator end()const{return const_iterator(nullptr, this);}HashBucket(){_hashtable.resize(10,nullptr);}~HashBucket(){for (size_t i = 0; i < _hashtable.size(); i++){Node* cur = _hashtable[i];Node* next = nullptr;while (cur){next = cur->next;delete cur;cur = next;}_hashtable[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 (_n == _hashtable.size()){size_t newsize = _hashtable.size() * 2;vector<Node*> Newhb ;Newhb.resize(newsize, nullptr);//将原来表里面的数据插入到新的表里面for (size_t i = 0; i < _hashtable.size(); i++){Node* cur = _hashtable[i];while (cur){Node* next = cur->next;//头插到新的表里面HashiFunc hf;size_t Hashi = hf(kot(cur->_Data)) % Newhb.size();cur->next = Newhb[Hashi];Newhb[Hashi] = cur;cur = next;}_hashtable[i] = nullptr;}_hashtable.swap(Newhb);}HashiFunc hf;size_t Hashi = hf(kot(Data)) % _hashtable.size();Node* newnode = new Node(Data);newnode->next = _hashtable[Hashi];_hashtable[Hashi] = newnode;_n++;return make_pair(iterator(newnode,this),true);}void Print(){for (size_t i = 0; i < _hashtable.size(); i++){Node* cur = _hashtable[i];printf("[%d]:", i);while (cur){//cout << cur->_Data << "->";cur = cur->next;}cout << "NULL";cout << endl;}}iterator Find(const K& key){HashiFunc hf;KeyOfT kot;size_t Hashi = hf(key) % _hashtable.size();Node* cur = _hashtable[Hashi];while (cur){if (kot(cur->_Data) == key){return iterator(cur, this);}cur = cur->next;}return end();}bool Earse(const K& key){HashiFunc hf;KeyOfT kot;size_t Hashi = hf(key) % _hashtable.size();Node* prev = nullptr;Node* cur = _hashtable[Hashi];if (kot(cur->_Data) == key){_hashtable[Hashi] = cur->next;delete cur;return true;}while (cur){if (kot(cur->_Data) == key){prev->next = cur->next;_n--;delete cur;return true;}prev = cur;cur = cur->next;}return false;}
private:vector<Node*> _hashtable;size_t _n = 0;
};

2、封装map和set

set:

template<class K, class HashiFunc = DefHashiFunc<K>>
class unordered_set
{struct SetKeyOfT{const K& operator()(const K& key){return key;}};typedef typename Hash_Bucket::HashBucket<K, K, SetKeyOfT, HashiFunc>::const_iterator iterator;typedef typename Hash_Bucket::HashBucket<K, K, SetKeyOfT, HashiFunc>::const_iterator const_iterator;public:pair<iterator, bool> insert(const K& key){//return _ht.Insert(key);pair<typename Hash_Bucket::HashBucket<K, K, SetKeyOfT, HashiFunc>::iterator, bool> ret = _ht.Insert(key);return pair<const_iterator, bool>(ret.first, ret.second);}iterator begin()const{return _ht.begin();}iterator end()const{return _ht.end();}private:Hash_Bucket::HashBucket<K, K, SetKeyOfT, HashiFunc> _ht;
};

map:

template<class K,class V, class HashiFunc = DefHashiFunc<K>>
class unordered_map
{struct MapKeyOfT{const K& operator()(const pair<K,V>& kv){return kv.first;}};typedef typename Hash_Bucket::HashBucket<K, pair<K, V>, MapKeyOfT, HashiFunc>::iterator iterator;typedef typename Hash_Bucket::HashBucket<K, pair<const K, V>, MapKeyOfT, HashiFunc>::const_iterator const_iterator;public:pair<iterator,bool> insert(const pair<K, V>& kv){return _ht.Insert(kv);}iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}V& operator[](const K& key){pair<iterator, bool> ret = _ht.Insert(make_pair(key, V()));return ret.first->second;}
private:Hash_Bucket::HashBucket<K, pair<K, V>, MapKeyOfT, HashiFunc> _ht;};

3、普通迭代器

4、const迭代器

5、insert返回值 operator[]

6、key不能修改的问题

4.哈希的应用

4.1 位图

所谓位图，就是用每一位来存放某种状态，适用于海量数据，数据无重复的场景。通常是用来判断某个数据存不存在的。

位图的实现：

template<size_t N>
class bitset
{
public:bitset(){_a.resize(N / 32 + 1);}void set(size_t x){size_t i = x / 32;size_t j = x % 32;_a[i] |= (1 << j);}void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_a[i] &= (~(1 << j));}bool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _a[i] & (1 << j);}
private:vector<int> _a;
};