本文主要講解哈希思想的實(shí)際應(yīng)用，位圖和布隆過濾器。

位圖

講解位圖之前我們先來解答這樣一道騰訊的面試題

給40億個(gè)不重復(fù)的無(wú)符號(hào)整數(shù)，沒排過序。給一個(gè)無(wú)符號(hào)整數(shù)，如何快速判斷一個(gè)數(shù)是否在這40億個(gè)數(shù)中?！掘v訊】

很多人立馬就想到了用哈希表或者紅黑樹，因?yàn)樽銐蚩?，特別是哈希表，它的查詢速度到達(dá)了O(1)，想法是非常好的，但是我們可以仔細(xì)思考一下，這樣真的可行嗎？
答案是不現(xiàn)實(shí)，因?yàn)檫@是四十億個(gè)整數(shù)，如果要全部寫入到內(nèi)存中，需要16GB大小的空間，并不是所有的計(jì)算機(jī)都能裝下這些數(shù)據(jù)，換而言之，就算能完全裝下，用這么大的空間去解決這個(gè)問題，也是不太好的，面試官也不會(huì)滿意。

所以這個(gè)時(shí)候就引入了位圖，我們可以想一想，這個(gè)問題只是讓我們求解一個(gè)整數(shù)在或者不在，這兩種狀態(tài)，我們只需要用一個(gè)bit位就可以標(biāo)記，例如1代表在，0代表不在。再配合哈希的映射思想，就產(chǎn)生了位圖這個(gè)數(shù)據(jù)結(jié)構(gòu)。如果不了解哈希，可以看看我之前的文章，我進(jìn)行了很詳細(xì)的講解，我把鏈接貼在這里：哈希。

可以先看一下位圖的結(jié)構(gòu)和代碼是怎么實(shí)現(xiàn)的

template<size_t N>
	class bitset {
	private:
		vector<char> bits;
	public:
		bitset()
		{
			bits.resize(N / 8,0);
		}
		//設(shè)置對(duì)應(yīng)bit位
		void set(size_t x)
		{

			size_t i = x / 8;
			size_t j = x % 8;

			bits[i] |= (1 << j);
		}
		//重置對(duì)應(yīng)數(shù)值bit位
		void reset(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;

			bits[i] &= ~(1 << j);
		}
		//是否存在
		bool test(size_t x)
		{
			size_t i = x / 8;
			size_t j = x % 8;

			return bits[i] & (1 << j);
		}
	};

其實(shí)再C++庫(kù)中是有位圖結(jié)構(gòu)的：bitset

布隆過濾器

上面的位圖結(jié)構(gòu)能很便捷的記錄整數(shù)在或者不在，那么布隆過濾器是什么呢？

布隆過濾器（Bloom Filter）是一種空間效率非常高的隨機(jī)數(shù)據(jù)結(jié)構(gòu)，用于判斷一個(gè)元素是否可能存在于一個(gè)集合中。布隆過濾器可以在時(shí)間和空間上做到很高效，但是會(huì)有一定的誤判率。
布隆過濾器的核心是一個(gè)位數(shù)組和一組哈希函數(shù)。假設(shè)位數(shù)組的長(zhǎng)度是 m，有 k 個(gè)哈希函數(shù)，則每個(gè)元素經(jīng)過 k 次哈希函數(shù)得到 k 個(gè)哈希值，將這 k 個(gè)值對(duì) m 取模，得到 k 個(gè)位置，將這 k 個(gè)位置的值都設(shè)置為 1。當(dāng)要查詢一個(gè)元素時(shí)，同樣地，將該元素經(jīng)過 k 次哈希函數(shù)得到 k 個(gè)哈希值，查詢這 k 個(gè)位置的值是否都為 1，如果都為 1，則說明該元素可能存在于集合中，如果有任何一個(gè)位置的值為 0，則說明該元素一定不存在于集合中。
布隆過濾器的優(yōu)點(diǎn)在于，它可以很高效地判斷一個(gè)元素是否存在于一個(gè)集合中，而且空間效率非常高，因?yàn)樗恍枰褂靡粋€(gè)位數(shù)組和一組哈希函數(shù)即可。但它的缺點(diǎn)在于，存在一定的誤判率，也就是說，有可能某個(gè)元素不在集合中，但是經(jīng)過判斷后，布隆過濾器認(rèn)為它存在于集合中。

簡(jiǎn)單來說就是一個(gè)元素通過K個(gè)哈希函數(shù)映射K個(gè)bit位，布隆過濾器如果說某個(gè)元素不存在時(shí)，該元素一定不存在，如果該元素存在時(shí)，該元素可能存在，因?yàn)橛行┕：瘮?shù)存在一定的誤判。

布隆過濾器實(shí)現(xiàn)代碼：

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 {

	private:
			static const size_t _X = 6;
			bitmap<N* _X> bts;
			size_t len = N * _X;
	public:

		void set(const K& key)
		{
			size_t hash1 = BKDRHash()(key) % len;
			bts.set(hash1);
			
			size_t hash2 = APHash()(key) % len;
			bts.set(hash2);

			size_t hash3 = DJBHash()(key) % len;
			bts.set(hash3);
		}
		bool test(const K& key)
		{
			if (!bts.test(BKDRHash()(key) % len))
			{
				return false;
			}
			if (!bts.test(APHash()(key) % len))
			{
				return false;
			}
			if (!bts.test(DJBHash()(key) % len))
			{
				return false;
			}
			return true;
		}
	};

布隆過濾器使用的哈希函數(shù)越多誤判率越低，但是占用的空間也就越大。用三個(gè)哈希函數(shù)是比較合適的。

這就是位圖和布隆過濾器的原理和實(shí)現(xiàn)，如果對(duì)您有所幫助，點(diǎn)個(gè)贊和關(guān)注吧！文章來源地址http://www.zghlxwxcb.cn/news/detail-482897.html

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