海量数据处理
哈希函数
什么是哈希函数
哈希函数又称为散列函数，哈希函数的输入域为无穷大，为输出域是固定大小范围如S。用于将输入域到输出域的映射
哈希函数的特点
- 输入任意或者称输入域为无穷
- 相同的输入值必定得到相同的输出值
- 不同的输入值可能会得到相同的输出值（小概率，因为输入域范围远大于输出域范围，所以必定出现这种情况）
- 不同的输入值，得到的输出值均匀的分布的 哈希函数的输出域S上。（评价一个哈希函数是否牛逼的标准）
常见的哈希函数
MD5、SHA等等
MapReduce
思想
总的来说是一种分治的思想，通过Map操作将海量数据重新映射（类似hash映射）成为一个个更小的数据集合，
然后通过分别对每个小的数据集合进行计算或者处理，得到结果，然后通过reduce操作，将每个小集合的处理结
果进行汇总，从而得到最终的结果。
举个栗子
一百万个单词统计词频率？
Map阶段
首先是map阶段，将一百万个单词通过对每个单词的hash得到哈希值，然后哈希值对n取模，比如说有一百台机器（n = 100），那么一百万个单词将均匀分布（哈希性质）到100台机器中，对每台机器来说，相同的单词必定会聚合到同一台机器，当然由于n太小，同一台机器可能会有不同的单词，但不会存在同一个单词跨机器的情况。
Reduce阶段
每一台机器分别统计词频，然后将100台机器统计的结果进行汇总。
问题1 — 10亿个ipv4的地址进行排序，每个ip只出现一次
方案一分析：
一个ipv4地址由4个字节组成，可以用32位无符号整型来表示，范围为从 0 ~ 2^32 -1 大概42亿个，
10亿个ipv4全部转为无符号整型，会占用 4 * 10亿 = 40亿个字节，约为4G的内存。然后对这10亿个无符号整型
进行排序，然后从小到大依次输出即可。排序还会需要额外的内存占用。
方案二分析：
使用bitmap位图来存储，既然ipv4的范围是42亿，我们可以申请一个包含42亿个bit长度的数组，42亿bit长度大概是 42亿 / 8 = = 512M字节空间，然后我们可以对每个出现过的ipv4转为无符号整型，吧数组中对应offset的位置设置为1即可。最后从头遍历数组，数组每个bit位置为1的ipv4即可。占用内存512M。而且最多可以对42亿个不重复出现的ipv4进行排序。
问题2 – 10亿个年龄进行排序
由于年龄的范围是从 0 ~200的不可能超过这个范围，所以我们可以使用计数排序，开一个200大小的数组计数即可哈哈。
问题3 –29亿个32位整数的大文件，统计出现次数最多的数
方案一：
直接使用hashMap来存储 key为出现的整数，value为次数，由于最大可能为20亿使用int来保存即可，占用4个字节，key也为int占用4个字节，总共需要20 * 8 亿 = 160亿字节大约16g的内存。可能 会导致内存不足。
方案二：
采用分治的思想，类似前面提到的MapReduce思想，将大文件按照哈希分桶到不同的小文件，对每个小文件使用哈希表统计，最后汇总即可。
问题4 – 找出包含在40亿个32位无符号数的文件中未出现过的整数，找出一个即可，内存 < 10M
因为32位无符号整数出现的范围是0~42亿（0 ~ 4294967295），因为必定存数字，没有在文件中出现过，
可以将文件中40亿个数按照大小进行分桶到n个不同的小文件，每个小文件n的范围是 42亿 / N，对于每个小文件，例如第一个，范围应该是0 ~ 42亿 / N - 1， 第二个42亿 / N ~ （42亿 / N + 42亿 / N）。任意找到一个小文件存在没有填满（比如文件范围是0-100，但是文件大小为79 < 100，说明有三十个数字没有出现过）。对这个小文件进行处理，使用bitmap对出现过的数字对应位置设置为1，最后遍历bitmap得到任意一个部位1的位置即可。
对于N个小文件来说，需要的内存空间为： 42亿 / N / 8 <= 10M ，所以 N >=51 。
问题5 – 百亿数据量查找最热点的100个
哈希分桶，使用topK统计每个桶，然后汇总，注意：每隔个桶如果还是数据量太大可以进行进一步划分。
