【C++高階(六)】哈希的應(yīng)用--位圖&布隆過(guò)濾器

這篇具有很好參考價(jià)值的文章主要介紹了【C++高階(六)】哈希的應(yīng)用--位圖&布隆過(guò)濾器。希望對(duì)大家有所幫助。如果存在錯(cuò)誤或未考慮完全的地方，請(qǐng)大家不吝賜教，您也可以點(diǎn)擊"舉報(bào)違法"按鈕提交疑問(wèn)。

??博主CSDN主頁(yè):杭電碼農(nóng)-NEO??
?
?專欄分類:C++從入門(mén)到精通?
?
??代碼倉(cāng)庫(kù):NEO的學(xué)習(xí)日記??
?
??關(guān)注我??帶你學(xué)習(xí)C++
? ????

【C++高階(六)】哈希的應(yīng)用--位圖&布隆過(guò)濾器,C++從入門(mén)到精通,c++,哈希算法,數(shù)據(jù)結(jié)構(gòu)

1. 前言

哈希最常用的應(yīng)用是unordered
系列的容器,但是當(dāng)面對(duì)海量數(shù)據(jù)
如100億個(gè)數(shù)據(jù)中找有沒(méi)有100這
個(gè)數(shù)時(shí),使用無(wú)序容器的話內(nèi)存放不下
所以哈希思想還有別的更重要的應(yīng)用!

本章重點(diǎn):

本篇文章著重講解哈希的應(yīng)用的
兩個(gè)容器,一個(gè)是位圖,一個(gè)是布隆
過(guò)濾器,并且模擬實(shí)現(xiàn)它們.最后會(huì)
講解如何使用這兩個(gè)容器來(lái)解決一
些海量數(shù)據(jù)的面試題問(wèn)題

2. 位圖的概念以及定義

請(qǐng)先看一道海量數(shù)據(jù)的面試題:

【C++高階(六)】哈希的應(yīng)用--位圖&布隆過(guò)濾器,C++從入門(mén)到精通,c++,哈希算法,數(shù)據(jù)結(jié)構(gòu)

如果要使用unordered_set來(lái)解決
40億個(gè)整數(shù),一個(gè)整數(shù)占4四節(jié),
總共大約占16個(gè)G的內(nèi)存空間
并且set容器中不止有整型數(shù)據(jù),還有
其他的數(shù)據(jù),所以不能用set!

而一個(gè)數(shù)在或不在可以用1/0來(lái)表示
也就是說(shuō)其實(shí)只需要一個(gè)比特位就可
以知道一個(gè)數(shù)在不在其中.
于是位圖橫空出世!

位圖概念:

所謂位圖，就是用每一位來(lái)存放某種狀態(tài)，適用于海量數(shù)據(jù)，數(shù)據(jù)無(wú)重復(fù)的場(chǎng)景。通常是用來(lái)判斷某個(gè)數(shù)據(jù)存不存在的

舉例說(shuō)明:

【C++高階(六)】哈希的應(yīng)用--位圖&布隆過(guò)濾器,C++從入門(mén)到精通,c++,哈希算法,數(shù)據(jù)結(jié)構(gòu)

判斷1~22中哪些數(shù)據(jù)是存在的
只需要用三個(gè)整型也就是24個(gè)
比特位的空間,同理,40億個(gè)數(shù)據(jù)
也用不著16G的內(nèi)存,使用0.5G
內(nèi)存的位圖即可判斷一個(gè)數(shù)在不在!

3. 位圖的模擬實(shí)現(xiàn)

先來(lái)看看庫(kù)中實(shí)現(xiàn)的位圖:
【C++高階(六)】哈希的應(yīng)用--位圖&布隆過(guò)濾器,C++從入門(mén)到精通,c++,哈希算法,數(shù)據(jù)結(jié)構(gòu)

模板參數(shù)N代表位圖的大小

位圖有三個(gè)主要的接口函數(shù):

set: 將一個(gè)數(shù)據(jù)放入位圖中
reset:將一個(gè)數(shù)據(jù)從位圖中刪掉
test:檢測(cè)一個(gè)數(shù)據(jù)在不在位圖中

位圖本身就是一段連續(xù)的空間
所以用char類型數(shù)組來(lái)充當(dāng)位圖的
基本結(jié)構(gòu)是很符合情況的!

先將位圖框架寫(xiě)出來(lái):

template<size_t N>//N是所有數(shù)中的最大值
class bit_set
{
public:
	bit_set()
	{
		_bit.resize(N / 8 + 1, 0);
	}
	void set(size_t x)//將第x位變成1
	{}
	void reset(size_t x)//將第x位由1變0
	{}
	bool test(size_t x)
	{}
private:
	vector<char> _bit;
};

在寫(xiě)set,reset等函數(shù)時(shí),要先清除一點(diǎn),
那就是char類型的數(shù)組一個(gè)元素有八個(gè)
比特位,所以我們需要確定兩個(gè)位置:
一是此數(shù)據(jù)在哪一個(gè)數(shù)組元素中
二是此數(shù)據(jù)對(duì)應(yīng)此元素的第幾個(gè)比特位
下面我們畫(huà)個(gè)圖來(lái)推導(dǎo)一下公式:

【C++高階(六)】哈希的應(yīng)用--位圖&布隆過(guò)濾器,C++從入門(mén)到精通,c++,哈希算法,數(shù)據(jù)結(jié)構(gòu)

現(xiàn)在已經(jīng)能準(zhǔn)確的找到這個(gè)比特位了
那么怎樣將這個(gè)比特位變成0/1并且
不會(huì)影響到其他的比特位呢?下面分享
兩個(gè)很巧妙的方法,請(qǐng)大家細(xì)細(xì)品嘗:

template<size_t N>//N是所有數(shù)中的最大值
class bit_set
{
public:
	bit_set()
	{
		_bit.resize(N / 8 + 1, 0);
	}
	void set(size_t x)//將第x位變成1
	{
		//x/8->在第幾個(gè)char
		//x%8->在這個(gè)char的第幾個(gè)比特位
		size_t i = x / 8;
		size_t j = x % 8;
		_bit[i] |= (1 << j);//將x對(duì)應(yīng)的比特位變成1
	}
	void reset(size_t x)
	{
		size_t i = x / 8;
		size_t j = x % 8;
		_bit[i] &= ~(1 << j);//將x對(duì)應(yīng)的比特位變成0
	}
	bool test(size_t x)
	{
		size_t i = x / 8;
		size_t j = x % 8;
		return _bit[i] & (1 << j);
	}
private:
	vector<char> _bit;
};

關(guān)于代碼的解釋都在注釋中,請(qǐng)耐心觀看
必要時(shí)可以自己畫(huà)圖做做試驗(yàn)

4. 布隆過(guò)濾器的概念以及定義

位圖有一個(gè)缺陷,那就是只能判斷整型是否存在
遇見(jiàn)字符串等類型的數(shù)據(jù)就很難處理了

布隆過(guò)濾器的提出:

【C++高階(六)】哈希的應(yīng)用--位圖&布隆過(guò)濾器,C++從入門(mén)到精通,c++,哈希算法,數(shù)據(jù)結(jié)構(gòu)
布隆過(guò)濾器的概念:

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

舉例說(shuō)明:

【C++高階(六)】哈希的應(yīng)用--位圖&布隆過(guò)濾器,C++從入門(mén)到精通,c++,哈希算法,數(shù)據(jù)結(jié)構(gòu)
查找字符"美團(tuán)"是否存在時(shí),會(huì)找到
這三個(gè)綠色的位置,看看是否都為1

布隆過(guò)濾器的拓展閱讀:

布隆過(guò)濾器原理

5. 布隆過(guò)濾器模擬實(shí)現(xiàn)(一)

首先,布隆過(guò)濾器的底層也是位圖,所以
只需封裝一層即可實(shí)現(xiàn)一個(gè)布隆過(guò)濾器!

但實(shí)現(xiàn)布隆過(guò)濾器的關(guān)鍵有以下幾個(gè)

一個(gè)字符串映射幾個(gè)位置?

怎樣把字符串轉(zhuǎn)換為整數(shù)?

一般而言,一個(gè)字符串映射的越多,那么
誤判率就越低,但是映射過(guò)多會(huì)導(dǎo)致不同
的字符串映射到相同的位置,所以一般映射
三個(gè)位置,并且將字符串轉(zhuǎn)換為整數(shù)也就
需要三種不同的方法,我在網(wǎng)上找了一些
字符串轉(zhuǎn)整數(shù)的算法,請(qǐng)看下面的代碼:

//三個(gè)不同的字符串映射成整數(shù)的函數(shù)
struct HashBKDR
{
	size_t operator()(const string& key)
	{
		size_t val = 0;
		for (auto ch : key)
		{
			val *= 131;
			val += ch;
		}
		return val;
	}
};
struct HashAP
{
	size_t operator()(const string& key)
	{
		size_t hash = 0;
		for (size_t i = 0; i < key.size(); i++)
		{
			if ((i & 1) == 0)
				hash ^= ((hash << 7) ^ key[i] ^ (hash >> 3));
			else
				hash ^= (~((hash << 11) ^ key[i] ^ (hash >> 5)));
		}
		return hash;
	}
};
struct HashDJB
{
	size_t operator()(const string& key)
	{
		size_t hash = 5381;
		for (auto ch : key)
			hash += (hash << 5) + ch;
		return hash;
	}
};

將這三個(gè)仿函數(shù)傳入類,用于字符串轉(zhuǎn)整型

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

// N表示準(zhǔn)備要映射N(xiāo)個(gè)值
template<size_t N,
	class K = string, class Hash1 = HashBKDR, class Hash2 = HashAP, class Hash3 = HashDJB>
class Bloom_Filter
{
public:
	void set(const K& key)
	{
		size_t hash1 = Hash1()(key) % (_ratio * N);
		_bits->set(hash1);
		size_t hash2 = Hash2()(key) % (_ratio * N);
		_bits->set(hash2);
		size_t hash3 = Hash3()(key) % (_ratio * N);
		_bits->set(hash3);
	}

	bool test(const K& key)
	{
		size_t hash1 = Hash1()(key) % (_ratio * N);
		if (!_bits->test(hash1))
			return false; // 準(zhǔn)確的
		size_t hash2 = Hash2()(key) % (_ratio * N);
		if (!_bits->test(hash2))
			return false; // 準(zhǔn)確的
		size_t hash3 = Hash3()(key) % (_ratio * N);
		if (!_bits->test(hash3))
			return false;  // 準(zhǔn)確的
		return true; // 可能存在誤判
	}

	void reset(const K& key)//支持刪除操作的話,可能會(huì)把其他數(shù)據(jù)對(duì)應(yīng)的映射值刪除
	{}
private:
	const static size_t _ratio = 5;//開(kāi)的空間越大,誤判率越小
	std::bitset<_ratio* N>* _bits = new std::bitset<_ratio * N>;//標(biāo)準(zhǔn)庫(kù)中的位圖是在棧上開(kāi)辟的靜態(tài)數(shù)組,過(guò)大會(huì)棧溢出
};

6. 布隆過(guò)濾器模擬實(shí)現(xiàn)(二)

布隆過(guò)濾器的查找是一個(gè)很玄幻的過(guò)程:

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

因?yàn)楣：瘮?shù)可能存在沖突的原因,如下:

【C++高階(六)】哈希的應(yīng)用--位圖&布隆過(guò)濾器,C++從入門(mén)到精通,c++,哈希算法,數(shù)據(jù)結(jié)構(gòu)
所以我們得出一個(gè)結(jié)論:

布隆過(guò)濾器說(shuō)一個(gè)元素存在,那它可能存在
布隆過(guò)濾器說(shuō)一個(gè)元素不在,那它一定不在

布隆過(guò)濾器的刪除操作:

如果你理解了上面的內(nèi)容,你一定能
明白布隆過(guò)濾器是不支持刪除的,因?yàn)?br> 刪除一個(gè)關(guān)鍵字時(shí)可能將其他的關(guān)鍵字
的一部分也給刪除了,因?yàn)橐粋€(gè)bit位
只能存儲(chǔ)一個(gè)二進(jìn)制信息!

【C++高階(六)】哈希的應(yīng)用--位圖&布隆過(guò)濾器,C++從入門(mén)到精通,c++,哈希算法,數(shù)據(jù)結(jié)構(gòu)

7. 處理海量數(shù)據(jù)的面試題

海量數(shù)據(jù)的處理,有對(duì)位圖的應(yīng)用
也有對(duì)布隆過(guò)濾器的應(yīng)用一步一步解析

位圖的應(yīng)用:

給100億個(gè)整數(shù),設(shè)法找到只出現(xiàn)一次的整數(shù)？
給兩個(gè)文件,分別有100億個(gè)整數(shù),只有1G內(nèi)存,如何找到兩個(gè)文件交集？
位圖應(yīng)用變形:一個(gè)文件有100億個(gè)int,1G內(nèi)存,設(shè)法找到出現(xiàn)次數(shù)不超過(guò)2次的所有整數(shù)

布隆過(guò)濾器的應(yīng)用:

給兩個(gè)文件，分別有100億個(gè)query，我們只有1G內(nèi)存，如何找到兩個(gè)文件交集？分別給出精確算法和近似算法
如何擴(kuò)展BloomFilter使得它支持刪除元素的操作

這些問(wèn)題大家可以下來(lái)想一想,有什么問(wèn)題歡迎私信

8. 總結(jié)

講到這里,哈希的所有內(nèi)容就已經(jīng)
講完了,所以無(wú)腦哈希無(wú)腦哈希,
但實(shí)際上要學(xué)好哈希還真得費(fèi)點(diǎn)腦子

海量數(shù)據(jù)得處理問(wèn)題在面試時(shí)也是
經(jīng)常問(wèn)的,希望同學(xué)們好好學(xué)扎實(shí)!文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-752297.html

?? 下期預(yù)告:C++11新改動(dòng)??

到了這里，關(guān)于【C++高階(六)】哈希的應(yīng)用--位圖&布隆過(guò)濾器的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！