海量数据问题指的是给定了一些无法一次放进内存的大文件，要求用内存有限的机器去处理这些海量数据。
一般海量数据的问题可以分为以下几类：
- 找第 k 大的数
- 找前 k 大的数
- 找中位数
- 查找一个条目在不在数据里
- 查找两个大文件的相同条目
- 出现频率最高的 k 个条目
- 提取数据中重复出现的条目
- 数据中没有重复出现的条目
- 去重
- 排序
=========================================================
首先我们引进一些工具，这些问题基本可以靠活用这些工具解决。
第一，子任务的分解
将大文件分解成多个小文件，然后让计算机对这些小文件逐个操作，这就相当于分解子任务。
哈希把不同的数最基础的做法，是拿数据对一个特定的数求余，得到对应的hash值。例如：hash = value % 1000。
哈希的办法适用于需要统计数值出现频率或者去重，但是会存在负载过大的问题。比如数据很多都是 1000 的倍数，那么 0 号文件就会比其它文件大很多。这可能需要一些前期的预处理来选取合适的数字，或者使用一些质数。STL 内部实现哈希表的时候就内置了一些质数来确定哈希表的桶数量。
还有一种更简单的方法就是直接分割文件。这样子可以很好地平均每个文件的大小，但是如果要考虑去重话就需要更多的措施。
第二，数表的压缩：位图
一般的四字节 int 类型变量，可表示 2^32 个数。若我们想用 int 存储每一个数出现的次数，那么空间开销就是 2^32 * 4 = 16 GB。一般的机器很难支持这么大的内存开销。
而如果我们只是想知道某个数是否出现过，那么我们并不需要用 int 存储，我们只需要用一个比特就可以了。这样的话，我们的开销变为 2^32 / 8 = 512 MB。512 MB 一般是可以接受的大小，如果内存限制更少，我们需要用别的方法，例如把这512 MB的位图分为多块，然后分别存储。
理论上，问题中包含数的多少种状态，我们就可以用对应多的比特位来记载这些状态。例如，我们要记录恰好出现两次的数，那么我们就可以为每一个数分配两个比特，00 代表未出现，01 出现 1 次，10 出现两次，11 出现多次。取状态为 10 的数就是出现过两次的数。
第三，布隆过滤器
布隆过滤器是哈希和位图的综合应用，它主要用来考察一个数是否不在一个数据集里。
具体是这样做的，首先我们取 k 个哈希函数，然后把他映射到多个位中。
例如，对于数字 37，我们可以以 2, 5, 11, 17 对其取余，得到 1, 2, 4, 3。于是，在我们的位表中，1、2、3、4 都被设置为1。
而如果数据集里面只有 25, 那么我们会发现只有 1, 3 被置 1。这就证明 37 并不在数据集中。
自然我们会想到，只要数据足够多，那么 1234 迟早都会被置 1，这时候我们就不好说 37 到底在不在数据集里面了。
因此布隆过滤器只能确保某个数不在数据集里，而想知道某个数是否在数据集里，是存在误算率的。
第四，哈希表
哈希表的功能就是通过哈希函数进行查找，它有很低的时间开销，但是空间开销会随之增大。
第五，最小堆
在堆里，我们可以在 logn 的时间内把一个数据插入堆内。这个性质对找最大的 k 个数比较有用，我们可以在 nlogn 的时间内完成我们的任务。
第六，字典树 / trie树
字典树是为了减少公共前缀的搜索时间而涉及的。字典树的根是空节点，根据字符集的大小，每个节点都可以有相对应多的子节点。例如，根据 [act, active, action]，我们可以得到字典树：
NULL -> a -> c -> t (is word) -> i -> v -> e (is word)
-> o -> n (is word)
对于单词数量较少而搜索次数较多的情况下，字典树就是一个非常合适的数据结构。
=========================================================
然后我们还要解决一些细节问题：
第一，限制很高的时候如何变通
如果内存限制很低，那么我们就只能通过多次 IO，把硬盘空间作为我们的“内存”来使用了。
第二，如何读写文件
这部分涉及到一个问题，就是文件很大的时候没法一次放进内存里。这时候我们需要对大文件进行有效的切分。例如，当我们的可用内存只有100M这么小的时候，我们就需要考虑把大文件切分成小于100M的小文件。
=========================================================
现在我们可以开始对每个问题进行具体探讨了。
- 找第 k 大的数
- 找前 k 大的数
- 找中位数
- 查找一个条目在不在数据里
- 查找两个大文件的相同条目
- 出现频率最高的 k 个条目
- 提取数据中重复出现的条目
- 数据中没有重复出现的条目
- 去重
- 排序
1. 找第 k 大的数（TopK）
构建最小堆，堆顶元素就是第 k 大的数字。每当有一个数进入，且这个数比堆顶元素大，就把这个元素替换掉堆顶元素，并维护堆。空间复杂度 O(k)，时间复杂度O(k+nlogk)。不需要切分文件，只需要顺序读取文件内容即可。若 k 比较大，则可以考虑把堆存储在不同的文件里。
2. 找前 k 大的数
这个问题和第 k 大也是一样的。只不过我们可能要另外对得到的 k 个数进行排序。当数量比较小，可以直接进行排序。如果数量比较大，可以看问题 10 对排序的讨论。
3. 找中位数
这里需要一个特殊的切分技巧。我们每次从数据中读入一小段（取决于内存大小），然后把最高位为 0 的数放到一个文件里，为 1 的数放到另一个文件里。这样，我们最终会得到两个文件，其中更大的一个会包含中位数。经过一定数量的操作之后，我们能得到一个区间靠近中部的小文件。这时候我们就可以把这个文件全部读入内存，然后排序，得到中位数。
4. 查找一个条目在不在数据里
对于数的单次查找而言，可以使用上面找中位数用到的切割方法，在 32 次以内就能得知是否存在数据。
不过，这种问题一般是以多次查询的方式来探讨的，所以接下来再看看多次查询怎么做。
搜索问题可以分为树和哈希两种解决方案。对于海量数据，我们只有在状态较少的时候才会考虑用树，否则应该用哈希的方案。
一般的搜索树会使用红黑树来保证平衡，而海量数据搜索问题中，因为会有搜索目标重复较多的情况存在，所以使用的是trie树。
如果内存空间不足，就要考虑用哈希。
对于URL这样的字符串，通过哈希的方式把海量数据分散到小文件里，然后在小文件中搜索。一般的字符串哈希函数（比如MD5）应该能确保小文件是平均分散的。
对于数字，我们还可以用位图来保存。
对于“不存在”问题，我们更可以用布隆过滤器。
5. 查找两个大文件的相同条目
对于这个问题，我们有两种解决思路。
首先，我们还是可以按分治的原则，用哈希值把大文件切割成小份。然后，两个大文件中哈希相同的小文件读入内存，然后在内存中再用哈希表的方式去对比。处理小文件的空间负责度是可以接受的。
其次，我们还可以使用布隆过滤器。用文件 A 设置了过滤器之后，分别对 B 的每一个条目进行过滤。布隆过滤器的方案需要有对误算的容忍。
6. 出现频率最高的 k 个条目
第一步，我们需要知道各个条目的出现频率。这个可以通过哈希切分小文件+字典树统计频率的方法完成。注意，因为我们通过哈希限制了理论的最大状态数，所以即使某一个小文件很大也没有关系。
然后就是用 topK 的方法就可以了。
7. 提取数据中重复出现的条目
起手还是先用哈希切割小文件，然后在小文件里存储出现频率并查询。
对于数，这个显然还可以用双比特位图。
8. 数据中没有重复出现的条目
本质上这个问题和上一个一样，只不过查询对象改变了而已。
9. 去重
哈希切分文件之后，用哈希表去重。然后逐个写回大文件。
注意有些问题是多个文件，要求把条目保存在优先级高的文件中。这种问题可以考虑把优先级记录到小文件中，然后在去重完成后，按优先级归类到不同的文件里。
10. 排序
大文件的排序一般使用归并，这个归并的形式比较自由，可以分出多个小文件之后，多路归并。每次从所有小文件中读出一小部分，然后同时归并。