大数据算法

先导 – 哈希算法

• 哈希函数，在于将输入映射到一定范围的输出，核心在于输出域的分布是否均匀。
• MD5,SHA都是经典的哈希函数算法实现

Map-Reduce

• 过程
  1. Map阶段（hash）：把大任务划分为小任务
  2. Reduce阶段：把结果合并
• 注意点：
  1. 备份的考虑
  2. 任务分配策略与任务进度跟踪
  3. 多用户权限的控制

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

1. 分而治之：通过哈希函数将大任务分流到及其，或分流成小文件。
2. 常用的hashMap或bitMap
   难点：通讯、时间和空间的估算

题目

1. 对10亿个IPV4的ip地址进行排序，每个ip只会出现一次。
   IPV4的ip数量约为42亿
   申请长度为2^32的bit类型的数组，bitmap。
   如果整数1出现，就把bitmap对应的位置从0变到1，这个数组可以表示任意一个（注意是一个）32位无符号整数是否出现过，然后把10亿个ip地址全部转换成整数，相应的在bitmap中相应的位置描黑即可，最后只要从bitmap的零位一直遍历到最后，然后提取出对应为1的下标整数k，再转换成ip地址，就完成了从小到大的排序。空间复杂度很小，时间复杂度O（n）
2. 10亿个年龄进行排序—-桶排序
   建立0到200个桶表示年龄从0到200，然后将10亿数据入桶，再依次倒出
3. 有一个包含20亿个全是32位整数的大文件，在其中找到出现次数最多的数，内存限制为2g
   通过哈希函数不断分流，分流到16个文件中，对每个小文件用哈希表来进行处理，全部处理完成后，得到16个文件中各自的第一名，再选出16个中的第一名

一致性哈希算法

通过哈希函数后的值首尾相连成一个圆，数据hash之后对应在圆上的一个位置，机器也处在这个圆上（根据机器id计算出哈希值），数据hash之后顺时针找离它的哈希值最近的机器