# 前言

这里主要针对案例进行分析讲解，欢迎大家在 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。所以不可能将其完全加载到内存中处理。

针对上述问题，我们分治算法的思想。

1. 遍历文件 a，对每个 url 求取 `hash(url)%1000`，然后根据所取得的值将 url 分别存储到 1000 个小文件（记为 a0,a1,...,a999 每个小文件约 300M），为什么是 1000？主要根据内存大小和要分治的文件大小来计算，我们就大致可以把 320G 大小分为 1000 份，每份大约 300M（当然，到底能不能分布尽量均匀，得看 hash 函数的设计）

2. 遍历文件 b，采取和 a 相同的方式将 url 分别存储到 1000 个小文件（记为 b0,b1,...,b999 ）

   为什么要这样做？文件 a 的 hash 映射和文件 b 的 hash 映射函数要保持一致，这样的话相同的 url 就会保存在对应的小文件中，比如，如果 a 中有一个 url 记录 data1 被 hash 到了 a99 文件中，那么如果 b 中也有相同 url，则一定被 hash 到了 b99 中。


　　所以现在问题转换成了：找出 1000 对小文件中每一对相同的 url（**不对应的小文件不可能有相同的 url**）

3. 求每对小文件中相同的 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



# 参考资料

- [搞定海量数据处理，六道海量数据处理面试题分析与十大方法总结](https://zhuanlan.zhihu.com/p/40430913)
- [海量数据处理：十道面试题与十个海量数据处理方法总结 - chenhuan001 - 博客园](https://www.cnblogs.com/chenhuan001/p/5866916.html)
- [大数据和空间限制问题专题（一） - CSDN博客](https://blog.csdn.net/qq_21688757/article/details/53993096)

- [Interview-Book/2018-03-31-数据分析师常见的7道面试题.md](https://github.com/ZuoAndroid/Interview-Book/blob/df3b37cf80de59015c6c3651b1e588d9cbeac889/%E9%9D%A2%E8%AF%95%E9%A2%98/2018-03-31-%E6%95%B0%E6%8D%AE%E5%88%86%E6%9E%90%E5%B8%88%E5%B8%B8%E8%A7%81%E7%9A%847%E9%81%93%E9%9D%A2%E8%AF%95%E9%A2%98.md)