大数据求交集和并集处理

结合网上面试的实例，下面分三种情况考虑：参考BitMap 详解、算法系列-大数据面试题-两个大文件中找出共同记录

**情况一、**有40亿个无序int类型的整数，再给一个新的整数，我需要判断新的整数是否在40亿个整数中，你会怎么做？

解法一、最常规直观的解法，就是使用一个HashSet，将所有数都add进去，然后对要判断的数，执行一下contains函数判断下就ok了。
但是这个HashSet会占用多少内存呢？

40亿*4Byte=40亿*4/1024/1024/1024G=14.9G空间

这需要一个很大的内存空间来处理，那么如果只有2G的内存空间呢？

解法二、BitMap
我们申请一个Bit数组，数组的每个元素，都能表示0或者1，数组的长度为2^32。
由于一个整数占4字节，所以一个无符号整数，取值范围是0 ~ (2^32 - 1)。
因此，对于40亿整数中的任何一个数，都可以对应放进这个数组里面。

例如:假设40亿的整数分别为 4，7，1，5，9 …
然后，对于40亿中的每个整数，我们都将这个整数作为下标，把数组中对应的位置为1。

而这个数组占用的空间大小为：

2^32 Bit = 2^32 (Bit) / 8 (Byte) / 1024 (KB) / 1024 (M) = 512M

这时，我们想要判断一个整数是否在这40亿整数中，我们只需要直接在数组中，取该数字下标的值。
对于该问题，利用BitMap，我们可以将计算时，近15G的空间占用，变成512M。而时间复杂度不变，依然是O(N)。

情况二、有两组40亿的整数，分别求出这两组数的交集和并集
类似上述解法二、构建两个BitMap，直接进行按位与和按位或操作。这样只需要512M*2的空间。也是可以接受的。

情况三、给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url?
hash+分治思想

（1）首先我们最常想到的方法是读取文件a，建立哈希表（为什么要建立hash表？因为方便后面的查找），然后再读取文件b，遍历文件b中每个url，对于每个遍历，我们都执行查找hash表的操作，若hash表中搜索到了，则说明两文件共有，存入一个集合。
（2）但上述方法有一个明显问题，加载一个文件的数据需要50亿*64bytes = 298G远远大于4G内存，何况我们还需要分配哈希表数据结构所使用的空间，所以不可能一次性把文件中所有数据构建一个整体的hash表。
（3）针对上述问题，我们分治算法的思想。

**step1：**遍历文件a，对每个url求取hash(url)%1000，然后根据所取得的值将url分别存储到1000个小文件(记为a0,a1,…,a999，每个小文件约300M)，为什么是1000？主要根据内存大小和要分治的文件大小来计算，我们就大致可以把298G大小分为1000份，每份大约300M（当然，到底能不能分布尽量均匀，得看hash函数的设计）

**step2：**遍历文件b，采取和a相同的方式将url分别存储到1000个小文件(记为b0,b1,…,b999)（为什么要这样做?
文件a的hash映射和文件b的hash映射函数要保持一致，这样的话相同的url就会保存在对应的小文件中，比如，如果a中有一个url记录data1被hash到了a99文件中，那么如果b中也有相同url，则一定被hash到了b99中）
所以现在问题转换成了：找出1000对小文件中每一对相同的url（不对应的小文件不可能有相同的url）

**step3：**因为每个hash大约300M，所以我们再可以采用（1）中的想法