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;
};