前言
这里主要针对案例进行分析讲解，欢迎大家在 issue 或是直接 contribution 更多相关的海量数据相关难题。这里我将持续性的更新一些面试中常见的海量数据案例。
这里我将会持续更新，时间有限不能全面总结，欢迎大家一起完善。
海量数据问题处理方法
- Hash
- Bit-Map
- 布隆过滤器 (Bloom Filter)
- 堆 (Heap)
- 双层桶划分
- 数据库索引
- 倒排索引 (Inverted Index)
- B+树
- Trie树
- MapReduce
海量数据案例
1. 两个大文件中找出共同记录
题目描述
给定 a、b 两个文件，各存放 50 亿个 url，每个 url 各占 64 字节，内存限制是 4G，让你找出 a、b 文件共同的 url？
解题思路
方案 1
首先我们最常想到的方法是读取文件 a，建立哈希表方便后面查找，然后再读取文件 b，遍历文件 b 中每个 url，对于每个遍历，我们都执行查找 hash 表的操作，若 hash 表中搜索到了，则说明两文件共有，存入一个集合。
可以估计每个文件安的大小为 5G×64 =320G，远远大于内存限制的 4G。所以不可能将其完全加载到内存中处理。
针对上述问题，我们分治算法的思想。
-
遍历文件 a，对每个 url 求取
hash(url)%1000，然后根据所取得的值将 url 分别存储到 1000 个小文件（记为 a0,a1,...,a999 每个小文件约 300M），为什么是 1000？主要根据内存大小和要分治的文件大小来计算，我们就大致可以把 320G 大小分为 1000 份，每份大约 300M（当然，到底能不能分布尽量均匀，得看 hash 函数的设计） -
遍历文件 b，采取和 a 相同的方式将 url 分别存储到 1000 个小文件（记为 b0,b1,...,b999 ）
为什么要这样做？文件 a 的 hash 映射和文件 b 的 hash 映射函数要保持一致，这样的话相同的 url 就会保存在对应的小文件中，比如，如果 a 中有一个 url 记录 data1 被 hash 到了 a99 文件中，那么如果 b 中也有相同 url，则一定被 hash 到了 b99 中。
所以现在问题转换成了：找出 1000 对小文件中每一对相同的 url（不对应的小文件不可能有相同的 url）
- 求每对小文件中相同的 url 时，可以把其中一个小文件的 url 存储到 hash_set 中。然后遍历另一个小文件的每个 url，看其是否在刚才构建的 hash_set 中，如果是，那么就是共同的 url，存到文件里面就可以了。
方案2
如果允许有一定的错误率，可以使用 Bloom filter，4G 内存大概可以表示 340 亿 bit。将其中一个文件中的 url 使用 Bloom filter 映射为这 340 亿 bit，然后挨个读取另外一个文件的 url，检查是否与 Bloom filter，如果是，那么该 ur l应该是共同的 url（注意会有一定的错误率）。
2. 大文件排序和去重
如果有一个500G的超大文件，里面都是数值，如何对这些数值排序？ - CSDN博客 https://blog.csdn.net/u011381576/article/details/79385133
大文件的排序和去重 超级简单的实现 - zero_learner - 博客园 https://www.cnblogs.com/yangxudong/p/3848453.html
