C++詳細(xì)講解模擬實(shí)現(xiàn)位圖和布隆過濾器的方法
位圖
引論
四十億個(gè)無符號(hào)整數(shù)，現(xiàn)在給你一個(gè)無符號(hào)整數(shù)，判斷這個(gè)數(shù)是否在這四十億個(gè)數(shù)中。
路人甲：簡(jiǎn)單，快排+二分。
可是存儲(chǔ)這四十億個(gè)整數(shù)需要多少空間？
簡(jiǎn)單算一下，1G=1024M=1024 * 1024KB=1024 * 1024 * 1024Byte，也就是說1G大概也就是十億個(gè)字節(jié)。
四十億個(gè)整數(shù)多大？40億 * 4==160億個(gè)字節(jié)，換算一下也就是16G。
我電腦內(nèi)存也就十六個(gè)G，還不加上別的應(yīng)用，顯然內(nèi)存超限了。
所以快排+二分是不可取的，那有沒有別的法子呢？
所以也就有了下面要講的位圖。
概念
位圖是什么？
根據(jù)上面的模型我們可以發(fā)現(xiàn)，之前要用四個(gè)字節(jié)存儲(chǔ)一個(gè)數(shù)字，現(xiàn)在只需一個(gè)比特位，當(dāng)然我們不是存儲(chǔ)具體數(shù)值，而是存儲(chǔ)數(shù)字的狀態(tài)。
因?yàn)橐粋€(gè)比特位只有兩種狀態(tài)，所以我們存儲(chǔ)的是該數(shù)字是否存在（數(shù)字存在對(duì)應(yīng)位為1，否則為0）
解決引論
上面發(fā)現(xiàn)本來需要4個(gè)字節(jié)存儲(chǔ)，現(xiàn)在只需要1位去存儲(chǔ)，一下子就縮小了32倍，所以原本需要16G內(nèi)存存儲(chǔ)的數(shù)據(jù)只需要0.5G。顯然這個(gè)內(nèi)存我們是開的起的。
那該怎么判斷這個(gè)數(shù)字是否存在呢？將這個(gè)數(shù)字/8得到它在第幾個(gè)字節(jié)，將這個(gè)數(shù)字%8即可得到他在這個(gè)數(shù)字在第幾位。
比如10，就在第一個(gè)字節(jié)的第二位。（都是從0開始計(jì)數(shù)）
總結(jié)一下應(yīng)該怎么解決引論提出的問題？開一個(gè)能存儲(chǔ)42億位的位圖，查找時(shí)算出待查找數(shù)的位置，如果這個(gè)位置為1則表示存在，否則就不存在。
位圖也是一種哈希思想的運(yùn)用
位圖的模擬實(shí)現(xiàn)
鋪墊
從上面可以看出，位圖的實(shí)現(xiàn)主要在于把某一位置為0和把某一位置為1。
如何把某一位置為1？
把那個(gè)位置 |1
|是按位或運(yùn)算符
如何把某一位置為0？
把那個(gè)位置 &0
&是按位與運(yùn)算符
所以我們?cè)趯?shí)現(xiàn)時(shí)只需要算出那個(gè)位置再進(jìn)行位操作即可。
結(jié)構(gòu)
構(gòu)造函數(shù)
BitSet()
{
_bits.resize(N / 8 + 1);//開這么多個(gè)字節(jié),+1是怕有余數(shù)
}
比如開10個(gè)位就要開兩個(gè)字節(jié)。
因?yàn)椴捎玫氖莢ector,所以所有的char都會(huì)被默認(rèn)置為0。char類型的默認(rèn)值就是0，空字符。
比如底層實(shí)現(xiàn)時(shí)resize第二個(gè)參數(shù)默認(rèn)值給成T()，T為模板，當(dāng)用char去實(shí)例化時(shí)，那默認(rèn)值就是char()了，也就是ASCII碼為0的字符。
存儲(chǔ)
vector<char>_bits;
用vector存的。
set,reset,test
test作用：檢查這一位是0還是1，是1返回true，否則返回false
bool test(size_t x)
{
size_t integer = x / 8;//第幾個(gè)字節(jié)
size_t rem = x % 8;//字節(jié)的第幾個(gè)位置
return ((_bits[integer] >> rem) & 1) ? true : false;
}
set作用：把某一個(gè)位置置為1
void set(size_t x)//第x位置為1
{
if (!test(x))//如果這一位是0，置為1的話++
{
_cnt++;
}
size_t integer = x / 8;//第幾個(gè)字節(jié)
size_t rem = x % 8;//字節(jié)的第幾個(gè)位置
_bits[integer] |= (1 << rem);
}
reset作用：把某一個(gè)位置置為0
void reset(size_t x)//第x位置為0
{
if (test(x))//如果這一位是1，置為0的話--
{
_cnt--;
}
size_t integer = x / 8;//第幾個(gè)字節(jié)
size_t rem = x % 8;//字節(jié)的第幾個(gè)位置
_bits[integer] &= (~(1 << rem));
}
flip,size,count
flip：翻轉(zhuǎn)，0變?yōu)?,1變?yōu)?
void flip(size_t x)//翻轉(zhuǎn)
{
if (test(x))//1
{
reset(x);
}
else//0
{
set(x);
}
}
size：位圖有多少位
size_t size() const
{
return N;//模板參數(shù)
}
count：位圖里有多少個(gè)1
size_t count()
{
return _cnt;
}
any,none,all
any：位圖里有沒有1，有1返回true，否則返回false
bool any()
{
if (_cnt)
{
return true;
}
return false;
}
none：與any相反
bool none()
{
return !any();
}
all：全為1返回true，否則返回false
bool all()
{
if (_cnt == N)
{
return true;
}
else
{
return false;
}
}
重載流運(yùn)算符
重載流運(yùn)算符必須在BitSet里面加上一個(gè)函數(shù)聲明
template<size_t T> friend ostream& operator<<(ostream& out, const BitSet<T>& bs);
這里會(huì)出現(xiàn)的一個(gè)問題是，因?yàn)轭愐呀?jīng)有了一個(gè)模板參數(shù)，所以很容易寫成
friend ostream& operator<<(ostream& out, const BitSet<N>& bs);
導(dǎo)致運(yùn)行時(shí)報(bào)鏈接錯(cuò)誤。
原因講解：目錄-解決方法
簡(jiǎn)單解釋一下，因?yàn)檫@是一個(gè)聲明，所以編譯到這里時(shí)只當(dāng)這是個(gè)友元函數(shù)的聲明，并不會(huì)把函數(shù)里的模板N參數(shù)實(shí)例化，只有調(diào)用流運(yùn)算符時(shí)才會(huì)去實(shí)例化，這就出現(xiàn)了二次編譯（第一次編譯只實(shí)例化了BitSet類，即類BitSet模板參數(shù)N被確定下來）
但因?yàn)橛言瘮?shù)只是聲明并沒有實(shí)例化，即第二種寫法的N并沒有被確定下來，到調(diào)用這個(gè)函數(shù)的時(shí)候要對(duì)N進(jìn)行編譯，但是不知道這個(gè)N具體是什么，因?yàn)镹是一個(gè)模板參數(shù)被第一次實(shí)例化確定下來后就沒了，編譯器往上找也找不到，導(dǎo)致有函數(shù)聲明但是找不到具體函數(shù)，從而發(fā)生了鏈接錯(cuò)誤。解決就是寫成第一種，第二次編譯時(shí)看到了上面有一個(gè)模板聲明就知道T是個(gè)模板參數(shù)，調(diào)用時(shí)第一次被確定的N傳給現(xiàn)在的T，所以就能正確運(yùn)行。
ostream& operator<<(ostream& out, const BitSet<T>& bs)
{
//從后往前是低位到高位，庫里面是這樣的
int len = bs.size() / 8 ;
char tmp;
tmp = bs._bits[len];
for (int i = bs.size() % 8 - 1; i >= 0; i--)
{
if ((tmp >> i) & 1)
{
cout << '1';
}
else
{
cout << '0';
}
}
for (int i = len-1; i >=0; i--)
{
tmp = bs._bits[i];
for (int j = 7; j >=0; j--)
{
if ((tmp >> j) & 1)
{
cout << '1';
}
else
{
cout << '0';
}
}
}
//從前往后是低位到高位（人看起來合適）
//for (int i=0;i<len;i++)
//{
// tmp = bs._bits[i];
// for (int i =0;i<8;i++)
// {
// if ((tmp >> i) & 1)
// {
// cout << '1';
// }
// else
// {
// cout << '0';
// }
// }
//}
//tmp = bs._bits[len];
//for (int i = 0; i < bs.size() % 8; i++)
//{
// if ((tmp >> i) & 1)
// {
// cout << '1';
// }
// else
// {
// cout << '0';
// }
//}
return out;
}比如有十個(gè)位，把第一位置為1，那打印出來就是0000000010
是從右往左數(shù)的，庫里的打印是這樣的，注釋掉的那部分代碼會(huì)打印0100000000
實(shí)際我們操作內(nèi)存實(shí)現(xiàn)的存儲(chǔ)是00000010 00000000
測(cè)試
void test_bitset()
{
BitSet<10> bits;
bits.set(1);
bits.set(9);
cout << bits.count() << endl;
bits.reset(1);
cout << bits.count() << endl;
cout << bits << endl;
/*cout << bits.none() << endl;
bits.set(4);
cout << bits.none() << endl;
cout << bits.any() << endl;
cout << bits.all() << endl;*/
/*bits.set(4);
cout << bits.test(4) << endl;
bits.flip(4);
cout << bits.test(4) << endl;
bits.flip(4);
cout << bits.test(4) << endl;*/
/*bits<0xffffffff>bits;
cout << endl;*/
}位圖簡(jiǎn)單應(yīng)用
100億個(gè)整數(shù)，找到只出現(xiàn)一次的數(shù)。
100億個(gè)整數(shù)不代表要開一百億位大小的空間，有些可能重復(fù)了幾次，所以開int大小的即可。
整兩個(gè)位圖代表兩位， 00 01 10 11， 第一個(gè)位圖代表第一位，第二個(gè)位圖表示第二位 ，初始狀態(tài)都是00，插入一個(gè)數(shù)后將其置為01， 再來就置為10 ，再去遍歷整個(gè)位圖得到只出現(xiàn)一次的數(shù)的集合。
template<size_t N>
class FindOnceVal
{
public:
void set(size_t x)
{
bool flag1 = _bs1.test(x);//得到第一位
bool flag2 = _bs2.test(x);//得到第二位
if (flag1 == false && flag2 == false)//00->01
{
_bs2.set(x);
}
else if (flag1 == false && flag2 == true)//01->10
{
_bs1.set(x);
_bs2.reset(x);
}
//10->11...不用再處理了
}
bool check(size_t x)
{
if (!_bs1.test(x) && _bs2.test(x))//01
{
return true;
}
return false;
}
void print()
{
for (size_t i = 0; i < N; i++)
{
if (check(i))
{
printf("%d\n",i);
}
}
}
private:
BitSet<N>_bs1;
BitSet<N>_bs2;
};
void TestFindOnceVal()
{
int a[] = { 1, 20, 30, 43, 5, 4, 1, 43, 43, 7, 9, 7, 7, 0 };
FindOnceVal<100> fov;
for (auto e : a)
{
fov.set(e);
}
fov.print();
}給兩個(gè)文件，分別有100億個(gè)整數(shù)，我們只有1G內(nèi)存，如何找到兩個(gè)文件交集？
兩個(gè)位圖，分別去映射兩個(gè)文件，再去遍歷比對(duì)即可。比如兩個(gè)位圖的同一個(gè)位置都為1說明整個(gè)數(shù)就在交集里面
給一個(gè)超過100G大小的log file, log中存著IP地址, 設(shè)計(jì)算法找到出現(xiàn)次數(shù)最多的IP地址？ 我們只有1G內(nèi)存，如何找到top K的IP？
哈希切割，運(yùn)用哈希算法將IP分類（切割），比如把IP轉(zhuǎn)成字符串，再映射成整形，這就是一種哈希算法，100G給分成100個(gè)文件，即100個(gè)小類，每一個(gè)文件去計(jì)數(shù)，比如就用map<string,int> 然后記錄下最大的，再將map清空。
第二個(gè)文件出來的最大次數(shù)再與第一個(gè)得到的最大次數(shù)進(jìn)行比較記錄下出現(xiàn)最大次數(shù)的ip和次數(shù)，如此循環(huán)遍歷完 100個(gè)文件即可。 如果要topK 建一個(gè)小堆即可
如果出現(xiàn)切分后一個(gè)文件還是過大，那換一種哈希算法再進(jìn)行切割
位圖的優(yōu)勢(shì)就在于可以大大節(jié)省空間！
位圖代碼匯總
#pragma once
#include <vector>
#include <string>
#include <iostream>
using namespace std;
namespace ck
{
template<size_t N>//N個(gè)數(shù)
class BitSet
{
public:
BitSet()
{
_bits.resize(N / 8 + 1);//開這么多個(gè)字節(jié)
}
void set(size_t x)//第x位置為1
{
if (!test(x))//如果這一位是0，置為1的話++
{
_cnt++;
}
size_t integer = x / 8;//第幾個(gè)字節(jié)
size_t rem = x % 8;//字節(jié)的第幾個(gè)位置
_bits[integer] |= (1 << rem);
}
void reset(size_t x)//第x位置為0
{
if (test(x))//如果這一位是1，置為0的話--
{
_cnt--;
}
size_t integer = x / 8;//第幾個(gè)字節(jié)
size_t rem = x % 8;//字節(jié)的第幾個(gè)位置
_bits[integer] &= (~(1 << rem));
}
bool test(size_t x)
{
size_t integer = x / 8;//第幾個(gè)字節(jié)
size_t rem = x % 8;//字節(jié)的第幾個(gè)位置
return ((_bits[integer] >> rem) & 1) ? true : false;
}
void flip(size_t x)//翻轉(zhuǎn)
{
if (test(x))//1
{
reset(x);
}
else//0
{
set(x);
}
}
size_t size() const
{
return N;//模板參數(shù)
}
size_t count()
{
return _cnt;
}
bool any()
{
if (_cnt)
{
return true;
}
return false;
}
bool none()
{
return !any();
}
bool all()
{
if (_cnt == N)
{
return true;
}
else
{
return false;
}
}
template<size_t T>
friend ostream& operator<<(ostream& out, const BitSet<T>& bs);
private:
vector<char>_bits;
size_t _cnt = 0;//被設(shè)置為1的個(gè)數(shù)
};
template<size_t T>//模板參數(shù)不能取名為N
ostream& operator<<(ostream& out, const BitSet<T>& bs)
{
//從后往前是低位到高位，庫里面是這樣的
int len = bs.size() / 8 ;
char tmp;
tmp = bs._bits[len];
for (int i = bs.size() % 8 - 1; i >= 0; i--)
{
if ((tmp >> i) & 1)
{
cout << '1';
}
else
{
cout << '0';
}
}
for (int i = len-1; i >=0; i--)
{
tmp = bs._bits[i];
for (int j = 7; j >=0; j--)
{
if ((tmp >> j) & 1)
{
cout << '1';
}
else
{
cout << '0';
}
}
}
//從前往后是低位到高位（人看起來合適）
//for (int i=0;i<len;i++)
//{
// tmp = bs._bits[i];
// for (int i =0;i<8;i++)
// {
// if ((tmp >> i) & 1)
// {
// cout << '1';
// }
// else
// {
// cout << '0';
// }
// }
//}
//tmp = bs._bits[len];
//for (int i = 0; i < bs.size() % 8; i++)
//{
// if ((tmp >> i) & 1)
// {
// cout << '1';
// }
// else
// {
// cout << '0';
// }
//}
return out;
}
void test_bitset()
{
BitSet<10> bits;
bits.set(1);
bits.set(9);
cout << bits.count() << endl;
bits.reset(1);
cout << bits.count() << endl;
cout << bits << endl;
/*cout << bits.none() << endl;
bits.set(4);
cout << bits.none() << endl;
cout << bits.any() << endl;
cout << bits.all() << endl;*/
/*bits.set(4);
cout << bits.test(4) << endl;
bits.flip(4);
cout << bits.test(4) << endl;
bits.flip(4);
cout << bits.test(4) << endl;*/
/*bits<0xffffffff>bits;
cout << endl;*/
}
/*1. 給定100億個(gè)整數(shù)，設(shè)計(jì)算法找到只出現(xiàn)一次的整數(shù)？
100億個(gè)整數(shù)不代表要開一百億位大小的空間，有些可能重復(fù)了幾次，所以開int大小的即可。
整兩個(gè)位圖 00 01 10 11 第一個(gè)位圖代表第一位 第二個(gè)位圖表示第二位 初始狀態(tài)都是00 來了一個(gè)數(shù)后將其置為01 再來就置為10 再去遍歷
*/
template<size_t N>
class FindOnceVal
{
public:
void set(size_t x)
{
bool flag1 = _bs1.test(x);
bool flag2 = _bs2.test(x);
if (flag1 == false && flag2 == false)//00->01
{
_bs2.set(x);
}
else if (flag1 == false && flag2 == true)//01->10
{
_bs1.set(x);
_bs2.reset(x);
}
//10->11...不用再處理了
}
bool check(size_t x)
{
if (!_bs1.test(x) && _bs2.test(x))//01
{
return true;
}
return false;
}
void print()
{
for (size_t i = 0; i < N; i++)
{
if (check(i))
{
printf("%d\n",i);
}
}
}
private:
BitSet<N>_bs1;
BitSet<N>_bs2;
};
void TestFindOnceVal()
{
int a[] = { 1, 20, 30, 43, 5, 4, 1, 43, 43, 7, 9, 7, 7, 0 };
FindOnceVal<100> fov;
for (auto e : a)
{
fov.set(e);
}
fov.print();
}
/*位圖應(yīng)用變形：1個(gè)文件有100億個(gè)int，1G內(nèi)存，設(shè)計(jì)算法找到出現(xiàn)次數(shù)不超過2次的所有整數(shù) 在第一題的基礎(chǔ)上稍作改動(dòng)即可*/
/*給兩個(gè)文件，分別有100億個(gè)整數(shù)，我們只有1G內(nèi)存，如何找到兩個(gè)文件交集？
兩個(gè)位圖，分別去映射兩個(gè)文件，再去遍歷即可
*/
/*給一個(gè)超過100G大小的log file, log中存著IP地址, 設(shè)計(jì)算法找到出現(xiàn)次數(shù)最多的IP地址？ 與上題條件相同，
如何找到top K的IP？*/
/*哈希切割 運(yùn)用哈希算法將IP分類（切割），比如把IP轉(zhuǎn)成字符串，再映射成整形，這就是一種哈希算法 100G給分成100個(gè)文件，即100個(gè)小類，
每一個(gè)文件去計(jì)數(shù)，比如就用map<string,int> 然后記錄下最大的，再將map清空
第二個(gè)文件出來的最大次數(shù)再與第一個(gè)得到的最大次數(shù)進(jìn)行比較
如果要topK 建一個(gè)小堆即可 如果出現(xiàn)一個(gè)文件還是過大，那換一種哈希算法在進(jìn)行切割
*/
}布隆過濾器
前提是已經(jīng)實(shí)現(xiàn)了位圖
引論
存在一億個(gè)ip，給一個(gè)ip,快速判斷這個(gè)ip在不在這一億個(gè)ip中
之前哈希切割能不能做？之前是切成小文件，但是其實(shí)歸根到底都只記錄了出現(xiàn)次數(shù)最多的，并沒有記錄所有人的狀態(tài)。
那我們可不可以通過位圖來做，把IP映射到位圖的一個(gè)位置，再去判斷這個(gè)IP是否在位圖中。聽起來可行，但是顯然會(huì)出現(xiàn)映射上的沖突，即兩個(gè)不同的IP映射到了同一個(gè)位置，這就導(dǎo)致了誤判。那有沒有更好的法子？
一個(gè)叫布隆的人發(fā)現(xiàn)消除沖突是不可能的，但是可以減緩沖突，他是怎么減緩沖突的呢？
之前一個(gè)ip映射一個(gè)位置，現(xiàn)在我去映射多個(gè)位置，比如映射三個(gè)，只有三個(gè)位置全部對(duì)上，那才說明這個(gè)ip存在，當(dāng)然這也可能存在誤判，但誤判概率已經(jīng)減小很多了。這就是布隆過濾器
要點(diǎn)
- 布隆過濾器沒有消除沖突，但是減緩了沖突。
- 布隆過濾器判斷數(shù)據(jù)是否存在時(shí)是可能誤判的，但是在判斷數(shù)據(jù)不存在時(shí)一定準(zhǔn)確
- 在一些允許誤判的情境下大大提高了判斷的效率。
一個(gè)經(jīng)典的場(chǎng)景就是取名，我們?cè)谝粋€(gè)軟件內(nèi)注冊(cè)一個(gè)用戶，用戶輸入一個(gè)名稱檢查是否重復(fù)，誤判的情景：用戶輸入一個(gè)名字，這個(gè)名字事實(shí)上不存在，但是被誤判為存在，那這個(gè)代價(jià)很小啊，大不了讓用戶換一個(gè)名字輸入不就行了。如果為了得到一個(gè)準(zhǔn)確的結(jié)果，可以在判斷存在后去對(duì)服務(wù)器發(fā)送一個(gè)請(qǐng)求去檢查這個(gè)名字是否存在（一般能不涉及服務(wù)器就不去涉及了）。
- 布隆過濾器可以刪除嗎？
理論上是可以的，但是不建議，比如兩個(gè)元素，每個(gè)元素映射三個(gè)位置，三個(gè)位置里有兩個(gè)位置相同，那刪除一個(gè)ip，即刪除三個(gè)位置肯定會(huì)影響到另一個(gè)，所以就不好刪除。
但也不是不能刪除，硬要?jiǎng)h除也是可以的，現(xiàn)在一個(gè)ip映射三個(gè)位置，每個(gè)位置都是1個(gè)比特位，只能表示兩種狀態(tài)，可以把每種狀態(tài)設(shè)置為8個(gè)位，也就是一個(gè)字節(jié)，就可以表示256種狀態(tài)，可以用來計(jì)數(shù)實(shí)現(xiàn)刪除。但是問題在開位圖的原因就是為了節(jié)省空間，現(xiàn)在一個(gè)狀態(tài)一個(gè)字節(jié)與初衷相違背了，可謂是殺敵一千自損八百。因此不建議刪除
代碼實(shí)現(xiàn)
這個(gè)比較簡(jiǎn)單，復(fù)用位圖即可，比如一個(gè)ip映射三個(gè)位置，也就是用來三個(gè)哈希函數(shù)而已。
哈希函數(shù)都是貼網(wǎng)上的代碼，處理string的哈希效率比較好的有BKDR哈希等等。實(shí)現(xiàn)的布隆過濾器默認(rèn)的哈希函數(shù)是處理string的
#include "BitSet_.h"http://復(fù)用位圖
namespace ck
{
struct HashFunc1
{
//BKDR Hash
size_t operator()(const string& str)
{
size_t seed = 131; // 31 131 1313 13131 131313 etc..
size_t hash = 0;
for (size_t i = 0; i < str.length(); i++)
{
hash = (hash * seed) + str[i];
}
return hash;
}
};
struct HashFunc2
{
//FNV Hash
size_t operator()(const string& str)
{
size_t fnv_prime = 0x811C9DC5;
size_t hash = 0;
for (std::size_t i = 0; i < str.length(); i++)
{
hash *= fnv_prime;
hash ^= str[i];
}
return hash;
}
};
struct HashFunc3
{
//APH Hash
size_t operator()(const string& str)
{
unsigned int BitsInUnsignedInt = (unsigned int)(sizeof(unsigned int) * 8);
unsigned int ThreeQuarters = (unsigned int)((BitsInUnsignedInt * 3) / 4);
unsigned int OneEighth = (unsigned int)(BitsInUnsignedInt / 8);
unsigned int HighBits = (unsigned int)(0xFFFFFFFF) << (BitsInUnsignedInt - OneEighth);
unsigned int hash = 0;
unsigned int test = 0;
for (std::size_t i = 0; i < str.length(); i++)
{
hash = (hash << OneEighth) + str[i];
if ((test = hash & HighBits) != 0)
{
hash = ((hash ^ (test >> ThreeQuarters)) & (~HighBits));
}
}
return hash;
}
};
template<size_t N, class K=string ,class Hash1 = HashFunc1, class Hash2 = HashFunc2, class Hash3 = HashFunc3>
class BloomFilter
{
public:
void set(const K& key)
{
size_t x1 = Hash1()(key)%len;
size_t x2 = Hash2()(key) % len;
size_t x3 = Hash3()(key) % len;
_bs.set(x1);
_bs.set(x2);
_bs.set(x3);
}
bool test(const K& key)
{
//不用一次性算出所有的值
size_t x1 = Hash1()(key) % len;
if (!_bs.test(x1))
{
return false;
}
size_t x2 = Hash2()(key) % len;
if (!_bs.test(x2))
{
return false;
}
size_t x3 = Hash2()(key) % len;
if (!_bs.test(x3))
{
return false;
}
return true;//三個(gè)位置全都存在才能說明存在
}
private:
BitSet<6*N>_bs;
size_t len = 6 * N;//位圖的大小可以決定過濾器的效率（越大哈希沖突概率越小，誤判概率越低）
};效率
效率指的就是誤判的概率。
多搞幾個(gè)哈希函數(shù)，或者把位圖開大一點(diǎn)都能提高降低誤判的可能性。
網(wǎng)上有很多大佬探究了位圖大小開多少合適，比如位圖要存儲(chǔ)N個(gè)數(shù)，那開多大可以讓性能還可以的同時(shí)也不用開過多的空間，結(jié)果是4。有N個(gè)數(shù)就開4N左右，當(dāng)然和存儲(chǔ)的具體數(shù)據(jù)有關(guān)。比如我上面就開了6N。
解決方法
1. 直接把定義和實(shí)現(xiàn)都寫在類中
2. 如下：
#include <iostream>
using namespace std;
template <class T>
class Compleax
{
template <class S> //注意這里是S,和上面的T的名字不一樣
friend ostream & operator<< (ostream &out, Compleax <S>&c);
public:
Compleax(T a, T b);
void PrintCom()
{
cout<<"a:"<<a<<" b:"<<b<<endl;
}
private:
T a;
T b;
};
template <class T>
Compleax<T> :: Compleax(T a, T b)
{
this->a = a;
this->b = b;
}
template <class T>
ostream &operator << (ostream &out, Compleax<T> &c)
{
out<<c.a<<" "<<c.b<<endl;
return out;
}
int main()
{
Compleax<int> c(2, 3);
c.PrintCom();
cout<<c<<endl;
return 0;
}3. 如下：
#include <iostream>
using namespace std;
//1.需要先聲明類模板
template <class T>
class Compleax;
//2.再聲明友元函數(shù)
template <class T>
ostream & operator<< (ostream &out, Compleax<T> &c);
template <class T>
class Compleax
{
//3.類中定義友元函數(shù)，注意需要加上<>
friend ostream & operator<< <T>(ostream &out, Compleax &c);
public:
Compleax(T a, T b);
void PrintCom()
{
cout<<"a:"<<a<<" b:"<<b<<endl;
}
private:
T a;
T b;
};
template <class T>
Compleax<T> :: Compleax(T a, T b)
{
this->a = a;
this->b = b;
}
template <class T>
ostream &operator << (ostream &out, Compleax<T> &c)
{
out<<c.a<<" "<<c.b<<endl;
return out;
}
int main()
{
Compleax<int> c(2, 3);
c.PrintCom();
cout<<c<<endl;
return 0;
}這樣即可解決錯(cuò)誤提示為無法解析的外部符之類的問題。下面來說明一下為什么會(huì)有這樣的現(xiàn)象發(fā)生。
其實(shí)在模板機(jī)制的內(nèi)部，編譯器做的工作和沒有模板機(jī)制時(shí)我們做的功能大同小異。在使用了函數(shù)模板的代碼中。編譯器其實(shí)進(jìn)行了二次編譯，第一次是在聲明函數(shù)模板時(shí)，會(huì)檢查你的函數(shù)模板的語法有沒有錯(cuò)誤，然后編譯你的函數(shù)頭，之后代碼中使用模板時(shí)，就會(huì)把函數(shù)模板的代碼根據(jù)變量類型來編譯后并實(shí)例化，完成二次編譯。
出現(xiàn)這種問題的原因就是，兩次編譯的函數(shù)頭不一樣，因?yàn)橛言瘮?shù)并不屬于類的成員函數(shù)，所以需要單獨(dú)聲明此友元函數(shù)是函數(shù)模板，如果沒有聲明，但是后面在實(shí)現(xiàn)的時(shí)候又使用了template <class T>，就會(huì)導(dǎo)致錯(cuò)誤的發(fā)生。所以需要額外使用template <class S>聲明。
加上<T>的目的是告訴編譯器當(dāng)前函數(shù)需要使用函數(shù)模板并且參數(shù)類型使用當(dāng)前模板類的參數(shù)類型。
到此這篇關(guān)于C++詳細(xì)講解模擬實(shí)現(xiàn)位圖和布隆過濾器的方法的文章就介紹到這了,更多相關(guān)C++模擬位圖內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
C++實(shí)現(xiàn)將輸入復(fù)制到輸出的方法
這篇文章主要介紹了C++實(shí)現(xiàn)將輸入復(fù)制到輸出的方法,實(shí)例分析了C++字符串轉(zhuǎn)換及輸入輸出操作的相關(guān)技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-07-07
C++標(biāo)準(zhǔn)模板庫vector的常用操作
今天小編就為大家分享一篇關(guān)于C++標(biāo)準(zhǔn)模板庫vector的常用操作，小編覺得內(nèi)容挺不錯(cuò)的，現(xiàn)在分享給大家，具有很好的參考價(jià)值，需要的朋友一起跟隨小編來看看吧2018-12-12
C通過運(yùn)行時(shí)堆棧支持遞歸函數(shù)的實(shí)現(xiàn)。遞歸函數(shù)就是直接或間接調(diào)用自身的函數(shù)2013-07-07
本篇文章是對(duì)C語言中段錯(cuò)誤的問題進(jìn)行了詳細(xì)的分析介紹，需要的朋友參考下2013-05-05
C語言實(shí)現(xiàn)將字符和數(shù)字串到一起
今天小編就為大家分享一篇C語言實(shí)現(xiàn)將字符和數(shù)字串到一起，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧2019-12-12
C語言實(shí)現(xiàn)五子棋人人對(duì)戰(zhàn)
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)五子棋人人對(duì)戰(zhàn)，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2020-12-12
本文主要介紹了Qt實(shí)現(xiàn)線程與定時(shí)器的方法，文中通過示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-01-01
這篇文章主要為大家詳細(xì)介紹了C語言實(shí)現(xiàn)導(dǎo)航功能，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2022-03-03
C語言中的strcpy函數(shù)，是一種C語言的標(biāo)準(zhǔn)庫函數(shù)，它用于對(duì)字符串進(jìn)行復(fù)制。本章帶你了解它的使用并模擬實(shí)現(xiàn)它2022-05-05
C語言 動(dòng)態(tài)分配數(shù)組案例詳解
這篇文章主要介紹了C語言 動(dòng)態(tài)分配數(shù)組案例詳解,本篇文章通過簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08