目錄
一、位圖
1.1 位圖的概念
1.2 位圖的實現
1.3 位圖的應用（面試題）
二、布隆過濾器
2.1 布隆過濾器的引入
2.2?布隆過濾器概念
2.3 布隆過濾器的插入和查找
2.4 布隆過濾器的實現
2.5 布隆過濾器的優點和缺陷
2.6 布隆過濾器的應用（面試題）
一、位圖
1.1 位圖的概念
在C++中，位圖（Bitmap）是一種數組，其中數組的每個元素可以表示多個布爾值。用于高效地存儲和查詢海量數據，其中元素的每個布爾值只占用一個位（bit）的空間。通常是用來判斷某個數據存不存在的。
例如在32位系統中，一個unsigned int類型的變量可以表示32個布爾值。通過位操作，我們可以檢查、設置或清除特定的位，從而實現對大量布爾值的快速訪問和修改。
面試題
給40億個不重復的無符號整數，沒排過序。給一個無符號整數，如何快速判斷一個數是否在
這40億個數中。【騰訊】方法：
1. 遍歷，時間復雜度O(N)
2. 排序(O(NlogN))，利用二分查找: logN
3. 位圖解決方法1和2中都需要將數據保存在數組中，40億個整數需要16G內存，內存開辟不了這么大的連續空間。
數據是否在給定的整形數據中，結果是在或者不在，剛好是兩種狀態，那么可以使用一
個二進制比特位來代表數據是否存在的信息，如果二進制比特位為1，代表存在，為0
代表不存在。比如：
40億個不重復的無符號整數的范圍在0 ~ 2^32，有42億多種可能性。一個字符型8個比特位，每個比特位來存儲一個數字是否存在的狀態，需要(2^32) / 8 = 2^29字節，即0.5G的內存。
1.2 位圖的實現
C++標準庫中的位圖在線文檔說明? ? ?#include <bitset>
在C++中，位圖的實現通常使用unsigned int數組或者std::vector<unsigned int>。下面是一個簡單的位圖實現：
// N是需要多少比特位
template<size_t N>
class myBitSet
{
public:myBitSet(){_bs.resize((N >> 5) + 1, 0);//一個size_t 4個字節，32個比特位，右移五位相當于除以32，+1是防止有余數//注意：右移運算符>>優先級高于+，需要在右移時加上括號}void set(size_t x)//對第x個比特位置為1{size_t i = x / 32;//確定在哪一個size_tsize_t j = x % 32;//確定在哪一個比特位上_bs[i] |= (1 << j);}void reset(size_t x)//第x個比特位置清0{size_t i = x / 32;//確定在哪一個size_tsize_t j = x % 32;//確定在哪一個比特位上_bs[i] &= ~(1 << j);}bool test(size_t x)//返回第x位的狀態{size_t i = x / 32;//確定在哪一個size_tsize_t j = x % 32;//確定在哪一個比特位上return _bs[i] & (1 << j);}private:vector<size_t> _bs;
};1.3 位圖的應用（面試題）
1. 快速查找某個數據是否在一個集合中
2. 排序 + 去重
3. 求兩個集合的交集、并集等
4. 操作系統中磁盤塊標記
1. 給定100億個整數，設計算法找到只出現一次的整數?
100一個整數，它的范圍也是只在0 ~ 2^32 之間，可以設計兩個位圖，每一次映射都調整位圖里面的數字。例如出現0次設為00，出現1次設為01，二次及以上都為10。
template<size_t N> class twobitset { public:void set(size_t x){//00->01//01->10//10->不變if (_bs1.test(x) == false && _bs2.test(x) == false)//出現0次{_bs2.set(x);//新增設為01}else if (_bs1.test(x) == false && _bs2.test(x) == true)//出現1次{_bs1.set(x);_bs2.reset(x);//新增設為10}//出現2次及以上}void PrintOnce(){for (size_t i = 0; i < N; i++){if (_bs1.test(i) == false && _bs2.test(i) == true){cout << i << endl;}}cout << endl;}private:myBitSet<N> _bs1;myBitSet<N> _bs2; };
2. 給兩個文件，分別有100億個整數，我們只有1G內存，如何找到兩個文件交集?
各自映射到一個位圖，若一個值在兩個位圖都存在，則是交集
3. 位圖應用變形:1個文件有100億個int，1G內存，設計算法找到出現次數不超過2次的所有整數。
方法同問題1，創建兩個位圖，出現0次00，出現1次01，出現2次10，出現3次及以上 11。
二、布隆過濾器
2.1 布隆過濾器的引入
之前的搜索方法中，傳統的數據結構和方法存在一定的局限性：
- 暴力查找：數據量大了，效率就低。O(n)
- 排序+二分查找：排序有代價、數組不方便增刪。雖然查找的時間復雜度為 O(log n)，但排序的時間復雜度為 O(n log n)
- 搜索樹 ->AVL樹+紅黑樹：隨著數據量的增加，樹的高度也會增加，導致性能下降。
- 哈希：當發生哈希碰撞時，性能會下降。此外，哈希表的空間消耗相對較高。
- 以上數據結構，空間消耗很高。如何應對數量很大的數據？
- 位圖及變形：位圖只能處理整數，對于其他類型的數據則不適用。
如果要應對其他類型數據的問題，如何快速查找？
- 用哈希表存儲用戶記錄，缺點：浪費空間
- 用位圖存儲用戶記錄，缺點：位圖一般只能處理整形，如果內容編號是字符串，就無法處理了。
- 將哈希與位圖結合，即布隆過濾器。
2.2?布隆過濾器概念
布隆過濾器（Bloom Filter）是一種由布隆在1970年提出的概率型數據結構，它通過使用多個哈希函數將元素映射到一個 bit 數組中來實現高效的數據查詢和插入。布隆過濾器的核心優勢在于它的空間效率：它使用相對較少的內存來表示一個可能非常大的集合。可以用來告訴你 “某樣東西 一定不存在 或者 可能存在”。
布隆過濾器的特點包括：
- 高效插入和查詢：插入和查詢操作都非常快速，因為它們只涉及到哈希計算和位操作。
- 概率性：布隆過濾器可能會返回誤報（即一個元素被錯誤地判斷為存在于集合中），但不會返回漏報（即如果一個元素被判斷為不存在，那么它一定不存在）。
- 固定大小：布隆過濾器的位數組大小在創建時確定，不會隨著元素的添加而改變。
- 不可刪除：一旦元素被插入布隆過濾器，就無法刪除，因為刪除可能會導致其他元素的位被錯誤地設置為0。（傳統布隆過濾器不可刪除）
舉個例子：原本在位圖或哈希表/桶中，可能出現多個關鍵字映射到同一個位置，現在使用多個哈希函數，讓原本映射到一個位置的結果映射到多個位置。檢查關鍵字在不在，要把關鍵字映射的所有位置都檢查一遍，只有所有位置的狀態都為1，這個關鍵字才 “可能存在”，如果映射的位置有一個檢測到了0，那么這個關鍵字肯定不存在。
詳解布隆過濾器的原理，使用場景和注意事項
上面鏈接的講解非常精彩，有興趣的話可以看一下。
2.3 布隆過濾器的插入和查找
布隆過濾器是一個 bit 向量或者說 bit 數組
如果我們要映射一個值到布隆過濾器中，我們需要使用多個不同的哈希函數生成多個哈希值，并對每個生成的哈希值指向的 bit 位置為?1，例如針對值 “baidu” 和三個不同的哈希函數分別生成了哈希值 1、4、7，則上圖轉變為：
在再存一個值 “tencent”，如果哈希函數返回 3、4、8 的話，圖繼續變為：
值得注意的是，4 這個 bit 位由于兩個值的哈希函數都返回了這個 bit 位，因此它被覆蓋了。現在我們如果想查詢 “dianping” 這個值是否存在，哈希函數返回了 1、5、8三個值，結果我們發現 5 這個 bit 位上的值為 0，說明沒有任何一個值映射到這個 bit 位上，因此我們可以很確定地說 “dianping” 這個值不存在。而當我們需要查詢 “baidu” 這個值是否存在的話，那么哈希函數必然會返回 1、4、7，然后我們檢查發現這三個 bit 位上的值均為 1，那么我們可以說 “baidu” 存在了么？答案是不可以，只能是 “baidu” 這個值可能存在。
這是為什么呢？答案跟簡單，因為隨著增加的值越來越多，被置為 1 的 bit 位也會越來越多，這樣某個值 “taobao” 即使沒有被存儲過，但是萬一哈希函數返回的三個 bit 位都被其他值置位了 1 ，那么程序還是會判斷 “taobao” 這個值存在。
2.4 布隆過濾器的實現
各種字符串Hash函數
選取3種平均分較高的哈希算法：BKDRHash，APHash，DJBHash。
#include "myBitSet.h"struct BKDRHash
{size_t operator()(const string& key){// BKDRsize_t hash = 0;for (auto e : key){hash *= 31;hash += e;}return hash;}
};struct APHash
{size_t operator()(const string& key){size_t hash = 0;for (size_t i = 0; i < key.size(); i++){char ch = key[i];if ((i & 1) == 0){hash ^= ((hash << 7) ^ ch ^ (hash >> 3));}else{hash ^= (~((hash << 11) ^ ch ^ (hash >> 5)));}}return hash;}
};struct DJBHash
{size_t operator()(const string& key){size_t hash = 5381;for (auto ch : key){hash += (hash << 5) + ch;}return hash;}
};template <size_t N, class K = string, class HashFunc1 = BKDRHash, class HashFunc2 = APHash, class HashFunc3 = DJBHash>
class myBloomFilter
{
public:void set(const K& key){size_t hash1 = HashFunc1()(key) % N;size_t hash2 = HashFunc2()(key) % N;size_t hash3 = HashFunc3()(key) % N;_bs.set(hash1);_bs.set(hash2);_bs.set(hash3);}// 一般不支持刪除，刪除一個值可能會影響其他值// 非要支持刪除，也是可以的，用多個位標記一個值，存引用計數// 但是這樣話，空間消耗的就變大了void reset(const K& key);bool test(const K& key){//判斷不存在是準確的size_t hash1 = HashFunc1()(key) % N;if (_bs.test(hash1) == false)return false;size_t hash2 = HashFunc2()(key) % N;if (_bs.test(hash2) == false)return false;size_t hash3 = HashFunc3()(key) % N;if (_bs.test(hash3) == false)return false;return true;//有可能誤判}private:myBitSet<N> _bs;
};2.5 布隆過濾器的優點和缺陷
布隆過濾器優點
1. 增加和查詢元素的時間復雜度為:O(K), (K為哈希函數的個數，一般比較小)，與數據量大小無關
2. 哈希函數相互之間沒有關系，方便硬件并行運算
3. 布隆過濾器不需要存儲元素本身，在某些對保密要求比較嚴格的場合有很大優勢
4. 在能夠承受一定的誤判時，布隆過濾器比其他數據結構有這很大的空間優勢
5. 數據量很大時，布隆過濾器可以表示全集，其他數據結構不能
6. 使用同一組散列函數的布隆過濾器可以進行交、并、差運算
布隆過濾器缺陷
1. 有誤判率，即存在假陽性(False Position)，即不能準確判斷元素是否在集合中(補救方法：再建立一個白名單，存儲可能會誤判的數據)
2. 不能獲取元素本身
3. 一般情況下不能從布隆過濾器中刪除元素
4. 如果采用計數方式刪除，可能會存在計數回繞問題
2.6 布隆過濾器的應用（面試題）
布隆過濾器使用場景：可以接受誤判的場景
1. 給兩個文件，分別有100億個query，我們只有1G內存，如何找到兩個文件交集？分別給出精確算法和近似算法。
query 是字符串，假設平均1個query是50byte，1G 約等于10億byte，100億個query就是5000億byte ，約等于 500G，內存根本存不下。
500G的文件存放不下，可以將它們拆分成多個小文件，例如500個小文件a0~a499，每個文件大小就是1G。讀取第一個文件的每個query，使用hash函數將query映射到500個文件中（計算 i = Hash(query) % 500），i 是幾，query就進入第幾個小文件。
兩個文件中相同的query分別進入了編號相同的小文件 ai 和 bi。
兩個大文件對應的編號相同的小文件ai 和 bi求交集，可以分別插入到一個setA和一個setB中，快速找到交集。
但是這樣也可能有其他問題，例如某個文件可能太大，原因：
- 小文件中大多數都是某一個query，重復過多。
- 小文件有很多不同的query。
如果是情況1，文件很大有很多重復，后面重復播入都失敗，可以插入到set，set可以去重。如果是情況2，不斷插入set以后，內存不足，會拋異常，需要換一個哈希函數進行二次切分，再找交集。
近似算法（布隆過濾器）
1. 創建布隆過濾器：由于1G內存大約可以表示10億字節，即約80億bit，我們可以創建一個布隆過濾器，使用足夠多的哈希函數（例如4到6個），以保持較低的誤報率。2. 插入第一個文件的query：遍歷第一個文件中的每個query，對每個query應用哈希函數，并將對應位設置為1。
3. 查詢第二個文件的query：遍歷第二個文件中的每個query，同樣應用哈希函數。如果布隆過濾器中的所有對應位都是1，則認為該query可能出現在第一個文件中。
4. 輸出可能交集：將所有可能出現在交集中的query輸出到新文件中。
5. 誤報處理：由于布隆過濾器的性質，輸出文件中可能包含一些誤報，即實際上并不在第一個文件中的query。可以通過調整布隆過濾器的參數來減少誤報率。
精確算法（哈希分割）
1文件分割：對兩個文件的query進行哈希處理，然后使用除留余數法（%5000）將query分布到5000個不同的子文件中。每個子文件的大小大約為100M，這樣每個文件的總大小就是5000 * 100M = 500G，符合原始數據的大小。2.讀取和比較：對于第二個文件中的每個query，同樣進行哈希處理，然后將query放入對應的子文件中。接著，對于每個子文件，將其內容讀取到內存中的unordered_map中，然后查找第一個文件中的對應子文件，看是否有相同的query。
3.輸出交集：如果在一個子文件中找到了匹配的query，那么這個query就屬于兩個文件的交集。將這些query輸出到新文件中。
4.內存使用：由于每個子文件是獨立處理的，所以每次只需要將一個子文件的內容讀取到內存中，這樣內存的使用就被限制在了100M左右，符合1G內存的限制。
精確算法的關鍵在于將大文件分割成多個小文件，然后逐個處理，這樣可以避免一次性將所有數據加載到內存中。這種方法雖然準確，但是處理時間可能會比近似算法長，因為需要多次讀寫磁盤。
2. 給一個超過100G大小的log file, log中存著IP地址, 設計算法找到出現次數最多的IP地址？
與上一題同理，i= Hash(ip) % 100，這個ip就進入Ai小文件。相同的ip一定進入了同一個小文件，我們對小文件用map統計出ip次數就是準確的。
的使用)
|PWM輸出)
)
