【数据结构】盘点那些经典的 [哈希面试题]【哈希切割】【位图应用】【布隆过滤器】（10）-Toy模板网

这篇具有很好参考价值的文章主要介绍了【数据结构】盘点那些经典的 [哈希面试题]【哈希切割】【位图应用】【布隆过滤器】（10）。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

前言

大家好吖，欢迎来到 YY 滴数据结构系列，热烈欢迎！本章主要内容面向接触过C++的老铁
主要内容含：

欢迎订阅 YY滴C++专栏！更多干货持续更新！以下是传送门！文章来源地址https://www.toymoban.com/news/detail-764640.html

YY的《C++》专栏

YY的《C++11》专栏

YY的《Linux》专栏

YY的《数据结构》专栏

YY的《C语言基础》专栏

YY的《初学者易错点》专栏

YY的《小小知识点》专栏

一.哈希切割

哈希切分的基本概念： 是将一个大文件，利用哈希的原理， 将其分为若干个小文件。

【1】给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？

根据 哈希切分的原理：相同的ip一定会进入同一个小文件中，用 map 统计每个小文件中相同ip出现的次数

二.位图应用

【1】给定100亿个整数，设计算法找到只出现一次的整数？

分析：我们可以用两个位图来控制，我们可以这样设计

代码展示设计思路如图所示：

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代表出现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内存，设计算法找到出现次数不超过2次的所有整数

此题的设计思路与上面的【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);                        //出现一次
			} // 01 -> 10
			else if (!_bs1.test(x) && _bs2.test(x))
			{
				_bs1.set(x);
				_bs2.reset(x);                    //出现两次
			}// 10 -> 11
			else if (_bs1.test(x) && !_bs2.test(x))
			{
				_bs2.set(x);                      //出现三次
			}
			// 此外代表出现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;
	};