??個(gè)人主頁(yè)：平凡的小蘇
??學(xué)習(xí)格言：命運(yùn)給你一個(gè)低的起點(diǎn)，是想看你精彩的翻盤，而不是讓你自甘墮落，腳下的路雖然難走，但我還能走，比起向陽(yáng)而生，我更想嘗試逆風(fēng)翻盤。
??C++專欄：C++內(nèi)功修煉基地
> 家人們更新不易，你們的??點(diǎn)贊??和?關(guān)注?真的對(duì)我真重要，各位路 過(guò)的友友麻煩多多點(diǎn)贊關(guān)注。 歡迎你們的私信提問(wèn)，感謝你們的轉(zhuǎn)發(fā)！ 關(guān)注我，關(guān)注我，關(guān)注我，你們將會(huì)看到更多的優(yōu)質(zhì)內(nèi)容！！
一、位圖的概念
所謂位圖，就是用每一位來(lái)存放某種狀態(tài)，適用于海量數(shù)據(jù)，數(shù)據(jù)無(wú)重復(fù)的場(chǎng)景。通常是用來(lái)判斷某個(gè)數(shù)據(jù)存不存在的。
1、位圖的面試題
給40億個(gè)不重復(fù)的無(wú)符號(hào)整數(shù)，沒(méi)排過(guò)序。給一個(gè)無(wú)符號(hào)整數(shù)，如何快速判斷一個(gè)數(shù)是否在這40億個(gè)數(shù)中。
- 數(shù)據(jù)是否在給定的整形數(shù)據(jù)中，結(jié)果是在或者不在，剛好是兩種狀態(tài)，那么可以使用一個(gè)二進(jìn)制比特位來(lái)代表數(shù)據(jù)是否存在的信息，如果二進(jìn)制比特位為1，代表存在，為0代表不存在。
2、位圖模擬實(shí)現(xiàn)
#include <iostream>
#include <vector>
using std::cout;
using std::endl;
namespace sqy
{
template<size_t N>
class bitset
{
public:
bitset()
{
_bits.resize(N / 8 + 1);
}
void set(size_t n)
{
size_t i = n / 8;//算出n屬于_bits的哪一個(gè)下標(biāo)
size_t j = n % 8;//算出屬于_bits下標(biāo)的哪一個(gè)比特位
_bits[i] |= 1 << j;
}
void reset(size_t n)
{
size_t i = n / 8;//算出n屬于_bits的哪一個(gè)下標(biāo)
size_t j = n % 8;//算出屬于_bits下標(biāo)的哪一個(gè)比特位
_bits[i] &= (~(1 << j));
}
bool test(size_t n)
{
size_t i = n / 8;//算出n屬于_bits的哪一個(gè)下標(biāo)
size_t j = n % 8;//算出屬于_bits下標(biāo)的哪一個(gè)比特位
return _bits[i] & (1 << j);
}
private:
std::vector<char> _bits;
};
3、位圖的應(yīng)用
- 給定100億個(gè)整數(shù)，設(shè)計(jì)算法找到只出現(xiàn)一次的整數(shù)？
我們可以使用兩個(gè)位圖，如果是00則表示沒(méi)有出現(xiàn)一次，01表示出現(xiàn)一次，10往后的就可以不用實(shí)現(xiàn)了。
- 給兩個(gè)文件，分別有100億個(gè)整數(shù)，我們只有1G內(nèi)存，如何找到兩個(gè)文件交集？
使用兩個(gè)位圖，將兩個(gè)文件的數(shù)據(jù)分別映射到對(duì)應(yīng)的位圖中，在進(jìn)行遍歷按位與，如果為1，則為交集，否則，反之。
- 位圖應(yīng)用變形：1個(gè)文件有100億個(gè)int，1G內(nèi)存，設(shè)計(jì)算法找到出現(xiàn)次數(shù)不超過(guò)2次的所有整數(shù)
我們可以使用兩個(gè)位圖，如果是00則表示沒(méi)有出現(xiàn)一次，01表示出現(xiàn)一次，10表示出現(xiàn)兩次，11往后的就可以不用實(shí)現(xiàn)了。
代碼示例
template<size_t N>
class twobitset
{
public:
void set(size_t n)
{
if (b1.test(n) == false && b2.test(n) == false) //00 -> 01
{
b1.set(n);
}
else if (b1.test(n) == true && b2.test(n) == false) //01 -> 10
{
b1.reset(n);
b2.set(n);
}
}
void printOnce()
{
for (size_t i = 0; i < N; i++)
{
if (!b2.test(i) && b1.test(i))
{
cout << i << " ";
}
}
cout << endl;
}
private:
bitset<N> b1;
bitset<N> b2;
};
4、位圖的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)：節(jié)省空間，查找速度快
缺點(diǎn)：要求范圍相對(duì)集中，范圍特別分散的，空間消耗大；
位圖只對(duì)整型使用，浮點(diǎn)數(shù)、string等等其他類型無(wú)法使用。
如果要判斷其他類型，該類型如果可以使用哈希函數(shù)轉(zhuǎn)換為整型的，可以考慮布隆過(guò)濾器
二、布隆過(guò)濾器
1、布隆過(guò)濾器的概念
布隆過(guò)濾器是由布?。˙urton Howard Bloom）在1970年提出的 一種緊湊型的、比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)，特點(diǎn)是高效地插入和查詢，可以用來(lái)告訴你 “某樣?xùn)|西一定不存在或者可能存在”，它是用多個(gè)哈希函數(shù)，將一個(gè)數(shù)據(jù)映射到位圖結(jié)構(gòu)中。此種方式不僅可以提升查詢效率，也可以節(jié)省大量的內(nèi)存空間。
我們?yōu)榱私档驼`判的概率，解決方法就是對(duì)同一個(gè)元素使用多組哈希函數(shù)進(jìn)行映射，它能降低誤判率，但增加了空間消耗，使用時(shí)需要把控號(hào)布隆過(guò)濾器的哈希函數(shù)的個(gè)數(shù)和布隆過(guò)濾器的長(zhǎng)度
2、布隆過(guò)濾器的使用場(chǎng)景
1、不需要一定準(zhǔn)確的場(chǎng)景，例如個(gè)人網(wǎng)站注冊(cè)的時(shí)候昵稱判重，使用布隆過(guò)濾器可以判斷某個(gè)昵稱一定沒(méi)有被使用過(guò)，但會(huì)誤判某些造成沖突但沒(méi)有被使用的昵稱
2、提高效率。例如客戶端查找信息時(shí)，先用布隆過(guò)濾器篩選一下，如果不在，則直接將未查到的信息反饋給客戶端；如果布隆過(guò)濾器發(fā)現(xiàn)查找信息與位圖匹配，則將需要查找的信息推送給服務(wù)器中的數(shù)據(jù)庫(kù)進(jìn)行精確查找
3、布隆過(guò)濾器的刪除
單純的布隆過(guò)濾器時(shí)不支持刪除的，因?yàn)橐粋€(gè)比特位可能被多個(gè)元素所映射。如果非要在布隆過(guò)濾器中實(shí)現(xiàn)刪除，那就只能將位圖結(jié)構(gòu)修改未計(jì)數(shù)器結(jié)構(gòu)。數(shù)據(jù)set時(shí)，每被映射一次，計(jì)數(shù)器加1，reset時(shí)，該位計(jì)數(shù)器-1，直到該位計(jì)數(shù)器為0.但是這種操作所需的空間消耗急劇增加。
4、布隆過(guò)濾器的優(yōu)缺點(diǎn)
優(yōu)點(diǎn)
-
增加和查詢?cè)氐臅r(shí)間復(fù)雜度為:O(K), (K為哈希函數(shù)的個(gè)數(shù)，一般比較小)，與數(shù)據(jù)量大小無(wú)關(guān)
-
哈希函數(shù)相互之間沒(méi)有關(guān)系，方便硬件并行運(yùn)算
-
布隆過(guò)濾器不需要存儲(chǔ)元素本身，在某些對(duì)保密要求比較嚴(yán)格的場(chǎng)合有很大優(yōu)勢(shì)
-
在能夠承受一定的誤判時(shí)，布隆過(guò)濾器比其他數(shù)據(jù)結(jié)構(gòu)有這很大的空間優(yōu)勢(shì)
-
數(shù)據(jù)量很大時(shí)，布隆過(guò)濾器可以表示全集，其他數(shù)據(jù)結(jié)構(gòu)不能
-
使用同一組散列函數(shù)的布隆過(guò)濾器可以進(jìn)行交、并、差運(yùn)算
缺點(diǎn)
-
有誤判率，即存在假陽(yáng)性(False Position)，即不能準(zhǔn)確判斷元素是否在集合中
(補(bǔ)救方法：再建立一個(gè)白名單，存儲(chǔ)可能會(huì)誤判的數(shù)據(jù))
-
不能獲取元素本身
-
一般情況下不能從布隆過(guò)濾器中刪除元素
-
如果采用計(jì)數(shù)方式刪除，可能會(huì)存在計(jì)數(shù)回繞問(wèn)題
5、布隆過(guò)濾器面試題
1、給一個(gè)超過(guò)100G大小的log file, log中存著IP地址, 設(shè)計(jì)算法找到出現(xiàn)次數(shù)最多的IP地址？
我們可以將它分成100個(gè)小文件，使用哈希算法，將ip轉(zhuǎn)換成整型，將它取模， i=HashFunc(ip)%100,i是多少，ip就進(jìn)入幾號(hào)小文件。
如果沖突的桶超過(guò)1G怎么辦？
1、這個(gè)桶沖突的IP很多，大多都是不重復(fù)的，map統(tǒng)計(jì)不下
2、這個(gè)桶沖突的IP很多，大多都是重復(fù)的，map可以統(tǒng)計(jì)
? 直接使用map中的insert將每一個(gè)沖突桶的元素插入到map中。情況一：
如果insert失敗，說(shuō)明空間不足，new節(jié)點(diǎn)失敗，拋出異常。解決方法是：
換個(gè)哈希函數(shù)，遞歸再次對(duì)這個(gè)桶進(jìn)行切分。情況二：map可以正常統(tǒng)計(jì)
2、給兩個(gè)文件，分別有100億個(gè)query，我們只有1G內(nèi)存，如何找到兩個(gè)文件交集？分別給出精確算法和近似算法文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-713461.html
精確算法：使用哈希切分，將兩個(gè)大文件分別切成一個(gè)個(gè)小文件A0-A99，B0-B99（蛋哥小文件超過(guò)1G換一個(gè)哈希函數(shù)）；因?yàn)槭褂玫氖峭粋€(gè)哈希函數(shù)，所以交集必定存在于A0和B0，A1和B1這種相同下標(biāo)的小文件中?？梢韵葘0存放至哈希表中，B0去重后與哈希表比對(duì)，就能夠得到精確交集文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-713461.html
6、布隆過(guò)濾器的實(shí)現(xiàn)
#include <iostream>
#include <vector>
#include <bitset>
#include <string>
using namespace std;
struct BKDRHash
{
size_t operator()(const string& s)
{
// BKDR
size_t value = 0;
for (auto ch : s)
{
value *= 31;
value += ch;
}
return value;
}
};
struct APHash
{
size_t operator()(const string& s)
{
size_t hash = 0;
for (long 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 DJBHash
{
size_t operator()(const string& s)
{
size_t hash = 5381;
for (auto ch : s)
{
hash += (hash << 5) + ch;
}
return hash;
}
};
template<size_t N,
size_t X = 5,
class K = string,
class HashFunc1 = BKDRHash,
class HashFunc2 = APHash,
class HashFunc3 = DJBHash>
class BloomFilter
{
public:
void set(const K& key)
{
size_t len = X * N;
size_t index1 = HashFunc1()(key) % len;
size_t index2 = HashFunc2()(key) % len;
size_t index3 = HashFunc3()(key) % len;
/* cout << index1 << endl;
cout << index2 << endl;
cout << index3 << endl<<endl;*/
_bs.set(index1);
_bs.set(index2);
_bs.set(index3);
}
bool test(const K& key)
{
size_t len = X * N;
size_t index1 = HashFunc1()(key) % len;
if (_bs.test(index1) == false)
return false;
size_t index2 = HashFunc2()(key) % len;
if (_bs.test(index2) == false)
return false;
size_t index3 = HashFunc3()(key) % len;
if (_bs.test(index3) == false)
return false;
return true;//存在誤判的
}
// 不支持刪除，刪除可能會(huì)影響其他值。
void reset(const K& key);
private:
bitset<X* N> _bs;
};
void test_bloomfilter1()
{
srand((unsigned int)time(0));
const size_t N = 100000;
BloomFilter<N> bf;
std::vector<std::string> v1;
std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
for (size_t i = 0; i < N; ++i)
{
v1.push_back(url + std::to_string(i));
}
for (auto& str : v1)
{
bf.set(str);
}
// v2跟v1是相似字符串集，但是不一樣
std::vector<std::string> v2;
for (size_t i = 0; i < N; ++i)
{
std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
url += std::to_string(999999 + i);
v2.push_back(url);
}
size_t n2 = 0;
for (auto& str : v2)
{
if (bf.test(str))
{
++n2;
}
}
cout << "相似字符串誤判率:" << (double)n2 / (double)N << endl;
// 不相似字符串集
std::vector<std::string> v3;
for (size_t i = 0; i < N; ++i)
{
string url = "zhihu.com";
url += std::to_string(i + rand());
v3.push_back(url);
}
size_t n3 = 0;
for (auto& str : v3)
{
if (bf.test(str))
{
++n3;
}
}
cout << "不相似字符串誤判率:" << (double)n3 / (double)N << endl;
}
到了這里，關(guān)于【C++】哈希與布隆過(guò)濾器的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[C++]哈希應(yīng)用之位圖&布隆過(guò)濾器](https://imgs.yssmx.com/Uploads/2024/04/852662-1.gif)
