大数据介绍

面试中关于大数据的题目有些是和采样结合的题目，其实更适合放在概率的章节，但值得注意的是越来越大的题更注重对map-reduce的理解和掌握，Map-reduce和Hadoop逐渐成为面试的热门。

介绍哈希函数

哈希函数又叫散列函数，哈希函数的输入域可以是非常大的范围，但是输出域是固定范围。假设为s。
哈希函数的性质：
1、典型的哈希函数都拥有无限的输入值域。
2、输入值相同时，返回值一样。
3、输入值不同时，返回值可能一样，也可能不一样。
4、不同输入值得到的哈希值，整体均匀的分布在输出域s上。（重要）
MD5与SHA1算法都是经典的哈希函数算法，了解即可，面试时不要求掌握。

map-reduce

1、Map阶段→把大任务分成子任务。
2、Reduce阶段→子任务并发处理，然后合并结果。
注意点：
1、备份的考虑，分布式存储的设计细节，以及容灾策略。
2、任务分配策略与任务进度跟踪的细节设计，节点状态的呈现。
3、多用户权限的控制。

常见的海量数据处理技巧

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

经典题

• 用map-reduce方法统计一篇文章中每个单词出现的个数
  1、预处理，生成只包含单词的文本
  2、map阶段：1）对每个单词生成词频为1的记录如：（dog，1）、（pig，1），一个单词可能有多个词频为1的记录此时还未进行合并；2）通过哈希函数得到每个单词的哈希值，并根据该值分成若干组任务，每个子任务中包含若干种单词，但同一种单词不会分配进不同的子任务中。
  3、reduce阶段：1）单个子任务中同一种单词的词频进行合并；2）所有记录统一合并
• 排序：请对10亿个ipv4的地址进行排序，每个ip只出现一次
  ipv4的ip数量有42亿多一点
  普通方法：将10亿ip转化为对应的用4个字节32位表示的整数，对这些数排序后再转换为ip地址
  更好的方法：申请长度为2³²的bit类型的数组，其大小约为500m，记为bitmap，将10一个ip转化为相应的整数后，在bitmap中会有对应的位置，将其描黑，表示其出现，最后按顺序遍历bitmap即可，遍历过程中再转回ip地址。
• 请对10亿人的年龄进行排序
  年龄的范围可以认为是0~200间，这样可以用200个桶，采用计数排序就行
• 有一个包含20亿个全是32位整数的大文件，在其中找到出现次数最多的数。但是内存限制只有2G
  通常做法：用hash表做词频统计，但此题需要以每个数作为键，以该数出现的次数作为值创建hash表，所以一条记录需要8个字节存储，一共20亿数据就需要大约16G的内存空间，显然不合适。
  推荐做法：用hash函数对不同的数进行分流，此处假设分流为16个小文件，再利用hash表进行词频统计，找出各自的词频最高的数，再进行比较。
• 32位无符号整数的范围是0~4294967295。现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然有没出现过的数。可以使用最多10M的内存，只用找到一个没出现过的数即可，该如何找？
  如果供hash表做：因为只记录是否出现，不需要记录词频，所以每条记录需要4个字节，一共40亿记录的话需要大约16G，远超题目给的10m
  如果用bitmap做：这里长度为2³²的bit类型数组可以表示42亿多的数，所以此处申请长度为2³²的bit类型数组，该数组的大小大约为500m，也不满足题意
  此题推荐做法：用hash函数对每个整数进行分流，此处需要分流64份，则每份数据用bitmap的话仅仅需512 / 64 = 8m空间。
  对每个区间做词数统计，假设a区间词数小于区间长度，则遍历一次40个数，此时只关注区间a上的数，并用bitmap统计区间a上的数的出现情况，在a区间必定至少有一个数不存在。
• 某搜索公司一天的用户搜索词汇是海量的，假设有百亿的数据量，请设计一种求出每天最热100词的可行办法
  还是用hash函数分流，然后在用hash表做词频统计，如果机器数有限，则需要分流每台机器上的文件，再用hash表做词频统计。
  创建hash表后，可以利用小根堆来进行top100筛选，得到每个小文件排序后的top100，然后再将同一台机器上所有文件的top100通过小根堆或外排得到每台机器上的排序后的top100，最后再通过小根堆或外排得到所有机器也就是所有数据桶的排序后的top100，返回即可。
• 工程师常使用服务器集群来设计和实现数据缓存，以下是常见的策略。1，无论是添加、查询还是删除数据，都先将数据的id通过哈希函数转换成一个哈希值，记为key。2，如果目前机器有N台，则计算key%N的值，这个值就是该数据所属的机器编号，无论是添加、删除还是查询操作，都只在这台机器上进行。请分析这种缓存策略可能带来的问题，并提出改进的方案
  带来的问题：如果增加或删除机器的话，数据迁移的代价太高
  推荐的一致性hash的算法：
  1、将所有的数据id的hash结果看成一个环形。
  2、将所有的机器工具其id计算hash结果，并将其插入到数据hash结果组成的环中
  3、数据处理时，计算某条数据的hash值后，在环中找从这个hash值开始顺时针方向最近的机器即可，那么数据的增删改查都在此机器上进行