目錄

一、位圖

1、位圖概念

2、位圖實(shí)現(xiàn)

2.1、位圖結(jié)構(gòu)

2.2、比特位置1

2.3、比特位置0

2.4、檢測(cè)位圖中比特位

3、位圖例題

3.1、找到只出現(xiàn)一次的整數(shù)

3.2、找到兩個(gè)文件交集

3.3、找到出現(xiàn)次數(shù)不超過2次的所有整數(shù)

二、布隆過濾器

1、布隆過濾器提出

2、布隆過濾器概念

3、布隆過濾器實(shí)現(xiàn)

3.1、布隆過濾器的插入

3.2、布隆過濾器的查找

3.3、布隆過濾器刪除

4、布隆過濾器例題

4.1、找到兩個(gè)存貯query的文件的交集

4.2、哈希切割

---

一、位圖

1、位圖概念

?所謂位圖，就是用每一個(gè)比特位來存放某種狀態(tài)，適用于海量數(shù)據(jù)，數(shù)據(jù)無重復(fù)的場(chǎng)景。通常是用來判斷某個(gè)數(shù)據(jù)存不存在的。

位圖的優(yōu)點(diǎn)：

• 速度快
• 節(jié)省空間

位圖的缺點(diǎn)：

• 只能映射整型 ，其他類型如：浮點(diǎn)數(shù)、string等等不能存儲(chǔ)映射。

2、位圖實(shí)現(xiàn)

2.1、位圖結(jié)構(gòu)

位圖類的結(jié)構(gòu)如下：

template<size_t N>
class bitset
{
public:bitset(){_bits.resize(N / 8 + 1, 0);}//將某個(gè)比特位置1void set(size_t x){}//將某個(gè)比特位置0void reset(size_t x){}//檢查位圖中某個(gè)比特位是否為1bool test(size_t x){}private:vector<char> _bits;
};

2.2、比特位置1

實(shí)現(xiàn)代碼：

	void set(size_t x){size_t i = x / 8;size_t j = x % 8;_bits[i] |= (1 << j);}

?用除法計(jì)算 x 映射的位在數(shù)組的第 i 個(gè) char 類型內(nèi)。?用取模計(jì)算 x 映射的位在第 i 個(gè) char 類型的第 j 個(gè)比特位。然后用按位或運(yùn)算把指定比特位置1。

?需要注意的是在進(jìn)行按位或運(yùn)算時(shí)，使用的是 1 左移 j 位，而不是右移。這是因?yàn)樵谖覀內(nèi)祟惖闹饔^認(rèn)識(shí)上，數(shù)位的排列是下面這樣的：

?但實(shí)際上，在計(jì)算機(jī)的虛擬層儲(chǔ)存邏輯上，數(shù)位的保存是這樣的：

?我們所說的左移與右移，并不是向左移動(dòng)或者向右移動(dòng)，而是向高位移動(dòng)與向低位移動(dòng)。因此為了找到目標(biāo)位置，需要使用左移，而不是右移。

2.3、比特位置0

實(shí)現(xiàn)代碼：

	void reset(){size_t i = x / 8;size_t j = x % 8;_bits[i] &= ~(1 << j);}

?用除法計(jì)算 x 映射的位在數(shù)組的第 i 個(gè) char 類型內(nèi)。?用取模計(jì)算 x 映射的位在第 i 個(gè) char 類型的第 j 個(gè)比特位。然后用按位非與運(yùn)算把指定比特位置1。

2.4、檢測(cè)位圖中比特位

實(shí)現(xiàn)代碼：

	bool test(size_t x){size_t i = x / 8;size_t j = x % 8;return _bits[i] & (1 << j);}

3、位圖例題

3.1、找到只出現(xiàn)一次的整數(shù)

設(shè)置狀態(tài)：出現(xiàn) 0 次，狀態(tài)是 00 。出現(xiàn) 1 次，狀態(tài)是 01 。出現(xiàn) 2 次及以上，狀態(tài)是 10 。

template<size_t N>
class twobitset
{
public:void set(size_t x){// 00->01if (_bs1.test(x) == false&& _bs2.test(x) == false){_bs2.set(x);}// 01->10else if (_bs1.test(x) == false&& _bs2.test(x) == true){_bs1.set(x);_bs2.reset(x);}//10}void Print(){for (size_t i = 0; i < N; ++i){if (_bs2.test(i)){cout << i << endl;}}}
public:bitset<N> _bs1;bitset<N> _bs2;
};

測(cè)試結(jié)果如下：?

3.2、找到兩個(gè)文件交集

?方法一：把其中一個(gè)文件的值讀取到位圖中，再讀取另一個(gè)文件，判斷在不在上面的位圖中，在就是交集，取出該值，并把對(duì)應(yīng)位圖置0。

?方法二：創(chuàng)建兩個(gè)位圖，讀取文件1的數(shù)據(jù)映射到位圖1，讀取文件2的數(shù)據(jù)映射到位圖2。然后讓位圖1與位圖2按位與。最終結(jié)果是交集。

3.3、找到出現(xiàn)次數(shù)不超過2次的所有整數(shù)

?設(shè)置狀態(tài)：出現(xiàn) 0 次，狀態(tài)是 00 。出現(xiàn) 1 次，狀態(tài)是 01 。出現(xiàn) 2 次，狀態(tài)是 10 。出現(xiàn) 3 次及以上，狀態(tài)是 11 。

實(shí)現(xiàn)代碼與 3.1 中類似。

二、布隆過濾器

1、布隆過濾器提出

?我們?cè)谑褂眯侣効蛻舳丝葱侣剷r(shí)，它會(huì)給我們不停地推薦新的內(nèi)容，它每次推薦時(shí)要去重，去掉那些已經(jīng)看過的內(nèi)容。問題來了，新聞客戶端推薦系統(tǒng)如何實(shí)現(xiàn)推送去重的？ 用服務(wù)器記錄了用戶看過的所有歷史記錄，當(dāng)推薦系統(tǒng)推薦新聞時(shí)會(huì)從每個(gè)用戶的歷史記錄里進(jìn)行篩選，過濾掉那些已經(jīng)存在的記錄。 如何快速查找呢？

1. ?用哈希表存儲(chǔ)用戶記錄，缺點(diǎn)：浪費(fèi)空間。
2. ?用位圖存儲(chǔ)用戶記錄，缺點(diǎn)：位圖一般只能處理整形，如果內(nèi)容編號(hào)是字符串，就無法處理了。
3. ?將哈希與位圖結(jié)合，即布隆過濾器。

2、布隆過濾器概念

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

?布隆過濾器可以降低沖突的概率。一個(gè)值映射到一個(gè)位置，容易誤判，映射到多個(gè)位置，就可以降低誤判率。

布隆過濾器的優(yōu)點(diǎn)：

• 增加和查詢?cè)氐臅r(shí)間復(fù)雜度為:O(K), (K為哈希函數(shù)的個(gè)數(shù)，一般比較小)，與數(shù)據(jù)量大小無關(guān)。
• 哈希函數(shù)相互之間沒有關(guān)系，方便硬件并行運(yùn)算。
• 布隆過濾器不需要存儲(chǔ)元素本身，在某些對(duì)保密要求比較嚴(yán)格的場(chǎng)合有很大優(yōu)勢(shì)。
• 在能夠承受一定的誤判時(shí)，布隆過濾器比其他數(shù)據(jù)結(jié)構(gòu)有這很大的空間優(yōu)勢(shì)。
• 數(shù)據(jù)量很大時(shí)，布隆過濾器可以表示全集，其他數(shù)據(jù)結(jié)構(gòu)不能。
• 使用同一組散列函數(shù)的布隆過濾器可以進(jìn)行交、并、差運(yùn)算。

?布隆過濾器的缺點(diǎn)：

• 有誤判率，即存在假陽性(False Position)，即不能準(zhǔn)確判斷元素是否在集合中(補(bǔ)救方法：再建立一個(gè)白名單，存儲(chǔ)可能會(huì)誤判的數(shù)據(jù))。
• 不能獲取元素本身。
• 一般情況下不能從布隆過濾器中刪除元素。
• 如果采用計(jì)數(shù)方式刪除，可能會(huì)存在計(jì)數(shù)回繞問題。

3、布隆過濾器實(shí)現(xiàn)

3.1、布隆過濾器的插入

?向布隆過濾器中插入："baidu"：

?向布隆過濾器中插入："tencent"：?

?

?實(shí)現(xiàn)代碼：

struct BKDRHash
{size_t operator()(const string& s){size_t hash = 0;for (auto ch : s){hash += ch;hash *= 31;}return hash;}
};struct DJBHash
{size_t operator()(const string& s){size_t hash = 5381;for (auto ch : s){hash += (hash << 5) + ch;}return hash;}
};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;}
};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);}
private:static const size_t _X = 4; // 布隆過濾器的長(zhǎng)度與數(shù)據(jù)數(shù)量的倍數(shù)關(guān)系bitset<N*_X> _bs;  //這樣可以有效的減少不同數(shù)據(jù)間的沖突
};

3.2、布隆過濾器的查找

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

實(shí)現(xiàn)代碼：

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;//依然存在誤判，有可能把不在的判斷成在
}

?需要注意的是，即使使用了三個(gè)哈希函數(shù)進(jìn)行判斷，仍然存在誤判的可能性。如果判斷該數(shù)據(jù)不存在，則該數(shù)據(jù)一定不存在。如果判斷該數(shù)據(jù)存在，則該數(shù)據(jù)有一定的可能性其實(shí)不存在。

?因此，布隆過濾器只能運(yùn)用于能夠容忍誤判的場(chǎng)景，比如視頻推送等等。而對(duì)于一些不容忍誤判的場(chǎng)景下，布隆過濾器也有相應(yīng)的解決方法：如果判斷出數(shù)據(jù)存在，就到數(shù)據(jù)庫(kù)中進(jìn)行二次確認(rèn)，依然存在就返回存在，不存在就返回不存在。

?哈希函數(shù)個(gè)數(shù)，代表一個(gè)值映射幾個(gè)位，哈希函數(shù)越多，誤判率越低，但是哈希函數(shù)越多，平均占的空間就越大。

3.3、布隆過濾器刪除

布隆過濾器不能直接支持刪除工作，因?yàn)樵趧h除一個(gè)元素時(shí)，可能會(huì)影響其他元素。

? 一種支持刪除的方法：將布隆過濾器中的每個(gè)比特位擴(kuò)展成一個(gè)小的計(jì)數(shù)器，插入元素時(shí)給k個(gè)計(jì)數(shù)器(k個(gè)哈希函數(shù)計(jì)算出的哈希地址)加一，刪除元素時(shí)，給k個(gè)計(jì)數(shù)器減一，通過多占用幾倍存儲(chǔ)空間的代價(jià)來增加刪除操作。

缺陷：

1. 無法確認(rèn)元素是否真正在布隆過濾器中。
2. 存在計(jì)數(shù)回繞。

4、布隆過濾器例題

4.1、找到兩個(gè)存貯query的文件的交集

使用哈希切分，把一個(gè)大文件分割成多個(gè)小文件，再讓小文件之間取交集：

?使用這種方法，因?yàn)椴皇瞧骄蟹?#xff0c;可能會(huì)出現(xiàn)沖突多，某一個(gè)Ai、Bi小文件過大的問題。出現(xiàn)這種問題無非兩種情況：

1. 單個(gè)文件中，有某個(gè)大量重復(fù)的query。
2. 單個(gè)文件中，有大量不同的query。

可以直接使用一個(gè)unordered_set/set，依次讀取文件query，插入set中：

1. 如果讀取了整個(gè)小文件的query，都可以成功插入set，說明是情況一。
2. 如果讀取了整個(gè)小文件的query，插入過程中出現(xiàn)拋異常，說明是情況二。換成其他哈希函數(shù)，再次分割，再求交集。

說明：set插入key，如果已經(jīng)有了，返回false。如果內(nèi)存用完了就會(huì)拋bad_alloc異常，剩下的都會(huì)成功。

4.2、哈希切割

?給一個(gè)超過100G大小的log file，log中存著IP地址，設(shè)計(jì)算法找到出現(xiàn)次數(shù)最多的IP地址。

依然使用哈希切割的方法：

?依次處理每一個(gè)小文件，使用unordered_map 或 map 統(tǒng)計(jì)ip出現(xiàn)的次數(shù)。

1. ?如果統(tǒng)計(jì)過程中，沒有拋異常則正常統(tǒng)計(jì)。統(tǒng)計(jì)完一個(gè)小文件，記錄最多的那一個(gè)。clear內(nèi)存，再統(tǒng)計(jì)下一個(gè)小文件。
2. ?如果統(tǒng)計(jì)過程中，出現(xiàn)拋異?，F(xiàn)象，說明單個(gè)文件過大，沖突太多。換成其他哈希函數(shù)，再次分割。

?建立一個(gè)k個(gè)數(shù)據(jù)的小堆，每統(tǒng)計(jì)一次，就插入小堆，轉(zhuǎn)換成topK問題，最終可以解決。