目錄

一、位圖

1、位圖的概念?

2、位圖的實(shí)現(xiàn)?

?①、基本結(jié)構(gòu)

②、set?

③、reset：

④、test?

⑤、問題：

⑥、位圖優(yōu)缺點(diǎn)及應(yīng)用：?

⑦、完整代碼及測試

二、布隆過濾器

1、布隆過濾器的提出

2、布隆過濾器的實(shí)現(xiàn)

①、基本結(jié)構(gòu)

②、三個(gè)Hash仿函數(shù)實(shí)現(xiàn)

③、 set

④、 test

⑤、?刪除

?⑥、完整代碼及測試

⑦、 優(yōu)缺點(diǎn)

---

一、位圖

1、位圖的概念?

1. 面試題

給 40 億個(gè)不重復(fù)的無符號整數(shù)，沒排過序。給一個(gè)無符號整數(shù)，如何快速判斷一個(gè)數(shù)是否在

這 40 億個(gè)數(shù)中?！掘v訊】

查找一個(gè)數(shù)在不在，其實(shí)就是key模型，那常見的幾種解法如下：

• 1. 遍歷，時(shí)間復(fù)雜度O(N)
• 2. 排序(O(NlogN))，利用二分查找: logN
• 3. 位圖解決

前兩個(gè)方案的問題：數(shù)據(jù)量太大，放不到內(nèi)存中。

我們可以先考慮40億個(gè)不重復(fù)的無符號整數(shù)占多少空間？

10億個(gè)字節(jié)是1個(gè)G，而40億個(gè)整數(shù)，一個(gè)整數(shù)4個(gè)字節(jié)，即需要160億（9個(gè)0）個(gè)字節(jié)，即需要16G，這些數(shù)據(jù)太占空間了，內(nèi)存根本存不下。

位圖是如何解決的呢？

所謂位圖，就是用每一bit位來存放某種狀態(tài)，適用于海量數(shù)據(jù)，數(shù)據(jù)無重復(fù)的場景。通常是用 來判斷某個(gè)數(shù)據(jù)存不存在的。數(shù)據(jù)是否在給定的整形數(shù)據(jù)中，結(jié)果是在或者不在，剛好是兩種狀態(tài)，那么可以使用一 個(gè)二進(jìn)制比特位來代表數(shù)據(jù)是否存在的信息，如果二進(jìn)制比特位為 1 ，代表存在，為0 代表不存在。（位圖是直接定址法的一種）

而40億個(gè)數(shù)據(jù)，我們起碼要開42億個(gè)空間，為什么？假如有一個(gè)數(shù)是4200000000，你要映射到哪個(gè)位置？我們開空間是要開數(shù)據(jù)的范圍，才能滿足全部映射進(jìn)去。

那我們直接開2^32個(gè)空間（這里說的每個(gè)位置就是比特位，2^32≈42億9千萬，因?yàn)槲粓D就是每個(gè)位置存的bit位），來對所有數(shù)直接定址法建立映射關(guān)系，即我們開辟42億9千萬個(gè)bit位，先把42億9千萬看成字節(jié)，則其≈4G，而4G≈4000M（或者M(jìn)B），而這里是比特位，故要除以8，4000/8=500M，故位圖存儲占用500M即可，這既節(jié)省了空間，效率又很高（效率高，因?yàn)橹苯佣ㄖ贩]哈希沖突）

---

2、位圖的實(shí)現(xiàn)?

?①、基本結(jié)構(gòu)

位圖的初始化應(yīng)該是開多少個(gè)比特位，因?yàn)槲粓D就是利用存比特位來節(jié)省的空間，你傳的N也是比特位，其次是vector的類型是int，因?yàn)?strong>類型不支持是比特位的

class bitset
{
public:bitset(size_t N){//N代表要開多少比特位（簡稱：位）_bits.resize(N / 32 + 1, 0);_num = N;}private://int* _bits;std::vector<int> _bits;size_t _num;  //表示存了多少個(gè)比特位，映射存儲的多少個(gè)數(shù)據(jù)
};

_bits.resize(N / 32 + 1, 0);

為什么要N / 32 + 1?呢？

因?yàn)?strong>vector的resize開空間是以整形為單位的，而位圖的每個(gè)位置存的都是一個(gè)比特位，而一個(gè)整形32個(gè)比特位，N代表的是比特位的位數(shù)，則N/32得到的是整形的個(gè)數(shù)，但是還需+1，為什么？比如N=100，100/32=3，那意思就是開3個(gè)整形，即32*3=96個(gè)位，但是100還是沒位置放，你就開了96個(gè)位（同理97,98...都沒位置），為了避免這個(gè)問題我們會(huì)+1，即多開一個(gè)整形，那最多只會(huì)浪費(fèi)31個(gè)位

---

②、set?

功能：把第x個(gè)位設(shè)置為1，表示這個(gè)位存在

void set(size_t x)
{//把第x位設(shè)置為1，表示此位置存在size_t index = x / 32; //算出映射的位置在第幾個(gè)整數(shù)size_t pos = x % 32;   //算出x在整數(shù)的第幾個(gè)位_bits[index] |= (1 << pos); //對于這個(gè)整數(shù)第pos的位置或1//1<<pos表示先把1移動(dòng)到和pos相同位置的比特位上，因?yàn)閜os=幾，1就會(huì)左移幾位//|=表示是或，即除了pos位置的位要變成1，其余位置都不受影響
}

?其實(shí)就是考察怎么把一個(gè)整數(shù)的某個(gè)位變成1，還不影響其他的31位

小端機(jī)的左移是向左?，?大端機(jī)的左移是向右

這是c語言設(shè)計(jì)的bug，歷史遺留問題，易讓人誤導(dǎo)，計(jì)算機(jī)技術(shù)發(fā)展百花齊放，再融合統(tǒng)一

---

③、reset：

功能：把第x個(gè)位置成0，表示這個(gè)位不存在

void reset(size_t x)
{//把第x位設(shè)置為0，表示此位置不存在size_t index = x / 32; //算出映射的位置在第幾個(gè)整數(shù)size_t pos = x % 32;   //算出x在整數(shù)的第幾個(gè)位_bits[index] &= ~(1 << pos); //對于這個(gè)整數(shù)第pos的位置與0
}

---

④、test?

功能：判斷第x位在不在（即判斷x所映射的位是否為1）

//判斷x在不在（也就是說x映射的位是否為1）
bool test(size_t x)
{size_t index = x / 32; //算出映射的位置在第幾個(gè)整數(shù)size_t pos = x % 32;   //算出x在整數(shù)的第幾個(gè)位return _bits[index] & (1 << pos); //結(jié)果非0為真，0則為假
}

---

⑤、問題：

理論上這40億個(gè)數(shù)不可能存在內(nèi)存當(dāng)中，應(yīng)該存在文件中，那我們就要去讀文件，40億個(gè)數(shù)因?yàn)橐捶秶_，故要開42億9千萬的空間，怎么開這么大的空間？常見方法如下：

①、bitset bs(-1);? //因?yàn)槲粓D的構(gòu)造函數(shù)參數(shù)是size_t，那-1若看為無符號數(shù)就是整形的最大值

②、bitset bs(0xffffffff);

---

⑥、位圖優(yōu)缺點(diǎn)及應(yīng)用：?

優(yōu)點(diǎn)：節(jié)省空間、效率高

缺點(diǎn)：只能處理整形

應(yīng)用：

• 快速查找某個(gè)數(shù)據(jù)是否在一個(gè)集合中
• 排序 + 去重
• 求兩個(gè)集合的交集、并集等
• 操作系統(tǒng)中磁盤塊標(biāo)記

---

⑦、完整代碼及測試

#pragma once
#include<iostream>
#include<vector>namespace mz
{class bitset{public:bitset(size_t N){//N代表要開多少比特位（簡稱：位）_bits.resize(N / 32 + 1, 0);_num = N;}void set(size_t x){//把第x位設(shè)置為1，表示此位置存在size_t index = x / 32; //算出映射的位置在第幾個(gè)整數(shù)size_t pos = x % 32;   //算出x在整數(shù)的第幾個(gè)位_bits[index] |= (1 << pos); //對于這個(gè)整數(shù)第pos的位置或1//1<<pos表示先把1移動(dòng)到和pos相同位置的比特位上，因?yàn)閜os=幾，1就會(huì)左移幾位//|=表示是或，即除了pos位置的位要變成1，++_num;}void reset(size_t x){//把第x位設(shè)置為0，表示此位置不存在size_t index = x / 32; //算出映射的位置在第幾個(gè)整數(shù)size_t pos = x % 32;   //算出x在整數(shù)的第幾個(gè)位_bits[index] &= ~(1 << pos); //對于這個(gè)整數(shù)第pos的位置與0--_num;}//判斷x在不在（也就是說x映射的位是否為1）bool test(size_t x){size_t index = x / 32; //算出映射的位置在第幾個(gè)整數(shù)size_t pos = x % 32;   //算出x在整數(shù)的第幾個(gè)位return _bits[index] & (1 << pos); //結(jié)果非0為真，0則為假}private://int* _bits;std::vector<int> _bits;size_t _num;  //表示存了多少個(gè)比特位，映射存儲的多少個(gè)數(shù)據(jù)};void test_bitset(){bitset bs(100);bs.set(99);bs.set(98);bs.set(97);bs.reset(98);for (size_t i = 0; i < 100; ++i){printf("[%d]:%d\n", i, bs.test(i));}}}

部分測試結(jié)果如下：?

?

---

二、布隆過濾器

1、布隆過濾器的提出

我們在使用新聞客戶端看新聞時(shí)，它會(huì)給我們不停地推薦新的內(nèi)容，它每次推薦時(shí)要去重，去掉 那些已經(jīng)看過的內(nèi)容。問題來了，新聞客戶端推薦系統(tǒng)如何實(shí)現(xiàn)推送去重的？ 用服務(wù)器記錄了用 戶看過的所有歷史記錄，當(dāng)推薦系統(tǒng)推薦新聞時(shí)會(huì)從每個(gè)用戶的歷史記錄里進(jìn)行篩選，過濾掉那 些已經(jīng)存在的記錄。 如何快速查找呢？

• 1. 用哈希表存儲用戶記錄，缺點(diǎn)：浪費(fèi)空間
• 2. 用位圖存儲用戶記錄，缺點(diǎn)：位圖一般只能處理整形，如果內(nèi)容編號是字符串，就無法處理了
• 3. 將哈希與位圖結(jié)合，即布隆過濾器

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

---

2、布隆過濾器的實(shí)現(xiàn)

①、基本結(jié)構(gòu)

?一般布隆過濾器存的是字符串或結(jié)構(gòu)體等，一般不會(huì)是整形，因?yàn)檎尉陀梦粓D來存了

布隆過濾器底層就是用位圖實(shí)現(xiàn)的，因?yàn)樽址容^常用，故我們直接把字符串作為默認(rèn)模板參數(shù)，其他三個(gè)Hash模板參數(shù)表示的是用三個(gè)位置來映射一個(gè)值

構(gòu)造函數(shù)開多少個(gè)空間？

有大佬已經(jīng)計(jì)算過了，10個(gè)元素就需要長度為43位，那我們干脆初始開個(gè)5倍

template<class K = string, class Hash1 = HashStr1, class Hash2 = HashStr2, class Hash3 = HashStr3>
class bloomfilter
{
public://直接上來開滿會(huì)有問題，因?yàn)榭赡芪冶旧砜赡芫蜎]映射幾個(gè)值//那就根據(jù)你大概會(huì)存多少個(gè)數(shù)據(jù)，來對應(yīng)開空間//到底開多少比較好有人算過，即你存多少個(gè)值就要映射到多少個(gè)位bloomfilter(size_t num):_bs(5 * num),_N(5 * num){}private:bitset _bs;	//底層是一個(gè)位圖size_t _N;
};

---

②、三個(gè)Hash仿函數(shù)實(shí)現(xiàn)

?因?yàn)橐萌齻€(gè)映射位置來映射一個(gè)值，故要寫三個(gè)字符串轉(zhuǎn)為整形的函數(shù)，而又因?yàn)閟tring類型比較常用，這三個(gè)仿函數(shù)會(huì)作為默認(rèn)模板參數(shù)

下面是能降低哈希沖突的字符串算法（我們下面三個(gè)仿函數(shù)就選用下面三個(gè)算法）：

struct HashStr1
{size_t operator()(const string& str){	//運(yùn)用BKDRHashsize_t hash = 0;for (size_t i = 0; i < str.size(); ++i){hash *= 131;hash += str[i];}return hash;}
};struct HashStr2
{size_t operator()(const string& str){	//運(yùn)用RSHashsize_t hash = 0;size_t magic = 63689; //魔數(shù)for (size_t i = 0; i < str.size(); ++i){hash *= magic;hash += str[i];magic *= 378551;}return hash;}
};struct HashStr3
{size_t operator()(const string& str){	//運(yùn)用SDBMHashsize_t hash = 0;for (size_t i = 0; i < str.size(); ++i){hash *= 65599;hash += str[i];}return hash;}
};

---

③、 set

函數(shù)是想把key這個(gè)數(shù)標(biāo)志為存在，而我們說了要用三個(gè)位置來映射這個(gè)key值，則調(diào)用Hash仿函數(shù)先計(jì)算出字符串的映射位置，%_N是因?yàn)槲覀儎傞_始給位圖就開了_N個(gè)比特位，你算出的映射位置很可能大于_N，故都%_N，既能存儲也能統(tǒng)一，則一個(gè)key值就能用三個(gè)映射位置來表示了

注：Hash1是仿函數(shù)類型，Hash1()是仿函數(shù)對象，當(dāng)然你也可以寫為Hash1 hs1;?hs1(key) % _N;但是明顯更麻煩

void set(const K& key)
{size_t index1 = Hash1()(key) % _N;//利用Hash1類型的匿名對象size_t index2 = Hash2()(key) % _N;size_t index3 = Hash3()(key) % _N;_bs.set(index1);//表示index1這個(gè)位置存在_bs.set(index2);_bs.set(index3);
}

---

④、 test

功能：判斷key值存不存在

因?yàn)橐粋€(gè)值用了三個(gè)映射位置，故我們判斷計(jì)算出key的三個(gè)映射位置在位圖中是否同時(shí)存在，同時(shí)存在key值才存在，反之有一個(gè)不存在就肯定不存在

bool test(const K& key)
{size_t index1 = Hash1()(key) % _N;if (_bs.test(index1) == false)return false;size_t index2 = Hash2()(key) % _N;if (_bs.test(index2) == false)return false;size_t index3 = Hash3()(key) % _N;if (_bs.test(index3) == false)return false;return true;  //但這里也不一定是真的在，還是可能存在誤判//判斷在，是不準(zhǔn)確的，可能存在誤判//判斷不在，是準(zhǔn)確的
}

---

⑤、?刪除

布隆過濾器不能直接支持刪除工作，因?yàn)樵趧h除一個(gè)元素時(shí)，可能會(huì)影響其他元素。

一種支持刪除的方法：將布隆過濾器中的每個(gè)比特位擴(kuò)展成一個(gè)小的計(jì)數(shù)器，插入元素時(shí)給 k個(gè)計(jì) 數(shù)器 (k 個(gè)哈希函數(shù)計(jì)算出的哈希地址 ) 加一，刪除元素時(shí)，給 k個(gè)計(jì)數(shù)器減一，通過多占用幾倍存儲 空間的代價(jià)來增加刪除操作。

缺陷：

1. 無法確認(rèn)元素是否真正在布隆過濾器中

2. 存在計(jì)數(shù)回繞

void reset(const K& key)	
{//將映射的位置給置0就可以？//不支持刪除，可能會(huì)存在誤刪，故布隆過濾器一般不支持刪除
}

---

?⑥、完整代碼及測試

#pragma once
#include"bitset.h"
#include<string>using std::string;
using std::cout;
using std::endl;namespace mz
{struct HashStr1{size_t operator()(const string& str){	//運(yùn)用BKDRHashsize_t hash = 0;for (size_t i = 0; i < str.size(); ++i){hash *= 131;hash += str[i];}return hash;}};struct HashStr2{size_t operator()(const string& str){	//運(yùn)用RSHashsize_t hash = 0;size_t magic = 63689; //魔數(shù)for (size_t i = 0; i < str.size(); ++i){hash *= magic;hash += str[i];magic *= 378551;}return hash;}};struct HashStr3{size_t operator()(const string& str){	//運(yùn)用SDBMHashsize_t hash = 0;for (size_t i = 0; i < str.size(); ++i){hash *= 65599;hash += str[i];}return hash;}};template<class K = string, class Hash1 = HashStr1, class Hash2 = HashStr2, class Hash3 = HashStr3>class bloomfilter{public://直接上來開滿會(huì)有問題，因?yàn)榭赡芪冶旧砜赡芫蜎]映射幾個(gè)值//那就根據(jù)你大概會(huì)存多少個(gè)數(shù)據(jù)，來對應(yīng)開空間//到底開多少比較好有人算過，即你存多少個(gè)值就要映射到多少個(gè)位bloomfilter(size_t num):_bs(5 * num),_N(5 * num){}void set(const K& key){size_t index1 = Hash1()(key) % _N;//利用Hash1類型的匿名對象size_t index2 = Hash2()(key) % _N;size_t index3 = Hash3()(key) % _N;_bs.set(index1);_bs.set(index2);_bs.set(index3);}bool test(const K& key){size_t index1 = Hash1()(key) % _N;if (_bs.test(index1) == false)return false;size_t index2 = Hash2()(key) % _N;if (_bs.test(index2) == false)return false;size_t index3 = Hash3()(key) % _N;if (_bs.test(index3) == false)return false;return true;  //但這里也不一定是真的在，還是可能存在誤判//判斷在，是不準(zhǔn)確的，可能存在誤判//判斷不在，是準(zhǔn)確的}void reset(const K& key){//將映射的位置給置0就可以？//不支持刪除，可能會(huì)存在誤刪，故布隆過濾器一般不支持刪除}private:bitset _bs;	//底層是一個(gè)位圖size_t _N;};void test_bloomfilter(){bloomfilter<string> bf(100); //這里不給string，直接用<>也行，因?yàn)閟tring是默認(rèn)的bf.set("abcd");bf.set("aadd");bf.set("bcad");cout << bf.test("abcd") << endl;cout << bf.test("aadd") << endl;cout << bf.test("bcad") << endl;cout << bf.test("cbad") << endl;}
}

---

⑦、 優(yōu)缺點(diǎn)

布隆過濾器優(yōu)點(diǎn)

• 1. 增加和查詢元素的時(shí)間復(fù)雜度為:O(K), (K為哈希函數(shù)的個(gè)數(shù)，一般比較小)，與數(shù)據(jù)量大小無
• 關(guān)
• 2. 哈希函數(shù)相互之間沒有關(guān)系，方便硬件并行運(yùn)算
• 3. 布隆過濾器不需要存儲元素本身，在某些對保密要求比較嚴(yán)格的場合有很大優(yōu)勢
• 4. 在能夠承受一定的誤判時(shí)，布隆過濾器比其他數(shù)據(jù)結(jié)構(gòu)有這很大的空間優(yōu)勢
• 5. 數(shù)據(jù)量很大時(shí)，布隆過濾器可以表示全集，其他數(shù)據(jù)結(jié)構(gòu)不能
• 6. 使用同一組散列函數(shù)的布隆過濾器可以進(jìn)行交、并、差運(yùn)算

布隆過濾器缺陷

• 1. 有誤判率，即存在假陽性(False Position)，即不能準(zhǔn)確判斷元素是否在集合中(補(bǔ)救方法：再
• 建立一個(gè)白名單，存儲可能會(huì)誤判的數(shù)據(jù))
• 2. 不能獲取元素本身
• 3. 一般情況下不能從布隆過濾器中刪除元素
• 4. 如果采用計(jì)數(shù)方式刪除，可能會(huì)存在計(jì)數(shù)回繞問題

---