【C++】哈希(2萬字)

提示：文章寫完后，目錄可以自動生成，如何生成可參考右邊的幫助文檔

前言

unordered系列關聯式容器

unordered_map

unordered_map的文檔介紹

unordered_map的接口說明

unordered_set

底層結構

哈希概念

哈希沖突

哈希函數

哈希沖突解決

閉散列

線性探測的實現并改造

二次探測

開散列

開散列概念

開散列實現并改造 + 迭代器的實現

開散列增容

開散列與閉散列比較

不同的類型轉換成整型的操作

MyOrderedMap.h

MyOrderedSet.h

哈希的應用

位圖

位圖概念

位圖的實現

位圖應用

布隆過濾器

布隆過濾器提出

布隆過濾器概念

布隆過濾器的插入

布隆過濾器的查找

布隆過濾器刪除

布隆過濾器優點

布隆過濾器缺陷

布隆過濾器的面試題

哈希切割

總結

前言

世上有兩種耀眼的光芒，一種是正在升起的太陽，一種是正在努力學習編程的你!一個愛學編程的人。各位看官，我衷心的希望這篇博客能對你們有所幫助，同時也希望各位看官能對我的文章給與點評，希望我們能夠攜手共同促進進步，在編程的道路上越走越遠！

提示：以下是本篇文章正文內容，下面案例可供參考

unordered系列關聯式容器

在C++98中，STL提供了底層為紅黑樹結構的一系列關聯式容器，在查詢時效率可達到$log_2 N$，即最差情況下需要比較紅黑樹的高度次，當樹中的節點非常多時，查詢效率也不理想。最好的查詢是，進行很少的比較次數就能夠將元素找到，因此在C++11中，STL又提供了4個 unordered系列的關聯式容器，這四個容器與紅黑樹結構的關聯式容器使用方式基本類似，只是其底層結構不同，本文中只對unordered_map和unordered_set進行介紹， unordered_multimap和unordered_multiset學生可查看文檔介紹。

unordered_map

unordered_map的文檔介紹

unordered_map文檔介紹

unordered_map是存儲鍵值對的關聯式容器，其允許通過keys快速的索引到與其對應的value。
在unordered_map中，鍵值通常用于惟一地標識元素，而映射值是一個對象，其內容與此鍵關聯。鍵和映射值的類型可能不同。
在內部，unordered_map沒有對按照任何特定的順序排序，為了能在常數范圍內找到key所對應的value，unordered_map將相同哈希值的鍵值對放在相同的桶中。
unordered_map容器通過key訪問單個元素要比map快，但它通常在遍歷元素子集的范圍迭代方面效率較低。
unordered_maps實現了直接訪問操作符(operator[])，它允許使用key作為參數直接訪問 value。
它的迭代器至少是前向迭代器。

unordered_map的接口說明

1. unordered_map的構造

函數聲明	功能介紹
unordered_map	構造不同格式的unordered_map對象

2. unordered_map的容量

函數聲明	功能介紹
bool empty() const	檢測unordered_map是否為空
size_t size() const	獲取unordered_map的有效元素個數

3. unordered_map的迭代器

函數聲明	功能介紹
begin	返回unordered_map第一個元素的迭代器
end	返回unordered_map最后一個元素下一個位置的迭代器
cbegin	返回unordered_map第一個元素的const迭代器
cend	返回unordered_map最后一個元素下一個位置的const迭代器

4. unordered_map的元素訪問

函數聲明	功能介紹
operator[]	返回與key對應的value，沒有一個默認值

注意：該函數中實際調用哈希桶的插入操作，用參數key與V()構造一個默認值往底層哈希桶中插入，如果key不在哈希桶中，插入成功，返回V()，插入失敗，說明key已經在哈希桶中，將key對應的value返回。

5. unordered_map的查詢

函數聲明	功能介紹
iterator find(const K& key)	返回key在哈希桶中的位置
size_t count(const K& key)	返回哈希桶中關鍵碼為key的鍵值對的個數

注意：unordered_map中key是不能重復的，因此count函數的返回值最大為1

6. unordered_map的修改操作

函數聲明	功能介紹
insert	向容器中插入鍵值對
erase	刪除容器中的鍵值對
void clear()	清空容器中有效元素個數
void swap(unordered_map&)	交換兩個容器中的元素

7. unordered_map的桶操作

函數聲明	功能介紹
size_t bucket count()const	返回哈希桶中桶的總個數
size_t bucket size(size_t n) const	返回n號桶中有效元素的總個數
size_t bucket(const K& key)	返回元素key所在的桶號

unordered_set

unordered_set文檔介紹

底層結構

unordered系列的關聯式容器之所以效率比較高，是因為其底層使用了哈希結構。

哈希概念

順序結構以及平衡樹中，元素關鍵碼與其存儲位置之間沒有對應的關系，因此在查找一個元素時，必須要經過關鍵碼的多次比較。順序查找時間復雜度為O(N)，平衡樹中為樹的高度，即 O($log_2 N$)，搜索的效率取決于搜索過程中元素的比較次數。

理想的搜索方法：可以不經過任何比較，一次直接從表中得到要搜索的元素。

如果構造一種存儲結構，通過某種函數(hashFunc)使元素的存儲位置與它的關鍵碼之間能夠建立一一映射的關系，那么在查找時通過該函數可以很快找到該元素。

當向該結構中：

插入元素：根據待插入元素的關鍵碼，以此函數計算出該元素的存儲位置并按此位置進行存放
搜索元素：對元素的關鍵碼進行同樣的計算，把求得的函數值當做元素的存儲位置，在結構中按此位置取元素比較，若關鍵碼相等，則搜索成功

該方式即為哈希(散列)方法，哈希方法中使用的轉換函數稱為哈希(散列)函數，構造出來的結構稱為哈希表(Hash Table)(或者稱散列表)

例如：數據集合{1，7，6，4，5，9}；

哈希函數設置為：hash(key) = key % capacity；capacity為存儲元素底層空間總的大小。

用該方法進行搜索不必進行多次關鍵碼的比較，因此搜索的速度比較快。

哈希沖突

對于兩個數據元素的關鍵字$k_i$和 $k_j$(i != j)，有$k_i$ != $k_j$，但有：Hash($k_i$) == Hash($k_j$)，即：不同關鍵字通過相同哈希函數計算出相同的哈希地址，該種現象稱為哈希沖突或哈希碰撞。

比如：5、25、45分別去%20，映射的位置都是5。

哈希函數

引起哈希沖突的一個原因可能是：哈希函數設計不夠合理。

哈希函數設計原則：

哈希函數的定義域必須包括需要存儲的全部關鍵碼，而如果散列表允許有m個地址時，其值域必須在0到m-1之間
哈希函數計算出來的地址能均勻分布在整個空間中
哈希函數應該比較簡單

常見哈希函數：

1. 直接定址法--(常用)一一映射

取關鍵字的某個線性函數為散列地址：Hash（Key）= A*Key + B
優點：簡單、均勻
缺點：需要事先知道關鍵字的分布情況
使用場景：適合查找比較小且連續的情況

2. 除留余數法--(常用)

設散列表中允許的地址數為m，取一個不大于m，但最接近或者等于m的質數p作為除數，按照哈希函數：Hash(key) = key% p(p<=m)，將關鍵碼轉換成哈希地址

3. 平方取中法--(了解)

假設關鍵字為1234，對它平方就是1522756，抽取中間的3位227作為哈希地址；
再比如關鍵字為4321，對它平方就是18671041，抽取中間的3位671(或710)作為哈希地址
平方取中法比較適合：不知道關鍵字的分布，而位數又不是很大的情況

4. 折疊法--(了解)

折疊法是將關鍵字從左到右分割成位數相等的幾部分(最后一部分位數可以短些)，然后將這幾部分疊加求和，并按散列表表長，取后幾位作為散列地址。
折疊法適合事先不需要知道關鍵字的分布，適合關鍵字位數比較多的情況

5. 隨機數法--(了解)

選擇一個隨機函數，取關鍵字的隨機函數值為它的哈希地址，即H(key) = random(key),其中 random為隨機數函數。
通常應用于關鍵字長度不等時采用此法

6. 數學分析法--(了解)

設有n個d位數，每一位可能有r種不同的符號，這r種不同的符號在各位上出現的頻率不一定相同，可能在某些位上分布比較均勻，每種符號出現的機會均等，在某些位上分布不均勻只有某幾種符號經常出現。可根據散列表的大小，選擇其中各種符號分布均勻的若干位作為散列地址。例如：

注意：哈希函數設計的越精妙，產生哈希沖突的可能性就越低，但是無法避免哈希沖突

哈希沖突解決

解決哈希沖突兩種常見的方法是：閉散列和開散列

閉散列

閉散列：也叫開放定址法，當發生哈希沖突時，如果哈希表未被裝滿，說明在哈希表中必然還有空位置，那么可以把key存放到沖突位置中的“下一個” 空位置中去。那如何尋找下一個空位置呢？

1. 線性探測

比如下圖中的場景，現在需要插入元素44，先通過哈希函數計算哈希地址，hashAddr為4，因此44理論上應該插在該位置，但是該位置已經放了值為4的元素，即發生哈希沖突。

線性探測：從發生沖突的位置開始，依次向后探測，直到尋找到下一個空位置為止。

插入

通過哈希函數獲取待插入元素在哈希表中的位置
如果該位置中沒有元素則直接插入新元素，如果該位置中有元素發生哈希沖突，使用線性探測找到下一個空位置，插入新元素

查找

i = key % 表的大小 ?
如果i為不是要查找的key值，就線性往后查找，直到找到或者遇到空，如果找到表的結尾位置，還沒有找到key值，要往頭回繞。

刪除

采用閉散列處理哈希沖突時，不能隨便物理刪除哈希表中已有的元素，若直接刪除元素會影響其他元素的搜索。比如刪除元素4，如果直接刪除掉，44查找起來可能會受影響。因此線性探測采用標記的偽刪除法來刪除一個元素。

// 哈希表每個空間給個標記
// EMPTY此位置空， EXIST此位置已經有元素， DELETE元素已經刪除
enum State{EMPTY, EXIST, DELETE};

線性探測的實現并改造

// 開放定址法
namespace open_address
{// 狀態enum State{EMPTY,EXIST,DELETE};template<class K, class V>struct HashData  // 類模板名：哈希表的數據是結構體的變量(數據和狀態){pair<K, V> _kv;State _state = EMPTY; // 標記默認初始化為空，一旦存進去值，標記為存在，刪除值之后，標記位刪除};template<class K>struct HashFunc // 仿函數：將key轉換成整型{size_t operator()(const K& key){return (size_t)key;// 不傳參數三，默認將key強轉成整型}};// 特化 ---> 在實踐當中string經常做key，所以做特化template<>struct HashFunc<string>{size_t operator()(const string& s){size_t hash = 0;for (auto e : s){hash += e;hash *= 131;}return hash;}};// stoi：只有阿拉伯的字符串數字"1224546"才能用stoi；像"比特"就不能用stoi// 將字符串強制轉換成整型//struct HashFuncString//{//	size_t operator()(const string& s)//	{//		// "abcd"//		// "bcad"//		// "aadd"//		size_t hash = 0;//		for (auto e : s) //		{//          // 將字符串中的每個字符ascll碼值加起來//			hash += e;//			hash *= 131;// 這樣可以避免ascll碼值相加相等的情況//		}////		return hash;//	}//};// 參數三：默認缺省的仿函數Hash，沒有傳確定的仿函數，就用缺省的發仿函數HashFunc<K>template<class K, class V, class Hash = HashFunc<K>>class HashTable // 類模板名：哈希表{public:HashTable(size_t size = 10){_tables.resize(size);// 使用resize的話，size和capcacity就相等了}HashData<K, V>* Find(const K& key){Hash hs; // 仿函數的對象// 線性探測size_t hashi = hs(key) % _tables.size();while (_tables[hashi]._state != EMPTY){if (key == _tables[hashi]._kv.first&& _tables[hashi]._state == EXIST){return &_tables[hashi];}++hashi;// 如果++超出size，則取模從頭再來hashi %= _tables.size();}return nullptr;}bool Insert(const pair<K, V>& kv){// 如果已經有了，就返回falseif (Find(kv.first))return false;// 擴容的問題  不強制類型轉換成double的話，會有7/10==0的情況//if ((double)_n / (double)_tables.size() >= 0.7)if (_n * 10 / _tables.size() >= 7){// 方法一：//size_t newSize = _tables.size() * 2;// 不能在原表的空間上擴容空間，因為這樣會使映射關系混亂//vector<HashData> newTables(newSize); // 需要重新開辟一塊新空間遍歷舊表，重新映射到新表，那么就得此處再次寫一遍線性探測的代碼，再讓兩個表交換一下....//_tables.swap(newTables);// 方法二：HashTable<K, V, Hash> newHT(_tables.size() * 2);// 遍歷舊表，插入到新表for (auto& e : _tables){if (e._state == EXIST){newHT.Insert(e._kv);// 這里新表調用Insert()函數，并不會陷入死循環，因為空間*2倍之后，不會再次進入if判斷條件了// 直接復用線性探測的代碼}}_tables.swap(newHT._tables);// 交換兩表，那么舊表出了作用域就會調用析構函數，舊表數據會被釋放}Hash hs;// 線性探測size_t hashi = hs(kv.first) % _tables.size(); // 除和取模都不能除或取模0// 這里要模取的是size，而不是capacity；假設表中的capacity和size是不一樣的，// 放值是需要[]的，[]會檢查i < size，如果值放在模capacity的那塊區間，超出size會越界；// 所以只能放值在size區間處，放在size和capacity區間，則越界。while (_tables[hashi]._state == EXIST) // 此位置狀態為存在{++hashi;hashi %= _tables.size();// 模上一個size，走到尾之后，從頭再來}// 此位置狀態為空或被刪除_tables[hashi]._kv = kv;_tables[hashi]._state = EXIST;++_n; // 實際數據個數+1return true;}bool Erase(const K& key){HashData<K, V>* ret = Find(key);if (ret){_n--;ret->_state = DELETE; // 直接改狀態就相當于刪除了return true;}else{return false;}}private:vector<HashData<K, V>> _tables;size_t _n = 0;  // 實際存儲的數據個數};

思考：哈希表什么情況下進行擴容？如何擴容？

哈希沖突越多，效率就越低。
負載因子/載荷因子 = 實際存進去數據個數/表的大小。
閉散列(開放定址法)：負載因子一般會控制在0.7左右。

線性探測優點：實現非常簡單。

線性探測缺點：一旦發生哈希沖突，所有的沖突連在一起，容易產生數據“堆積”，即：不同關鍵碼占據了可利用的空位置，使得尋找某關鍵碼的位置需要許多次比較，導致搜索效率降低。

二次探測

線性探測的缺陷是產生沖突的數據堆積在一塊，這與其找下一個空位置有關系，因為找空位置的方式就是挨著往后逐個去找，因此二次探測為了避免該問題，找下一個空位置的方法為：$H_i$ = ($H_0$ + $i^2$ )% m, 或者：$H_i$ = ($H_0$ - $i^2$ )% m。其中：i = 1,2,3…， $H_0$是通過散列函數Hash(x)對元素的關鍵碼 key 進行計算得到的位置，m是表的大小。

對于下圖中如果要插入44，產生沖突，使用解決后的情況為：

研究表明：當表的長度為質數且表裝載因子a不超過0.5時，新的表項一定能夠插入，而且任何一個位置都不會被探查兩次。因此只要表中有一半的空位置，就不會存在表滿的問題。在搜索時可以不考慮表裝滿的情況，但在插入時必須確保表的裝載因子a不超過0.5，如果超出必須考慮增容。

因此：閉散列最大的缺陷就是空間利用率比較低，這也是哈希的缺陷。

開散列

開散列概念

開散列法又叫鏈地址法(開鏈法)，首先對關鍵碼集合用散列函數計算散列地址，具有相同地址的關鍵碼歸于同一子集合，每一個子集合稱為一個桶，各個桶中的元素通過一個單鏈表鏈接起來，各鏈表的頭結點存儲在哈希表中。

從上圖可以看出，開散列中每個桶中放的都是發生哈希沖突的元素。

開散列實現并改造 + 迭代器的實現

template<class K>
struct HashFunc // 仿函數：將key轉換成整型
{size_t operator()(const K& key){return (size_t)key;// 不傳參數三，默認將key強轉成整型}
};// 特化 ---> 在實踐當中string經常做key，所以做特化
template<>
struct HashFunc<string>
{size_t operator()(const string& s){size_t hash = 0;for (auto e : s){hash += e;hash *= 131;}return hash;}
};
// 哈希桶
namespace hash_bucket
{// T -> K// T -> pair<K, V>template<class T>struct HashNode{HashNode<T>* _next;T _data;HashNode(const T& data):_next(nullptr), _data(data){}};// 編譯器有一個原則：先定義或先聲明，再使用。// 在使用一個變量、類型、函數，要先定義或先聲明，再使用。因為編譯器為了提高編譯速度，有一個原則，// 比如：在使用一個變量、類型或函數時，編譯器只會向上找，不會向下找，只向上找，編譯速度會快很多。// 下面__HTIterator類模板中使用了HashTable<K, T, KeyOfT, Hash>，在上面沒有HashTable的定義，// 所以編譯器會報錯，因為編譯器不認識HashTable。// 類里面是不受影響的，因為類里面的規則，是在整個類域里面進行查找，編譯器把類域當成一個整體。// 那我們如果把整個HashTable類模板放在__HTIterator類模板之前，也會有問題，// 因為HashTable類模板中也使用了__HTIterator類型，這個地方就是一個經典的互相引用。// 那么這時候就只能增加一個前置聲明// 前置聲明(聲明中不能有缺省值)template<class K, class T, class KeyOfT, class Hash>class HashTable;template<class K, class T, class KeyOfT, class Hash>struct __HTIterator{typedef HashNode<T> Node;typedef HashTable<K, T, KeyOfT, Hash> HT;typedef __HTIterator<K, T, KeyOfT, Hash> Self;Node* _node;HT* _ht;__HTIterator(Node* node, HT* ht):_node(node), _ht(ht){}T& operator*(){return _node->_data;}T* operator->(){return &_node->_data;}// 返回的是哈希表中對應的元素Self& operator++(){// 當前哈希表所在位置的桶沒有走完if (_node->_next){// 當前桶還是節點_node = _node->_next;}else{// 當前桶走完了，找下一個桶KeyOfT kot;Hash hs;// _tables是HashTable的私有，所以_tables無法使用。我們可以采用友元的方法size_t hashi = hs(kot(_node->_data)) % _ht->_tables.size();// 找下一個桶hashi++;while (hashi < _ht->_tables.size()){if (_ht->_tables[hashi]){_node = _ht->_tables[hashi];break;}hashi++;}// 后面沒有桶了if (hashi == _ht->_tables.size()){_node = nullptr;}}return *this;}bool operator!=(const Self& s){return _node != s._node;}};// 參數三：仿函數，對于set來說，返回key；對于map來說，返回pair<key,value>中的key// 參數四：轉換成整型的仿函數template<class K, class T, class KeyOfT, class Hash>class HashTable{// 迭代器想要使用哈希表，就得把迭代器變成哈希表的友元template<class K, class T, class KeyOfT, class Hash>friend struct __HTIterator;// 普通類的友元，只有這一行代碼；類模板的友元，得把模板參數聲明一下typedef HashNode<T> Node;public:typedef __HTIterator<K, T, KeyOfT, Hash> iterator;iterator begin(){for (size_t i = 0; i < _tables.size(); i++){// 找到第一個桶的第一個節點if (_tables[i]){// this就是哈希表對象的地址return iterator(_tables[i], this);}}// 找不到返回空return end();}iterator end(){return iterator(nullptr, this);// 調用的是__HTIterator的構造函數}HashTable(){_tables.resize(10, nullptr);_n = 0;}// 這里析構的是表中所掛的哈希桶中的節點；vector出了作用域之后會自己調用析構函數// 哪怕我們自己顯示寫了析構函數，自定義類型出了作用域也會顯示調用析構~HashTable(){for (size_t i = 0; i < _tables.size(); i++){Node* cur = _tables[i];while (cur){Node* next = cur->_next;delete cur;cur = next;}_tables[i] = nullptr;}}pair<iterator, bool> Insert(const T& data){KeyOfT kot;// 此時Find()函數返回的是迭代器，不能轉換成bool值，所以要拿迭代器進行比較// 之前Find()函數返回的是節點的指針，可以隱式類型轉換成bool值/*	if (Find(kot(data)) != end())return false;*/iterator it = Find(kot(data));if (it != end())return make_pair(it, false);Hash hs;// 負載因子到1就擴容if (_n == _tables.size()){// 創建一個新表vector<Node*> newTables(_tables.size() * 2, nullptr);// 調用HashTable的構造函數for (size_t i = 0; i < _tables.size(); i++){// 取出舊表中節點，重新計算掛到新表桶中Node* cur = _tables[i];while (cur){Node* next = cur->_next;// 保存下一個節點// 頭插到新表size_t hashi = hs(kot(cur->_data)) % newTables.size();cur->_next = newTables[hashi];newTables[hashi] = cur;cur = next;// 查看下一個節點應該掛到那個桶中}_tables[i] = nullptr;// 將舊表置空}_tables.swap(newTables);// 交換兩表之后，舊表出了作用域就被釋放掉}size_t hashi = hs(kot(data)) % _tables.size();Node* newnode = new Node(data);// 頭插newnode->_next = _tables[hashi];_tables[hashi] = newnode;++_n;return make_pair(iterator(newnode, this), true);}iterator Find(const K& key){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _tables.size();Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){return iterator(cur, this);}cur = cur->_next;}return iterator(nullptr, this);}bool Erase(const K& key){KeyOfT kot;Hash hs;size_t hashi = hs(key) % _tables.size();Node* prev = nullptr;Node* cur = _tables[hashi];while (cur){if (kot(cur->_data) == key){// 刪除if (prev) // 不是桶中的第一個節點{prev->_next = cur->_next;}else // 是桶中的第一個節點{_tables[hashi] = cur->_next;}delete cur;--_n;return true;}prev = cur;cur = cur->_next;}return false;}private:vector<Node*> _tables; // 指針數組size_t _n;};
}

開散列增容

桶的個數是一定的，隨著元素的不斷插入，每個桶中元素的個數不斷增多，極端情況下，可能會導致一個桶中鏈表節點非常多，會影響的哈希表的性能，因此在一定條件下需要對哈希表進行增容，那該條件怎么確認呢？開散列最好的情況是：每個哈希桶中剛好掛一個節點，再繼續插入元素時，每一次都會發生哈希沖突，因此，在元素個數剛好等于桶的個數時，可以給哈希表增容。

開散列與閉散列比較

應用鏈地址法處理溢出，需要增設鏈接指針，似乎增加了存儲開銷。事實上：由于開地址法必須保持大量的空閑空間以確保搜索效率，如二次探查法要求裝載因子a <= 0.7，而表項所占空間又比指針大的多，所以使用鏈地址法反而比開地址法節省存儲空間。

不同的類型轉換成整型的操作

struct Date
{int _year;int _month;int _day;
};// 將日期類轉換成整型
struct HashFuncDate
{// 2024/6/3// 2024/3/6size_t operator()(const Date& d){size_t hash = 0;hash += d._year;hash *= 131;hash += d._month;hash *= 131;hash += d._day;hash *= 131;return hash;}
};

struct Person
{string _name;string _id;   // 身份證號碼string _tel;int _age;string _class;string _address;  // //...
};struct HashFuncPerson
{// 2024/6/3// 2024/3/6size_t operator()(const Person& p){size_t hash = 0;for (auto e : p._id){hash += e;hash *= 131;}return hash;}
};

MyOrderedMap.h

#include"HashTable.h"namespace bit
{template<class K, class V, class Hash = HashFunc<K>>class unordered_map{struct MapKeyOfT{const K& operator()(const pair<K, V>& kv){return kv.first;}};public:typedef typename hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}pair<iterator, bool> insert(const pair<K, V>& kv){return _ht.Insert(kv);}// Map要把[]實現出來，就得解決insert(),[]的本質就是insert()V& operator[](const K& key){pair<iterator, bool> ret = insert(make_pair(key, V()));return ret.first->second;}iterator find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, pair<const K, V>, MapKeyOfT, Hash> _ht;};void test_map1(){unordered_map<string, string> dict;dict.insert(make_pair("sort", ""));dict.insert(make_pair("left", ""));dict.insert(make_pair("right", "?"));for (auto& kv : dict){//kv.first += 'x';kv.second += 'y';cout << kv.first << ":" << kv.second << endl;}}
}

MyOrderedSet.h

#include"HashTable.h"namespace bit
{template<class K, class Hash = HashFunc<K>>class unordered_set{struct SetKeyOfT{const K& operator()(const K& key){return key;}};public:typedef typename hash_bucket::HashTable<K, const K, SetKeyOfT, Hash>::iterator iterator;iterator begin(){return _ht.begin();}iterator end(){return _ht.end();}bool insert(const K& key){return _ht.Insert(key);}pair<iterator, bool> find(const K& key){return _ht.Find(key);}bool erase(const K& key){return _ht.Erase(key);}private:hash_bucket::HashTable<K, const K, SetKeyOfT, Hash> _ht;};void test_set1(){unordered_set<int> us;us.insert(3);us.insert(1);us.insert(5);us.insert(15);us.insert(45);us.insert(7);unordered_set<int>::iterator it = us.begin();while (it != us.end()){//*it += 100;cout << *it << " ";++it;}cout << endl;int x = 0;cin >> x;if (us.find(x) != us.end()){cout << "找到了" << endl;}else{cout << "沒有找到" << endl;}for (auto e : us){cout << e << " ";}cout << endl;}}

int a[10];// 靜態數組
// 動態數組：malloc或new出來的數組是動態數組

哈希的應用

位圖

位圖概念

面試題

給40億個不重復的無符號整數，沒排過序。給一個無符號整數，如何快速判斷一個數是否在這40億個數中。【騰訊】

遍歷，時間復雜度O(N)
排序(O(NlogN))，利用二分查找: logN
位圖解決數據是否在給定的整形數據中，結果是在或者不在，剛好是兩種狀態，那么可以使用一個二進制比特位來代表數據是否存在的信息，如果二進制比特位為1，代表存在，為0 代表不存在。比如：

位圖概念

所謂位圖，就是用每一位來存放某種狀態，適用于海量數據，數據無重復的場景。通常是用來判斷某個數據存不存在的。

位圖的實現

namespace bit
{// 用一個非類型模板參數來控制位圖要開多大(位圖是存在于數組里面的)template<size_t N>class bitset{public:bitset(){// 假如：N是50個比特位，50除以32是1個整型，還有18個比特位沒有開出來，所以要向上取整// 多開一個整型_bits.resize(N / 32 + 1, 0);//cout << N << endl;}// 把x映射的位標記成1void set(size_t x){assert(x <= N);// x不能超出Nsize_t i = x / 32;// 計算x在第幾個整型上size_t j = x % 32;// 計算x在這個整型的第幾個位上_bits[i] |= (1 << j);}// 把x映射的位標記成0void reset(size_t x){assert(x <= N);size_t i = x / 32;size_t j = x % 32;_bits[i] &= ~(1 << j);}// 檢測x映射的標記位是1還是0bool test(size_t x){assert(x <= N);size_t i = x / 32;size_t j = x % 32;return _bits[i] & (1 << j);}private:vector<int> _bits;};void test_bitset(){bitset<100> bs1;bs1.set(50);bs1.set(30);bs1.set(90);for (size_t i = 0; i < 100; i++){if (bs1.test(i)){cout << i << "->" << "在" << endl;}else{cout << i << "->" << "不在" << endl;}}bs1.reset(90);bs1.set(91);cout << endl << endl;for (size_t i = 0; i < 100; i++){if (bs1.test(i)){cout << i << "->" << "在" << endl;}else{cout << i << "->" << "不在" << endl;}}// 這三種方式都可以開42億9千萬個位圖大小的空間bitset<-1> bs2;bitset<UINT_MAX> bs3;bitset<0xffffffff> bs4;}

位圖應用

快速查找某個數據是否在一個集合中
排序 + 去重
求兩個集合的交集、并集等
操作系統中磁盤塊標記

給定100億個整數，設計算法找到只出現一次的整數？

思路：出現1次和1次以上的整數需要兩個比特位：00 ---> 0次；01 ---> 1次；10 ---> 2次及以上。

代碼展示：

template<size_t N>
class two_bit_set
{
public:void set(size_t x){// 00 -> 01if (_bs1.test(x) == false&& _bs2.test(x) == false){_bs2.set(x);}// 01 -> 10else if (_bs1.test(x) == false&& _bs2.test(x) == true){_bs1.set(x);_bs2.reset(x);}}//int test(size_t x)//{//	if (_bs1.test(x) == false//		&& _bs2.test(x) == false)//	{//		return 0;//	}//	else if (_bs1.test(x) == false//		&& _bs2.test(x) == true)//	{//		return 1;//	}//	else//	{//		return 2; // 2次及以上//	}//}bool test(size_t x){if (_bs1.test(x) == false&& _bs2.test(x) == true){return true;}return false;}
private:bitset<N> _bs1;// 自定義類型的對象會去調用它的構造函數bitset<N> _bs2;
};void test_bitset2()
{int a[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 };two_bit_set<100> bs;for (auto e : a){bs.set(e);}for (size_t i = 0; i < 100; i++){//cout << i << "->" << bs.test(i) << endl;if (bs.test(i)){cout << i << endl;}}
}

給兩個文件，分別有100億個整數，我們只有1G內存，如何找到兩個文件交集？

思路：分別set到兩個位圖，同時為1的就是交集。

1G內存是夠的，100億個整數，并不需要100億個比特位，因為整數最多42億9千萬個，所以說映射的位圖只需要42億9千萬個位，42億9千萬個比特位換算成1G，兩個0.5G就是1G。

?1GB是2的30次方，是10億字節，100億字節是10G，那么100億個整型是40G。

代碼展示：

void test_bitset3()
{int a1[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6 };int a2[] = { 5,3,5,99,6,99,33,66 };bitset<100> bs1;bitset<100> bs2;for (auto e : a1){bs1.set(e);}for (auto e : a2){bs2.set(e);}for (size_t i = 0; i < 100; i++){// 尋找交集if (bs1.test(i) && bs2.test(i)){cout << i << endl;}}
}

位圖應用變形：1個文件有100億個int，1G內存，設計算法找到出現次數不超過2次的所有整數

內存當中一般是存不下這些值，這些值都是存在文件里面的。位圖不是開40億，而是按照范圍來開的(42億9千萬)，因為它的范圍是無符號的整數，(0~2^32-1)。

采用兩個比特位：00 ---> 0次；01 ---> 1次；10 ---> 2次；11 ---> 3次及以上

給定100億個整數，只有512M，需要在512M內存中設計算法找到只出現一次的整數？

因為1G是10億字節，1G是2^30，1G是42億9千萬個比特位，整數的范圍最大才到42億9千萬，所以100億個整數中有大量是重復的數字，所以要在512M內存中查找只出現一次的整數，可以讓42億9千萬個整數分成兩份，因為512M是是42億9千萬個比特位的一半。

先查找前一半，再查找后一半，映射的過程中就是去重的過程。

布隆過濾器

布隆過濾器提出

我們在使用新聞客戶端看新聞時，它會給我們不停地推薦新的內容，它每次推薦時要去重，去掉那些已經看過的內容。問題來了，新聞客戶端推薦系統如何實現推送去重的？用服務器記錄了用戶看過的所有歷史記錄，當推薦系統推薦新聞時會從每個用戶的歷史記錄里進行篩選，過濾掉那些已經存在的記錄。如何快速查找呢？

用哈希表存儲用戶記錄，缺點：浪費空間
用位圖存儲用戶記錄，缺點：位圖一般只能處理整形，如果內容編號是字符串，就無法處理了。
將哈希與位圖結合，即布隆過濾器

布隆過濾器概念

布隆過濾器是由布隆（Burton Howard Bloom）在1970年提出的一種緊湊型的、比較巧妙的概率型數據結構，特點是高效地插入和查詢，可以用來告訴你 “某樣東西一定不存在或者可能存在”，它是用多個哈希函數，將一個數據映射到位圖結構中。此種方式不僅可以提升查詢效率，也可以節省大量的內存空間。

布隆過濾器的插入

#pragma once
#include<bitset>
#include<string>struct HashFuncBKDR
{// BKDRsize_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash *= 131;hash += ch;}return hash;}
};struct HashFuncAP
{// APsize_t operator()(const string& s){size_t hash = 0;for (size_t i = 0; i < s.size(); i++){if ((i & 1) == 0) // 偶數位字符{hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));}else              // 奇數位字符{hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));}}return hash;}
};struct HashFuncDJB
{// DJBsize_t operator()(const string& s){size_t hash = 5381;for (auto ch : s){hash = hash * 33 ^ ch;}return hash;}
};
// 參數三：三個哈希仿函數的個數，表示一個值能映射3個位
template<size_t N,class K = string,class Hash1 = HashFuncBKDR,class Hash2 = HashFuncAP,class Hash3 = HashFuncDJB>
class BloomFilter
{
public:void Set(const K& key){// 比如：插入第一個數，映射0~M-1的比特位區間// 一個值要映射到三個比特位上，為了減少沖突size_t hash1 = Hash1()(key) % M;size_t hash2 = Hash2()(key) % M;size_t hash3 = Hash3()(key) % M;_bs->set(hash1);_bs->set(hash2);_bs->set(hash3);}// 這里不需要寫reset()刪除函數，因為刪除百度，騰訊判斷也可能不在了。因為百度和騰訊可能會映射到同一個位置bool Test(const K& key){// 值映射的三個比特位上，只要有一個比特位為0，就是該值不在哈希表中size_t hash1 = Hash1()(key) % M;if (_bs->test(hash1) == false)return false;size_t hash2 = Hash2()(key) % M;if (_bs->test(hash2) == false)return false;size_t hash3 = Hash3()(key) % M;if (_bs->test(hash3) == false)return false;return true; // 存在誤判(有可能3個位都是跟別人沖突的，所以誤判)}private:// const size_t M = 10 * N;// 我們不能用這種成員變量，因為這個成員變量是屬于對象的，只是聲明，沒有空間，只在初始化列表才會初始化// 加一個靜態static就可以了，那么這個變量就在靜態區，就不屬于對象了，而是屬于整個類// N：比特位。插入一個整數，也就是一個整數映射一個比特位，比特位擴容10倍的Nstatic const size_t M = 10 * N; // 想降低誤判率：可以增大比特位的空間bit::bitset<M> _bs;// 如果就是想要使用庫里面的bitset，可以new在堆區開辟一個std::bitset<M>類型的空間，將空間的地址給_bs//std::bitset<M>* _bs = new std::bitset<M>;
};// 庫里面的stl::bitset<M>類型所開辟的空間是開在對象里面的，這個對象是一個靜態數組
// 我們自己用vector<>實現的bitset是調用resize()函數開辟空間是在堆上的void TestBloomFilter1()
{string strs[] = { "百度","字節","騰訊" };// 中文是由多個字符構成的BloomFilter<10> bf;for (auto& s : strs){bf.Set(s);}for (auto& s : strs){cout << bf.Test(s) << endl;}for (auto& s : strs){cout << bf.Test(s + 'a') << endl;}cout << bf.Test("擺渡") << endl;cout << bf.Test("百渡") << endl;
}