上一章講了位圖，我們知道了在海量數(shù)據(jù)中查找一個數(shù)是否存在，可以用每一個比特位標識。

但是位圖只能處理整數(shù)，要是字符串或者其它的呢，位圖便無法處理了，這個時候便需要用到布隆過濾器了.

目錄

布隆過濾器提出

布隆過濾器概念

布隆過濾器的實現(xiàn)以及最優(yōu)值

?哈希切分

布隆過濾器提出

我們在看b站視頻時，它會給我們不停地推薦新的內(nèi)容，它每次推薦時要去重，去掉那些已經(jīng)看過的內(nèi)容。問題來了，b站推薦系統(tǒng)如何實現(xiàn)推送去重的？ 用服務器記錄了用戶看過的所有歷史記錄，當b站推薦系統(tǒng)推薦視頻時會從每個用戶的歷史記錄里進行篩選，過濾掉那些已經(jīng)存在的記錄。 如何快速查找呢？
1. 用哈希表存儲用戶記錄，缺點：浪費空間
2. 用位圖存儲用戶記錄，缺點：位圖一般只能處理整形，如果內(nèi)容編號是字符串，就無法處理了。
3. 將哈希與位圖結合，即布隆過濾器

布隆過濾器概念

布隆過濾器（Bloom Filter）是一種概率型的數(shù)據(jù)結構，用于快速判斷一個元素是否存在于一個集合中。它基于位圖（或稱為位數(shù)組）和多個哈希函數(shù)構成。

布隆過濾器的主要目標是在存儲空間相對較小的情況下，實現(xiàn)高效的成員查詢。它通過使用多個哈希函數(shù)將要查詢的元素映射到位圖中的多個位上。當一個元素要插入布隆過濾器時，通過多個哈希函數(shù)計算出多個索引位置，并將對應位設置為1。當判斷一個元素是否存在時，再次通過多個哈希函數(shù)計算出多個索引位置，并檢查對應位是否都為1。如果有任何一個位為0，則可以確定該元素一定不存在于集合中；如果所有位都為1，則表示該元素可能存在于集合中，但有一定的誤判率。

注意，只有判斷一個數(shù)據(jù)存在的時候才會有誤判。

因為如果判斷一個數(shù)據(jù)它存在了，但是它可能和別的數(shù)據(jù)沖突了，即別的數(shù)據(jù)占的這些位恰好是這個數(shù)據(jù)的那些位。這樣就會造成誤判。

我舉個例子可以說明一下：

而判斷一個數(shù)據(jù)不存在這是絕對不可能誤判的，因為不存在說明別的數(shù)據(jù)都還沒有占用這些位，一定沒有和這個數(shù)據(jù)相同的數(shù)據(jù)存在，因為如果存在了，對應的所有位就都是1了，此時便會判它存在了.

這個誤判是不可能去掉的，但是可以降低誤判的概率。比如增加多個哈希函數(shù)。

這樣的話，每個數(shù)據(jù)對應的位就會多了，這樣重合的概率就會更低。

例如之前一個數(shù)據(jù)對應兩個位，現(xiàn)在對應了三個位，是不是重合的概率又降低了呢？

雖然原來我們兩個位沖突了，現(xiàn)在又多了一個位，又多了一個機會，此時便相當于降低了誤判率。

但是也不能盲目的增加哈希函數(shù)，具體會有一個合適的值.

?如果映射函數(shù)的越多，空間消耗就會增多，就失去了原本的優(yōu)勢。

這個會被應用在哪些地方呢？

比如訪問一個網(wǎng)站，會有黑名單用戶，每個用戶訪問的時候，都需要判斷一下是不是黑名單用戶。

我們?nèi)绻看味家?shù)據(jù)庫中查找，那么經(jīng)過網(wǎng)絡傳輸?shù)冗^程會使效率變得非常低下，所以是不被采用的。

這個時候便用到了我們的布隆過濾器，每當有用戶訪問，先查找存在不存在，有兩種情況：

1.存在：如果存在，我們才再次需要去數(shù)據(jù)庫中查找，因為存在會有誤判，萬一人家不是黑名單用戶，你卻誤判成了黑名單，這當然是不合理的，這個時候才去數(shù)據(jù)庫中查找。

2.不存在：不存在那就說明這個人一定不是黑名單用戶了，因為不存在不會有誤判，直接返回即可：

還有一個我們常見的情景，就是在注冊申請一個賬號的時候，比如輸入昵稱的時候，有的后面會立馬顯示“此昵稱已被占用”。這其實就是應用了布隆過濾器。

當你輸入一個名字的時候，如果利用布隆過濾器查找，發(fā)現(xiàn)存在了，會給你提示已經(jīng)存在，但是這個名字一定是存在的嗎？那不一定，畢竟有可能是誤判。

但是你也不會察覺到，占用就占用了唄，然后換一個就行。當然這也對這個公司有好處，報總比不報好，萬一就是已經(jīng)存在的呢，這樣就不好了。

但是不存在的話，就不會報，因為它一定不存在了。這也是前面一直所說的.

布隆過濾器的實現(xiàn)以及最優(yōu)值

由于C++STL庫中并沒有布隆過濾器，所以得靠我們自己手動實現(xiàn)。

首先由于布隆過濾器的數(shù)據(jù)類型不再只是整數(shù)，所以我們要利用模板。

可以定義K為數(shù)據(jù)的類型，那么我們每次需要給位圖開多大空間呢？

總不能一上來開41億，比如就100個數(shù)據(jù)，開這么大就有點浪費了，所以再給出一個非類型模板參數(shù)N，代表數(shù)據(jù)的個數(shù)，然后在成員變量中定義一個_ratio表示倍數(shù)，每次開N*_ratio的空間即可。

可能有同學會有疑問，之前位圖不是說開多少空間取決于數(shù)據(jù)范圍嗎？這個怎么不用？

因為位圖采用的是直接定址法，它這個數(shù)據(jù)是多少，它就會對應在位圖的相應位置，所以數(shù)據(jù)范圍的大小決定了開多少空間。

而布隆過濾器是對每個數(shù)據(jù)采用了哈希映射，而且是多個哈希映射，這樣當然不需要多么大的空間了。比如一個數(shù)據(jù)1，和99999999，采用了哈希映射后，1對應的位圖中是1,2,3，而99999999對應的位圖是1,3,4、這個只是一個假設，目的是理解為什么不用根據(jù)數(shù)據(jù)范圍來開空間。

然后毋庸置疑，就是對應的哈希函數(shù)模板，那么具體定義多少個哈希映射函數(shù)呢？

不僅如此，布隆過濾器(內(nèi)部其實就是一個位圖)的長度也影響了誤判率，那么長度為多少合適呢？

這個有一套數(shù)學理論和實驗證明，這里我們只看一下最終結果和公式：

“很顯然，過小的布隆過濾器很快所有的 bit 位均為 1，那么查詢?nèi)魏沃刀紩祷亍翱赡艽嬖凇?，起不到過濾的目的了。布隆過濾器的長度會直接影響誤報率，布隆過濾器越長其誤報率越小。

另外，哈希函數(shù)的個數(shù)也需要權衡，個數(shù)越多則布隆過濾器 bit 位置位 1 的速度越快，且布隆過濾器的效率越低；但是如果太少的話，那我們的誤報率會變高”

k 為哈希函數(shù)個數(shù)，m 為布隆過濾器長度，n 為插入的元素個數(shù)，p 為誤判率

那么具體該如何選擇k和m的值是最優(yōu)的呢？

有兩個公式：

根據(jù)這兩個公式可以選出最優(yōu)的m和k的值。

然后下面就是布隆過濾器的代碼，代碼不唯一的，具體根據(jù)m和k的值進行調(diào)整。

//N表示準備要映射N個值.
template<size_t N,class K,
class Hash1,class Hash2,class Hash3>
class BloomFilter
{
public:
	void Set(const K& key)
	{
		size_t hash1 = Hash1()(key) % (_ratio * N);
		_bits.set(hash1);
		size_t hash2 = Hash2()(key) % (_ratio * N);
		_bits.set(hash2);
		size_t hash3 = Hash3()(key) % (_ratio * N);
		_bits.set(hash3);
	}
	bool Test(const K& key)
	{
		size_t hash1 = Hash1()(key) % (_ratio * N);
		if (!bits.test(hash1))
			return false;
		size_t hash2 = Hash2()(key) % (_ratio * N);
		if (!bits.test(hash2))
			return false;
		size_t hash3 = Hash3()(key) % (_ratio * N);
		if (!bits.test(hash3))
			return false;
		return true;//可能存在誤判
	}
private:
	const static size_t _ratio = 5;
	bitset<_ratio*N> _bits;
};

這是主體部分的代碼，可以看到以上代碼中用了3個哈希函數(shù)，具體每個哈希算法怎么實現(xiàn)，則由自己進行決定。也可以在網(wǎng)上搜索一些哈希相關的算法。

然后我們定義3個類，每個類中重載()運算符，然后進行哈希算法的實現(xiàn)。最后創(chuàng)建對象時，把這三個類傳入即可。

下面講解兩道布隆過濾器相關的題目：

1、?如何擴展BloomFilter使得它支持刪除元素的操作？

首先我們要知道，布隆過濾器一般情況下是不能被刪除的。大家想一想，為什么？

因為位圖中的某一個位可能是兩個字符串的位，即它們有公共比特位，例如這張圖：

如果我們想刪除百度，即將百度的對應的位全部置為0，b站也會受到影響，?最后只剩下1個位了。

這樣在查找的時候，便也查找不到b站了，所以對其他數(shù)據(jù)也造成影響了。

那么我們能不能強行改造一下呢？

當然是可以的，我們另創(chuàng)建一個位來保存每個位置1的個數(shù)count，若每次刪除，則將count減1。

如果count為0說明此時已經(jīng)沒有數(shù)據(jù)再占用這個位了，便可以置為0了，否則，count--即可.

當然這么做會增加了空間的消耗，會削弱布隆過濾器的優(yōu)勢，與其有這些空間存這個，不如用這些空間來降低一些誤判率呢.

?哈希切分

先來看下面這個問題：

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

以上這張圖已經(jīng)說明了，我們可以將100G數(shù)據(jù)中的每個ip地址由哈希函數(shù)轉(zhuǎn)為整數(shù)，再進行切分到不同的桶中，這樣每個桶中都有對應的ip地址了。

那么我們該如何統(tǒng)計每個桶中的ip地址的個數(shù)呢？

當然是利用map進行統(tǒng)計，如果超過1G了呢？這里也會出現(xiàn)兩種情況：

1.這個桶中不相同的ip很多，由于每次遇到不同的ip值，map都要進行插入，所以map統(tǒng)計不了。

2.這個桶中相同的ip很多，雖然有很多的ip，但是由于很多是相同的，所以直接在key對應的value上加1節(jié)課即可，并不會消耗空間。

直接使用map中的insert將每一個桶的元素插入到map中。

情況一：如果insert插入失敗，說明空間不足，new節(jié)點失敗，拋出異常。解決方法是換個哈希函數(shù)，遞歸再次對這個沖突桶進行切分。

情況二：map可以正常統(tǒng)計。

這樣找到map中value值最高的即可。

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

近似算法：先將一個文件中的數(shù)據(jù)全部set進布隆過濾器中，然后分別用另一個文件的數(shù)據(jù)test比對，可以淘汰一定不是交集的部分。當然淘汰完剩下的那部分數(shù)據(jù)中，也會有非交集的存在。

精確算法：這個可以參考第一個問題的哈希切分方法。

思路是：利用相同的哈希函數(shù)(記住一定相同!)將兩個文件的數(shù)據(jù)進行哈希切分，最后每個文件都會切分出許多小文件。然后我們分別比對下標相同的小文件，找出交集即可。

例如A文件切分出了A0,A1,A2...A999.

B文件切分出了B0,B1,B2....B999.

我們直接A0和B0,A1和B1,...A999和B999進行比較即可，因為兩個文件使用了相同的哈希函數(shù)，所以對于兩個文件相同的數(shù)據(jù)，經(jīng)過切分后，一定會在編號相同的桶中.

然后再利用哈希表或set都可以，先將一個文件全部插入，經(jīng)過去重后，再用另一個文件進行比對，找出交集即可。

?文章來源地址http://www.zghlxwxcb.cn/news/detail-525634.html

到了這里，關于哈希與位圖的結合--布隆過濾器與哈希切分的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！