C++位圖,哈希切分與布隆過(guò)濾器怎么應(yīng)用

本篇內(nèi)容主要講解“C++位圖,哈希切分與布隆過(guò)濾器怎么應(yīng)用”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“C++位圖,哈希切分與布隆過(guò)濾器怎么應(yīng)用”吧!

一、位圖

1、位圖的概念

所謂位圖，就是用每一位來(lái)存放某種狀態(tài)，適用于海量數(shù)據(jù)，數(shù)據(jù)無(wú)重復(fù)的場(chǎng)景。通常是用來(lái)標(biāo)記某個(gè)數(shù)據(jù)在或不在，它解決不了哪個(gè)數(shù)據(jù)出現(xiàn)次數(shù)最多的問(wèn)題。

2、大廠面試題

2.1位圖應(yīng)用

給40億個(gè)不重復(fù)的無(wú)符號(hào)整數(shù)，沒(méi)排過(guò)序。給一個(gè)無(wú)符號(hào)整數(shù)，如何快速判斷一個(gè)數(shù)是否在這40億個(gè)數(shù)中？

開(kāi)一個(gè)位圖，使用哈希的直接定址法，值是幾，就把位圖中的比特位標(biāo)記成1，僅占用512M空間。

但我們不能按照比特位來(lái)開(kāi)辟空間，所以使用char或int等內(nèi)置類型進(jìn)行空間的開(kāi)辟：

仿寫bitset：

#pragma once
#include <iostream>
#include <vector>
namespace jly
{
	template <size_t N>
	class bitset
	{
	public:
		bitset()
		{
			_bits.resize(N / 8 + 1, 0);
		}
	public:
		void set(size_t x)//將某個(gè)比特位標(biāo)記為1
		{
			size_t i = x / 8;//算出x位于哪個(gè)字節(jié)
			size_t j = x % 8;//算出x位于該字節(jié)的哪一位
			_bits[i] |= (1 << j);
		}
		void reset(size_t x)//將某個(gè)比特位標(biāo)記為0
		{
			size_t i = x / 8;
			size_t j = x % 8;
			_bits[i] &= (~(1 << j));
		}
		bool test(size_t x)//測(cè)試這個(gè)值在不在位圖中
		{
			size_t i = x / 8;
			size_t j = x % 8;
			return _bits[i] & (1 << j);
		}
	private:
		std::vector<char> _bits;
	};
	void test_bitset()
	{
		bitset<-1> bs;
	}
}

這是一種又快又省空間的辦法，也是面試官最想聽(tīng)到的回答。

但個(gè)人認(rèn)為如果將題目要求的40億數(shù)字全部錄入位圖中，等于遍歷了一遍40億個(gè)數(shù)字，既然都遍歷一遍原數(shù)據(jù)了，那還不如在遍歷的時(shí)候直接比對(duì)呢，對(duì)吧，相比之下直接比對(duì)數(shù)據(jù)連512M的位圖都不用開(kāi)。

2.2位圖應(yīng)用

1、給定100億個(gè)整數(shù)，設(shè)計(jì)算法找到只出現(xiàn)一次的整數(shù)？

可以認(rèn)為這里的整數(shù)的最大值為unsigned int的最大值，一個(gè)整數(shù)共有三種狀態(tài)：00,01,02，分別代表不存在，出現(xiàn)一次，出現(xiàn)兩次及以上，代碼如下：

template <size_t N>
class twobitset
{
public:
	void set(size_t x)
	{
		if (_bs1.test(x))//01->10
		{
			_bs1.reset(x);
			_bs2.set(x);
		}
		else if (_bs1.test(x)==false&&_bs2.test(x)==false)//00->01
		{
			_bs1.set(x);
		}
	}
	void PrintOnce()
	{
		for (size_t i = 0; i < N; ++i)
		{
			if (_bs1.test(i) && !_bs2.test(i))
			{
				std::cout << i << std::endl;
			}
		}
	}
private:
	std::bitset<N> _bs1;
	std::bitset<N> _bs2;
};
void test()
{
	twobitset<100> tbs;
	int a[] = { 3,5,6,3,5,8,9,4,3,6,9,4 };
	for (auto& e : a)
	{
		tbs.set(e);
	}
	tbs.PrintOnce();//打印8
}

2、給兩個(gè)文件，分別有100億個(gè)整數(shù)，我們只有1G內(nèi)存，如何找到兩個(gè)文件交集？ 

和第一問(wèn)類似，開(kāi)兩個(gè)位圖，分別將兩組數(shù)據(jù)映射進(jìn)位圖，兩個(gè)位圖對(duì)應(yīng)的比特位均為1即為交集。

3、位圖應(yīng)用變形：1個(gè)文件有100億個(gè)int，1G內(nèi)存，設(shè)計(jì)算法找到出現(xiàn)次數(shù)不超過(guò)2次的所有整數(shù)

同第一問(wèn)，開(kāi)兩個(gè)位圖，00代表不存在，01代表出現(xiàn)一次，10代表出現(xiàn)兩次，11代表出現(xiàn)兩次以上。

3、位圖的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：節(jié)省空間，查找速度快

缺點(diǎn)：要求范圍相對(duì)集中，范圍特別分散的，空間消耗大；位圖只對(duì)整型使用，浮點(diǎn)數(shù)、string等其他類型無(wú)法使用。

如果要判斷其他類型，該類型如果可以使用哈希函數(shù)轉(zhuǎn)為整型的，可以考慮下布隆過(guò)濾器哈（見(jiàn)下文布隆過(guò)濾器的介紹）。

二、哈希切分

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

如果Ai沖突桶超過(guò)1G怎么辦？

1、這個(gè)桶沖突的IP很多，大多都是不重復(fù)的，map統(tǒng)計(jì)不下；

2、這個(gè)桶沖突的IP很多，大多都是重復(fù)的，map可以統(tǒng)計(jì)；

直接使用map中的insert將每一個(gè)沖突桶的元素插入到map中。情況一：如果insert插入失敗，說(shuō)明空間不足，new節(jié)點(diǎn)失敗，拋出異常。解決方法是換個(gè)哈希函數(shù)，遞歸再次對(duì)這個(gè)沖突桶進(jìn)行切分。情況二：map可以正常統(tǒng)計(jì)。

三、布隆過(guò)濾器

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

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

既然這種方法能判斷某個(gè)元素一定不存在，那么如何降低“誤判”（映射為1的概率）的概率，提升準(zhǔn)確判定（映射為0的概率）的概率呢？

解決方法就是對(duì)同一個(gè)元素使用多組哈希函數(shù)進(jìn)行映射，它能降低誤判率，但是增加了空間消耗。使用時(shí)需要把控好布隆過(guò)濾器的哈希函數(shù)的個(gè)數(shù)和布隆過(guò)濾器的長(zhǎng)度。公式為k=(m/n)*lg2

【k:哈希函數(shù)的個(gè)數(shù)；m:布隆過(guò)濾器的長(zhǎng)度；n:插入元素的個(gè)數(shù)】(選型可參照本文)

2、布隆過(guò)濾器的應(yīng)用場(chǎng)景

1、不需要一定準(zhǔn)確的場(chǎng)景，例如個(gè)人網(wǎng)站注冊(cè)時(shí)候的昵稱判重，使用布隆過(guò)濾器可以判斷某個(gè)昵稱一定沒(méi)有被使用過(guò)，但會(huì)誤判某些造成沖突但沒(méi)有被使用的昵稱。

2、提高效率。例如客戶端查找信息時(shí)，先用布隆過(guò)濾器篩一下，如果不在，則直接將未查到的信息反饋給客戶端；如果布隆過(guò)濾器發(fā)現(xiàn)查找信息與位圖匹配，則將需要查找的信息推送給服務(wù)器中的數(shù)據(jù)庫(kù)進(jìn)行精確查找。

3、布隆過(guò)濾器的刪除

單純的布隆過(guò)濾器是不支持刪除的，因?yàn)橐粋€(gè)比特位可能被多個(gè)元素所映射。如果非要在布隆過(guò)濾器中實(shí)現(xiàn)reset，那就只能將位圖結(jié)構(gòu)修改為計(jì)數(shù)器結(jié)構(gòu)。數(shù)據(jù)set時(shí)，每被映射一次，計(jì)數(shù)器加1，reset時(shí)，該位計(jì)數(shù)器-1，直到該位計(jì)數(shù)器為0。毫無(wú)疑問(wèn)，這種操作所需的空間消耗急劇增加。

4、布隆過(guò)濾器的優(yōu)缺點(diǎn)

優(yōu)點(diǎn)：

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

缺點(diǎn)：

有誤判率，即存在假陽(yáng)性(False Position)，即不能準(zhǔn)確判斷元素是否在集合中(補(bǔ)救方法：再建立一個(gè)白名單，存儲(chǔ)可能會(huì)誤判的數(shù)據(jù))不能獲取元素本身一般情況下不能從布隆過(guò)濾器中刪除元素如果采用計(jì)數(shù)方式刪除，可能會(huì)存在計(jì)數(shù)回繞問(wèn)題

5、布隆過(guò)濾器面試題

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

近似算法：使用布隆過(guò)濾器，先將其中一個(gè)文件set進(jìn)布隆過(guò)濾器中，再將另一個(gè)文件的數(shù)據(jù)進(jìn)行比對(duì)，可以淘汰一定不是交集的那部分，不過(guò)余下的那部分?jǐn)?shù)據(jù)中，仍會(huì)有非交集的存在。

精確算法：使用哈希切分，將兩個(gè)大文件分別切成一個(gè)個(gè)小文件A0-A99，B0-B99（單個(gè)小文件超過(guò)1G參照上文哈希切分對(duì)于此問(wèn)題的解決方法）；因?yàn)槭褂玫氖窍嗤墓：瘮?shù)，所以交集必定存在于A0和B0，A1和B1這種相同下標(biāo)的小文件中?？梢韵葘0存放至哈希表中，B0去重后與哈希表比對(duì)，就能夠精確得到交集。

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

#pragma once
#include <iostream>
#include <bitset>
#include <string>
using namespace std;
struct BKDRHash
{
	size_t operator()(const std::string& key)
	{
		size_t hash = 0;
		for (auto& ch : key)
		{
			hash *= 131;
			hash += ch;
		}
		return hash;
	}
};
struct APHash
{
	size_t operator()(const std::string& key)
	{
		unsigned int 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 std::string& key)
	{
		unsigned int hash = 5381;
 
		for (auto ch : key)
		{
			hash += (hash << 5) + ch;
		}
 
		return hash;
	}
};
 
struct JSHash
{
	size_t operator()(const std::string& s)
	{
		size_t hash = 1315423911;
		for (auto ch : s)
		{
			hash ^= ((hash << 5) + ch + (hash >> 2));
		}
		return hash;
	}
};
 
//N為最大存儲(chǔ)的個(gè)數(shù),X為存一個(gè)值，需要開(kāi)辟的比特位
template <size_t N,size_t X=5,class K=std::string,
class HashFunc1= BKDRHash,
class HashFunc2= APHash,
class HashFunc3= DJBHash>
class BloomFilter
{
public:
	void set(const K& key)
	{
		size_t hash2 = HashFunc1()(key) % (X * N);
		size_t hash3 = HashFunc2()(key) % (X * N);
		size_t hash4 = HashFunc3()(key) % (X * N);
		_bs.set(hash2);
		_bs.set(hash3);
		_bs.set(hash4);
	}
	bool test(const K& key)
	{
		size_t hash2 = HashFunc1()(key) % (X * N);
		size_t hash3 = HashFunc2()(key) % (X * N);
		size_t hash4 = HashFunc3()(key) % (X * N);
		return _bs.test(hash2) && _bs.test(hash3) && _bs.test(hash4);
	}
private:
	std::bitset<X*N> _bs;
};
void test_bloomfilter1()
{
	// 10:46繼續(xù)
	string str[] = { "a", "s", "d", "w", "a1","1a","白1a","c11a","1a1" };
	BloomFilter<10> bf;
	for (auto& str : str)
	{
		bf.set(str);
	}
 
	for (auto& s : str)
	{
		cout << bf.test(s) << endl;
	}
	cout << endl;
 
	srand((unsigned int)time(0));
	for (const auto& s : str)
	{
		cout << bf.test(s + to_string(rand())) << endl;
	}
}
void test_bloomfilter2()
{
	srand((unsigned int)time(0));
	const size_t N = 100000;
	BloomFilter<N> bf;
 
	std::vector<std::string> v1;
	std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
 
	for (size_t i = 0; i < N; ++i)
	{
		v1.push_back(url + std::to_string(i));
	}
 
	for (auto& str : v1)
	{
		bf.set(str);
	}
 
	// v2跟v1是相似字符串集，但是不一樣
	std::vector<std::string> v2;
	for (size_t i = 0; i < N; ++i)
	{
		std::string url = "https://www.cnblogs.com/-clq/archive/2012/05/31/2528153.html";
		url += std::to_string(999999 + i);
		v2.push_back(url);
	}
 
	size_t n2 = 0;
	for (auto& str : v2)
	{
		if (bf.test(str))
		{
			++n2;
		}
	}
	cout << "相似字符串誤判率:" << (double)n2 / (double)N << endl;
 
	// 不相似字符串集
	std::vector<std::string> v3;
	for (size_t i = 0; i < N; ++i)
	{
		string url = "zhihu.com";
		url += std::to_string(i + rand());
		v3.push_back(url);
	}
 
	size_t n3 = 0;
	for (auto& str : v3)
	{
		if (bf.test(str))
		{
			++n3;
		}
	}
	cout << "不相似字符串誤判率:" << (double)n3 / (double)N << endl;
}

到此，相信大家對(duì)“C++位圖,哈希切分與布隆過(guò)濾器怎么應(yīng)用”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！