【声明】 图源：牛客网
基本概念
哈希函数
- 哈希函数又叫散列函数，哈希函数的输入域可以是非常大的范围，但是输出域是固定范围。假设为s。
- 典型的哈希函数都拥有无限的输入值域。
- 输入值相同时，返回值一样。
- 输入值不同时，返回值可能一样，也可能不一样。
- 不同输入值得到的哈希值，整体均匀的分布在输出域s上。（重要）
- 1~3点性质是哈希函数的基础，第4点是评价一个哈希函数优劣的关键。
- 不同输入值得到的哈希值越均匀分布在s上，该哈希函数越优秀。
MD5与SHA1算法都是经典的哈希函数算法。
Map-Reduce
- Map阶段
- 通过哈希函数把大任务分成子任务，哈希函数可以是系统默认的，也可以是用户指定的
- 哈希值的任务会被分配到一个节点上进行处理
- 在分布式系统中，一个节点可能是一台机器，也可能是一个计算节点
- Reduce阶段
- 子任务并发处理，然后合并结果
- 难点：工程上的处理
- 注意点：
- 备份的考虑，分布式存储的设计细节，以及容灾策略
- 任务分配策略与任务进度跟踪的细节设计，节点状态的呈现
- 多用户权限的控制
Map-Reduce应用
案例一
题目
用map-reduce方法统计一篇文章中每个单词出现的个数
分析
- 去掉文章中的标点符号
- 对连字符号
-的处理，如pencil-box（尤其单词在结尾处没写完，用连字符连接的情况） - 对于缩写的处理，如I’m，don’t，It’s，I’d like等等
- 大小写的处理
- map阶段：
- 对每个单词生成词频为1的记录，如(dog,1)、(pig,1)，一个单词可能有多个词频为1的记录，此时还未进行合并
- 通过哈希函数得到每个单词的哈希值，并根据该值分成若干组任务。根据哈希函数的性质可知，单词相同的记录会被分配在一起。
- reduce阶段：
- 每个子任务中相同单词记录进行合并，生成一个记录
- 将所有记录返回即整篇文章的词频统计
- 每个子任务是并行处理的，所以会节省时间
海量处理
常见海量处理题目解题关键
- 分而治之，通过哈希函数将大任务分流到机器，或分流成小文件
- 常用hashmap或bitmap
- 难点：通讯、时间和空间的估算
案例一
题目
请对10亿个IPV4的ip地址进行排序，每个ip只会出现一次
分析
- IPV4的ip数量≈42亿
- 普通方法：
- 将ip地址转换为32位无符号整数，对其进行排序后再转回ip地址的形式
- 更优方法：
- 申请长度为$2^{32}$的bit类型的数组
- 将10亿个ip地址全部变成整数，将其在bitmap上对应的位置描黑即可
- bitmap从0位置开始依次遍历，把描黑位置对应的ip依次还原即可
案例二
题目
请对10亿人的年龄进行排序
分析
- 10亿个年龄分布在[0,200]之间，按计数排序即可
案例三
题目
有一个包含20亿个全是32位整数的大文件，在其中找到出现次数最多的数，但是内存限制只有2G
分析
- 普通方法（直接用哈希记录）
- 利用hashmap记录所有数出现的次数，其中
key表示具体某一种数，value表示这种数出现的次数 
- 缺点：会导致内存不足
- 利用hashmap记录所有数出现的次数，其中
- 哈希分流
- 使用哈希函数进行分流，将大文件分成多个小文件，假设为16个小文件
- 哈希函数性质决定同一种数不会被分流到不同文件上
- 哈希函数对不同的数分配均匀
- 对每个小文件用哈希表来统计每个整数出现的次数
- 各自选出每个小文件出现次数最多的数，再从这些数中选出最大的那一个即可
案例四
题目
32位无符号整数的范围是0~4294967295。现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然有没出现过的数。可以使用最多10M的内存，只用找到一个没出现过的数即可，该如何找？
分析
20亿个32位整数的大文件
- 方法一
- 如果用
哈希表来记录所有的数，最差情况下，将出现40亿个不同的数。 - 每一条记录占有4字节，大约需要16G内存
- 如果用
- 方法二
- 利用
bitmap，每个位置为1bit，只能表示0或1两种状态，大约占500M空间。 
- 利用
- 方法三
- 将[0,$2^{32}-1$]范围分成64个区间，单个区间可容纳$2^{32}/64$个数
- 总共的范围为42亿，但数一共为40亿，所以必然会有区间计数不足$2^{32}/64$
- 选择一个计数不足的区间，遍历该区间，并用bitmap统计此区间上的数的出现情况
- 此时占用差不多8M空间
- 总结
- 根据内存限制决定区间大小，根据区间大小，得到有多少个变量，来记录每个区间的数出现的次数
- 统计区间上的数的出现次数，找到不足的区间
- 利用bitmap对不满的区间，进行这个区间上的数的词频统计，找到没出现过的数即可
案例五
题目
某搜索公司一天的用户搜索词汇是海量的，假设有百亿的数据量，请设计一种求出每天最热100词的可行办法。
分析
- 利用哈希函数进行分流，将包含百亿数据量的词汇文件分流到不同的机器上（机器数目视具体情况而定）
- 对每台机器而言，如果分到的词汇量依然很大，比如内存不足或其他问题，可以再根据哈希函数将每台机器上的分流文件拆成更小的文件来进行处理。
- 处理每一个小文件，得到每个小文件词汇的词频统计
- 哈希表建立记录，然后遍历哈希表，使用大小为100的小根堆来选出每个小文件的top100
- 每个小文件都有自己词频的小根堆，将小根堆里的词按照词频排序，得到每个小文件排序后的top100
- 然后将各个小文件排序后的top100进行外排序，或者继续利用小根堆就可以选出每个机器上的top100
- 不同机器之间的top100可以再根据外排序或继续利用小根堆求出总体数据的top100
案例六
题目
工程师常使用服务器集群来设计和实现数据缓存，以下是常见的策略：
1、无论是添加、查询还是删除数据，都先将数据的id通过哈希函数转换成一个哈希值，记为key。
2、如果目前机器有N台，则计算key%N的值，这个值就是该数据所属的机器编号，无论是添加、删除还是查询操作，都只在这台机器上进行。
请分析这种缓存策略可能带来的问题，并提出改进的方案。
分析
潜在问题：如果增加或删除机器，数据迁移的代价很大
当机器数N发生变化时，所有数据必须重新计算哈希值，以及对新的机器数M取余，来决定各自数据的归属，导致大规模的数据迁移。
一致性哈希算法（很好的数据缓存设计方案）
- 假设数据id通过哈希函数转换成的哈希范围是[0,$2^{32}$]
- 将这些数字首尾相连成一个闭合的环形，数字id在计算完哈希之后可以对应到环中的某个位置
- 假设有三台机器也处在这个环中，这三台机器在环中的位置根据机器id计算出哈希值来决定
- 一条数据确定归属于哪台机器的方法：
- 首先该数据的id用哈希函数算出哈希值，并映射到环中相应的位置上
- 之后顺时针找寻离这个数据位置最近的机器，此机器即这个数据的归属
- 添加一台机器的处理方式：
- 假设有两台机器m1和m2，三个数据data1、data2和data3，数据和机器的机构如下图所示
- 如果此时计算出m3的id，并计算出m3处在m1和m2右半侧的环中，在未添加m3之前，从m1到现在m3这一段由m2来掌管，再添加m3之后则统一归属在m3上，同时将这一段的旧数据从m2迁移到m3上。添加机器时的调整代价和数据迁移代价较小。
- 删除一台机器的处理方式：
- 将删除机器的数据全部复制到顺时针的下一台机器即可。如下图所示：
