快捷導(dǎo)航

C++ BloomFilter布隆過(guò)濾器應(yīng)用及概念詳解

更新時(shí)間：2023年03月08日 10:17:19 作者：平凡的人1

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

一、布隆過(guò)濾器概念

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

位圖的優(yōu)點(diǎn)是節(jié)省空間，快，缺點(diǎn)是要求范圍相對(duì)集中，如果范圍分散，空間消耗上升，同時(shí)只能針對(duì)整型，字符串通過(guò)哈希轉(zhuǎn)化成整型，再去映射，對(duì)于整型沒(méi)有沖突，因?yàn)檎褪怯邢薜模成湮ㄒ坏奈恢?，但是?duì)于字符串來(lái)說(shuō)，是無(wú)限的，會(huì)發(fā)生沖突，會(huì)發(fā)生誤判：此時(shí)的情況的是不在是正確的，在是不正確的，因?yàn)榭赡懿粊?lái)是不在的，但是位置跟別人發(fā)生沖突，發(fā)生誤判

此時(shí)布隆過(guò)濾器就登場(chǎng)了，可以降低誤判率：讓一個(gè)值映射多個(gè)位置，但是并不是消除誤判

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

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

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

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

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

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

不需要一定準(zhǔn)確的場(chǎng)景。比如游戲注冊(cè)時(shí)候的昵稱的判重：如果不在那就是不在，沒(méi)被使用，在的話可能會(huì)被誤判。

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

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

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

一般情況下布隆過(guò)濾器都是用來(lái)處理字符串的，所以布隆過(guò)濾器可以實(shí)現(xiàn)為一個(gè)模板類，將模板參數(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;
	};

這里布隆過(guò)濾器提供三個(gè)哈希函數(shù)，由于布隆過(guò)濾器一般處理的是字符串類型的數(shù)據(jù)，所以我們默認(rèn)提供幾個(gè)將字符串轉(zhuǎn)換成整型的哈希函數(shù)：選取綜合評(píng)分最高的 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.插入

布隆過(guò)濾器復(fù)用bitset的 set 接口用于插入元素，插入元素時(shí)，我們通過(guò)上面的三個(gè)哈希函數(shù)分別計(jì)算出該元素對(duì)應(yīng)的三個(gè)比特位，然后在位圖中設(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.查找

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

如果出現(xiàn)一個(gè)比特位未被設(shè)置成1說(shuō)明該元素一定不存在，也就是如果一個(gè)比特位為0就是false；而如果三個(gè)比特位全部都被設(shè)置，則return true表示該元素已經(jīng)存在（注：可能會(huì)出現(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.刪除

布隆過(guò)濾器一般沒(méi)有刪除，因?yàn)椴悸∵^(guò)濾器判斷一個(gè)元素是會(huì)存在誤判，此時(shí)無(wú)法保證要?jiǎng)h除的元素在布隆過(guò)濾器中，如果此時(shí)將位圖中對(duì)應(yīng)的比特位清0，就會(huì)影響到其他元素了：