总是会想起之前自己的哑口无言
海量数据处理
基本方法，常见的有 Hash 法， Bit-map 法，Bloom filter 法，数据库优化法，倒序索引法，外排序法，Trie 树，堆，双层桶法，以及 MapReduce 法。
BitMap 算法
BitMap 实际上就是用第 n 个 bit 位是否为 1 表示是否存在数字 n
例题
- 存在 10 亿个数字，请对其去重并排序。 一个 int 型数字 32 位，创建一个 bitmap 大小为 4G，遍历一遍 10 亿个数字，然后将对应的 bitmap 的位设置为 1，遍历完成之后从 bitmap 的开始位置依次取出标志为 1 的位置的索引，即为结果。
Bloom Filter 法
过程
控制一个长为 m 的数组，维护 k 个 hash 函数。
- 插入值 value，用 k 个 Hash 函数计算出 k（也可能小于 k） 个位置，将这些位置置为 1
- 查找是否存在 value，用 k 个 Hash 函数计算出 k（也可能小于 k） 个位置，查看这些位置是否全部都为 1，如果是，那么大概率说明存在 value。如果不全是 1，那么肯定不存在。
例题
- 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？ 4G 大概是 8 * 1024 * 1024 * 1024 * 4 = 320 亿位 bit，用 4G 内存做为哈希表。 维护 k 个 hash 函数，将 a 中的 url 用 k 个hash 函数计算出来的位置置为 1。 对 b 的每个 url 测试，用 k 个 hash 函数计算 hash 位置，检查是否全为 1，如果全为 1，那么说明很大概率是共同的，如果不是全为 1，那么肯定不共同存在。
本质
牺牲了准确性，提高了速度和效率。因为即使 hash 出来的 k 个位置都为 1，也不能证明该值一定是存在的。
倒序索引
每次检索的时候，搜索引擎并非遍历每一个保存下来的网页中是否存在关键词。 而是将每篇文章中的关键词存下来，然后将关键字指向这些文章。当用户搜索对应关键词的时候，会自动指向对应的文章。
外排序
不能一下将所有的元素装入内存。一般使用归并排序。
Trie 树
用来快速字符串检索的多叉树结构。 利用字符串的公共前缀减少时空开销，以空间换时间。 三个特点：
- 根节点不包含字符，除根节点外，其他节点均包含一个字符
- 从根节点到某一个节点，路径上经过的字符连接起来就是该节点对应的字符串
- 每个节点的所有子节点包含的字符都不相同
堆
常用来解决 topK 问题，常常和其他解法配合使用
双层桶法
过程
将搜索区间分成 n 个大小相同的子区间，每一个子区间都是一个桶，然后将 n 个记录分配到各个桶中。 对每个桶中的数据进行插入排序。 然后依次将每个桶连接起来。
时间复杂度
O(n) 最坏情况下可能是 O(n^2)
例题
- 对文件中 20 亿个数字进行排序 文件中的数字分散到 100 个小文件中，如果某个小文件过大，那么再对该小文件进行相同操作，直到能够对小文件进行排序。每个小文件排完序之后，再将其连接起来。
MapReduce
- Map 用来分配子任务
- Reduce 用来归纳结果
例题
- 10 台电脑中分别存有 1G 的数字，要求找出全部的数字中最大的十个。 首先每台电脑用最小堆找出各自的 10 个最大的数字，然后 10 台电脑将结果汇总到同一台电脑上，找出最大的十个数字。
