牛客网《BAT面试算法精品课》笔记十：大数据

牛客网《BAT面试算法精品课》视频链接：《BAT面试算法精品课》 笔记链接： 牛客网《BAT面试算法精品课》笔记一：排序 牛客网《BAT面试算法精品课》笔记二：字符串 牛客网《BAT面试算法精品课》笔记三：队列和栈 牛客网《BAT面试算法精品课》笔记四：链表 牛客网《BAT面试算法精品课》笔记五：二分搜索 牛客网《BAT面试算法精品课》笔记六：二叉树 牛客网《BAT面试算法精品课》笔记七：位运算 牛客网《BAT面试算法精品课》笔记八：排列组合 牛客网《BAT面试算法精品课》笔记九：概率 牛客网《BAT面试算法精品课》笔记十：大数据 牛客网《BAT面试算法精品课》笔记十一：动态规划 Map-Reduce和Hadoop逐渐成为面试热门 先介绍下哈希函数：[

](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042232-300x226.png)](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042232.png) 优秀的哈希函数：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042233.png) **Map-Reduce：** 1.Map阶段：把大任务分成子任务 2.Reduce阶段：子任务并发处理，然后合并结果 Map-Reduce的难点不在于原理，而在于工程上需要注意的一些问题，比如： 01.备份的考虑，分布式存储的设计细节，以及容灾策略 02.任务分配策略与任务进度跟踪的细节设计，节点状态的呈现 03.多用户权限的控制 用Map-Reduce统计文章中每个单词出现的个数：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042234.png) 获得单词文本后，进入map阶段：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042235.png) Reduce阶段：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042236.png) **常见的海量数据处理技巧：** 01.分而治之，通过哈希函数将大任务分流到机器，或分流成小文件。 02.常用的hashMap或bitmap 难点在于：通讯，时间和空间的估算 **案例一：** 请对十亿个IPV4的ip地址排序，每个ip只会出现一次[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042237.png) 更好的方法：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042238.png) **案例二：** 请对10亿人的年龄排序 年龄在0到200之间，然后用一个数组对这10亿人的年龄进行计数排序就可以了[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042239.png) **案例三：** 有一个包含20亿个全是32位整数的大文件，在其中找到出现次数最多的数，但是内存限制只有2G. 哈希表方法：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042240.png) 使用哈希函数进行分流：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042241.png) **案例四：** 32位无符号整数的范围是0~4294967295，现在有一个正好包含40亿个无符号整数的文件，所以在整个范围中必然有没出现过的数。可以使用最多10M的内存，只用找到一个没出现过的数即可，该如何找？ 哈希表： 如果用哈希表来记录所有的数，最差情况下，将出现40亿个不同的数。每一条记录占有4字节，大约需要16G内存。不符合内存限制 Bitmap方法： [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042242.png) Bitmap也不符合内存限制。 正确方法：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042243.png) 区间a并未占满，所以a区间上肯定少了某个数，再遍历一次40亿个数，此时只关注a区间上的数，并用bitmap统计区间a上的数的出现情况。需要占用的空间为500M/64，也就是8M. 总结：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042244.png) **案例五：** 某搜索公司一天的用户搜索词汇是海量的，假设有百亿的数据量，请设计一种求出每天最热100词的可行办法。 哈希分流：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042245.png) **案例六：** [](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042246.png) 分析：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042247.png) 一致性哈希算法：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042248.png) 顺时针：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042249.png) 添加一个机器m3：[](http://www.wjgbaby.com/wp-content/uploads/2018/04/18042250.png) [