哈希处理海量数据

接下来我们将以问题的形式来介绍如何用hash处理海量数据。

1.问题1 （位图）

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

1.1问题分析

100亿个整数，一个整数占用4byte，那么就需要约40G左右的空间来存储。显然常见的map等数据结构无法在运行内存中进行处理。我们会想到之前学的位图，其是用一个bite位来标记数字的两种状态（0表示不存在，1表示存在），但此题中的每个整数可以看成三种状态（00表示不存在，01表示出现一次，10表示出现两次）。

1.2问题解答

方案一：

在位图的基础上，我们利用其原理，对位图的进行改造。我们不再用一个bite位映射一个整数，而是用两个bite位映射一个整数。

方案二：

既然每个数字要两个bite位存储，那么我们可以用两个位图来存储每个数字的信息，bm1存储第一个bite位，bm2存储第二个bite位

2.问题2（位图）

两个文件，各有100亿个整数，我们只有1G的内存，如何找到这两个文件的交集

2.1问题分析

海量数据处理，显然普通的数据结构无法解决，我们考虑用位图来解决问题。一个能代表整形的位图有0.5G的大小

2.2问题解答

方案1：

我们可以利用一个位图来存储文件1的信息，再读取文件2的整数依次在位图中test即可解决问题。

方案2：

我们可以利用位图1来存储文件1的信息，位图2来存储文件2的信息。再将两个位图的bite位按位与，得到的新位图即为交集部分。

3.问题3（布隆过滤器and哈希分割）

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

3.1问题分析

一个query我们可以将其看为字符串，大概有30个字节大小，那么100亿个query就是300-600G的大小，显然常规的数据结构无法解决。我们考虑用bloom_filter来解决近视算法。

3.2问题解决

方案1：近似算法

我们用一个布隆过滤器来存储文件1的信息，再将文件2的信息依次在布隆过滤器中test，如果每个hash都test成功，那么就可能是交集（也有可能误判，将不是交集的判断为交集）。

方案2：准确算法

显然准确算法不能使用bloom_filter，但是这么多数据无法一一放进内存中，我们思考可否将文件切分为小的文件，再放入内存中呢？

上述的算法就是先将A文件均分为小文件，将B文件也均分为小文件，让在内存中用set进行处理。例如A0，先将A0存储到set中，再B0,B1,B2 ...B999中的数据依次在set中查找；接着A1-B0,B1,B2...B999。显然效率实在是太低了。

那如果我们不均分呢？用hash切割呢？

如图，我们在前期切割的时候，不采用均分切割，采用hash切割：依次取出文件中的字符串，利用字符哈希函数，得到hash值%文件个数，得到的结果就是这个数据一个要进的小文件编号。这样就保证了相同的字符串会进入相同的文件中，这样我们只需要将A0与B0在内存中用set处理，A1与B1....

4.问题4（哈希分割）

给一个超过100G的文件，里面存储着ip地址，设计算法找到出现次数最多的ip地址，或者出现次数为top k的地址？

4.1问题分析

处理数据是string，精确查找要求不能使用bloom过滤器，那么我们思考采用划分小文件的方法。

4.2问题解决

我们可以创建1000个小文件，依次编号A0-A999.采用Hash分割，将相同的ip分到同一个文件中。在内存中我们利用map，统计A0文件中的各个ip出现的次数，再利用multimap<int,string>统计出现最多的字符串，在创建一个pair<string,int> max，存储这个字符串。再依次A1-A999，每次更新最多字符串即可。

如果是要topk的字符串，那么我们可以建一个小堆进行数据处理。