# 哈希函数、Map 和 Reduce
哈希函数： 1.无限的输入域 2.输入值相同，输出相同 3.输入值不同，输出可能相同也可能不同 4.不同输入值得到的哈希值，应该整体均匀分布在输出域s上。（重要，评价函数优劣的关键）
对哈希值取余m，得到的结果也均匀分布在0~m-1上
MD5 和 SHA1 都是经典的哈希算法
Map 和 Reduce
- Map 将大任务分成子任务
- Reduce 子任务并发处理，合并结果
# 统计一篇文章中每个单词出现的次数
map-reduce 的思想
- 预处理：取出标点符号、大小写、省略等
- 通过哈希函数确定每个单词分配的子任务，同一种单词不会分进不同的子任务中。分别进行词频统计，然后合并。
- 统计网页上每个单词词频，就大有用处
- 本质是分而治之
# 10亿个IP地址排序，每个地址只会出现一次
关键：只会出现一次，所以可以考虑使用 bitmap 模型。
- IPv4 中规定IP地址长度为32（按TCP/IP参考模型划分) ，即有
2^32-1个地址。 - IPv6 协议的地址长度是128位，全部可分配地址数为2的128次方（2^128）个。
（1）普通方法 IPV4 的 ip 数量大约为42亿，我们要记住2^32约等于 42亿！每个ip需要 4B 来存储，10亿个 ip 全部转换为无符号整数，然后使用快速排序方法，然后把 10 亿个排好序的数字转换为ip地址。需要 4GB 的内存空间！但是有更好的方法。
（2）bitmap方法
申请一个长度为 2^32 的 bit 类型的数组，每个位置上是一个 bit，只可表示0或者1两种状态，空间为 512MB。
每个IP地址转化成无符号整数 k ，数组下标 0~2^32-1 与 k 对应起来。如果 k==1 , 就把 bitmap[0]=1；如果 k==n , 把bitmap[n-1] =1；
如果整数1出现，就把bitmap对应的位置从0变到1，这个数组可以表示任意一个（注意是一个）32位无符号整数是否出现过，
然后把10亿个ip地址全部转换成整数，相应的在bitmap中相应的位置描黑即可，
最后只要从bitmap的零位一直遍历到最后，然后提取出对应为1的下标整数k，再转换成ip地址，就完成了从小到大的排序。空间复杂度很小(约512M)，时间复杂度O（n）
1GB = 2^10 Mb = 2^20 kb = 2^30 Byte ≈ 2^33 bit 而 2^30 = 2^10 * 2^10 * 2^10 = 10^3 * 10^3 * 10^3 = 10^9 所以 1GB ≈ 10亿个Byte
# 10亿人的年龄排序
分布在0-200区间，准备201个桶，用一个足够大的数组对这些年龄进行计数排序。
# 10G自然数排列
一个10G的文件，里面全部是自然数，一行一个，乱序排列，对其排序。在32位机器上面完成，内存限制为 2G。
答案：也是用bitmap
# 给定a、b两个文件，各存放50亿个url，每个url各占用64字节，内存限制是4G，如何找出a、b文件共同的url？
分析：我们先来看如果要把这些URL全部加载到内存中，需要多大的空间。 1MB = 2^20 = 10^6 = 100W 1GB = 2^30 = 10^9 = 10亿 50亿 = 5G * 64 Byte = 320G
明显是不可能全部加载到内存中的。我们可采用以下方法解决：
方法1： 采用Bloom filter，假设布隆过滤器的错误率为0.01，则位数组大小m约为输入元素个数n的13倍，此时需要的哈希函数k约为8个。
元素个数：n = 5G 位数组大小：m = 5G * 13 = 65G = 650亿 即需要650亿个bit位才能达到错误率0.01
而我们拥有的内存可容纳bit位个数：4G * 8bit = 32G bit = 320亿，按此实现错误率大于0.01。
方法2：
分别扫描A，B两个文件，根据hash(url)%k(k为正整数，比如k = 1000，那么每个小文件只占用300M，内存完全可以放得下)将url划分到不同的k个文件中，比如a0，a1,....a999;b0，b1，...b999；
这样处理后相同的url肯定在对应的小文件中（a0 vs b0,a1 vs b1,...a999 vs b999）因为相同的url%1000的值肯定相同，不对应的小文件不可能有相同的url；
然后我们只要求出1000对小文件中相同的url即可。比如对于a0 vs b0，我们可以遍历a0，将其中的url存放到hash_map中，然后遍历b0，如果b0中的某个url在hash_map中，则说明此url在a和b中同时存在，保存下来即可。
# 2G内存，一个包含20亿个全是32位整数的文件，找出现次数最多的数
先通过哈希函数，将大文件转为小文件，再用哈希表统计次数
大数据题目往往是通过哈希函数分流，解决内存限制或者其他限制的问题。
# 找出40亿个数中没出现的一个, 10M内存
分析： 首先我们看下40亿个整数大概占用多少内存？
40 * 10^8 * 4B = 16GB
这个明显无法一次性装入内存中。但是，如果我们用计算机中的一位来表示某个数出现与否， 就可以减少内存使用量。比如在一块连续的内存区域，19出现，则将第19位置1。 这个就是Bit Map算法。此时所需内存是：
40 * 10^8 b = 5 * 10^8 B = 0.5GB
但是如果我们只有10MB的内存，明显使用Bit Map也无济于事了。 内存这么小，注定只能分块处理。
- 我们可以将这么多的数据分成许多块， 比如每一个块的大小是2000，那么第一块保存的就是0到1999的数，第2块保存的就是2000 到3999的数……实际上我们并不保存这些数，而是给每一个块设置一个计数器。
- 这样每读入一个数，我们就在它所在的块对应的计数器加1。
- 处理结束之后， 我们找到一个块，它的计数器值小于块大小(2000)， 说明了这一段里面一定有数字是文件中所不包含的。然后我们单独处理这个块即可。【注意该方法仅支持没有重复数字出现的情况！】
- 接下来我们就可以用Bit Map算法了。我们再遍历一遍数据， 把落在这个块的数对应的位置1(我们要先把这个数通过求模，归约到0到
blocksize之间)。 - 最后我们找到这个块中第一个为0的位，其对应的数就是一个没有出现在该文件中的数。
总结：
- 根据内存限制决定区间大小，根据区间大小，得到有多少变量，来记录每个区间的数出现的次数
- 统计区间上的出现次数，找到不足的区间
- 利用
bitmap对不满的区间，进行这个区间上的数的词频统计
# 百亿数据量求最热100词
- 首先用哈希函数分流，分到不同的机器上，若某一机器上文件仍然很大，再用哈希函数拆成更小的文件。
- 处理每一个小文件，得到小文件中词汇的词频统计，用小根堆进行 TOP100 的筛选。
- 再利用小根堆，得到机器上的 top100，不同机器上的 top100 也可以根据外排序或者小根堆实现。
# 为什么是小根堆
起初前100个条数据建立最小堆，堆顶肯定是词频最低的那条，第101条记录过来时和堆顶比较，如果比堆顶小直接pass，反之替换堆顶，重新维持最小堆性质。也就是说堆顶为截止当前位置，词频第100位的那条记录，新记录只要和堆顶比较即可。