常见海量数据处理的关键
1、分而治之。通过哈希函数将大人物分流到机器，或分流成小文件
2、常用的hashMap或bitMap
难点：通讯、时间、空间的估算
哈希函数：
哈希函数又叫散列表，哈希函数的输入可以使非常大的范围，但是输出与是固定范围。假设为S。
性质：
- 典型的哈希函数都拥有无限的输入值域
- 输入值相同时，返回值一样
- 输入值不同时，返回值可能一样，也可能不一样
- 不同输入值得到的哈希值，整体均匀的分布在输出域S上（重要）
不同输入值得到的哈希值越均匀分布在S上，该哈希函数越优秀。
MD5算法与SHA1算法都是经典的哈希函数算法。
Map-Reduce：
1、Map阶段：通过哈希函数把大任务分成子任务
2、Reduce阶段：子任务并发处理，然后合并结果。
难点在于工程商的处理
注意点：
* 备份的考虑，分布式存储的设计细节，以及容灾策略
* 任务分配策略与任务进度跟踪的细节设计，节点状态的呈现
* 多用户权限的控制
示例1
统计一片文章中每个单词出现的个数
示例2
请对10亿个ipv4的ip地址进行排序，每个ip只会出现一次。分析：ipv4的数量大约为42亿，大约为2^32
做法：
申请一个长度为2^32的bit类型的数组(每位是一个bit，只可表示0或1两种状态)，该数组大约占用空间为512M
示例3
对10亿个人的年龄进行排序分析：由于人的年龄大约在0-200之间，故，可以建立一个长度为200的数组，然后按照计数排序进行排序。
示例4
有一个包含20亿个全是32位整数的大文件，在其汇总找到出现次数最多的数，但是内存限制在2G
同一种数不会被分流到不同的文件，这是哈希函数性质决定的
对于不同的数，每个文件中含有整数的种数几乎一样，这也是哈希函数性质决定的
然后用哈希表统计每一个小文件中每种数出现的次数，统计之后得到16个小文件中各自出现次数最多的数，以及该数对应出现的次数
然后对这16个第一名进行对比，得到第一名中的第一名。
示例5
32位无符号整数的范围是0-4294967295.现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然有没出现过的数。可以使用最多10M的内存，只用找到一个没出现过的数即可，该如何找？分析 将0 - 2^32-1范围分成64个区间，那么每个U期间应该装下2^32/64个数
由于总范围42亿大于需要装的数40亿，所以必然出现有些区间计数不足2^32/64。
假设区间A计数不足2^32/64
此时对40亿个数进行遍历，但是只关注落在区间A上的数，并用bitMap统计区间A上的数出现情况。则可以找到这个缺失的数
使用的空间大小为512M/64 = 8M < 10M
总结
* 根据内存限制决定区间大小，根据区间大小，得到有多少个变量，来记录每个区间的数出现的次数。
* 统计区间上的数出现次数，找到不足的区间
* 利用bitMap对不满的区间进行这个区间上的数的词频统计
示例6
某搜索公司一天用户搜索词汇是海量的，假设有百亿的数据量，请设计一种求出每天最热100词的可行办法
分析
根据需求可以对搜搜词汇进行分流、二次分流、三次分流等（假设是三次分流）
然后对每一个分流后的文件进行处理，得到每一个小文件中词频统计，
接着，利用小堆进行TOP100的筛选,，一直回溯到最原始无分流的时候，即找到整体的TOP100
如下图所示，每一次分流都是使用哈希函数进行分流；
先求出M中的一个的TOP100，即并行求出了M个小文件各自的TOP100，然后第一次合并，进而求出一个大的TOP100，
对于N各文件即为并行求出了N个TOP100，
接着对N个TOP100合并求出TOP100，此时的TOP100即为原始数据的TOP100