今天分享几道常见的海量数据面试题，看完这几道就能融汇贯通了
文章目录
海量数据相关的面试题主要是考察数据量比较大，内存不足时数据的处理方式，规律性还是很强的，其实简单来说就是分治，将大的数据分成多个小的数据，分别进行处理。
需要先掌握的一些基本概念
题目的隐藏含义就是海量日志数据不能一次读取到内存中，否则直接用HashMap统计IP出现的频率（IP为key，频率为Value），然后按照频率排序就好了。
这道题的做法是先对文件遍历一遍，将一天访问百度的IP记录到一个单独的文件，如果这个文件还是很大，可以对IP进行hash取余，将IP映射到多个文件中，然后利用HashMap统计每个文件中IP的频率，分别找到每个文件中频率最高的IP，再从这些IP中找到整体频率最高的IP。
如果是频率最高的前N个怎么办？这时可以在利用HashMap统计每个文件中IP的频率后，维护一个小顶堆，找到TopN。具体方法是：依次遍历每个小文件，构建一个小顶堆，堆大小为 N。如果遍历到的IP的出现次数大于堆顶IP的出现次数，则用新IP替换堆顶的IP，然后重新调整为小顶堆，遍历结束后，小顶堆上的词就是出现频数最高的 N 个IP。
注：TopN问题在手写代码也是高频题，需要重点掌握，比如力扣215题：https://leetcode.cn/problems/kth-largest-element-in-an-array/comments/
题目详细描述：搜索引擎会通过日志文件把用户每次检索使用的所有查询串都记录下来，每个查询床的长度不超过 255 字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门），请你统计最热门的10个查询串，要求使用的内存不能超过1G。
这也就是热榜的简单实现，当然实际的热榜会复杂很多，毕竟还要考虑一部分人要撤热搜或降热度等需求。
方法一：分治+HashMap
还是前面的老方法，先用Hash映射将查询字符串映射到多个小文件中，然后用HashMap统计每个小文件中查询字符串出现的频率（key为热门字符串，value为频率），找到每个小文件中的频率最高的top10，最后通过一个小顶堆统计所有小文件中的top10。
方法二：直接用HashMap
题目中写道，去重后只有300w条数据，每条查询不超过255字节，一共是700多M，小于1G。所以可以直接遍历查询字符串，并存入到HashMap中（key为热门字符串，value为频率），通过小顶堆找到频率最高的top10
方法三：前缀树
只是把方法二中的HashMap换成了前缀树，在遍历字符串时，在前缀树中查找该字符串，如果找到，则将节点中保存的当前前缀的次数加1，没有找到，则为这个字符串构建新结点，并将新构建的结点中的次数置为1。最后还是通过小顶堆找到频率最高的top10
方法还是前面的分治+HashMap+小顶堆
首先遍历文件，对每个词进行hash，比如hash(x)%5000，将所有词分别存入到5000个小的文件中，每个文件大概200k左右，然后通过HashMap统计每个小文件中词的频率（key为词，value为频率）。对于每个遍历到的词，如果在HashMap中，则将value值加1，不在HashMap中，则将词存入HashMap，并将值置为1。最后构建小顶堆，堆的大小为100，找到频率最高的100个词。
本题和前面的大同小异，首先遍历这10个文件，对每个query进行Hash映射，将这些query重新映射到10个文件，这是为了保证相同的query都在同一个文件中，然后在每个文件中分别使用HashMap统计query的频率，分进行排序，最后通过归并排序将所有文件中的query进行排序
每个url是64字节，50亿*64大约等于300多G，内存限制为4G，所以不能直接放入内存中。
还是前面的分治思路，遍历文件a中的url，对url进行hash(url)%1000，将50亿的url分到1000个文件中存储（a0，a1，a2.......），每个文件大约300多M，对文件b进行同样的操作，因为hash函数相同，所以相同的url必然会落到对应的文件中，比如文件a中的url1与文件b中的url2相同，那么它们经过hash(url)%1000也是相同的。即url1落入第n个文件中，url2也会落入到第n个文件中。
第二步是遍历a0中的url，存入HashSet中，同时遍历b0中的url，查看是否在HashSet中存在，如果存在则保存到单独的文件中。然后以此遍历a2，a3，a4.........，b2，b3，b4.........
方法一：分治法
先将2.5已个整数通过hash取余，存到多个文件中，这时相同的整数会存入同一个文件。第二步是通过HashMap统计每个小文件中整数出现的频率（key为整数，value为频率），将所有value为1的整数存到单独的文件中，即为不重复的整数
方法二：位图法
如果对布隆过滤器有了解的同学一定记得位图是什么，布隆过滤器在面试中也是经常问到的，下面简答说下什么是位图
简单来说，位图就是，用每一位来存放某种状态，通常是用来判断某个数据存不存在的。位图可以用数组实现的，数组的每一个元素的每一个二进制位都可以表示一个数据在或者不在，0表示数据存在，1表示数据不存在。如下，表示0-6中的元素，0-6中只有7个数，所以用7bit足以表示，例如5可以表示为
[0,0,0,0,0,1,0]那为什么要使用位图，使用位图有什么好处呢？
使用位图可以大大缩短存储空间，一个int占用4byte，1byte=8bit，也就说本来4byte只能存1个整数，而现在4type可以存32个整数。
回到本题，要找出不重复的整数，那么一个整数可以有三种状态，即不存在、存在1次、存在多次，根据题目需要找出的是存在1次的
对于三种状态只用0或1肯定是表示不了的，所以可以用两位来表示整数的状态，00表示不存在，01表示存在1次，10表示存在多次。
具体做法，首先遍历 2.5 亿个整数，查看对应位图中对应的位，如果是 00，则变为 01，如果是 01 则变为 10，如果是 10 则保持不变。最后遍历位图，找出01对应的整数，即为2.5亿整数中只出现一次的整数
可以用分治法，然后遍历一遍，查看这个数是否在40亿个数中
不过这种判断某个数据是否存在，用位图法更合适，40亿个不重复的数需要40亿个bit，大约需要内存500多M，申请一个数组，遍历40亿个数，将对应的bit设置为1，然后查看需要查询的数的bit，如果为1，则表明在40亿个数中，如果为0，则表示不在40亿个数中。
很明显，还是使用位图法最为简便，每个号码八位数，不考虑实际情况，一共有种情况，也就是需要位bit，大约需要内存100M。申请一个数组，遍历所有号码，将号码对应的bit置为1，最后统计bit位1的数量即为不同的号码数。
中位数是按顺序排列的一组数据中居于中间位置的数，如果观察值有偶数个，通常取最中间的两个数值的平均数作为中位数。
如果题目没有内存限制，只需将5亿个数直接读取到内存中，然后排序，找到中间的数即可
但排序的时间复杂度最快也得O(NlogN)，想用空间换时间有没有什么好办法呢？
当然是有的，请看力扣295题（数据流的中位数），https://leetcode-cn.com/problems/find-median-from-data-stream/
为了方便，这里贴出了一个高赞题解，原链接：https://leetcode-cn.com/problems/find-median-from-data-stream/solution/gong-shui-san-xie-jing-dian-shu-ju-jie-g-pqy8/
我们可以使用两个优先队列（堆）来维护整个数据流数据，令维护数据流左半边数据的优先队列（堆）为 l，维护数据流右半边数据的优先队列（堆）为 r。
显然，为了可以在 O(1) 的复杂度内取得当前中位数，我们应当令 l 为大根堆，r 为小根堆，并人为固定 l 和r之前存在如下的大小关系：
当数据流元素数量为偶数：l 和 r 大小相同，此时动态中位数为两者堆顶元素的平均值；当数据流元素数量为奇数：l 比 r 多一，此时动态中位数为 l 的堆顶原数。为了满足上述说的奇偶性堆大小关系，在进行 addNum 时，我们应当分情况处理：
插入前两者大小相同，说明插入前数据流元素个数为偶数，插入后变为奇数。我们期望操作完达到「l 的数量为r多一，同时双堆维持有序」，进一步分情况讨论：
如果 r 为空，说明当前插入的是首个元素，直接添加到 l 即可；如果r不为空，且 num <= r.peek()，说明 num 的插入位置不会在后半部分（不会在r中），直接加到l即可；如果 r 不为空，且 num > r.peek()，说明 num 的插入位置在后半部分，此时将 r 的堆顶元素放到 l 中，再把 num 放到 r（相当于从r中置换一位出来放到l中）。插入前两者大小不同，说明前数据流元素个数为奇数，插入后变为偶数。我们期望操作完达到「l 和r数量相等，同时双堆维持有序」，进一步分情况讨论（此时l必然比 r 元素多一）：
如果 num >= l.peek()，说明num的插入位置不会在前半部分（不会在 l 中），直接添加到 r 即可。如果 num < l.peek()，说明 num 的插入位置在前半部分，此时将 l 的堆顶元素放到 r 中，再把 num 放入 l 中（相等于从 l 中替换一位出来当到 r 中）。
Java代码
class MedianFinder { PriorityQueue l = new PriorityQueue<>((a,b)->b-a); PriorityQueue r = new PriorityQueue<>((a,b)->a-b); public void addNum(int num) { int s1 = l.size(), s2 = r.size(); if (s1 == s2) { if (r.isEmpty() || num <= r.peek()) { l.add(num); } else { l.add(r.poll()); r.add(num); } } else { if (l.peek() <= num) { r.add(num); } else { r.add(l.poll()); l.add(num); } } } public double findMedian() { int s1 = l.size(), s2 = r.size(); if (s1 == s2) { return (l.peek() + r.peek()) / 2.0; } else { return l.peek(); } }} 时间复杂度：addNum 函数的复杂度为 O(logn)；findMedian 函数的复杂度为 O(1)空间复杂度：O(n)
当然如果内存不足怎么办，不能把数据全部放入内存
还是之前的老办法，分治法。但是这道题不能用hash映射的方法分流，因为这是无序的，而把数据打乱分散到不同文件中就找不到中位数了，所以需要一种按大小分流的方法。
首先遍历这5亿个数，遍历的时候将每个数转换位二进制，如果最高位为1存入文件1，最高位为0存入文件2，这样文件1中的数是一定比文件2中的小的。因为最高位是符号位，0表示正数，1表示负数
如果恰好文件1和文件2中的数都是2.5亿个，那么中位数则是文件1中的最小值和文件2中的最大值的平均值。
一般不会这么恰好，假设文件1中的数为2亿个，文件2中的数为3亿个，那么中位数是文件中的第五千万个数及下一个数的平均值。
那3亿个数还是不能一次读取进内存要怎么办？
还是使用这个方法根据次高位进行分流，并一直关注位数的位置，直到中位数所在的那部分数据大小可以直接放到内存中，然后对这部分排序，计算出中位数的值
如果本文对你有帮助，别忘记给我个3连 ，点赞，转发，评论，
咱们下期见！答案获取方式：已赞 已评 已关~
学习更多知识与技巧，关注与私信博主（03）
原文出处：https://mp.weixin.qq.com/s?__biz=MzA4NjU1MzA2MQ==&mid=2647726553&idx=1&sn=1858f317ceeaa69a13d4b08cb19765ed&chksm=87e34153b094c8450871160b2c9f56efb3b2207a524aecdb5e31dc4257d0459b473578ef2b4a&scene=178&cur_album_id=1966226418825035778#rd
| 留言与评论（共有 0 条评论） “” |
