哈希位圖和布隆過濾器都是常用的概率數(shù)據(jù)結(jié)構(gòu)，用于高效地判斷一個(gè)元素是否存在于一個(gè)集合當(dāng)中，但它們?cè)趯?shí)現(xiàn)方法和各自的優(yōu)缺點(diǎn)上有所區(qū)別。
哈希位圖
哈希位圖（Hash Bitmap）是由一個(gè)位數(shù)組構(gòu)成，每個(gè)元素（通常是一個(gè)整數(shù)）被映射到位數(shù)組中的某個(gè)位置。對(duì)于集合中的每個(gè)元素，通過哈希函數(shù)將其映射到位數(shù)組的對(duì)應(yīng)位置，并將該位置標(biāo)記為已經(jīng)存在。判斷一個(gè)元素是否存在時(shí)，只需檢查位數(shù)組中對(duì)應(yīng)的位置是否被標(biāo)記，若被標(biāo)記則表示元素存在，否則表示元素不存在
哈希位圖（Hash Bitmap）是由一個(gè)位數(shù)組構(gòu)成，每個(gè)元素（通常是一個(gè)整數(shù)）被映射到位數(shù)組中的某個(gè)位置。對(duì)于集合中的每個(gè)元素，通過哈希函數(shù)將其映射到位數(shù)組的對(duì)應(yīng)位置，并將該位置標(biāo)記為已經(jīng)存在。判斷一個(gè)元素是否存在時(shí)，只需檢查位數(shù)組中對(duì)應(yīng)的位置是否被標(biāo)記，若被標(biāo)記則表示元素存在，否則表示元素不存在。
當(dāng)我們存儲(chǔ)整數(shù)時(shí)，因?yàn)橐粋€(gè)整數(shù)為四個(gè)bit位，一個(gè)比特位八個(gè)字節(jié)，這樣算下來占存的空間極大，我們可以使用
char類型進(jìn)行存儲(chǔ)，因?yàn)?code>char只占一個(gè)字節(jié)。
我們可以將數(shù)組按字節(jié)來進(jìn)行歸類，就如上圖來說
當(dāng)我們要進(jìn)行存儲(chǔ)X的時(shí)候，我們先用 X / 8 來算出它在哪個(gè)比特位，然后再進(jìn)行X % 8 來計(jì)算出他在這個(gè)bit位的第幾個(gè)字節(jié)，計(jì)算出后將此位置設(shè)置為1，標(biāo)記此數(shù)字
優(yōu)缺點(diǎn)
優(yōu)點(diǎn)
- 簡(jiǎn)單高效：哈希位圖通過位運(yùn)算可以在常量時(shí)間內(nèi)完成元素的插入和查詢操作。
- 空間效率高：相對(duì)于其他數(shù)據(jù)結(jié)構(gòu)，哈希位圖在空間使用上非常緊湊，只需要存儲(chǔ)每個(gè)元素的標(biāo)記位即可。
缺點(diǎn)
- 無法刪除元素：哈希位圖只能進(jìn)行插入和查詢操作，無法刪除已經(jīng)插入的元素。
- 內(nèi)存占用：如果集合中的元素較多，哈希位圖會(huì)占用較大的內(nèi)存空間。
位圖應(yīng)用
- 快速查找某個(gè)數(shù)據(jù)是否在一個(gè)集合中
- 排序 + 去重
- 求兩個(gè)集合的交集、并集等
- 操作系統(tǒng)中磁盤塊標(biāo)記
例：
給兩個(gè)文件，分別有100億個(gè)整數(shù)，我們只有1G內(nèi)存，如何找到兩個(gè)文件交集？
分析：首先不要受到題目的迷惑，100億整數(shù)中包括很多重復(fù)數(shù)據(jù)，實(shí)際范圍是0到0xffffffff。
512M左右就可以表示數(shù)據(jù)是否存在了。
代碼邏輯分析：
用兩個(gè)位圖來放兩文件中的數(shù)據(jù)，用兩個(gè)位圖中的對(duì)應(yīng)位置表示不同的狀態(tài)：
00表示兩文件中都沒有某個(gè)數(shù)據(jù)，10表示在一個(gè)位圖中出現(xiàn)過，01表示在兩個(gè)位圖中都出現(xiàn)了，這種狀態(tài)也就是交集數(shù)據(jù)的狀態(tài)。
模擬實(shí)現(xiàn)代碼
using namespace std;
//普通類型模板
template<size_t N>
class bitset
{
public:
bitset()
{
_bits.resize((N / 8) + 1, 0);
}
//將對(duì)應(yīng)的值按照位圖存放
void set(size_t x)
{
size_t i = x / 8;//計(jì)算x映射的位在第i個(gè)char數(shù)組位置
size_t j = x % 8;//計(jì)算x映射的位在這個(gè)char的第j個(gè)比特位
_bits[i] |= (1 << j);
}
void reset(size_t x)
{
size_t i = x / 8;//計(jì)算x映射的位在第i個(gè)char數(shù)組位置
size_t j = x % 8;//計(jì)算x映射的位在這個(gè)char的第j個(gè)比特位
_bits[i] &= ~(1 << j);
}
//檢查是否將位圖修改
bool test(size_t x)
{
size_t i = x / 8;//計(jì)算x映射的位在第i個(gè)char數(shù)組位置
size_t j = x % 8;//計(jì)算x映射的位在這個(gè)char的第j個(gè)比特位
return _bits[i] & (1 << j);
}
private:
vector<char> _bits;
};
template<size_t N>
class twobitset
{
public:
//查找唯一出現(xiàn)一次的數(shù)
void set(size_t x)
{
// 00 -> 01
if (_bs1.test(x) == false
&& _bs2.test(x) == false)
{
_bs2.set(x);
}
else
{
//01 -> 10
_bs1.set(x);
_bs2.reset(x);
}
}
、
void Print()
{
for (size_t i = 0; i < N; ++i)
{
if (_bs2.test(i))
{
cout << i << endl;
}
}
}
void Print_more()
{
for (size_t i = 0; i < N; ++i)
{
if (_bs1.test(i))
{
cout << i << endl;
}
}
}
private:
bitset<N> _bs1;
bitset<N> _bs2;
};
void test_twobitset()
{
int a[] = { 1,1,2,2,3,3,4,4,5,5,6,6,7 };
twobitset<20> t;
for (auto e : a)
{
t.set(e);
}
t.Print();
t.Print_more();
}
哈希布隆過濾器
布隆過濾器（Bloom Filter）是一種概率型數(shù)據(jù)結(jié)構(gòu)，基于位數(shù)組和多個(gè)哈希函數(shù)實(shí)現(xiàn)。對(duì)于集合中的每個(gè)元素，通過多個(gè)哈希函數(shù)將其映射到位數(shù)組的多個(gè)位置，并將對(duì)應(yīng)位置標(biāo)記為已經(jīng)存在。判斷一個(gè)元素是否存在時(shí)，需要對(duì)該元素進(jìn)行多次哈希，并檢查所有對(duì)應(yīng)位置是否都被標(biāo)記，若有任何一個(gè)位置未被標(biāo)記，則表示元素不存在。
哈希布隆過濾器的提出
在注冊(cè)賬號(hào)設(shè)置昵稱的時(shí)候，為了保證每個(gè)用戶昵稱的唯一性，系統(tǒng)必須檢測(cè)你輸入的昵稱是否被使用過，這本質(zhì)就是一個(gè)key的模型，我們只需要判斷這個(gè)昵稱被用過，還是沒被用過。
- 方法一：用紅黑樹或哈希表將所有使用過的昵稱存儲(chǔ)起來，當(dāng)需要判斷一個(gè)昵稱是否被用過時(shí)，直接判斷該昵稱是否在紅黑樹或哈希表中即可。但紅黑樹和哈希表最大的問題就是浪費(fèi)空間，當(dāng)昵稱數(shù)量非常多的時(shí)候內(nèi)存當(dāng)中根本無法存儲(chǔ)這些昵稱
- 方法二：用位圖將所有使用過的昵稱存儲(chǔ)起來，雖然位圖只能存儲(chǔ)整型數(shù)據(jù)，但我們可以通過一些哈希算法將字符串轉(zhuǎn)換成整型，比如BKDR哈希算法。當(dāng)需要判斷一個(gè)昵稱是否被用過時(shí)，直接判斷位圖中該昵稱對(duì)應(yīng)的比特位是否被設(shè)置即可。
位圖雖然能夠大大節(jié)省內(nèi)存空間，但由于字符串的組合形式太多了，一個(gè)字符的取值有256種，而一個(gè)數(shù)字的取值只有10種，因此無論通過何種哈希算法將字符串轉(zhuǎn)換成整型都不可避免會(huì)存在哈希沖突。
這里的哈希沖突就是不同的昵稱最終被轉(zhuǎn)換成了相同的整型，此時(shí)就可能會(huì)引發(fā)誤判，即某個(gè)昵稱明明沒有被使用過，卻被系統(tǒng)判定為已經(jīng)使用過了，于是就出現(xiàn)了布隆過濾器。
哈希布隆過濾器概念
布隆過濾器是由布隆（Burton Howard Bloom）在1970年提出的一種緊湊型的、比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)，特點(diǎn)是高效地插入和查詢。
- 布隆過濾器其實(shí)就是位圖的一個(gè)變形和延申，雖然無法避免存在哈希沖突，但我們可以想辦法降低誤判的概率。
- 當(dāng)一個(gè)數(shù)據(jù)映射到位圖中時(shí)，布隆過濾器會(huì)用多個(gè)哈希函數(shù)將其映射到多個(gè)比特位，當(dāng)判斷一個(gè)數(shù)據(jù)是否在位圖當(dāng)中時(shí)，需要分別根據(jù)這些哈希函數(shù)計(jì)算出對(duì)應(yīng)的比特位，如果這些比特位都被設(shè)置為1則判定為該數(shù)據(jù)存在，否則則判定為該數(shù)據(jù)不存在。
- 布隆過濾器使用多個(gè)哈希函數(shù)進(jìn)行映射，目的就在于降低哈希沖突的概率，一個(gè)哈希函數(shù)產(chǎn)生沖突的概率可能比較大，但多個(gè)哈希函數(shù)同時(shí)產(chǎn)生沖突的概率可就沒那么大了。
假設(shè)布隆過濾器使用三個(gè)哈希函數(shù)進(jìn)行映射，那么“張三”這個(gè)昵稱被使用后位圖中會(huì)有三個(gè)比特位會(huì)被置1，當(dāng)有人要使用“李四”這個(gè)昵稱時(shí)，就算前兩個(gè)哈希函數(shù)計(jì)算出來的位置都產(chǎn)生了沖突，但由于第三個(gè)哈希函數(shù)計(jì)算出的比特位的值為0，此時(shí)系統(tǒng)就會(huì)判定“李四”這個(gè)昵稱沒有被使用過。
但隨著位圖中添加的數(shù)據(jù)不斷增多，位圖中1的個(gè)數(shù)也在不斷增多，此時(shí)就會(huì)導(dǎo)致誤判的概率增加。
比如“張三”和“李四”都添加到位圖中后，當(dāng)有人要使用“王五”這個(gè)昵稱時(shí)，雖然“王五”計(jì)算出來的三個(gè)位置既不和“張三”完全一樣，也不和“李四”完全一樣，但“王五”計(jì)算出來的三個(gè)位置分別被“張三”和“李四”占用了，此時(shí)系統(tǒng)也會(huì)誤判為“王五”這個(gè)昵稱已經(jīng)被使用過了。
布隆過濾器的特點(diǎn)
- 當(dāng)布隆過濾器判斷一個(gè)數(shù)據(jù)存在可能是不準(zhǔn)確的，因?yàn)檫@個(gè)數(shù)據(jù)對(duì)應(yīng)的比特位可能被其他一個(gè)數(shù)據(jù)或多個(gè)數(shù)據(jù)占用了。
- 當(dāng)布隆過濾器判斷一個(gè)數(shù)據(jù)不存在是準(zhǔn)確的，因?yàn)槿绻摂?shù)據(jù)存在那么該數(shù)據(jù)對(duì)應(yīng)的比特位都應(yīng)該已經(jīng)被設(shè)置為1了。
如何控制誤判率
- 很顯然，過小的布隆過濾器很快所有的比特位都會(huì)被設(shè)置為1，此時(shí)布隆過濾器的誤判率就會(huì)變得很高，因此布隆過濾器的長(zhǎng)度會(huì)直接影響誤判率，布隆過濾器的長(zhǎng)度越長(zhǎng)其誤判率越小。
- 此外，哈希函數(shù)的個(gè)數(shù)也需要權(quán)衡，哈希函數(shù)的個(gè)數(shù)越多布隆過濾器中比特位被設(shè)置為1的速度越快，并且布隆過濾器的效率越低，但如果哈希函數(shù)的個(gè)數(shù)太少，也會(huì)導(dǎo)致誤判率變高。
那應(yīng)該如何選擇哈希函數(shù)的個(gè)數(shù)和布隆過濾器的長(zhǎng)度呢，有人通過計(jì)算后得出了以下關(guān)系式：
其中k為哈希函數(shù)個(gè)數(shù)，m為布隆過濾器長(zhǎng)度，n為插入的元素個(gè)數(shù)，p為誤判率。
我們這里可以大概估算一下，如果使用3個(gè)哈希函數(shù)，即k的值為3，l n 2 的值我們?nèi)?.7，那么 m 和 n的關(guān)系大概是m = 4 × n ，也就是布隆過濾器的長(zhǎng)度應(yīng)該是插入元素個(gè)數(shù)的4倍。
模擬實(shí)現(xiàn)代碼
//布隆過濾器
//N位最多插入的key個(gè)數(shù)據(jù)
template<size_t N, class K = string,
class Hash1 = BKDRHash,
class Hash2 = APHash,
class Hash3 = DJBHash>
class BloomFilter
{
public:
void set(const K& key)
{
size_t len = N * _x;
size_t hash1 = Hash1()(key) % len;
_bs.set(hash1);
size_t hash2 = Hash2()(key) % len;
_bs.set(hash2);
size_t hash3 = Hash3()(key) % len;
_bs.set(hash3);
cout << hash1 << " " << hash2 << " " << hash3 << endl;
}
bool test(const K& key)
{
size_t len = N * _x;
size_t hash1 = Hash1()(key) % len;
if (!_bs.test(hash1))
{
return false;
}
size_t hash2 = Hash2()(key) % len;
if (!_bs.test(hash2))
{
return false;
}
size_t hash3 = Hash3()(key) % len;
if (!_bs.test(hash3))
{
return false;
}
return true; //key對(duì)應(yīng)的三個(gè)位都被設(shè)置，key存在（可能誤判）
}
private:
static const size_t _x = 4;
bitset<N * _x> _bs;//求布隆過濾器長(zhǎng)度
};
_X代表布隆過濾器的長(zhǎng)度，是通過以下公式計(jì)算得來的
為什么哈希布隆圖要比位圖省空間
哈希布隆圖相比于位圖在空間使用上更加高效，這是因?yàn)楣２悸D利用了多個(gè)哈希函數(shù)和位數(shù)組的重復(fù)利用，減少了所需的內(nèi)存空間。
首先，讓我們對(duì)比一下位圖和哈希布隆圖的實(shí)現(xiàn)方式：
-
位圖：位圖是一個(gè)固定大小的位數(shù)組，數(shù)組中的每個(gè)位置表示一個(gè)元素，當(dāng)元素存在時(shí)，對(duì)應(yīng)位置的位值為1；當(dāng)元素不存在時(shí)，對(duì)應(yīng)位置的位值為0。位圖的大小與集合中元素的總數(shù)相一致，每個(gè)元素都需要一個(gè)位置來進(jìn)行標(biāo)記。
-
哈希布隆圖：哈希布隆圖也是一個(gè)位數(shù)組，但與位圖不同的是，哈希布隆圖的位數(shù)組長(zhǎng)度通常會(huì)遠(yuǎn)遠(yuǎn)小于集合中元素的總數(shù)。它利用了多個(gè)哈希函數(shù)，每個(gè)元素通過這些哈希函數(shù)映射到位數(shù)組中的多個(gè)位置，將這些位置標(biāo)記為1。判斷一個(gè)元素是否存在時(shí)，需要對(duì)該元素進(jìn)行多次哈希，并檢查所有對(duì)應(yīng)位置是否都被標(biāo)記。
那么為什么哈希布隆圖能夠在空間上節(jié)?。?/p>
-
多個(gè)哈希函數(shù)：哈希布隆圖使用多個(gè)哈希函數(shù)，將每個(gè)元素映射到位數(shù)組的多個(gè)位置上。通過這種方式，可以減少?zèng)_突的可能性，使得位數(shù)組中的每個(gè)位置都能夠被更多元素共享，從而減少了位圖中的重復(fù)位。
-
位數(shù)組的重復(fù)利用：由于每個(gè)元素都會(huì)被多次哈希并占用多個(gè)位置，在位數(shù)組中的某個(gè)位置可能被多個(gè)元素標(biāo)記。利用這種重復(fù)標(biāo)記的方式，哈希布隆圖可以在相對(duì)較小的位數(shù)組中表示更多的元素。
舉個(gè)例子來說明，假設(shè)我們要表示一個(gè)集合，其中包含100個(gè)元素。如果使用位圖，我們需要一個(gè)大小為100的位數(shù)組，每個(gè)元素都占用一個(gè)位；而使用布隆過濾器，我們可以選擇一個(gè)相對(duì)較小的位數(shù)組，比如大小為50，并使用多個(gè)哈希函數(shù)將元素映射到位數(shù)組的多個(gè)位置，每個(gè)元素可以占用多個(gè)位。通過合理的設(shè)計(jì)，可以在僅占用50個(gè)位的情況下，仍然能夠高效地判斷集合中的元素是否存在。文章來源：http://www.zghlxwxcb.cn/news/detail-718960.html
需要注意的是，哈希布隆圖的節(jié)省空間是以犧牲一定的查詢準(zhǔn)確率為代價(jià)的。由于哈希沖突和位數(shù)組的重復(fù)利用，布隆過濾器可能存在一定的誤判率，即判斷元素不存在時(shí)，仍有一定概率判斷為存在。因此，在使用哈希布隆圖時(shí)需要權(quán)衡空間利用和查詢準(zhǔn)確率之間的關(guān)系。文章來源地址http://www.zghlxwxcb.cn/news/detail-718960.html
到了這里，關(guān)于【C++】哈希位圖和布隆過濾器的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
![[C++]哈希應(yīng)用之位圖&布隆過濾器](https://imgs.yssmx.com/Uploads/2024/04/852662-1.gif)
