一、布隆過濾器概念

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

位圖的優(yōu)點(diǎn)是節(jié)省空間，快，缺點(diǎn)是要求范圍相對集中，如果范圍分散，空間消耗上升，同時只能針對整型，字符串通過哈希轉(zhuǎn)化成整型，再去映射，對于整型沒有沖突，因為整型是有限的，映射唯一的位置，但是對于字符串來說，是無限的，會發(fā)生沖突，會發(fā)生誤判：此時的情況的是不在是正確的，在是不正確的，因為可能不來是不在的，但是位置跟別人發(fā)生沖突，發(fā)生誤判

此時布隆過濾器就登場了，可以降低誤判率：讓一個值映射多個位置，但是并不是消除誤判

可能還是會出現(xiàn)誤判：

雖然布隆過濾器還是會出現(xiàn)誤判，因為這個數(shù)據(jù)的比特位被其他數(shù)據(jù)所占，但是判斷一個數(shù)據(jù)不存在是準(zhǔn)確，不存在就是0！

布隆過濾器改進(jìn)：映射多個位置，降低誤判率（位置越多，消耗也越多）

如果布隆過濾器長度比較小，比特位很快會被占為1，誤判率自然會上升，所以布隆過濾器的長度會影響誤判率，理論上來說，如果一個值映射的位置越多，則誤判的概率越小，但是并不是位置越多越好，空間也會消耗：大佬們自然也能夠想得到，所以有公式：

我們可以來估算一下，假設(shè)用 3 個哈希函數(shù)，即K=3，ln2 的值我們?nèi)?0.7，那么 m 和 n 的關(guān)系大概是 m = n×k/ln2=4.2n ，也就是過濾器長度應(yīng)該是插入元素個數(shù)的 4 -5倍

二、布隆過濾器應(yīng)用

不需要一定準(zhǔn)確的場景。比如游戲注冊時候的昵稱的判重：如果不在那就是不在，沒被使用，在的話可能會被誤判。

提高查找效率：客戶端中查找一個用戶的ID與服務(wù)器中的是否相同，在增加一層布隆過濾器提高查找效率：

三、布隆過濾器實現(xiàn)

布隆過濾器的插入元素可能是字符串，也可能是其他類型，只要提供對應(yīng)的哈希函數(shù)將該類型的數(shù)據(jù)轉(zhuǎn)換成整型就可以了。

一般情況下布隆過濾器都是用來處理字符串的，所以布隆過濾器可以實現(xiàn)為一個模板類，將模板參數(shù) T 的缺省類型設(shè)置為 string：

template <size_t N,size_t X = 5,class K=string,
		class HashFunc1 = BKDRHash,
		class HashFunc2 = APHash,
		class HashFunc3 = DJBHash>
class BloomFilter
	{
    public:
    private:
		bitset<N * X> _bs;
	};

這里布隆過濾器提供三個哈希函數(shù)，由于布隆過濾器一般處理的是字符串類型的數(shù)據(jù)，所以我們默認(rèn)提供幾個將字符串轉(zhuǎn)換成整型的哈希函數(shù)：選取綜合評分最高的 BKDRHash、APHash 和 DJBHash這三種哈希算法：

   struct BKDRHash
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			for (auto ch : key)
			{
				hash *= 131;
				hash += ch;
			}
			return hash;
		}
	};
	struct APHash
	{
		size_t operator()(const string& key)
		{
			size_t hash = 0;
			int i = 0;
			for (auto ch : key)
			{
				if ((i & 1) == 0)
				{
					hash ^= ((hash << 7) ^ (ch) ^ (hash >> 3));
				}
				else
				{
					hash ^= (~((hash << 11) ^ (ch) ^ (hash >> 5)));
				}
				++i;
			}
			return hash;
		}
	};
	struct DJBHash
	{
		size_t operator()(const string& key)
		{
			size_t hash = 5318;
			for (auto ch : key)
			{
				hash += (hash << 5) + ch;
			}
			return hash;
		}
	};

1.插入

布隆過濾器復(fù)用bitset的 set 接口用于插入元素，插入元素時，我們通過上面的三個哈希函數(shù)分別計算出該元素對應(yīng)的三個比特位，然后在位圖中設(shè)置為1即可：

        void set(const K& key)
		{
			size_t hash1 = HashFunc1()(key) % (N * X);
			size_t hash2 = HashFunc2()(key) % (N * X);
			size_t hash3 = HashFunc3()(key) % (N * X);
			_bs.set(hash1);
			_bs.set(hash2);
			_bs.set(hash3);
			_bs.set(hash4);
		}

2.查找

通過三個哈希函數(shù)分別算出對應(yīng)元素的三個哈希地址，得到對應(yīng)的比特位，然后去判斷這三個比特位是否都被設(shè)置成了1

如果出現(xiàn)一個比特位未被設(shè)置成1說明該元素一定不存在，也就是如果一個比特位為0就是false；而如果三個比特位全部都被設(shè)置，則return true表示該元素已經(jīng)存在（注：可能會出現(xiàn)誤判）

        bool test(const K& key)
		{
			size_t hash1 = HashFunc1()(key) % (N * X);
			if (!_bs.test(hash1))
			{
				return false;
			}
			size_t hash2 = HashFunc2()(key) % (N * X);
			if (!_bs.test(hash2))
			{
				return false;
			}
			size_t hash3 = HashFunc3()(key) % (N * X);
			if (!_bs.test(hash3))
			{
				return false;
			}
			return true;
		}

3.刪除

布隆過濾器一般沒有刪除，因為布隆過濾器判斷一個元素是會存在誤判，此時無法保證要刪除的元素在布隆過濾器中，如果此時將位圖中對應(yīng)的比特位清0，就會影響到其他元素了：

這時候我們只需要在每個比特位加一個計數(shù)器，當(dāng)存在插入操作時，在計數(shù)器里面進(jìn)行 ++，刪除后對該位置進(jìn)行 -- 即可

但是布隆過濾器的本來目的就是為了提高效率和節(jié)省空間，在每個比特位增加額外的計數(shù)器，空間消耗那就更多了

四、布隆過濾器優(yōu)缺

優(yōu)

\1. 增加和查詢元素的時間復(fù)雜度為:O(K), (K為哈希函數(shù)的個數(shù)，一般比較小)，與數(shù)據(jù)量大小無關(guān)

\2. 哈希函數(shù)相互之間沒有關(guān)系，方便硬件并行運(yùn)算

\3. 布隆過濾器不需要存儲元素本身，在某些對保密要求比較嚴(yán)格的場合有很大優(yōu)勢

\4. 在能夠承受一定的誤判時，布隆過濾器比其他數(shù)據(jù)結(jié)構(gòu)有這很大的空間優(yōu)勢

\5. 數(shù)據(jù)量很大時，布隆過濾器可以表示全集，其他數(shù)據(jù)結(jié)構(gòu)不能

\6. 使用同一組散列函數(shù)的布隆過濾器可以進(jìn)行交、并、差運(yùn)算

缺

\1. 有誤判率，不能準(zhǔn)確判斷元素是否在集合中(補(bǔ)救方法：再建立一個白名單，存儲可能會誤判的數(shù)據(jù))

\2. 不能獲取元素本身

\3. 一般情況下不能從布隆過濾器中刪除元素

五、結(jié)語

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

近似算法：利用布隆過濾器，交集的就一定會進(jìn)去，但是可能會存在誤判：不同的也會進(jìn)去，這是近似

精準(zhǔn)算法：query一般是查詢指令，比如可能是網(wǎng)絡(luò)請求，或者是一個數(shù)據(jù)庫sql語句

100億個query,假設(shè)平均每個query是50byte，則100億個query那就是合計500GB

相同的query，是一定進(jìn)入相同編號的小文件，再對這些文件放進(jìn)內(nèi)存的兩個set中，編號相同的Ai和Bi小文件找交集即可

到此這篇關(guān)于C++ BloomFilter布隆過濾器應(yīng)用及概念詳解的文章就介紹到這了,更多相關(guān)C++ BloomFilter內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論