解析海量数据难题

海量数据高频(topK)问题

解决思路：

1. 分而治之，进行哈希取余；
2. 使用 HashMap 统计频数；
3. 求解最大的 TopN 个，用小顶堆；求解最小的 TopN 个，用大顶堆。

高频(topK)问题如：

• 有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。

  方案：顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为x0,x1,...x4999）中。这样每个文件大概是200k左右。
  
  如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。
  对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用trie树/hash_map等），并取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100个词及相应的频率存入文件，这样又得到了5000个文件。下一步就是把这5000个文件进行归并（类似与归并排序）的过程了。
  

• 如何找出某一天访问百度网站最多的 IP

• 如何查询最热门的查询串？

  本质也是topK问题

  1. 分治法：若文件过大，采用分治法，大文件一直拆分成若干份且其大小可以载入内存，对每个文件，通过一个大小为K的小顶堆或hashMap统计前K个高频字符串，最后用同样的方法(小顶堆/hashmap)对所有文件进行合并得到最终结果。
  2. HashMap：若去重后不超过限制使用的内存，可以装入hashmap统计次数，然后遍历map，用小顶堆得出前K个高频字符串。
  3. 字典树：若文件含有大量相同前缀，可以考虑前缀树，遍历所有字符串时，在前缀树中查找，若找到则该字符串对应的节点出现次数+1，否则新建节点并置1。最后用小顶堆得到前K个高频字符串。

如何从 5 亿个数中找出中位数？

1. 双堆法。一个大顶堆一个小顶堆，保证他们俩堆大小之差不超过1，遍历完最后，两个堆总长度奇数则是某个堆顶元素，为偶数则是堆顶之和除2。

2. 分治法。分为小文件，然后归并排序。

海量数据重复问题

• 如何统计不同电话号码的个数？

  ​ 本质是重复数据问题，电话号码可以当成整数，可以用位图法，省空间

• 如何在大量的数据中判断一个数是否存在

  ​ 给定 40 亿个不重复的没排过序的 unsigned int 型整数，然后再给定一个数，如何快速判断这个数是否在这 40 亿个整数当中？

  ​ 本质是重复数据问题，可以用分治法和位图法。

• 如何在大量的数据中找出不重复的整数

  ​ 分治+hashmap 或 位图法

• 如何从大量的 URL 中找出相同的 URL？

  ​ 给定 a、b 两个文件，各存放 50 亿个 URL，每个 URL 各占 64B，内存限制是 4G。请找出 a、b 两个文件共同的 URL。

  • 分治。首先进行哈希取余(如hash(URL) % 1000)，这样a、b各自分治出来的(1000个)子文件中，可能相同的URL都被分到同一个子文件中了，对子文件进行HashSet统计看是否重复。
  • 布隆过滤器。如果允许一定错误率，可以用BF。4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url（注意会有一定的错误率）。

有500W个QQ号，设计一个合适的数据结构进行储存、查找与维护？

​ 字典树(前缀树)，便于维护，字典树常用与统计字符串数量和查找字符串。

​ 类似的问题还有：10亿个QQ号中快速查找给定的QQ号？ 可以把QQ号当成整数，先排序，后面的查找用二分法时间复杂度都是O(logn)，非常快。

如何从大量的 URL 中找出相同的 URL？

如何按照 query 的频度排序？

​ 有 10 个文件，每个文件大小为 1G，每个文件的每一行存放的都是用户的 query，每个文件的 query 都可能重复。要求按照 query 的频度排序。

​ 本质是排序问题，只不过排序的依据是出现的频次。看是否可以全部载入内存，可以就用hashmap统计，然后排序放到新文件中。内存不足则分治+归并排序。

如何找出排名前 500 的数

​ 有 20 个数组，每个数组有 500 个元素，并且有序排列。如何在这 20*500 个数中找出前 500 的数？

​ 用大小为20的大顶堆，把每个数组最大值存到堆中，每次删除堆顶到结果数组中即可。