一、位圖

1.1 位圖概念

1. 面試題
   給40億個(gè)不重復(fù)的無(wú)符號(hào)整數(shù)，沒(méi)排過(guò)序。給一個(gè)無(wú)符號(hào)整數(shù)，如何快速判斷一個(gè)數(shù)是否在這40億個(gè)數(shù)中。【騰訊】

2. 遍歷查找：內(nèi)存中無(wú)法存放40億個(gè)整數(shù)（約占內(nèi)存15-16G）；時(shí)間復(fù)雜度O(N)；

3. 先排序O(NlogN)，再利用二分查找O(logN)：數(shù)據(jù)太大，只能存放在磁盤(pán)文件中，數(shù)據(jù)讀取速度慢。

4. 位圖
   數(shù)據(jù)是否在給定的集合中，結(jié)果是在或者不在，剛好是兩種狀態(tài)，那么可以使用一個(gè)二進(jìn)制比特位來(lái)代表數(shù)據(jù)是否存在的信息，如果二進(jìn)制比特位為1，代表存在，為0代表不存在。利用位圖解決該問(wèn)題，無(wú)符號(hào)整數(shù)的取值范圍是0~2^32，一個(gè)位代表一個(gè)整數(shù)，只需要2^32bit = 512MB內(nèi)存空間即可。
   

5. 位圖概念
   所謂位圖，就是用每一位來(lái)存放某種狀態(tài)，適用于海量數(shù)據(jù)，數(shù)據(jù)無(wú)重復(fù)的場(chǎng)景。通常是用來(lái)判斷某個(gè)數(shù)據(jù)存不存在的。數(shù)據(jù)的鍵值通過(guò)直接定址法與位圖中的位建立聯(lián)系。

提示：位圖在STL中的實(shí)現(xiàn)為bitset，在頭文件<bitse>中聲明

---

1.2 位圖的實(shí)現(xiàn)

關(guān)于位運(yùn)算的相關(guān)知識(shí)請(qǐng)閱讀：

【C語(yǔ)言進(jìn)階】位運(yùn)算 {位運(yùn)算符；位運(yùn)算符的優(yōu)先級(jí)；位運(yùn)算的應(yīng)用 ：關(guān)閉位，判斷位，打開(kāi)位，轉(zhuǎn)置位；位域}

#include <vector>                
#include <math.h>     
using namespace std;    namespace zty{         template <size_t N>    class bitset{        vector<char> _bt;    size_t _count;    public:     bitset()                    :_bt(ceil((double)N/8)), //ceil向上取整   _count(0)    {}    //打開(kāi)位                     void set(size_t x){    if(x>N) return;    size_t i = x/8; //計(jì)算在第幾個(gè)char類(lèi)型    size_t j = x%8; //計(jì)算在char類(lèi)型的第幾位   _bt[i] |= (1<<j);    ++_count;    }  //關(guān)閉位void reset(size_t x){if(x>N) return;size_t i = x/8;size_t j = x%8;_bt[i] &= ~(1<<j);--_count;}//判斷位        bool test(size_t x){if(x>N) return false;size_t i = x/8;size_t j = x%8;return _bt[i] & (1<<j);}//返回bitset中被置為1的比特位數(shù)size_t count(){return _count;}//返回bitset中的比特位總數(shù)size_t size(){return N;}};
}

---

1.3 位圖應(yīng)用

1. 快速查找某個(gè)數(shù)據(jù)是否在一個(gè)集合中
2. 排序 + 去重
3. 求兩個(gè)集合的交集、并集等
4. 操作系統(tǒng)中磁盤(pán)塊標(biāo)記

相關(guān)面試題

1. 給定100億個(gè)整數(shù)，設(shè)計(jì)算法找到只出現(xiàn)一次的整數(shù)？

思路：

• 每個(gè)整數(shù)有3種狀態(tài)：出現(xiàn)0次；出現(xiàn)1次；出現(xiàn)2次及以上
• 需要兩個(gè)位圖解決

  template <size_t N>class twobitset1{bitset<N> bs1;bitset<N> bs2;public:void set(size_t x){if(!bs1.test(x) && !bs2.test(x)) //出現(xiàn)0次(00)-->出現(xiàn)1次(01){bs2.set(x);}else if(!bs1.test(x) && bs2.test(x)) //出現(xiàn)1次(01)-->出現(xiàn)2次(10){bs1.set(x);bs2.reset(x);}}void print_once_num(){for(size_t i = 0; i<N; ++i){//找到只出現(xiàn)一次的整數(shù)(01)if(!bs1.test(i) && bs2.test(i)){cout << i << " ";}}cout << endl;}};void test1(){int arr[] = {6,99,1,1,2,4,3,5,6,7,1,3,2,4,7,9,8,5,4,3,21,8,9,4,2,3,1,4,3,57};zty::twobitset1<100> tbs;for(int e : arr){tbs.set(e);}tbs.print_once_num();
}

2. 給兩個(gè)文件，分別有100億個(gè)整數(shù)，我們只有1G內(nèi)存，如何找到兩個(gè)文件交集？

   思路：每個(gè)文件對(duì)應(yīng)一個(gè)位圖，兩位圖的對(duì)應(yīng)位都為1就是交集。

     template <size_t N>class twobitset2{bitset<N> bs1; //文件1對(duì)應(yīng)的位圖bitset<N> bs2; //文件2對(duì)應(yīng)的位圖public:void setbs1(size_t x){bs1.set(x);} void setbs2(size_t x){bs2.set(x);} void print_intersection_set(){for(size_t i = 0; i<N; ++i){//找出兩個(gè)文件中數(shù)據(jù)的交集(11)if(bs1.test(i) && bs2.test(i)){cout << i << " ";}}cout << endl;}};void test2(){int file1[] = {6,99,1,1,2,4,3,5,6,7,1,3,2,4,7,9,8,5,4,3,21,8,9,4,2,3,1,4,3,57};int file2[] = {5,3,1,5,12,23,45,6,78,9,12,13,15,57,3,4,9};zty::twobitset2<100> tbs;for(int e : file1){tbs.setbs1(e);}for(int e : file2){tbs.setbs2(e);}tbs.print_intersection_set();
   }
   

3. 位圖應(yīng)用變形：1個(gè)文件有100億個(gè)int，1G內(nèi)存，設(shè)計(jì)算法找到出現(xiàn)次數(shù)不超過(guò)2次的所有整數(shù)

思路：

• 每個(gè)整數(shù)有4種狀態(tài)：出現(xiàn)0次；出現(xiàn)1次；出現(xiàn)2次；出現(xiàn)3次及以上
• 需要兩個(gè)位圖解決

  template <size_t N>class twobitset3{bitset<N> bs1;bitset<N> bs2;public:void set(size_t x){if(!bs1.test(x) && !bs2.test(x)) //出現(xiàn)0次(00)-->出現(xiàn)1次(01){bs2.set(x);}else if(!bs1.test(x) && bs2.test(x)) //出現(xiàn)1次(01)-->出現(xiàn)2次(10){bs1.set(x);bs2.reset(x);}else if(bs1.test(x) && !bs2.test(x)) //出現(xiàn)2次(10)-->出現(xiàn)3次(11){bs2.set(x);}}void print_atmost_twice(){//找到出現(xiàn)次數(shù)不超過(guò)2次的所有整數(shù)for(size_t i = 0; i<N; ++i){if(!bs1.test(i) && bs2.test(i)) //出現(xiàn)1次(01){cout << i << " ";}else if(bs1.test(i) && !bs2.test(i)) //出現(xiàn)2次(10){cout << i << " ";}}cout << endl;}};void test3(){int arr[] = {1,1,1,2,2,2,3,4,4,4,4,4,5,5,6};zty::twobitset3<100> tbs;for(int e : arr){tbs.set(e);}tbs.print_atmost_twice();
}

---

二、布隆過(guò)濾器

2.1 布隆過(guò)濾器概念

• 位圖一般只能解決整形數(shù)據(jù)在或不在的問(wèn)題，如果數(shù)據(jù)是字符串或者其他類(lèi)型，可以先將其轉(zhuǎn)換為無(wú)符號(hào)整型再插入位圖。但這樣的處理方式存在哈希沖突的概率比較大。

• 哈希表需要將數(shù)據(jù)全部加載到內(nèi)存中還要開(kāi)辟額外的指針(鏈表指針)和數(shù)組空間(負(fù)載因子)，面對(duì)海量數(shù)據(jù)會(huì)占用大量的內(nèi)存，甚至可能出現(xiàn)內(nèi)存空間不夠用的情況。

• 于是誕生了新的容器——布隆過(guò)濾器。布隆過(guò)濾器是由布隆（Burton Howard Bloom）在1970年提出的 一種緊湊型的、比較巧妙的概率型數(shù)據(jù)結(jié)構(gòu)，特點(diǎn)是高效地插入和查詢，可以用來(lái)告訴你 “某樣?xùn)|西一定不存在或者可能存在”，它是用多個(gè)哈希函數(shù)，將一個(gè)數(shù)據(jù)映射到位圖結(jié)構(gòu)中的多個(gè)位上，以此來(lái)降低哈希沖突的概率。此種方式不僅可以提升查詢效率，也可以節(jié)省大量的內(nèi)存空間。

• 布隆過(guò)濾器雖然可以降低哈希沖突的概率但不可完全避免。因此布隆過(guò)濾器可能發(fā)生誤判：**不存在一定是準(zhǔn)確的，但存在則可能發(fā)生誤判。**誤判率可以通過(guò)增加哈希函數(shù)(映射位數(shù))來(lái)進(jìn)一步降低。理論而言，一個(gè)值映射的位越多，誤判率越低，但同時(shí)空間消耗也就越多

提示：STL沒(méi)有實(shí)現(xiàn)布隆過(guò)濾器，如有需要請(qǐng)自行實(shí)現(xiàn)。

---

2.2 布隆過(guò)濾器的結(jié)構(gòu)

布隆過(guò)濾器的結(jié)構(gòu)實(shí)際就是一個(gè)位圖：

2.2.1 插入

如果我們要映射一個(gè)值到布隆過(guò)濾器中，我們需要使用多個(gè)不同的哈希函數(shù)生成**多個(gè)哈希值，**并對(duì)每個(gè)生成的哈希值指向的 bit 位置 1，例如針對(duì)值 “baidu” 和三個(gè)不同的哈希函數(shù)分別生成了哈希值 1、4、7，則上圖轉(zhuǎn)變?yōu)?#xff1a;

2.2.2 查找

• 布隆過(guò)濾器的思想是將一個(gè)元素用多個(gè)哈希函數(shù)映射到一個(gè)位圖中，因此被映射到的位置的比特位一定為1。所以可以按照以下方式進(jìn)行查找：分別計(jì)算每個(gè)哈希值對(duì)應(yīng)的比特位置存儲(chǔ)的是否為零，只要有一個(gè)為零，代表該元素一定不在哈希表中，否則可能在哈希表中。

• 比如：在布隆過(guò)濾器中查找：“tencent”

  

  假設(shè)3個(gè)哈希函數(shù)計(jì)算的哈希值為：3、4、8，雖然"baidu"和"tencent"兩者通過(guò)Hash2計(jì)算的哈希值(4)相同，造成哈希沖突。但Hash1和Hash3的計(jì)算結(jié)果不同，只要三個(gè)哈希值中有一個(gè)位為0就能確定該字符串不存在。

• 再比如：在布隆過(guò)濾器中查找：“alibaba”

假設(shè)3個(gè)哈希函數(shù)計(jì)算的哈希值為：1、4、7，剛好和"baidu"的比特位全部重疊。此時(shí)布隆過(guò)濾器返回該元素存在，但實(shí)際該元素是不存在的，發(fā)生誤判。

• 綜上所述：布隆過(guò)濾器如果說(shuō)某個(gè)元素不存在時(shí)，該元素一定不存在，如果該元素存在時(shí)，該元素可能存在，因?yàn)橛行┕：瘮?shù)存在一定的誤判。

2.2.3 刪除

布隆過(guò)濾器不能直接支持刪除工作，原因有二：

• 在刪除一個(gè)元素時(shí)，如果直接將該元素所對(duì)應(yīng)的二進(jìn)制比特位置0，而該元素恰好與其他元素有重疊的位，就會(huì)導(dǎo)致這些重疊元素也被刪除。

• 不能確定待刪除元素本身是存在于布隆過(guò)濾器的，可能會(huì)導(dǎo)致誤刪。

---

2.3 如何選擇哈希函數(shù)個(gè)數(shù)和布隆過(guò)濾器長(zhǎng)度

很顯然，過(guò)小的布隆過(guò)濾器很快所有的 bit 位均為 1，那么查詢?nèi)魏沃刀紩?huì)返回“可能存在”，起不到過(guò)濾的目的了。布隆過(guò)濾器的長(zhǎng)度會(huì)直接影響誤報(bào)率，布隆過(guò)濾器越長(zhǎng)其誤報(bào)率越小。

另外，哈希函數(shù)的個(gè)數(shù)也需要權(quán)衡，個(gè)數(shù)越多則布隆過(guò)濾器 bit 位置位 1 的速度越快，且布隆過(guò)濾器的效率越低；但是如果太少的話，那我們的誤報(bào)率會(huì)變高。

如何選擇適合業(yè)務(wù)的 k 和 m 值呢，這里直接貼一個(gè)公式：

例如：當(dāng)k為3時(shí)，m≈4.2n，我們向上取整為5。即布隆過(guò)濾器的長(zhǎng)度是插入元素個(gè)數(shù)的5倍。

---

2.4 布隆過(guò)濾器的實(shí)現(xiàn)

  //三種字符串哈希算法struct BKDRHash{size_t operator()(const string& s){// BKDRsize_t value = 0;for (auto ch : s){value += ch;value *= 31;}return value;}};struct APHash{size_t operator()(const 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 DJBHash{size_t operator()(const string& s){size_t hash = 5381;for (auto ch : s){hash += (hash << 5) + ch;}return hash;}};//布隆過(guò)濾器//N是要插入的元素個(gè)數(shù)//布隆過(guò)濾器默認(rèn)處理字符串template <size_t N, class K = string,class Hash1 = BKDRHash,class Hash2 = APHash,class Hash3 = DJBHash>class BloomFilter{std::bitset<N*5> _bs; //當(dāng)哈希函數(shù)的個(gè)數(shù)為3時(shí)，布隆過(guò)濾器的長(zhǎng)度是插入元素個(gè)數(shù)的5倍public:void set(const K& key){//將三個(gè)哈希函數(shù)計(jì)算得到映射位置置1size_t hashi1 = Hash1()(key) % _bs.size(); //_bs.size()-->N*5_bs.set(hashi1);size_t hashi2 = Hash2()(key) % _bs.size();_bs.set(hashi2);size_t hashi3 = Hash3()(key) % _bs.size();_bs.set(hashi3);}bool test(const K& key){//只要三個(gè)哈希函數(shù)計(jì)算得到映射位置中有一個(gè)位為0就返回falsesize_t hashi1 = Hash1()(key) % _bs.size();if(!_bs.test(hashi1)) return false; //準(zhǔn)確的size_t hashi2 = Hash2()(key) % _bs.size();if(!_bs.test(hashi2)) return false; //準(zhǔn)確的size_t hashi3 = Hash3()(key) % _bs.size();if(!_bs.test(hashi3)) return false; //準(zhǔn)確的return true; //可能存在誤判}};

測(cè)試代碼：

//簡(jiǎn)單測(cè)試
void TestBloomFilter1()
{zty::BloomFilter<11> bf;string arr1[] = { "蘋(píng)果", "西瓜", "阿里", "美團(tuán)", "蘋(píng)果", "字節(jié)", "西瓜", "蘋(píng)果", "香蕉", "蘋(píng)果", "騰訊" };for (auto& str : arr1){bf.set(str);}for (auto& str : arr1){cout << bf.test(str) << endl;}cout << endl << endl;string arr2[] = { "蘋(píng)果111", "西瓜", "阿里2222", "美團(tuán)", "蘋(píng)果dadcaddxadx", "字節(jié)", "西瓜sSSSX", "蘋(píng)果", "香蕉", "蘋(píng)果$", "騰訊" };for (auto& str : arr2){cout <<str<<":"<<bf.test(str) << endl;}
}//誤判率測(cè)試
void TestBloomFilter2()
{srand(time(0));const size_t N = 100000;zty::BloomFilter<N> bf;cout << "sizeof BloomFilter: " << sizeof(bf) << endl; 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(1234 + i));}for (auto& str : v1){bf.set(str);}//測(cè)試相似字符串誤判率：std::vector<std::string> v2;for (size_t i = 0; i < N; ++i){std::string url = "http://www.cnblogs.com/-clq/archive/2021/05/31/2528153.html";url += std::to_string(rand() + i);v2.push_back(url);}size_t n2 = 0;for (auto& str : v2){if (bf.test(str)){++n2;}}cout << "相似字符串誤判率:" << (double)n2 / (double)N << endl;//測(cè)試不相似字符串誤判率：std::vector<std::string> v3;for (size_t i = 0; i < N; ++i){string url = "zhihu.com";url += std::to_string(rand()+i);v3.push_back(url);}size_t n3 = 0;for (auto& str : v3){if (bf.test(str)){++n3;}}cout << "不相似字符串誤判率:" << (double)n3 / (double)N << endl;
}

---

2.5 布隆過(guò)濾器的應(yīng)用

提高查找效率：利用布隆過(guò)濾器減少磁盤(pán) IO 或者網(wǎng)絡(luò)請(qǐng)求，因?yàn)橐坏┮粋€(gè)值必定不存在的話，我們可以不用進(jìn)行后續(xù)昂貴的查詢請(qǐng)求。

海量數(shù)據(jù)處理：

給兩個(gè)文件，分別有100億個(gè)query(字符串)，我們只有1G內(nèi)存，如何找到兩個(gè)文件交集？分別給出精確算法和近似算法

• 近似算法：將其中一個(gè)文件中的query插入到布隆過(guò)濾器中，再在布隆過(guò)濾器中遍歷查找另一個(gè)文件的query。如果找到就是交集。近似算法的問(wèn)題有：1.可能存在誤判 2.沒(méi)有進(jìn)行去重

• 精確算法：哈希切分

  

哈希切分：

給一個(gè)超過(guò)100G大小的log file, log中存著IP地址, 設(shè)計(jì)算法找到出現(xiàn)次數(shù)最多的IP地址？如何找到top K的IP？

拓展：一致性哈希

---

2.6 布隆過(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ò)濾器中刪除元素