??????歡迎來到程序員餐廳??????

? ? ? ? ??主廚：邪王真眼

主廚的主頁：Chef‘s blog??

所屬專欄：c++大冒險

總有光環(huán)在隕落，總有新星在閃爍

前言：

? ? ? ?我們之前學(xué)習(xí)了哈希表，哈希表通過映射關(guān)系，實現(xiàn)了O(1)的復(fù)雜度來查找數(shù)據(jù)，哈希在實踐中是一個非常重要的思想，今天要學(xué)習(xí)的就是哈希思想的兩大應(yīng)用：位圖與布隆過濾器

一、?位圖

1.1 面試題【騰訊】

給 40 億個不重復(fù)的無符號整數(shù)，沒排過序。給一個無符號整數(shù)，如何快速判斷一個數(shù)是否在

這40億個數(shù)中。

• 1.?直接遍歷，時間復(fù)雜度O(N)
• 2.?先排序(O(NlogN))，在利用二分查找: logN
• 3.二叉搜索樹、map、set、哈希.......

? ? ? ? ? 但是不要忽略了一個問題：40億個整型，存入內(nèi)存就是大約16G，而且還會有別的內(nèi)存開銷（例如紅黑樹），所以上述方法是不現(xiàn)實的。

? ? ? ? ?我們仔細想想，對于這道題目而言，一個數(shù)據(jù)只有兩種狀態(tài)：在/不在。如果我們想要標識兩種狀態(tài)，其實只需要一個比特位就夠了，0表示不存在，1表示存在。通過哈希的映射思想，我們可以把每一個數(shù)據(jù)映射到一個比特位中，這就是位圖的概念。

template<size_t N>
class bitset
{
public:
protected:
	vector<int> _bits;
};

?思路：
? ? ? ? ? 我們先開一個數(shù)據(jù)類型是int的vector對象，一個int包含32比特位，接著直接對把數(shù)據(jù)的存在/不存在兩種狀態(tài)存放在對應(yīng)比特位中，c++的除法是向下取整，所以要開（N/32+1）個int

BitSet()
{
	_bits.resize(N /32 + 1);
}

size_t i = x / 32; // vector的第i個元素
size_t j = x % 32; // 第i個元素的第j個比特位

1000100 //待修改數(shù)據(jù),把第3位修改為1
00000001 //數(shù)字1
00001000 //數(shù)字1左移3位
------------
10000100
00001000 //按位或
------------
10001100//得到結(jié)果

void set(size_t x)
{
	assert(x <= N);//別忘了斷言
	int i = x / 32;
	int j = x % 32;
	_bits[i] |=1 << j;
}

void reset(size_t x)
{
	assert(x <= N);//別忘了斷言
	int i = x / 32;
	int j = x % 32;
	_bits[i] &= ~(1 << j);
}

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

題目一?

1個文件有100億個int，1G內(nèi)存，設(shè)法找到出現(xiàn)次數(shù)不超過2次的所有整數(shù)。

這種問題很明顯就是利用位圖來解決，可是前面的問題我們用了一個比特位標識出一個數(shù)字在/不在的兩種狀態(tài)。

那么這個問題呢？

我們可以設(shè)想為3種狀態(tài)，出現(xiàn)0次、出現(xiàn)1次、出現(xiàn)2次、出現(xiàn)3次及以上，分別用如下數(shù)字標識：

?出現(xiàn)0次：00

出現(xiàn)1次：01

出現(xiàn)2次：10

出現(xiàn)3次及以上：11?

這樣的位圖每個數(shù)據(jù)就要用到兩個比特的空間了，那我們要重新寫一份嗎？

NO！

我選擇前人栽樹后人乘涼：

template<size_t N>
class twobitset
{
public:
	twobitset()
	{
		bs1(N);
		bs2(N);
	}
	void set(size_t x)
	{
		//00->01
		if (bs1.test(x) == false && bs2.test(x) == false)
			bs2.set(x);
		//01->10
		else if (bs1.test(x) == false && bs2.test(x))
		{
			bs1.set(x);
			bs2.reset(x);
		}
		//10->11及以上
		else
		{
			bs2.set(x);
		}
	}
	int test(size_t x)
	{
		if (bs1.test(x) == false && bs2.test(x) == false)
			return 0;
		//01->10
		else if (bs1.test(x) == false && bs2.test(x))
		{
			return 1;
		}
		//10->11及以上
		else if (bs1.test(x) && bs2.test(x) == false)
		{
			return 2;
		}
		else
			return 3;
	}
protected:
	bitset<N> bs1;
	bitset<N> bs2;
}; 

題目二：?

?給兩個文件，分別有100億個整數(shù)（unsigned int），我們只有1G內(nèi)存，如何找到兩個文件的交集？

? ? ? ? ?一個文件的大小大約就在40G，不可能放進內(nèi)存中直接比較的，因此我們可以考慮位圖，我們要開42億個比特位。大概也就是0.5G。

? ? ? ? ? 我們分別把兩個文件的數(shù)據(jù)分別插入到兩個位圖中，此時我們就有兩個范圍是0 - 42億數(shù)的位圖了，總共也就是1G。然后我們同時再遍歷兩個位圖，分別對比每一個位，只要兩張位圖該比特位都是1，那就是文件的交集，把值存到其中一張位圖中（別再開vector了，咋沒空間了），最后銷毀其中一個位圖，把交集放到新建的vector中并返回。

二、布隆過濾器

2.1 布隆過濾器提出

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

2.2布隆過濾器概念

• "C語言"
• "C++"
• "C#"
• "Java"
• "go to"

? ? ? ? 我們一一通過哈希函數(shù)把他們映射到vector的某一個比特位中，這時候就可能發(fā)生哈希沖突，數(shù)值之間相互覆蓋?

?那我們該怎么降低誤差呢？

把一個數(shù)據(jù)通過三套不同的哈希函數(shù)，映射到三個比特位上

降低誤差的原理：
? ? ? ? ?插入元素時，我們會把它所對應(yīng)的三個比特位都修改為1，而在檢查某元素是否存在時，只有這三個比特位值都為1時才認為該數(shù)據(jù)存在，所以如果只是一兩個比特位發(fā)生沖突那也不會影響結(jié)果，當該數(shù)據(jù)的三個比特位都發(fā)生哈希沖突才會產(chǎn)生識別存在與否錯誤（這就是布隆過濾器誤差來源） 。因此降低了誤差，理論上你設(shè)定的1個數(shù)據(jù)用n個比特位存儲，n越大，誤差越小，但占用空間也更多。

相互不影響狀態(tài)：

發(fā)生哈希沖突但不會產(chǎn)生錯誤：

當我們查找數(shù)據(jù)的時候，只有這個數(shù)據(jù)上的三個比特位都為1，才說明這個數(shù)據(jù)存在。

2 .3布隆過濾器的實現(xiàn)?

2.3.1成員變量：

template<size_t N, class K = string, class HF1 = HashFuncAP, class HF2 = HashFuncBKDR, class HF3 = HashFuncDJB>
class BloomFilter
{
public:
protected:
	bitset<5 * N> _bs;
}

struct HashFuncBKDR
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		for (auto ch : s)
		{
			hash += ch;
			hash *= 131;
		}

		return hash;
	}
};
struct HashFuncAP
{
	size_t operator()(const string& s)
	{
		size_t hash = 0;
		int i;

		for (i = 0; i < s.size(); i++)
		{
			if ((i & 1) == 0)// 偶數(shù)位字符
				hash ^= ((hash << 7) ^ (s[i]) ^ (hash >> 3));
			else//奇數(shù)位字符
				hash ^= (~((hash << 11) ^ (s[i]) ^ (hash >> 5)));
		}

		return hash;
	}
};
struct HashFuncDJB
{
	size_t operator()(const string& s)
	{
		register size_t hash = 5381;
		for (auto ch : s)
			hash = hash * 33 ^ ch;

		return hash;
	}
};

void set(const K& key)
{
	size_t hash1=(HF1()(key))%(5*N);
	size_t hash2 = (HF2()(key)) % (5 * N);
	size_t hash3 = (HF3()(key)) % (5 * N);
	_bs.set(hash1);
	_bs.set(hash2);
	_bs.set(hash3);
}

2.3.3查找test

bool test(const& K key)
{
	size_t hash1 = (HF1()(key)) % (5 * N);
	size_t hash2 = (HF2()(key)) % (5 * N);
	size_t hash3 = (HF3()(key)) % (5 * N);
	return _bs.test(hash1)&&_bs.test(hash2)&&_bs.test(hash3);
}

2.3.4刪除reset

2.4?布隆過濾器優(yōu)點

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

2.5?布隆過濾器缺陷

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

2.6布隆過濾器使用場景：

小明買了手機，去注冊手機號，選了一個號碼

1.把號碼輸入布隆過濾器，接受返回值

2.返回值是假，說明該號碼沒被用過

3.返回值是真，說明該號碼可能用過，則再去數(shù)據(jù)庫中尋找看是否用過

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