前言

大家好吖，歡迎來到 YY 滴 數(shù)據(jù)結(jié)構(gòu) 系列 ，熱烈歡迎！ 本章主要內(nèi)容面向接觸過C++的老鐵
主要內(nèi)容含：

歡迎訂閱 YY滴C++專欄！更多干貨持續(xù)更新！以下是傳送門！文章來源地址http://www.zghlxwxcb.cn/news/detail-764640.html

• YY的《C++》專欄
• YY的《C++11》專欄
• YY的《Linux》專欄
• YY的《數(shù)據(jù)結(jié)構(gòu)》專欄
• YY的《C語言基礎》專欄
• YY的《初學者易錯點》專欄
• YY的《小小知識點》專欄

一.哈希切割

• 哈希切分的基本概念： 是將一個大文件，利用哈希的原理， 將其分為若干個小文件。

【1】給一個超過100G大小的log file, log中存著IP地址, 設計算法找到出現(xiàn)次數(shù)最多的IP地址？

• 根據(jù) 哈希切分的原理：相同的ip一定會進入同一個小文件中，用 map 統(tǒng)計每個小文件中相同ip出現(xiàn)的次數(shù)

二.位圖應用

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

• 分析：我們可以用兩個位圖來控制，我們可以這樣設計
  

• 代碼展示設計思路如圖所示：

template<size_t N>
	class twobitset
	{
	public:
		void set(size_t x)
		{
			// 00 -> 01
			if (!_bs1.test(x) && !_bs2.test(x))
			{
				_bs2.set(x);
			} // 01 -> 10
			else if (!_bs1.test(x) && _bs2.test(x))
			{
				_bs1.set(x);
				_bs2.reset(x);
			}
			// 本身10代表出現(xiàn)2次及以上，就不變了
		}

		bool is_once(size_t x)
		{
			return !_bs1.test(x) && _bs2.test(x);
		}
	private:
		bitset<N> _bs1;
		bitset<N> _bs2;
	};

【2】位圖應用變形：1個文件有100億個int，1G內(nèi)存，設計算法找到出現(xiàn)次數(shù)不超過2次的所有整數(shù)

• 此題的設計思路與上面的【1】基本一致，設計上要稍作改動：
  

• 代碼展示設計思路如圖所示：

template<size_t N>
	class twobitset
	{
	public:
		void set(size_t x)
		{
			// 00 -> 01
			if (!_bs1.test(x) && !_bs2.test(x))
			{
				_bs2.set(x);                        //出現(xiàn)一次
			} // 01 -> 10
			else if (!_bs1.test(x) && _bs2.test(x))
			{
				_bs1.set(x);
				_bs2.reset(x);                    //出現(xiàn)兩次
			}// 10 -> 11
			else if (_bs1.test(x) && !_bs2.test(x))
			{
				_bs2.set(x);                      //出現(xiàn)三次
			}
			// 此外代表出現(xiàn)3次及以上，就不變了
		}

		bool max_two(size_t x)
		{
			return (_bs1.test(x) && !_bs2.test(x))||(!_bs1.test(x) && _bs2.test(x));   //10 或者 01
		}
	private:
		bitset<N> _bs1;
		bitset<N> _bs2;
	};

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

• 分析：
• 第一種思路是：把其中一個文件存入位圖，遍歷另一個文件元素，將問題轉(zhuǎn)變成"在不在"問題
• 問題缺陷： 這種問題存在去重問題，即多次重復（下圖中，交集明明只有一個3，但是會出現(xiàn)多個重復的3交集）
  

• 分析：
• 第二種思路是：將兩個文件映射到兩個位圖中去（實現(xiàn)去重）
• 如果相對應的位置都是1（滿足相＆為1），則此元素就在交集中

三.布隆過濾器

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

• 我們先有一個內(nèi)存大小基本概念：1G約為10億byte，假設一個query平均為30byte，那么100億query就約為3000億byte，約為300G

• 哈希切分的基本概念： 是將一個大文件，利用哈希的原理， 將其分為若干個小文件。
• 相同的數(shù)據(jù)都被分到同一個文件里
• 在此題中，如下圖所示，即：A和B中相同的query就會進入相同的小文件中
  
  

【2】如何擴展BloomFilter使得它支持刪除元素的操作

• 多個位標識同一個值，使用 引用計數(shù)

到了這里，關于【數(shù)據(jù)結(jié)構(gòu)】盤點那些經(jīng)典的 [哈希面試題]【哈希切割】【位圖應用】【布隆過濾器】（10）的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關文章，希望大家以后多多支持TOY模板網(wǎng)！