點擊跳轉(zhuǎn)至文章： 【C++/STL】：哈希 – 線性探測&哈希桶

🚀🚀前言

在前面的文章里我們已經(jīng)學(xué)習(xí)了什么是哈希和以哈希表為底層的unordered系列容器的使用。本篇文章的位圖&布隆過濾器也是哈希思想下的產(chǎn)物，經(jīng)常使用它們來解決有關(guān)海量數(shù)據(jù)的問題。

一，位圖

1. 位圖的概念

在引出位圖的概念之前，先來看一個經(jīng)典面試題：

深入分析：

解題思路2是否可行，我們先算算40億個數(shù)據(jù)?概需要多少內(nèi)存。
1G = 1024MB =1024 * 1024KB = 1024*1024 * 1024byte約等于10億多byte，那么40億個整數(shù)約等于16G，說明40億個數(shù)是無法直接放到內(nèi)存中的，只能放到硬盤文件中。而二分查找只能對內(nèi)存數(shù)組中的有序數(shù)據(jù)進(jìn)行查找。

解題思路3：數(shù)據(jù)是否在給定的整形數(shù)據(jù)中，結(jié)果是在或者不在，剛好是兩種狀態(tài)，那么可以使??個?進(jìn)制?特位來代表數(shù)據(jù)是否存在的信息，如果?進(jìn)制?特位為1，代表存在，為0代表不存在。

那么我們設(shè)計?個?二進(jìn)制比特位表?數(shù)據(jù)是否存在的數(shù)據(jù)結(jié)構(gòu)，這個數(shù)據(jù)結(jié)構(gòu)就叫位圖。

2. STL庫中的位圖

根據(jù)文檔可知，位圖bitset 是非類型模板，N是指需要多少比特位。使用時需要包含頭文件：

#include <bitset>

位圖常用的核心接口主要有三個：

(1) x 映射位標(biāo)記成1(插入 x，有這個數(shù)據(jù)了)

(2) x 映射位標(biāo)記成0(刪除 x，沒有這個數(shù)據(jù)了)

(3) 檢查是否存在這個數(shù)據(jù)
x映射的位是1，返回真
x映射的位是0，返回假

3. 位圖的設(shè)計

位圖本質(zhì)是?個直接定址法的哈希表，每個整型值映射?個bit位，位圖提供控制這個bit的相關(guān)接口。

實現(xiàn)中需要注意的是，C/C++沒有對應(yīng)位的類型，只能看int/char這樣整形類型，我們再通過位運算去控制對應(yīng)的?特位。?如我們數(shù)據(jù)存到vector< int >中，相當(dāng)于每個int值映射對應(yīng)的32個值，?如第?個整形映射0-31對應(yīng)的位，第?個整形映射32-63對應(yīng)的位，后?的以此類推，那么來了?個整形值x，i = x / 32；j = x % 32；計算出x映射的值在vector的第 i 個整形數(shù)據(jù)的第 j 位。

4. 位圖的模擬實現(xiàn)

#include<vector>//非類型模板參數(shù)。需要多少比特位
template <size_t N>
class bitset
{
public:bitset(){_bs.resize(N / 32 + 1);}//x映射位標(biāo)記成1void set(size_t x){//映射的位置：第i個整型數(shù)據(jù)的第j位size_t i = x / 32;size_t j = x % 32;_bs[i] |= (1 << j);}//x映射位標(biāo)記成0void reset(size_t x){size_t i = x / 32;size_t j = x % 32;_bs[i] &= (~(1 << j));}//x映射的位是1，返回真//x映射的位是0，返回假bool test(size_t x){size_t i = x / 32;size_t j = x % 32;return _bs[i] & (1 << j);}
private:vector<size_t> _bs;
};

5. 位圖的優(yōu)缺點

優(yōu)點：增刪查改快，節(jié)省空間
缺點：只適?于整形

6. 位圖相關(guān)考察題?

深入分析：

第一題和第三題是同一類型的題，我們先來分析這兩題。首先我們知道把數(shù)據(jù)放入位圖中只能標(biāo)記在或不在兩種狀態(tài)，而題目要求的是找出出現(xiàn)幾次的數(shù)據(jù)，可能是出現(xiàn)0次，1次……，顯然單用一個位圖的一個比特位是無法滿足的。

用兩個位圖的標(biāo)記就可以解決。我們規(guī)定00表示數(shù)據(jù)出現(xiàn)0次，01表示數(shù)據(jù)出現(xiàn)1次，10表示數(shù)據(jù)出現(xiàn)2次，11表示數(shù)據(jù)出現(xiàn)3次及以上

代碼實現(xiàn)如下：
注意：這里用的bitset是上文我們自己實現(xiàn)的bitset。

我們針對第一題和第三題設(shè)計一個結(jié)構(gòu)：

template<size_t N>
class twobitset
{
public:void set(size_t x){bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);if (!bit1 && !bit2) // 00->01{_bs2.set(x);}else if (!bit1 && bit2) // 01->10{_bs1.set(x);_bs2.reset(x);}else if (bit1 && !bit2) // 10->11{_bs1.set(x);_bs2.set(x);}}// 返回0 出現(xiàn)0次數(shù)// 返回1 出現(xiàn)1次數(shù)// 返回2 出現(xiàn)2次數(shù)// 返回3 出現(xiàn)2次及以上int get_count(size_t x){bool bit1 = _bs1.test(x);bool bit2 = _bs2.test(x);if (!bit1 && !bit2){return 0;}else if (!bit1 && bit2){return 1;}else if (bit1 && !bit2){return 2;}else{return 3;}}private:bitset<N> _bs1;bitset<N> _bs2;
};//測試代碼，可以統(tǒng)計出100以內(nèi)哪個數(shù)據(jù)出現(xiàn)了幾次
void test_twobitset()
{twobitset<100> tbs; //開100個bit位int a[] = { 5,7,9,2,5,99,5,5,7,5,3,9,2,55,1,5,6,6,6,6,7,9 };for (auto e : a){tbs.set(e);}for (size_t i = 0; i < 100; ++i){cout << i << "->" << tbs.get_count(i) << endl;//if (tbs.get_count(i) == 1 || tbs.get_count(i) == 2)//cout << i << endl;}
}

第二題的代碼實現(xiàn)：
把數(shù)據(jù)分別放入兩個位圖中，如果兩個位圖的標(biāo)記均為1，說明都存在，就是二者的交集。

void test_bitset1()
{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 };bit::bitset<100> bs1;bit::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;}
}

二，布隆過濾器

有?些場景下?，有?量數(shù)據(jù)需要判斷是否存在，?這些數(shù)據(jù)不是整形，那么位圖就不能使?了，使?紅?樹/哈希表等內(nèi)存空間可能不夠。這些場景就需要布隆過濾器來解決。

1. 布隆過濾器的概念

布隆過濾器是?種可以?來告訴你"某樣?xùn)|西?定不存在或者可能存在"的數(shù)據(jù)結(jié)構(gòu)，它是?多個哈希函數(shù)，將?個數(shù)據(jù)映射到位圖結(jié)構(gòu)中。

布隆過濾器的思路就是把key先映射轉(zhuǎn)成哈希整型值，再映射?個位，如果只映射?個位的話，沖突率會?較多，所以可以通過多個哈希函數(shù)映射多個位，降低沖突率。

布隆過濾器這?跟哈希表不?樣，它?法解決哈希沖突的，因為他壓根就不存儲這個值，只標(biāo)記映射的位。它的思路是盡可能降低哈希沖突。判斷?個值key在是不準(zhǔn)確的，判斷?個值key不在是準(zhǔn)確的。

2. 布隆過濾器的實現(xiàn)

說明：我們這里用的bitset是我們上文自己實現(xiàn)的bitset，不是庫里的。

#include "BitSet.h"
#include <string>struct HashFuncBKDR
{size_t operator()(const std::string& s){size_t hash = 0;for (auto ch : s){hash *= 31;hash += ch;}return hash;}
};struct HashFuncAP
{ size_t operator()(const std::string& s){size_t hash = 0;for (size_t i = 0; i < s.size(); i++){if ((i & 1) == 0) // 偶數(shù)位字符hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));else              // 奇數(shù)位字符hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));}return hash;}
};struct HashFuncDJB
{size_t operator()(const std::string& s){size_t hash = 5381;for (auto ch : s)hash = hash * 33 ^ ch;return hash;}
};//要用多個哈希函數(shù)多映射幾個位，以便降低哈希沖突
template <size_t N,size_t X = 5,class K = string,class Hash1 = HashFuncBKDR,class Hash2 = HashFuncAP,class Hash3 = HashFuncDJB>
class BloomFilter
{
public:void Set(const K& key){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);}//如果其中一個位為0，就確定不在，如果都為1，那就在(存在誤判)bool Test(const K& key){size_t hash1 = Hash1()(key) % M;if (!_bs.test(hash1))return false;size_t hash2 = Hash2()(key) % M;if (!_bs.test(hash2))return false;size_t hash3 = Hash3()(key) % M;if (!_bs.test(hash3))return false;return true;}
private:static const size_t M = N * X; //布隆過濾器的bit長度bit::bitset<M> _bs;
};//測試代碼
void TestBloomFilter1()
{BloomFilter<10> bf;bf.Set("豬八戒");bf.Set("孫悟空");bf.Set("唐僧");cout << bf.Test("豬八戒") << endl;cout << bf.Test("孫悟空") << endl;cout << bf.Test("唐僧") << endl;cout << bf.Test("沙僧") << endl;cout << bf.Test("豬八戒1") << endl;cout << bf.Test("豬戒八") << endl;
}

3. 布隆過濾器刪除問題

布隆過濾器默認(rèn)是不?持刪除的，因為?如"豬?戒“和”孫悟空“都映射在布隆過濾器中，他們映射的位有?個位是共同映射的(沖突的)，如果我們把孫悟空刪掉，那么再去查找“豬?戒”會查找不到，因為那么“豬?戒”間接被刪掉了。

4. 布隆過濾器的優(yōu)缺點

優(yōu)點：增刪查改快，節(jié)省空間
缺點：只適?于整形