一、前提引入

思考如下的題目

將長度為10的字符串保存在哈希表中，需要多少空間

對于每個(gè)字符來說，都有256中可能（即ASCII的理論字符數(shù)量，常用ASCII編碼只有128個(gè)），因此一個(gè)長度為10的字符串有種比特組合

因此將字符串轉(zhuǎn)換成整型，是從大范圍轉(zhuǎn)換到小范圍。也就是多對一，因此將其映射到哈希表中，一定會(huì)產(chǎn)生沖突

可能出現(xiàn)如下情況

將其進(jìn)行二次映射，也就是采用兩個(gè)位置進(jìn)行映射，從而盡量減少?zèng)_突。二次映射可能又會(huì)導(dǎo)致沖突，但是二次映射的目的不是消除沖突，而是盡量減少?zèng)_突

 由于是多個(gè)哈希函數(shù)映射，因此對于一個(gè)字符串x是否存在的判斷可能出現(xiàn)以下情況

①x在哈希表中：x的多個(gè)映射位置的比特值都為1。但由于多次映射，比特值為1可能是別的字符串映射的結(jié)果。因此x在哈希表中的判斷是不一定準(zhǔn)確的，可能出現(xiàn)誤判情況

②x不在哈希表中：如果x的多個(gè)映射位置中有任意一個(gè)的比特值為0，則代表x不在哈希表中。也就是說別的字符串映射結(jié)果并不影響x不在哈希表中的映射。所以x不在哈希表中的判斷是一定準(zhǔn)確的

二、布隆過濾器概念

布隆過濾器是哈希與位圖的結(jié)合

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

在數(shù)據(jù)量足夠大的時(shí)候，不論如何選擇哈希函數(shù)，都一定會(huì)出現(xiàn)沖突問題，而布隆過濾器的設(shè)計(jì)理念就是降低沖突的概率

布隆過濾器將哈希的單次映射調(diào)整為多次映射。也就是對于同一個(gè)關(guān)鍵字使用多個(gè)哈希函數(shù)進(jìn)行映射，一個(gè)值映射一個(gè)位置，容易出現(xiàn)誤判，但是一個(gè)值映射多個(gè)位置就可以降低誤判率

哈希函數(shù)的數(shù)量并不是越多越好，每多一個(gè)哈希函數(shù)，關(guān)鍵字映射的位就越多，占用的比特?cái)?shù)量就越多。因此需要選擇數(shù)量合適的哈希函數(shù)個(gè)數(shù)。

最佳的哈希函數(shù)個(gè)數(shù)計(jì)算：

其中k為哈希函數(shù)個(gè)數(shù)，m為布隆過濾器長度，n為元素個(gè)數(shù)

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

查找

分別計(jì)算每個(gè)哈希值對應(yīng)的比特位置存儲(chǔ)的是否為零，只要有一個(gè)為零，代表該元素一定不在哈希表中，否則可能在哈希表中

刪除 

布隆過濾器不能直接支持刪除工作，因?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ù)回繞

程序?qū)崿F(xiàn)

以下實(shí)現(xiàn)的幾種哈希函數(shù)，采用其他大佬實(shí)現(xiàn)的經(jīng)過數(shù)學(xué)驗(yàn)證的，盡量減少?zèng)_突的哈希函數(shù)。可以根據(jù)自己的需求更改

#pragma once
#include<iostream>
#include<vector>
#include<string>
#include<bitset>
using std::string;
using std::bitset;
namespace my_BloomFilter
{
	struct BKDRHash
	{
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (auto ch : s)
			{
				hash += ch;
				hash *= 31;
			}
			return hash;
		}
	};
	struct APHash
	{
		size_t operator()(const string& s)
		{
			size_t hash = 0;
			for (long i = 0; i < s.size(); i++)
			{
				size_t ch = s[i];
				if ((i & 1) == 0)
				{
					hash ^= ((hash << 7) ^ ch ^ (hash >> 3));
				}
				else
				{
					hash ^= (~((hash << 11) ^ ch ^ (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;
		}
	};
	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);
		}
		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;
			}
			// 在      不準(zhǔn)確的，存在誤判
			// 不在    準(zhǔn)確的
			return true;
		}
	private:
		static const ssize_t _X = 6;
		bitset<N*_X> _bs;
	};
}

四、布隆過濾器的實(shí)現(xiàn)場景

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

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

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

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

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

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

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

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

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

2. 不能獲取元素本身

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

4. 如果采用計(jì)數(shù)方式刪除，可能會(huì)存在計(jì)數(shù)回繞問題

可以通過布隆過濾器對數(shù)據(jù)進(jìn)行初步判斷。比如在賬號(hào)注冊階段，可以用于用戶名查重等操作，如果該用戶名不存在，則可以注冊。如果該用戶名存在，則在數(shù)據(jù)庫中進(jìn)行查找，二次確認(rèn)

實(shí)際應(yīng)用中數(shù)據(jù)庫中的數(shù)據(jù)量可能特別大，數(shù)據(jù)都存儲(chǔ)在硬盤中。因此采用過濾操作提升查找速度是十分必要的

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

最新評(píng)論