海量数据处理——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<size_t N>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<N> _bit1;bitset<N> _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<size_t n>    //模板使用来规定创建的位图大小。 n是几， 就保证最少有几个比特位。class bitset {};

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

	template<size_t n>class bitset {bitset() {//这里要保证开的空间足够， 但是n / 32会消除小数点，开的空间要小于等于需求。 所以要多开一个整形空间。_bits.resize(n / 32 + 1);      }private:vector<int> _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<size_t n>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 << j);         //按位或：有1就是1， 全0才是0.}private:vector<int> _bits;    //使用整型数组来模拟一块连续的空间。};

 //消除某一个比特位的映射（reset接口)

消除某一个位置的映射需要只将某一个比特位置为0， 其他的位置不变。如果是或操作， 就要让其他位置都是0， 但是并不能消除特定位置的1. 所以就要使用与操作， 让其他位置都是1， 特定位置都是0. 就能让特定位置由1变成0. 而其他位置与上1还是它本身, 代码如下:

	template<size_t n>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 << j);         //按位或：有1就是1， 全0才是0.}void reset(int x) {int i = x / 32;int j = x % 32;_bits[i] &= ~(1 << j);}private:vector<int> _bits;    //使用整型数组来模拟一块连续的空间。};

//测试某一个数据有没有被映射过， 其实就是看某一个比特位有没有被映射过（test) 

        测试某一个位置有没有被映射过， 只需要让该位置与上1， 其他位置遇上0即可。 当其他位置与上0， 那么都变成0， 特定位置与上1， 如果这个位置原本是1， 那么结果就是1。 非0就是真， 如果该位置原本是0， 与上0之后也是零， 其他位置也是零。 所以结果就是0， 0为假。 代码如下:

	template<size_t n>class bitset {public:bitset() {//这里要保证开的空间足够， 但是n / 32会消除小数点，开的空间要小于等于需求。 所以要多开一个整形空间。_bits.resize((n / 32) + 1, 0);      }void set(int x) {int i = x / 32;   //要映射的第几个整形int j = x % 32;   //要映射的第几个整形的第几个比特位。_bits[i] |= (1 << j);         //按位或：有1就是1， 全0才是0.}void reset(int x) {int i = x / 32;int j = x % 32;_bits[i] &= ~(1 << j);}bool test(int x) {int i = x / 32;int j = x % 32;return _bits[i] &= (1 << j);}private:vector<int> _bits;    //使用整型数组来模拟一块连续的空间。};

布隆过滤器

        位图只能用来处理整形， 而布隆过滤器可以用来处理字符串。 弥补了位图只能用来处理整形的缺点。 但是因为字符串的个数太多，（首先长度不确定， ascii码中的字符就有128个。 如果是10位长， 就是128^10） 如果一个字符串可以利用哈希函数转化为一个整形，而字符串的个数远远超过了整形的个数（整型只有四十二亿九千万个）。那么根据鸽巢原理， 就一定会有两个不同的字符串被转化成了相同的整数。 这个时候结果就不准了， 所以布隆过滤器就使用了多个哈希函数， 将一个字符串来映射多个位置。 如图:

图中有三个字符串——苹果、梨、桃子。 同时每个字符串都有三个映射的位置， 并且苹果和桃子有一个哈希映射的位置相同。 如果这个时候再来一个西瓜， 我们要查找一下西瓜存在不存在。

        如图， 虽然西瓜有两个哈希函数映射的位置都被标记过了， 但是最左边那个映射的位置没有被标记过， 那么这样就可以看作西瓜没有出现过。 因为如果西瓜出现过。 这三个位置应该都被映射过， 但是现在这三个位置中有一个没有被映射过。 所以说明其他两个位置应该是和其他字符串发生了哈希冲突导致的, 西瓜就没有被映射过——现在， 这种没有被映射过的情况是一定的， 只要判断出一个字符串没有被映射过， 那么结果就是准确的。即：布隆过滤器的没有出现过是准确的。

        那么， 如果西瓜的映射位置不是上面那样了， 变成下图:

        现在， 这三个位置都发生了哈希冲突， 返回的结果告诉我们西瓜出现过。 但是其实习惯并没有出现过， 这就说明如果判断一个字符串， 结果是出现过。 那么结果就是不准确的——现在， 这种被映射过的情况是不准确的。 即：布隆过滤器的出现过是不准确的。

        要提升布隆过滤器判断出现过的准确性， 就要增加哈希函数。 从图中我们可以看出来， 如果一个字符串映射的位置越多，那么就越难发生所有位置都冲突的情况。 但是， 另一个需要注意的是， 如果我们的字符串映射的位置太多了， 可能导致空间内大部分空间都被映射过。 那么哈希冲突的概率也会提升， 所以还是不行， 那么就要增加空间。 这就导致了一个问题——如果要提高布隆过滤器判断出现过的准确性， 就要增加哈希函数。 而增加哈希函数， 就要消耗更多的空间。 

        下面是布隆过滤器的准确性和哈希函数的个数的关系图：

        布隆过滤器可以用来处理字符串， 以及其他类型。 只要使用相应的哈希函数即可。 这里使用三个哈希函数来封装布隆过滤器——三个哈希函数分别是：BKDR哈希， DJB哈希， AP哈希

//模版参数有五个， 一个要处理的数据个数， 一个要处理的数据类型， 三个哈希函数。 如图:

template<size_t n, class type = string, class HF1 = BKDRHash<type>, class HF2 = DJBHash<type>, class HF3 = APHash<type>>class BloomFilter {};

//三个哈希函数（都可以在网上找到， 这里贴上方便友友使用）

三个哈希函数， 都要有一个关于字符串类型的特化形式。 因为我们使用布隆过滤器使用的最多的就是字符串类类型。  要实现字符串类型的特化就是使用模板的特化机制。如下代码:

//一般先创建一个模板类	
template<class t>
class _class 
{};
//然后在该模板类后面再跟一模板类，但是这个类里面没有参数， 类名后面跟参数。
template<>//没参数
class _class<string>//类名后跟string
{};

BKDR函数的定义是这样的

	//第一个带参数的自行进行修改template<class type>struct BKDRHash{int operator()(const type& key) {return key;}};//字符串处理的特化template<>struct BKDRHash<string>{int operator()(const string& str) {int hash = 0;for (auto& e : str) {hash *= 31;hash += e;}return hash;}};

DJB哈希的定义如下：

    //	//第一个带参数的自行进行修改template<class type>struct DJBHash {int operator()(const type& key) {return key;}};template<>struct DJBHash<string>  {int operator()(const string& str){int hash = 0;for (auto& e : str) {hash += (hash << 5) + e;}hash = hash & ~(hash << 31);return hash;}};

APHash 

template<class type>struct APHash {int operator()(const type& x) {return x;}};template<>struct APHash<string> {int operator()(const string& str) {int hash = 0;for (int i = 0; i < str.size(); i++) {if (i & 1 == 0){hash ^= ((hash << 7) ^ str[i] ^ (hash >> 3));}else{hash ^= ((hash << 11) ^ str[i] ^ (hash >> 5));}}return hash;}};

//布隆过滤器也是一个比特位，一个比特位进行映射。所以底层可以使用位图， 如下：

	template<size_t n, class type = string, class HF1 = BKDRHash<type>, class HF2 = DJBHash<type>, class HF3 = APHash<type>>class BloomFilter {public://不需要构造函数private:bitset<n> _bits;};

//布隆过滤器的接口——set（建立映射关系）、test（查看该数据是否存在， 存在不准确， 不存在准确）

	template<size_t n, class type = string, class HF1 = BKDRHash<type>, class HF2 = DJBHash<type>, class HF3 = APHash<type>>class BloomFilter{public://不需要构造函数, 自动调用位图的构造函数//set就是利用三个哈希函数， 分别在位图上面映射一次。void set(type x){int hash1 = HF1()(x);int hash2 = HF2()(x);int hash3 = HF3()(x);_bits.set(hash1);_bits.set(hash2);_bits.set(hash3);}bool test(type x) {int hash1 = HF1()(x);int hash2 = HF2()(x);int hash3 = HF3()(x);//只有当三个位置都是映射过的， 这个数据才可能被映射过。但只要有一个没有映射过， 那么这个数据就一定没有映射过 if (_bits.test(hash1) && _bits.test(hash2) && _bits.test(hash3)) return true;return false;}private:bitset<n> _bits;};

以上， 就是海量数据处理方面相关的知识点。