【C++篇】位圖與布隆過濾器

一，位圖

1.1，位圖的概念

1.2，位圖的設計與實現

1.5，位圖的應用舉例

1.4，位圖常用應用場景

?二，布隆過濾器

2.1，定義：

?2.2，布隆過濾器的實現

2.3，?應用場景

三，海量數據處理問題

3.1，10億個整數求最大的前100個數

3.2，給兩個文件，分別有100億個query（查詢字符串），我們只有1G內存，如何找到兩個文件交集？

一，位圖

1.1，位圖的概念

位圖是一種高效的數據結構，通過二進制位（0或1）的數組來高效存儲和操作數據，常用于標記狀態或處理大規模數據。

位圖的優缺點：

優點：增刪查改快，節省空間

缺點：只適用于整形

核心特性

空間高效：每個元素僅占1 bit，適合處理海量數據（如去重、統計）。
快速操作：支持位運算（與、或、異或等）進行高效查詢和修改。

1.2，位圖的設計與實現

位圖本質是一個直接定址法的哈希表，每個整型值映射一個bit位。

?核心接口：

對于一個整形值x。計算x對應的bit位：i=x/32，j=i%32，得到x在第i個整形的第j個bit位。

對于一個整形值x。要將它放入到數據中，只需將x對應的bit位由0置為1。?

對于一個整形值x，將它從數據中刪除，只需將x對應的bit位由1置為0.

判斷一個值x存不存在

代碼：

//N空間大小，比特位
template<size_t N>
class bitset
{
public:bitset(){_bs.resize(N / 32 + 1);}//將x位置的bit值 置為1void set(const int& x){//第i個整型的第j個bit位size_t i = x / 32;size_t j = x % 32;_bs[i] |= (1 << j);}//刪除x位置//將x位置的bit值 置為0void reset(const int& x){//第i個整型的第j個bit位size_t i = x / 32;size_t j = x % 32;_bs[i] &= (~(1 << j));}//判斷x值在不在bool test(const int& x){//第i個整型的第j個bit位size_t i = x / 32;size_t j = x % 32;return _bs[i] & (1 << j);}
private:std::vector<int> _bs;
};

1.5，位圖的應用舉例

(1) 給40億個不重復的unsigned int的整數，沒排過序的，然后再給一個數，如何快速判斷這個數是否在那40億個數當中。

40億數據量太大，如果將40億個int數據變量完全存儲到內存中可不得了，可以采用40億個位來存儲這些數據的狀態。

首先遍歷這40億個數，在位圖中將對應的位置為1，再對于給出的數，進行判斷即可。

(2) 在2.5億個整數中找出不重復的整數，注，內存不足以容納這2.5億個整數。

使用2個位圖，每個數分配2個位圖，用這兩個位圖來表示存儲狀態，00表示不存在，01表示出現一次，10表示多次，11無意義

代碼示例：

?? ?template<size_t N>
?? ?class twobitset
?? ?{
?? ?public:
?? ??? ?//添加x
?? ??? ?void set(const int& x)
?? ??? ?{
?? ??? ??? ?bool bit1 = bs1.test(x);
?? ??? ??? ?bool bit2 = bs2.test(x);
?? ??? ??? ?//出現0次->出現1次
?? ??? ??? ?if (!bit1 && !bit2)//00->01
?? ??? ??? ?{
?? ??? ??? ??? ?bs2.set(x);
?? ??? ??? ?}
?? ??? ??? ?//出現1次->出現2次
?? ??? ??? ?else if (!bit1 && bit2)//01-> 10
?? ??? ??? ?{
?? ??? ??? ??? ?bs1.set(x);
?? ??? ??? ??? ?bs2.reset(x);
?? ??? ??? ?}
?? ??? ??? ?//出現2次->出現多次
?? ??? ??? ?else if (bit1 && !bit2)//10 ->11
?? ??? ??? ?{
?? ??? ??? ??? ?bs2.set(x);
?? ??? ??? ?}
?? ??? ?}
?? ??? ?//獲取x的出現次數
?? ??? ?int getcount(const int& x)
?? ??? ?{
?? ??? ??? ?bool bit1 = bs1.test(x);
?? ??? ??? ?bool bit2 = bs2.test(x);

?? ??? ??? ?if (!bit1 && !bit2)//00
?? ??? ??? ?{
?? ??? ??? ??? ?return 0;
?? ??? ??? ?}
?? ??? ??? ?else if (!bit1 && bit2)//01
?? ??? ??? ?{
?? ??? ??? ??? ?return 1;
?? ??? ??? ?}
?? ??? ??? ?else if (bit1 && !bit2)//10?
?? ??? ??? ?{
?? ??? ??? ??? ?return 2;
?? ??? ??? ?}
?? ??? ??? ?else
?? ??? ??? ?{
?? ??? ??? ??? ?return 3;
?? ??? ??? ?}
?? ??? ?}
?? ?private:
?? ??? ?bitset<N> bs1;
?? ??? ?bitset<N> bs2;
?? ?};

1.4，位圖常用應用場景

去重與存在性檢查：
例如，統計10億用戶中哪些已注冊，僅需約120MB內存（109÷8≈125MB109÷8≈125MB）。
布隆過濾器（Bloom Filter）：
利用多個哈希函數和位圖實現概率型數據存在性判斷。
數據庫索引：
快速篩選滿足條件的記錄（如性別為“男”的用戶）。
內存管理：
操作系統用位圖標記內存頁的分配狀態。

?二，布隆過濾器

2.1，定義：

有一些場景，由大量數據需要判斷是否存在，而這些數據不是整形，比如string，就不能使用位圖了，這些場景就需要布隆過濾器來解決。利用多個哈希函數和位圖實現，哈希函數內容見上篇文章【哈希表】。

?核心原理

位數組（Bit Array）：長度為?m?的二進制數組，初始全為0。
哈希函數集合：k個獨立的哈希函數，每個函數將元素映射到位數組的某個位置。

以string類型為例：

而這種沖突是無法避免的，因為位圖中只存儲了狀態，即0或1，無法改變。所以我們只能做到降低沖突概率，對于一個字符串，讓它映射到多個位置上。經過k個哈希函數的轉化，映射到k個位置，將這k位置都置為1。在查找時也是如此，經過k個哈希函數，k個位置都為1，才能說明該數據存在，否則就是與其他位置存在沖突，導致幾個位置位1，幾個位置為0，說明該數據不存在。

布隆過濾器優缺點：

?2.2，布隆過濾器的實現

下圖中：

k代表哈希函數的個數

m為布隆過濾器的大小

n為插入的元素個數。

通過觀察誤判率的公式可得：在k一定的情況下，當n增加時，誤判率增加，當m增加時，誤判率越小。也就是哈希函數一定的情況下，插入元素越多時，誤判率增加，布隆過濾器長度越長時，誤判率減小。令X=m/n，可得，X越大，誤判率越小。

//哈希函數
struct HashFuncBKDR
{// @detail 本 算法由于在Brian Kernighan與Dennis Ritchie的《The CProgramming Language》// 一書被展示而得 名，是一種簡單快捷的hash算法，也是Java目前采用的字符串的Hash算法累乘因子為31。size_t operator()(const std::string& s){size_t hash = 0;for (auto ch : s){hash *= 31;hash += ch;}return hash;}
};
struct HashFuncAP
{// 由Arash Partow發明的一種hash算法。  size_t operator()(const std::string& s){size_t hash = 0;for (size_t 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 HashFuncDJB
{// 由Daniel J. Bernstein教授發明的一種hash算法。 size_t operator()(const std::string& s){size_t hash = 5381;for (auto ch : s){hash = hash * 33 ^ ch;}return hash;}
};//布隆過濾器
//M布隆過濾器的長度
//N插入元素個數
//X=M/N 越大，誤判率越小
template<size_t  N,size_t X=5,class k=string,class Hash1= HashFuncBKDR,class Hash2= HashFuncAP,class Hash3= HashFuncDJB>
class BloomFilter
{
public:void set(const k& key){size_t hash1 = Hash1()(key) % M;size_t hash2 = Hash2()(key) % M;size_t hash3 = Hash3()(key) % M;_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}//可能存在誤判bool test(const k& key){//只要一個位置為0，就不存在size_t hash1 = Hash1()(key) % M;if (_bs.test(hash1) == 0)return false;size_t hash2 = Hash2()(key) % M;if (_bs.test(hash2) == 0)return false;size_t hash3 = Hash3()(key) % M;if (_bs.test(hash3) == 0)return false;return true;}
private:static const int M = N * X;bitset<M> _bs;
};

2.3，?應用場景

緩存穿透防護：
? ? 在分布式緩存系統中，布隆過濾器可以?來解決緩存穿透的問題。緩存穿透是指惡意用戶請求?個不存在的數據，導致請求直接訪問數據庫，造成數據庫壓力過?。布隆過濾器可以先判斷請求的數據是否存在于布隆過濾器中，如果不存在，直接返回不存在，避免對數據庫的無效查詢。
爬蟲去重：
? ?在爬蟲系統中，為了避免重復爬取相同的URL，可以使?布隆過濾器來進行URL去重。爬取到的URL可以通過布隆過濾器進行判斷，已經存在的URL則可以直接忽略，避免重復的網絡請求和數據處理。
對數據庫查詢提效：
? 在數據庫中，布隆過濾器可以用來加速查詢操作。例如：一個app要快速判斷一個電話號碼是否注冊過，可以使用布隆過濾器來判斷一個用戶電話號碼是否存在于表中，如果不存在，可以直接返回不存在，避免對數據庫進行無用的查詢操作。如果在，再去數據庫查詢進行二次確認。
垃圾郵件過濾：
? ?在垃圾郵件過濾系統中，布隆過濾器可以用來判斷郵件是否是垃圾郵件。系統可以將已知的垃圾郵件的特征信息存儲在布隆過濾器中，當新的郵件到達時，可以通過布隆過濾器快速判斷是否為垃圾郵件，從而提高過濾的效率。

布隆過濾器通過犧牲一定的準確性，在海量數據去重、快速過濾等場景中展現了不可替代的優勢，是分布式系統和大數據處理的基石技術之一。

三，海量數據處理問題

3.1，10億個整數求最大的前100個數

本題是topk問題，用堆解決，建一個100個數的小堆，讓這10億個整數分別與堆頂元素比較，如果大于堆頂元素，就交換，再調整堆。最后最大的前100個就保存在小堆中。

3.2，給兩個文件，分別有100億個query（查詢字符串），我們只有1G內存，如何找到兩個文件交集？

解法一：使用布隆過濾器存儲文件1，再遍歷文件2，看布隆過濾器中是否存在，存在就是交集。

解法二：

哈希切分，首先內存的訪問速度遠大于硬盤，大文件放到內存搞不定，那么我們可以考慮切分為

文件，再放進內存處理。

本質是相同的query在哈希切分過程中，一定進入的同一個小文件Ai和Bi，不可能出現A中的的 query進入Ai，但是B中的相同query進入了和Bj的情況，所以對Ai和Bi進行求交集即可，不需要Ai 和Bj求交集。

?哈希切分的問題就是每個??件不是均勻切分的，可能會導致某個小文件很大內存放不下。我們細細分析?下某個小文件很?有兩種情況：1.這個小文件中?部分是同一個query。2.這個小文件是有很多的不同query構成，本質是這些query沖突了。針對情況1，其實放到內存的set中是可以放下的，因為set是去重的。針對情況2，需要換個哈希函數繼續二次哈希切分。所以我們遇到大?于1G小文件，可以繼續讀到set中找交集，若set.insert時拋出了異常(set插?數據拋異常只可能是申請內存失敗了，不會有其他情況)，那么就說明內存放不下是情況2，換個哈希函數進行二次哈希切分。