1.2 如何处理海量数据

1. 什么是海量数据

就是数据量太大，没法一次性加载到内存进行处理

2. 如何处理海量数据

分而治之+合适的数据结构处理【关键点】+合并结果 既然没法一次性加载，那么拆分之后多次加载，选用合适的数据结构处理，最后把结果进行合并

2.1. 怎么分

一行行读取大文件，利用hash+取模分成小文件。

2.2. 怎么选数据结构

思考数据量小的时候会怎么做即可

1. Bloom Filter 用来快速判断一个值是否在集合中，有一定的误判率 适用于数据判重、集合求交集 BloomFilter.md（关联笔记尚未公开）
2. Hash 任意长度的值->固定长度的整型值 适用于划分数据，构造HashMap统计数量、HashSet判断重复等
3. Bit Map 用一个bit表示一个数字，第一个bit代表1，第二个bit代表2……极大的节省空间 适用于排序、判重等
4. 堆 用数组表示一颗二叉树 堆.md（原链接已失效） 适用于取出Top K的数
5. Trie树 用二叉树存储公共前缀 适用于词频统计
6. 外排序 将大文件分成内存能容纳的小文件，对小文件分别进行排序，最后进行归并 适用于大文件排序

2.3. 怎么合并结果

归并算法

3. 例子

3.1. 统计访问量最多的IP【Hash拆分小文件+HashMap】

海量日志数据，提取出某日访问百度次数最多的那个IP

• 分析
  • 先思考数据量不大的场景，Top 1问题可以使用HashMap<IP, 次数>统计次数，然后排序找出次数最大的那个（Top 1可以用选择排序）
  • 问题在于对于IP，有2^32=4G可能，创建4G大小的HashMap不太现实，所以需要拆分
• 解决
  1. 按行读取文件，将文件根据Hash(IP)%1024分散到1024个小文件中。如此每个文件耗费的HashMap最多占用为4G/1024=4M，并且相同的IP必然分到同一个文件中（当然极端情况可能所有IP相同，那么最终只有一个文件，也没问题，毕竟按行读取）
  2. 按行读取每个小文件，利用HashMap统计IP的数量，把数量最多的（IP，count）保存到一个新的HashMap中
  3. 对这个HashMap根据统计数量进行排序，找出数量最多的IP即可

3.2. 统计最热门的10个搜索关键词【HashMap+堆】

搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

• 分析
  • 先思考数据量不大的场景，Top K问题可以使用HashMap<查询串，次数>统计次数，然后排序找出次数最大的K个（TopK可以用堆处理）
  • 由于去重后不超过300w，如果使用HashMap的话耗费内存3000000*255/1024/1024=729.5608520507812M，符合题意
• 解决
  1. 按行读取文件，使用HashMap统计关键词的数量
  2. 对这个HashMap，使用最小堆完成TOP K排序

3.3. 统计频数最高的100个词【HashMap+堆】

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

• 分析
  • 先思考数据量不大的场景，Top K问题可以使用HashMap<查询串，次数>统计次数，然后排序找出次数最大的K个（TopK可以用堆处理）
  • 由于文件大小为1G，而内存限制为1M，所以我们需要先拆分为小文件，可以使用Hash拆分
• 解决
  1. 按行读取文件，对于每个词，按照Hash(词)%5000的结果分散到5000个小文件中
  2. 读取1.的每个小文件，使用HashMap统计数量，把结果存到另一个HashMap中
  3. 对于2的HashMap，使用长度为100的最小堆完成TOP K排序
• 类似的题目

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

3.4. 统计共同的URL【Bloom Filter / Hash拆分小文件+HashSet】

给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url

• 分析
  • 先思考数据量不大的场景，可以把a文件中的URL放入HashSet中，然后遍历b文件的URL，是否在HashSet中
  • 由于内存限制为4G，而50亿*64B/1024/1024妥妥超出限制了，因此需要拆分
  • 如果可以接受误差的话那么可以使用Bloom Filter解决，50Y bit数据大概需要内存5000000000/1024/1024/1024/8=0.5820766091346741G的内存
• 解决
  • 方案1：Bloom Filter
    1. 先读取a文件，将url映射到bloom filter中
    2. 读取b文件，判断是否在1.的bloom filter中，在的话就是共同的url，保存起来
  • 方案2：分而治之
    1. 读取a、b文件，使用Hash(URL)%1000拆分为a001…a999和b001…b999
    2. 读取a001和b001，使用HashSet判断是否共同的，是则保存
    3. 如2.继续读取余下的文件

3.5. 整形数字判重【BitMap / Hash拆分小文件+HashSet】

在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数

• 分析
  • 先思考数据量不大的场景，可以使用HashMap<数字，次数>统计次数，然后找出次数为1的即可
  • 由于内存不足以容纳这2.5Y个数字，因此需要拆分
  • 或者可以使用BitMap表示这2.5Y个数字，每个数字用2个bit（不是1个bit的原因在于判重）。那么需要5000000000*2/8/1024/1024=1200M内存
• 解决
  • 方案1
    • 一个个读取整数，Hash拆分到小文件中
    • 读取每个小文件中的整数，使用HashMap统计数量，将数量为1的存储到单独的文件中
    • 最后这个文件中的就是所有数量为1的数字
  • 方案2
    • 构造1200M的bit map
    • 读取这些数字，如果第一次出现那么置为01，2次及以上置为10，没有则为00
    • 读出01的数字即可

3.6. 判断某个数字是否在集合中【BitMap/BloomFilter】

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

• 分析
  • 先思考数据量不大的场景，可以使用HashSet存储所有整数，然后判断数字是否在HashSet即可
  • 由于内存不足以容纳这40亿个数字，因此需要拆分，然后拆分后无法满足快速判断的需求
  • 可以使用BitMap表示这40Y个数字，需要4000000000/8/1024/1024=476.837158203125M内存
• 解决
  1. 使用500M表示这些数字
  2. 读取这些数字，存入bit map中
  3. 读取这个数字，看bit map是否为1

3.7. X个数字，我需要取出最大的Y个，怎么处理

• 如果X比较小，那么可以一次性加载到内存中，使用排序后取出前Y个。比如快排效率为O(XlogX)
• 如果X比较大，那么无法一次性加载到内存中，只需要前Y个的话那么其实没必要全部加载到内存中，使用最小堆完成TopK问题：如果堆中元素不够100，那么直接插入最小堆，否则如果新的数比堆顶大，那么删除堆顶调整，然后插入这个元素继续调整堆。效率为O（XlogY）

4. 参考

• 十道海量数据处理面试题与十个方法大总结_结构之法 算法之道-CSDN博客
• 面试必备之海量数据处理 - 简书
• 教你如何迅速秒杀掉：99%的海量数据处理面试题_结构之法 算法之道-CSDN博客
• 海量数据处理 - 10亿个数中找出最大的10000个数（top K问题）_大数据_yofer张耀琦的专栏-CSDN博客
• 大容量文件夹的拆分和合并处理-Java - 简书
• 面试官：把访问P站次数最多的那个哥们儿给我找出来？
• 外部排序：如何用 2GB内存给 20 亿个整数排序？