大数据基础知识
什么是大数据
hadoop，spark
给定a、b两个文件，各存放50亿个url，每个url各占用64字节，内存限制是4G，如何找出a、b文件共同的url？
每个文件 50亿*64B 约为300GB大小，内存肯定是装不下了。毫无疑问还是采用分而治之的思想：
遍历文件a，对每个url求取hash(url)%1000，然后根据所得值将url分别存储到1000个小文件（设为a0,a1,...a999）当中； 遍历文件b，对每个url求取hash(url)%1000，然后根据所得值将url分别存储到1000个小文件（设为b0,b1,...b999）当中； 这样处理后，所有可能相同的url都在对应的小文件(a0-b0, a1-b1....a999-b999)当中，不对应的小文件（比如a0-b99）不可能有相同的url。hash(url)%1000代表对url进行hash值，然后对1000取余数。
统计1000对文件中相同的url，采用hash_set.比如对a0-b0，遍历a0，将其中的url存储到hash_set当中； 然后遍历b0，如果url在hash_map中，则说明此url在a和b中同时存在，保存到文件中即可。
有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M，要求返回频数最高的100个词。
Step1：顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为f0 ,f1 ,... ,f4999）中，这样每个文件大概是200k左右，如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M；
Step2：对每个小文件，统计每个文件中出现的词以及相应的频率（可以采用trie树/hash_map等），并取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100词及相应的频率存入文件，这样又得到了5000个文件；
Step3：把这5000个文件进行归并（类似与归并排序）；