对于常见的海量数据处理方法，通常为以下几种，下面的题解也会围绕这几种解法展开
位图 / 布隆过滤器字典树 / 倒排索引外部排序分治 / 哈希切割 + 堆 / 排序
1. 给40亿个不重复的无符号整数，没排过序。给一个无符号整数，如何快速判断一个数是否在这40亿个数中。
当我们看到这样一个题目时，脑海中可能第一时间想到的就是排序 + 二分，但是要知道40亿个无符号整数所占据的内存空间达到了16G，这样的数据是无法放进内存中进行计算的，所以上面的方法无法实现。
我们需要用位图来完成这道题，我们用一个位来表示一个整数，所以40亿个数据也仅仅只占用了500M，然后将所有的数据用直接定址法放入位图中，并将放入的对应位置1。当进行查询时，只要位图的对应位置为1，则说明该数据在这40亿个数据中。
2. 给定100亿个整数，设计算法找到只出现一次的整数？
这道题还是使用位图来解决，但是由于我们需要找到只出现一次的整数，此时对于每一个整数就存在着3种状态(出现0次， 出现1次，出现多次),由于一个位只能表示两种，所以我们需要对位图进行改造，此时变成用两个位来映射一个数据。并且00代表出现0次，01代表出现1次，11代表出现多次。此时占据的空间是1G
但是使用两个位的位图映射稍微有一点麻烦，所以可以考虑使用双位图来进行解决，一个位图就代表着一个位，组合起来就是我们需要的结果。做法如下
当数据第一次出现时位图1对应位置置1，如果位图1为1后再次出现，则将位图2对应位置也置1，此时达到最终状态，对于后面的出现直接忽略。
3.给两个文件，分别有100亿个整数，我们只有1G内存，如何找到两个文件交集？
100亿个整数需要40G的内存，所以我们这里还是使用位图来解决。
方法1：将文件1的整数全部映射到位图中，接着从文件2中读取数据，并在位图中查询该数据，如果数据存在，则说明该数据是交集之一。内存消耗500M。
方法2：将文件1和文件2中的整数分别映射到位图1，位图2中。接着遍历两个位图，对每个位置按位与，如果为1则说明该整数是交集之一，内存消耗1G。
4.位图应用变形：1个文件有100亿个int，1G内存，设计算法找到出现次数不超过2次的所有整数
此时的状态有四种，出现次数为0，出现次数为1，出现次数为2，出现次数超过2。需要用到两个位表示，所以还是使用第二题的双位图来进行解决，00代表1次，01代表2次，10代表2次，11代表多次。消耗内存1G。
5.给两个文件，分别有100亿个query，我们只有1G内存，如何找到两个文件交集？分别给出精确算法和近似算法
query一般为URL中的查询字符串或者SQL中的查询语句，假设每个query30个字节，那么100亿个query也得300G的内存才能装下，而我们只有1G，所以直接放弃装入内存直接比对的做法。
近似算法：对于字符串，也可以采用位图的思路进行对某个字符串进行标记，也就是使用布隆过滤器来进行处理。但是由于数据过多且空间不足，可能会因为映射时映射到了其他数据的比特位上，导致造成误判。所以当一个数据不存在于布隆过滤器中，则它必定不存在，但是如果一个数据存在于布隆过滤器中，它也不一定存在，所以布隆过滤器是近似算法。
精确算法：如果要精确的进行查找，那就必须得将数据放入内存中，但是由于数据过大无法一次性放入，所以我们可以考虑对数据进行切分。切割的方式有两种，哈希切割和平均切割
平均切割：平均切割不是一个很好的方法，但是它确实是我们很容易就能思考到的方法，我们将两个文件中的数据平均切分为M份(能放入内存)，分别存储到一个set中，然后以此将数据进行比较。这种方法就需要以此对所有的数据进行比对，效率会比较低
哈希切割：这时就可以采取哈希切割的思路，使用字符串哈希算法进行哈希映射，映射位置为i，则放入编号为i的文件中，对两个文件都采用这样的做法进行切分，分别为Ai和Bi。
之后，由于我们使用的是同一种字符串哈希算法，所以相同的字符串必定会被映射到同一个编号下的文件中，所以我们只需要依次进入编号相同的Ai和Bi文件中寻找交集即可。
6.给一个超过100G大小的log file, log中存着IP地址, 设计算法找到出现次数最多的IP地址？ 与上题条件相同，如何找到top K的IP？如何直接用Linux系统命令实现？
统计次数我们首先想到的方法就是使用键值对的方式，将每一个string的ip地址与出现次数相关联，pair<string, int>，然后使用KV模型的Map进行存储。但是由于数据超过100个G，内存中无法直接存下，所以我们需要对数据进行切割。
我们可以使用哈希切割的方式来解决文件分片的问题。相同的IP地址必定会被映射到同一个文件中，所以我们依次读取文件，使用Map进行次数统计即可。
之后再进行排序即可
Linux的命令如下
sort log_file | uniq -c | sort -nr | head -k
首先使用sort log_file来将数据进行一个排序，使得相同的IP地址全部靠在一起。接着使用uniq - c进行去重，并将重复的次数显示在每列的旁边，通过这个次数来使用sort -nr进行降序排序，使得出现次数最的IP地址在前面，然后使用head -k获取前k个IP地址即可。
7.100w个数中找出最大的100个数
由于100w个数据并不算多，可以存放进内存中，所以可以考虑以下解法
方法1：采用快排中的partition划分思想，即单趟划分后，枢轴s前面的数据都比他大，后面的数据都比他小，此时我们选取其中较大的那一部分，继续划分。当划分后前端的数据刚好等于100后划分结束，对前端数据进行排序即可得到结果。如果前端数据不足100，则从后端数据进行排序后取出不足的那部分补上，再进行排序即可。O(100w*100)
方法2：局部淘汰法，使用一个大小为100的小堆来完成，维护一个小堆，当数据比堆顶也就是最小值大的时候，用新数据替换掉堆顶，然后调整堆的结构。遍历完所有数据后就可以得到前100的数据。O(100w*lg100)
方法3：局部淘汰法，使用插入排序来完成，首先取出前100个数据进行排序，然后依次遍历后面的数据，如果数据大于最小值，则将最小值删除，然后按照插入排序的思路将数据插入进去。
O(100w*100)
8.海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。
解法与上一题类似，可以使用堆来完成
对于每一个电脑，都构建一个大小为10的堆(选大的构建小堆，选小的构建大堆)，选出当前电脑的TOP10。接着将所有电脑的数据汇总起来，共1000个数据，继续用堆从其中选出TOP10
9.给上千个文件，每个文件大小为 1K—100M。给 n 个词，设计算法对每个词找到所有包含它的文件，你只有 100K 内存
这题可以使用倒排索引来解决，即建立起单词——文件的映射。
很简单，只需要遍历所有文章，如果文章中出现过查询词，则将文件号追加在对应词的倒排拉链中即可。如果100M的文件放不下内存中，就对数据进行切割后处理即可。
如果觉得《海量数据处理（二） ：常见海量数据处理方法》对你有帮助，请点赞、收藏，并留下你的观点哦！
