首页

海量数据处理（1GB == 2^30B == 2^33bit ≈≈ 10亿字节 == 80亿位）

前提：文件散列

创建N个小文件，遍历大文件（顺序读取到内存缓冲区），对数据按哈希值取余散列到小文件中（顺序写入磁盘），遍历完成后，如果某些小文件的大小仍然超过了内存限制，则对这些小文件使用同样的方法继续散列为更小的文件，最终可以保证重复的数据只可能出现在同一个小文件中。

特殊情况下小文件无法再被散列为更小的文件，可能是单个重复的数据就超过了内存限制，也可能是大量的数据出现哈希冲突。可以更换哈希函数再次尝试，或使用投票算法找出文件中的众数，以此确认到底属于哪种特殊情况。

如何从大量的 URL 中找出相同的 URL？

给定 a、b 两个文件，找出 a、b 两个文件共同的 URL。

  1. 将文件a、b分别按URL使用相同的哈希函数散列到N个小文件中；
  2. 对文件a的每个小文件进行统计，由于URL的特性，适合使用前缀树统计；
  3. 每个小文件统计完成后，遍历文件b对应编号的小文件，使用前缀树判断URL是否存在，然后将相同的URL保存到单独文件中。

因为是按相同的哈希函数散列，即同一个文件的不同小文件之间的URL不可能重复，不同文件的相同编号的小文件有可能重复。

如何从大量数据中找出高频词？

  1. 将文件按单词散列成小文件；
  2. 在内存中构建一个大小为N的小顶堆；
  3. 依次遍历每个小文件，使用哈希表统计单词的频次；
  4. 遍历哈希表，如果单词频次大于堆顶单词频次，则pop出堆顶单词，并将当前单词加入堆中恢复平衡，或堆内元素个数小于N也直接加入堆；
  5. 遍历完所有小文件，小顶堆内剩余的N个单词就是topN。

如何找出某一天访问网站最多的 IP？

  1. 将文件按IP散列成小文件；
  2. 在内存中只需要维护一个最大值；
  3. 依次遍历每个小文件，使用哈希表统计单词的频次，然后找出最高频次IP，最后判断是否需要更新最大值即可。

如何在大量的数据中找出不重复的整数？

方法一：分治法，文件散列，分开统计，合并结果。

方法二：位图法，用2个bit标识一个整数的状态（00不存在，01出现一次，10出现n次），如果内存大于1GB，且整数为int类型，2^32*2b刚好等于1GB，则可以直接遍历文件使用bitmap统计即可。

方法三：分治法和位图法结合，根据内存的大小结合整数的范围，分成多个区间使用位图法统计。

如何在大量的数据中判断一个数是否存在？

方法一：位图法，使用位图法统计数字，只需要一位即可标识数字是否存在，则512M内存即可统计所有int类型整数。如果内存不足则结合分治法，将数字分为多个区间分开统计即可。

方法二：布隆过滤器，1GB内存大约可以保存80亿数据。如果内存不足则需要结合分治法，先文件散列，然后将每个小文件内的数据保存到布隆过滤器并写入磁盘，之后对需要查找的数据使用同样的哈希函数散列，读取对应的布隆过滤器进行判断。

如何从大量数字中找出中位数？

  1. 遍历文件，将最高位为1的数和为0的数分开写入两个文件并统计个数；
  2. 判断中位数位于哪个文件中，继续按次高位将该文件的数据分开写入两个新的文件并统计个数；
  3. 重复以上步骤，直到内存能加载目标文件，然后排序或直接使用选择算法确定到中位数。

如何按照数据的频度排序？

  1. 文件散列；
  2. 小文件哈希表统计并排序；
  3. 使用外排序方式归并小文件的排序结果。

如何找出已经排序的多个数组的topN？

  1. 维护一个大小为数组个数的大顶堆，因为已经排序，首先往堆中加入每个数组的最大值；
  2. 删除堆顶元素，加入结果集内；
  3. 从被删除元素所属的数组内取出一下最大值加入堆内，恢复平衡；
  4. 重复2、3步骤直到结果集添加完毕。

总结