海量数据处理——bitMap/BloomFilter、hash + 统计 + 堆/归并/快排

        前言：海量数据处理是面试中一道常考的问题， 生活中也容易遇到这种问题。 通常就是有一个大文件， 让我们对这个文件进行一系列操作——找出现次数最多的数据、求交集、是否重复出现等等。 因为文件的内容太多， 我们的内存通常是放不下的。这个时候， 我们就要用到一些别的处理手段， 也就是我们的标题——位图， 布隆过滤器以及哈希切分。

        本篇内容分为两个板块——第一个板块实现位图以及布隆过滤器； 第二个板块是大概模拟处理几道海量数据相关题。

        ps：本篇的主要内容就是海量数据如何进行处理，但是需要使用位图和布隆过滤器的内容。 如果没有学过位图和布隆过滤器的友友们， 自行划到文章后面有位图和布隆过滤器的模拟实现。 已经学过的友友们就可以忽略后半部分的位图和布隆的部分， 只观看前半部分的海量数据处理部分。

海量数据处理

一、已知有100亿个int数据， 现在只有1G内存， 如何在这100个int数据里面找出出现次数为2的那些数据。

解：

        整形先考虑位图：100亿个int， 但是这里面隐含了一个条件， 就是整形最多只有四十二亿九千万个。 就是160亿字节。 而10亿个字节为1G。 显然， 如果将所有整形放到内存中是放不下的。 但是我们不需要储存， 只需要查找哪个数据出现次数为2， 那么就可以利用位图和布隆过滤器优化空间。 而且数据类型是int， 那么就可以使用位图——一个整形映射一个比特位。

         那么， 我们就要思考， 四十亿个整形可以映射5亿个字节， 也就是500MB。同时， 我们也要思考，位图只能标记出现过或者没有出现过， 但是不能标记出现过几次。 所以要使用两个位图——位图1， 位图2。 我们都知道位图的一个比特位置为1，代表数据出现过； 一个比特位置为0， 代表数据没有出现过。

        那么如果有两个位图，我们就可以让这两个比特位合起来使用。 如果位图1的对应比特位为0， 位图2的对应比特位置为1，也就是01， 代表出现一次；如果位图1的对应比特位是1， 位图2的对应比特位是0， 那么就是10， 代表出现过2次。所以两个位图一共可以统计次数最多为3.

        而使用两个位图所用空间最多为1G， 空间足够。 所以可是使用两个位图的策略。 具体实现如下：

	template
	class bit_dou 
	{
	public:
		
		void set(size_t x) 
		{
			if (_bit1.test(x) == false && _bit2.test(x) == false) 
			{
				_bit1.set(x);
			}
			else if (_bit1.test(x) == true && _bit2.test(x) == false) 
			{
				_bit1.reset(x);
				_bit2.set(x);
			}
			else if (_bit1.test(x) == false && _bit2.test(x) == true) 
			{
				_bit1.set(x);
			}
		}
		
		bool test(size_t x) 
		{
			if (_bit2.test(x) == true) 
			{
				return true;
			}
			else 
			{
				return false;
			}
		}
	private:
		bitset _bit1;
		bitset _bit2;
	};

       

二、给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法。

        精确策略：这里使用的是hash映射 + 统计（使用哈希map或者map） + （堆/归并/快排）

        具体步骤：

         假设一个query50字节， 那么100亿个query就是5000亿字节，而10亿字节是1g， 那么5000亿字节就是500G， 所以1G内存不能将这些字符串全部存下来。

        这里我们使用的策略是hash + 统计（使用hashmap或者treemap） +  堆排/归并/快排，先使用hash映射将100亿个query划分到500个小文件中， 着500个小文件分别命名为A1、A2、A3……A500——这样能保证平均1个小文件里面有1G内存。

        然后将另一个文件也平均分成500个小文件, 这500个小文件命名为B1、B2、B3……B500——其实两个文件可以分的再多一些， 那样就能减少一个小文件映射的query太多的概率， 导致读取文件时内存空间不足。

        使用hash映射到500个小文件中， 这时候我们可以确定， 相同的query一定会被映射到同一个文件中。 并且两个大文件中如果有相同的query，那么这个query在两个大文件形成的小文件中的下标一定是相同的。 比如一个q0在第一个大文件哈希映射的文件是A122， 那么他在另一个大文件中哈希映射的文件一定是B122。

        那么我们就可以利用这种性质来判断这两组小文件的交集——即A1 和B1寻找交集，寻找出来后将交集放到一个文件中（最好不要放到内存， 因为如果交集很多， 可能导致内存不够。）A2和B2寻找交集后将交集放到一个文件中……A500和B500寻找交集放到一个文件中。

        要注意的是应该考虑如果划分小文件的时候， 出现单个小文件个数太大。 那么也要分情况讨论：第一种情况就是单个小文件太大，但是其中重复的元素很少， 这个时候需要将元素全部映射到map之中空间不够用， 那么就要重新使用新的哈希函数， 重新映射。另一种情况就是虽然单个小文件很大， 但是其中重复的元素很多， 可以将全部元素映射到map之中。那么就正常读取小文件即可。 

        上面这种做法叫做哈希切分， 就是利用分治思想： 哈希映射 + hashmap/treemap （+ 堆/归并/快排）。

        近似策略：使用布隆过滤器。

近似策略就是使用布隆过滤器， 先将一个大文件中的query映射到布隆过滤器当中， 然后再将另一个大文件的数据一个一个读取， 查找是否在当前布隆过滤器之中已经出现过。 如果出现过， 就保存下来。 

        最后保存下来的数据， 就是两个文件的交集。

三、给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？

        这个问题和第一个问题类似，都是使用位图。 100亿个整形其实里面最多只有42亿个不同的整形， 而四十二亿个整形使用位图映射后最多只需要使用400MB， 那么我们就可以使用位图先将一个大文件的数据映射进来， 然后再对另一个文件里面的数据一个一个读取， 查看是否在当前位图映射过。如果映射过， 那么就是交集。

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

        很明显就是使用位图的一个题， 同样的使用两个位图， 建立一个能够统计次数， 最高次数是3的位图（可以叫dou_bitMap)。 那么再统计这100亿个整形， 就能统计他们的出现次数。 最后再从0开始遍历四十二亿的整数， 判断这四十二亿个整数之中哪个出现过1次。 

五、给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？ 与上题条件相同，如何找到top K的IP？

        log file明显不是整形， 那么这道题hash + 统计(hashmap/treemap) + 堆/归并/快排。

首先将100G的大文件利用hash函数切分成100个小文件。 再利用hashmap或者treemap将每个小文件中的出现最多的那个数据保存到一个文件中。 然后遍历这个文件就能找到出现次数最多的那个ip地址。 

        然后如何求topk的ip就要从遍历小文件的时候进行。 将每个小文件中的所有数据读到hashmap中统计其中数据出现的个数。   再利用排序将这些数据的出现个数从高到底排。 取出其中前k个ip放到一个文件之中。 所有的小文件都是上面这个操作。 最后使用一个含有k个数据的小堆。 依次遍历整个文件， 只要遇到比堆顶的数据大的， 就将数据放进堆里面。 然后弹出推顶数据， 维护堆的固定个数。最后堆中剩余的ip就是最大的k个ip。而堆顶就是topk的ip。  

ps:这里总结的方法其实只有:bloomFilter/bitMap 以及 hash + 统计 + 堆/归并/快排； 另外还有几种处理海量数据的方法——外排序、多层划分、倒排索引等等。 这些博主知识储备不足， 在这里不好讲解， 有兴趣的友友可以按照自己的兴趣以及能力自行学习。

位图

        学习位图之前首先要知道的一点就是位图， 布隆过滤器都是利用了哈希的思想。解决的是内存不够的问题。 就是说， 它们可以处理的数据更多。 更能节省空间。 但是也并不是只有优点，位图存在只能处理整形数据的问题。 而布隆过滤器存在不准确的问题。接下来实现位图：

        一般的哈希表像哈希桶， 闭散列。 都是利用一块空间来映射数据，同时需要开空间储存数据。如图位哈希桶图：

但是位图是利用一个比特位来映射数据，只用来映射， 不进行存储。如果改位置映射过， 就置为1（下图中的红代表1）， 没映射过就是0（下图无色， 即默认值）。

 //类的定义（要用模板size_t, 因为要指定位图的大小， 参数是几， 说明至少有多少数据， 就要保证最少开几个比特位空间。）

	template    //模板使用来规定创建的位图大小。 n是几， 就保证最少有几个比特位。
	class bitset 
	{
	};

//使用整形数组来模拟一块连续的空间

	template
	class bitset 
	{
		bitset() 
		{
			//这里要保证开的空间足够， 但是n / 32会消除小数点，开的空间要小于等于需求。 所以要多开一个整形空间。
			_bits.resize(n / 32 + 1);      
		}
	private:
		vector _bits;    //使用整型数组来模拟一块连续的空间。
	};

//进行映射时， 如何定位第几个比特位

        一个整形时4个字节， 32个比特位， 假设当前数据位x。 那么x / 32就是当前需要映射的第几个整形。而x % 32就是当前要映射的这个整形的第几个比特位。

        当进行定位比特位时， 我们就可以这样写:

	int i = x / 32;   //要映射的第几个整形
	int j = x % 32;   //要映射的第几个整形的第几个比特位。

 //将当前比特位标记为1， 如何不修改其他比特位， 只将当前比特位置为1.

        标记比特位要使用按位操作。 而按位操作分为按位与‘&’， 按位或'|', 按位异或'^'。 其中‘&’的规则是：有0就是0， 全1才是1； '|'的规则是：有1就是1， 全0才是0； '^'的规则是：相同为0， 相异为1。

        这里可以使用'|‘操作， 先将1向高位移动 j 个位置。再让第 i 个整形按位或上1移动后的数。 就是想要的结果， 如图:

  

转化为代码就是如下， 这也是第一个接口（位图有三个接口， set, reset, test。该接口是set).

	template
	class bitset 
	{
	public:
		bitset() 
		{
			//这里要保证开的空间足够， 但是n / 32会消除小数点，开的空间要小于等于需求。 所以要多开一个整形空间。
			_bits.resize(n / 32 + 1);      
		}
		void set(int x) 
		{
			int i = x / 32;   //要映射的第几个整形
			int j = x % 32;   //要映射的第几个整形的第几个比特位。
			_bits[i] |= (1