海量数据处理常用思想及重要数据结构

1、大顶堆、小顶堆

特别适合topN问题，如求海量日志中最大的100个数。既然是海量数据，那么内存中一下子无法加载所有的数据集，此时可以先读取海量数据中的100个数，建立数据集为100的小顶堆(小顶堆的对顶比所有元素都小)，然后依次往堆结构中读取数字，调整堆，使其保持小顶堆，最后得到top100的最大数。

2、hash映射进行分治，然后归并

hash映射按照数据特征把海量数据变的不海量，然后分别处理各段数据，再归并处理。例如：给定两个文件，各存放50亿个url，让你找出两个文件中共同的url，则可以根据url的特征，将两个文件分别映射到上千个小文件中，只要保证两个文件用的相同的hash映射方法，那么相同的url映射后一定在相同的小文件中，所以逐一比较各个小文件中的url，然后归并即可。

3、hash统计

以特征为key值利用hash表进行统计，比如，求一本书中26个字母出现的个数，可以以26个字母分别为key值，进行hash统计即可。

4、bloom filter

可以用于判重，此方法存在一定的误差，但是比较高效。方法是利用多种不同的hash方法对数据集做hash运算，将对应的结果为key，值为1，然后判断一个新数在不在这个数据集中，则用相同的n中hash方法进行计算，如果全为1则认为在，任何一个不为1，则认为不在。

5、外排序

外只的是外存，因为内存一下子放不下海量的数据，所以只好把大数据拆成小数据，在内存中进行排序，在外存中进行存储。基本思想是先对大数据拆分成n个小数据，然后对小数据排序，然后放入文件中，再用归并的方法，将已排序的小数据集进行归并。

6、bitmap

位图用一个bit位来标记某个元素所对应的value，而key即是该元素本身，位图可以节约大量的空间。例如判断一个32位的整数是否在海量的32位整数数据集中出现过，则可使用位图。

7、多层划分

和hash映射类似也是分而治之，只不过是如果数据集恰好有一些可以分层的特点，则可以直接分层化大为小。如，海量32位整数的数据集中找中位数，首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。最后再次扫描我们只统计落在这个区域中的那些数就可以了。

8、tire树

比较适合字符串类的查找，如把1000万个单词中的大量的重复单词去掉，可以使用tire树进行查重。

9、mapreduce

有现成的大数据计算框架。