海量数据处理问题

一、方法论

对于字符串数据，可以对字符串进行哈希，哈希值%n(n为分文件数量)，这样来说同一个字符串必然分配到一个文件当中，然后如果哈希均匀的话，就能够保证每个文件可以放入内存当中，在内存当中采用通用方法进行处理获得每个文件的结果，然后写到磁盘中，最后汇总或者直接在内存中汇总。
对于数字，可以直接x%n（n为分文件数量）或者采用二进制前k位来分成2^k个文件块。

判断一条记录在另一个记录集合中是否存在。具体操作时，对于记录集合S中的n条记录，设置m位的bitmap和k个独立hash函数，遍历S集合，对于每条记录，将其k个hash函数值对应位置1。要判断一条记录是否存在时，查看其k个hash函数值对应位是否都是1，如果是，就认为存在，否则就不存在。bloom filter对于有hash函数值为0的，那么就可以100%确定这条记录不存在，但是可能把不存在的误判成存在的。但是这样的概率很小。
m应该>=nlg(1/E)lge 大概就是nlg(1/E)1.44倍，当hash函数个数k=(ln2)(m/n)时错误率最小。
Counting bloom filter（CBF）将位数组中的每一位扩展为一个counter，从而支持了元素的删除操作。counter可以记录hash值对应到该counter的次数

外部排序是针对海量数据无法放入内存中排序而产生的一种排序算法。基本算法是拆分成多个小文件，每个小文件可以放入内存当中，对于小文件进行排序后，再采用多路归并排序，也就是构造一个大小为文件块数的堆（升序就是小堆，降序就是最大堆），先分别从k个文件中读取一个数插入堆中，将堆顶元素写到文件中，然后从写出元素所在文件中再读入一个数，依次进行下去。
适用范围：大数据的排序，去重

方法一:
1. 分而治之/哈希映射：读取ip，划分成n个文件根据hashCode%n值，分划到相应的文件当中
2. 哈希统计：对于每个文件，可以读入内存，hashmap统计ip次数（注意一个ip只会出现在一个文件当中），然后通过排序或者遍历获得最大次数的ip。
3. 汇总：获得每个文件中出现次数最多的ip，进行堆排或者快排或者扫描，就可以获得出现次数最多的ip。
方法二：
trie树，用第k叉表示ip的一部分（ip可以分为四部分）。叶结点值可以存放ip次数。

寻找热门查询，300万个查询字符串中统计最热门的10个查询
300万个字符串如果可以放进内存存储为hashmap，那么就不用分而治之/哈希映射了。
哈希统计：hashmap统计每个字符串出现次数
堆排序：简历大小为10的小顶堆，堆元素为键值对，键为字符串，值为字符串出现次数，遍历hasmap或者读入文件流，遇到键值对的值大于堆顶元素值，就插入堆，并且删除堆顶键值对。遍历完毕后就可以获得top k查询结果。
trie树加大小为10的最小堆的方法也能够解决
在10G数据中，数据类型为uint32，内存1G，寻找其中重复出现的数字
方法一、分而治之/哈希映射：根据uint32前4位将数据分成2^4个文件块
哈希统计：hashmap统计每个文件块中重复出现的数字
汇总：将每个文件快重复出现的数字直接并起来
方法二、 bitmap
uint32为2^32次方，对于每个数用一个bit记录是否出现，如果出现，就置该bit为1，如果发现该bit位已经为1，那么就直接将该数写到文件中，说明已经出现过。这种方法效率很高，但是如果可用内存更小或者改成uint64，那么就不行了。
海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。

如果每个数据只在一台电脑上出现，那么求出每台电脑的TOP10，再进行汇总。
遍历一遍所有数据，重新hash取摸，如此使得同一个元素只出现在单独的一台电脑中，然后采用上面所说的方法，统计每台电脑中各个元素的出现次数找出TOP10，继而组合100台电脑上的TOP10，找出最终的TOP10。
或者，暴力求解：直接统计统计每台电脑中各个元素的出现次数，然后把同一个元素在不同机器中的出现次数相加，最终从所有数据中找出TOP10。

给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
将a,b两个文件中的url经哈希分散到a[1000]个子文件中和b[1000]子文件中后，文件 $a_i$ 与 $b_i$ 放入内存取交集即可。
怎么在海量数据中找出重复次数最多的一个？
先做hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个,然后求所有文件中最大的重复次数。

对于固定大小的海量数据，通用做法就是分文件hash+内存处理（堆/快速/归并排序）+汇总方法解决。可以一次性放进内存中处理的做法有bitmap，trie树。