哈希函数、Map-Reduce与Hadoop

哈希函数

哈希函数又叫散列函数，哈希函数的输入域可以是非常大的范围，比如任意字符串，但是输出域是固定范围，假设为s。
哈希函数的性质：

1. 典型的哈希函数都拥有无限的输入值域。
2. 输入值相同时，返回值相同，通常将返回值称为哈希值。
3. 输入值不同时，返回值可能相同，也可能不同。
4. 不同输入值得到的哈希值，整体均匀的分布在输出域s上。（重要）
   性质1,2,3是哈希函数的基础，性质4是评价一个哈希函数的关键。不同输入得到的哈希值越均匀的分布在s上，哈希值被认为越优秀。并且这种均匀分布是与输入值出现的规律无关的。
   比如“aaa1”，“aaa2”，“aaa3”，虽然相似，但计算出的哈希值相差巨大。
   如果将所有的哈希值对m取余的话，所有取余后的值也会均匀分布在 0 , … , m 1 0,ldots,m-1 0,…,m1上。
   MD5算法与SHA1算法都是经典的哈希函数算法。

Map-Reduce

1. map阶段，通过哈希函数把大任务分成子任务，同样哈希值的任务会被分到同一个节点上进行处理。
2. reduce阶段，子任务分开并发处理，然后合并结果的阶段。

注意点：

1. 备份的考虑，如果其中一个计算节点坏了，数据需要备份才能保存。那么一份数据需要多少个副本备份才合适。
2. Map-Reduce会生成大量的文件，生成的文件可能在一台电脑的硬盘里存不下，如何分布式存储是一个问题。
3. 如果让这个系统对用户来讲是透明的，让用户在终端使用的感觉与在一台电脑上使用的感觉相同。
4. 任务分配是否均衡，可能出现有的节点负担大，有的节点负担小的情况，跟踪每个任务完成的进程，一旦有任务失败需要想办法重新执行该任务。
5. 多用户权限的控制，防止用户删除或修改系统的重要文件。

用Map-Reduce统计一篇文章中每个单词出现的次数

1. 文章预处理：去掉文章中的标点符号，连字符“-”，缩写处理，大小写转换。
2. 在Map阶段，对每个单词都生成词频为1的记录，例如(dog,1)、(cat,1)。此时一个单词可能有多个词频为1的记录，此时还未进行合并。
3. 通过哈希函数，把所有单词分成若干个子任务，根据哈希函数的性质可知，相同的单词会分配到同一个子任务中。
4. 在Reduce阶段，对相同单词词频进行合并，生成一个记录，然后把所有记录返回，就是整篇文章每一次出现的次数。

常见海量处理题目结题关键

1. 分而治之，通过哈希函数将大任务分流到机器，或将大文件分流为小文件。
2. 常用hashMap或bitMap数据结构。

难点：通讯，时间与空间的估算。

案例一

请对10亿个IPV4的地址进行排序，每个ip只会出现一次。
分析：一个ip地址相当于一个四字节的整数。申请一个大小为 2 32 2^{32} 232的bit类型的数组初始化为 0 0 0，每当遇到一个IPV4就将数组对应位置变为 1 1 1。这样就记录了所有出现过的IPV4，然后再将数组转化为IPV4，就是排序后的IPV4。

案例二

给定10亿个整数，每个整数代表一个人的年龄，请对这10亿人的年龄进行排序。
分析：申请一个大小为200的数组，每出现一个整数，数组对应位置+1，就完成排序了。

案例三

有一个包含20亿个全是32位整数的大文件，在其中找到出现次数最多的数。但是内存限制只有2G。
分析：
通常使用哈希表对每个数进行词频统计，如果key与value都是32位的整数，则2亿条记录就会占用1.6G内存。一次性统计会产生内存超出。
方法：使用哈希函数将大文件中的数据分流，假设分为16个小文件，根据哈希函数的性质，同一种数不能被分流道不同的文件中。因此可以在同一个文件中统计出这种数出现的次数，并且哈希函数对每个小文件的分配也是非常均匀的。选取16个小文件中出现的最多的数再进行比较，可以得到最终结果。

案例四

32位无符号整数的范围是0~4294967295。现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然有没出现过的数。可以使用最多10M的内存，只用找到一个没出现过的数即可，该如何找？
分析：如果用哈希表或者bitMap（500M）都会出现超内存。将 0 0 0~ 2 32 1 2^{32}-1 2321平均分为64个区间，必然有一个区间数量小于 2 32 / 64 2^{32}/64 232/64，找到任意一个这样的区间，然后再该区间内建立bitMap，只需要8M内存。

案例五

某搜索公司一天的用户搜索词汇是海量的，假设有百亿的数据量，请设计一种求出每天最热100词的可行办法。
分析：利用哈希函数进行分流，然后对每个小文件利用哈希表进行词频计数，然后利用小根堆进行前100的排序，然后将每个小文件合并排序，最终选出最热100词。

案例六

工程师常使用服务器集群来设计和实现数据缓存，以下是常见的策略。1. 无论是添加、查询还是删除数据，都先将数据的id通过哈希函数映射为一个哈希值，记为key。2. 如果目前机器有N台，则计算key%N的值，这个值就是该机器所属的数据编号，无论是添加、查询还是删除都是在这台机器上进行。请分析这种缓存策略可能带来的问题，并提出改进方案。
分析：如果增加或删除机器，数据迁移的代价很大。需要根据新机器数，重新计算一遍哈希值，然后再将数据重新划分到新的机器中。
改进：一致性哈希算法
将计算后得到的哈希值想象为一个闭合的环形，一个数据根据id通过哈希函数对应到环中的位置。然后想象有三台机器，根据机器id计算出哈希值，放到环中的对应位置，然后将数据放到顺时针最近的机器进行处理。