大数据之Hadoop（四）
查找场景
设想一种场景，一种是需要在1亿行数据中查到相同的行。这么大的数据如果读入内存中进行计算，那么对机器的要求非常高非常耗费成本；其次，也有单点故障的风险。如果考虑用100台机器进行计算，可以采用下面的算法：
1）计算每行数据的哈希值，并用hash值为文件名创建文件；如果文件已经存在，则将改行数据追加到文件中
2）相同的行一定在同一个文件中，在同一个较小的文件中查找相同的行
因此1一亿数据查找的问题，转换为了再多个小文件中各自查找相同的行的问题。
但是引入了一个问题，会产生多少hash的小文件是不可控的，可能超出系统支持的最大文件数。因此需要在用hashcode再对1000取后，使用取模后的值作为文件名，使之正定。
计算场景
有1亿数据，需要对他们进行排序。可以进行分组排序，分组有两种方法：1）组内无序，组间有序；2）组内有序，组间无序；
组内无序，组间有序
- 根据文件的大小，按梯度创建文件，比如1-100；201-200。。。然后将数据放到各自的所属的文件中；
2）因此外部文件级别已经有序了，需要对文件内部的数据进行排序即可
组内有序，组间无序
1）将数据划分为100堆，在每个堆的内部进行排序
2）堆内有序，堆外无序，再对这100堆采用归并排序算法
下面是先分堆再归并排序的示意图：