做自己的網(wǎng)站花多錢2345網(wǎng)址導(dǎo)航桌面版
目錄
一、位圖
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ù)回繞問題