用低内存处理大量数据，统一参考 hoodap 的 mapreduce 思路，先映射，再集合

1，先映射：读取文件，将文件整合（映射）成我们需要的样子 2，再集合：读取整合后的文件，集合处理，进行统计操作

下面是一些 case，在实战的时候可以参考这些，举一反三

出现频率最高的 100 个词

假如有一个 1G 大小的文件，文件里每一行是一个词，每个词的大小不超过 16byte，要求返回出现频率最高的 100 个词。内存大小限制是 10M

1，先映射：读取文件，将每个文件 hash 到对应的小文件中 2，再集合：挨个取出小文件的数据，使用 hash 来计数。计数完毕后用大根堆进行排序

可以采用分治策略，把一个大文件分解成多个小文件，保证每个文件的大小小于 10M， 进而直接将单个小文件读取到内存中进行处理

第一步，首先遍历大文件，对遍历到的每个词 x，执行 hash(x) % 500，将结果为 i 的 词存放到文件 f(i)中，遍历结束后，可以得到 500 个小文件，每个小文件的大小为 2M 左右

第二步，接着统计每个小文件中出现频数最高的 100 个词。可以使用 HashMap 来实 现，其中 key 为词，value 为该词出现的频率。对于遍历到的词 x，如果在 map 中不存在，则执行 map.put(x, 1)。若存在，则执行 map.put(x, map.get(x)+1)，将该词出现的次数加 1。这里如果直接维护一个大根堆，直接对每个小文件遍历并且计数，然后排序的话，可能会占用一定的内存限制

第三步，在第二步中找出了每个文件出现频率最高的 100 个词之后，通过维护一个大根堆来找出所有小文件中出现频率最高的 100 个词

具体方法是，遍历第一个文件，把第一个文件中出现频率最高的 100 个词构建成一个 大根堆

如果第一个文件中词的个数小于 100，可以继续遍历第二个文件，直到构建好有 100 个结点的大根堆为止

继续遍历其他小文件，如果遍历到的词的出现次数大于堆顶上词的出现次数，可以用新 遍历到的词替换堆顶的词，然后重新调整这个堆为大根堆

当遍历完所有小文件后，这个大根堆中的词就是出现频率最高的 100 个词

查找两个100亿数据量大文件中共同的 URL

思路是一样的，先将差不多的 url 放到同一个文件中，然后再比较这些文件

先遍历 A 文件，使用 hash 将其分成很多小 a 文件，再遍历 B 文件，生成很多小 b 文件

由于小 a 和小 b 都是一一对应的关系，因此我们可以直接将他们取到内存中做比较，比较也是先将 a 放进 hashMap，然后遍历 b

如何在 100 亿数据中找到中位数

我们允许向磁盘中的各个文件存入无限数据，但是内存是有限的，一次只能读一点。因此我们按照 hoodope 的指导思想，先分批转换

我们想想中位数怎么算，我们可以用快速查找的方式，先读一个数据 A，然后每读一个数，比 A 大的放进a文件，比它小的放进b文件。并且对a、b文件的大小计数。分组完毕后一定有一组数据大，另外一组数据小，我们进入数量大的组中。循环这个流程，直到找到我们需要的数据

这个可以优化吗，我们想到找中位数这个操作，是不是桶排序更加合适一些

先遍历一次所有数据，取出最大值和最小值，目的是找到数字的界限，让我们知道要生成什么样子的桶

最大最小之间，生成x个桶，每个桶的大小需要计数。再遍历一次文件，将数据放进每个桶中。我们知道每个桶的大小了，可以很简单的找到中位数存在的桶。一般来说我们找到的桶内存是放的下的，如果桶文件过大，循环执行该流程

只有 4G 内存进行 500G 数据需要排序

当需要在有限内存下排序大规模数据时，可以采用外部排序算法。以下是解决方案：

1，分块阶段：将 500GB 数据分成多个适合内存的小块，每块大小约为3-3.5GB，因为我们需要留出部分内存给系统和其他操作，大约需要分成150-170个块

2，内部排序阶段：逐块将数据读入内存，使用高效的内部排序算法，如快速排序、堆排序，对每块数据进行排序，将排序后的块写入临时文件

3，归并阶段：使用 k 路归并算法合并这些已排序的块，由于内存限制，可能需要多轮归并，例如如果有3GB可用于归并缓冲区，每路分配100MB缓冲区，则可同时合并30路