海量数据处理在进行分块处理的时候一般包括以下步骤：
首先进行数据预处理，一般采用的方法就是使用hash把大文件映射成小文件，这样的好处就是每个相同类型的值肯定被映射到了同一个文件中，如：在处理url的时候采用hash(url)%1000，或者在处理ip的时候采用hash(ip)%1000，则可以保证相同的重复出现的url或者ip会映射到相同的小文件内，如果设计的hash函数分布不均匀，导致映射后的小文件还是超出了内存的大小，则可以在这个小文件上再采用hash映射，映射长跟小的文件，直至符合内存大小位置。
然后进行各个映射到小文件中的海量数据处理：根据需要把各个小文件读入内存，之后在这个文件上根据需要进行排序、去重、统计重复出现的关键字的次数、查找前k大/小的元素等操作，在进行这些操作的时候一般采用的算法可以使用内部排序算法、STL的hash_map或者hash_set容器进行排序、去重、统计、查找前k大/小的元素的操作
最后将各个经过处理的小文件结果进行归并得出最终结果：这个时候一般使用的算法就是trie树、败者树、堆、外排序，以及内排和外排相结合的方法进行处理。
以下几个问题采用了这种海量数据处理方式：
1. 给定a、b连个文件，各存放50亿调url，每个url最大为64字节，内存限制是4G，找出两个文件中相同的url
方案：将a、b两个文件分别使用hash(url)%1000的hash函数映射为1000个大小约为300M的文件，这样大小的文件就可以读入内存进行处理，并且二者如果存在相同的url则比存在于对应的ai和bi小文件中，之后分别对比ai和bi文件对比即可，具体方法可以是将ai读入内存存入到一个hash_set中，分别遍历bi中的每个url看是否存在于这个hash_set中，若存在则重复，此外由于ai和bi与其他文件没有任何关系，可以通过多线程或GPU并行处理进行加速。
2. 有10个文件，每个文件大小是1G，每个文件中的每一行存放的都是用户的query，每个文件中的query都可能重复，要求按照query的频度进行排序。
方案：顺序读取这10个文件，使用hash(query)%10的hash函数将每条query映射到10个文件中，这样处理的目的在于使得存在于不同文件中的相同的query存储到同一个文件中。然后找一台内存为2G大小的机器，一次将这10个文件读入内存使用hash_map(query,query_count)进行统计，将统计后的结果使用快排/堆/归并排序等内存排序算法进行排序，将排序之后的结果写会到文件中；分别对这10个文件进行处理之后，利用归并排序将这个10个文件处理后的结果进行排序即可，这个时候使用外排序和内排序相结合的方法进行
3. 有一个1G大小的文件，其中每一行是一个词，词的大小不超过16字节，内存大小限制是1M，返回频数最高的100个词
方案：顺序读取文件，对于每个词使用hash(x)%5000的hash函数映射到5000个大小为200kB大小的小文件中，这个时候相同的词肯定都映射到了相同的文件中，之后将每一个小文件顺序读入内存，使用hash_map或者tri树统计词频，并去除出现频率最大的100个词，可以使用100个节点的堆，之后把结果写回文件，最后把这5000个文件进行归并得出5000个文件中出现频率最高的100个词，这个过程可以使用败者树来进行。
4. 海量数据日志数据处理，提取出某日访问百度次数最多的那个IP
方案：和第三个题目处理过程相似，只是每次取最大的即可
5. 海量数据分布在100台电脑中，想办法高效统计出这批数据的TOP10
方案：和第二题的解决方案类似，这里不比进行词频统计了。分别在每台电脑上求出TOP10，每个求取TOP10的时候可以使用10个顶点的堆来完成，之后归并100台电脑上的TOP10来得出最终的TOP10数据。
6. 在海量数据中找出重复次数最多的一个、最大的一个、（重复次数）最大的n个
方案：分别题目二、四、三结题思路相同
7. 有海量字符串数据处理，其中有些是重复的，需要把重复的全部去掉保留没有重复的字符串
方案：首先映射为内存可以处理的n个小文件，这时相同的字符串肯定在同一个文件中，在每个小文件中使用hash_set取出重复的字符串，之后写到一个文件中，依次处理n个文件，即可得到结果
8. 100W个数中找出最大的100个数
方案：使用一个100个节点的小顶堆来进行查找即可，复杂度为100w*log100
使用Bit-Map一般处理的是数字的问题，其中心思想就是使用bit数组来表示某些key值的存在，一般用来处理查找某些数值型值是否存在的问题：
1. 在2.5亿个整数中找出不重复的整数，内存不足以容纳着2.5亿个整数
方案：整数是4个字节32bit的，所以一共可能有2^32个整数，为了表示这些整数是否存在，使用2bit来表示，00表示这个整数不存在，01表示出现1次，10表示出现多次，11表示无意义，这个bit数组共需要2^32*2bit=1GB内存。数组的下标对应整数值，当该整数不存在是，这个下标中元素为00，出现1次时为01，多次时为10；最后将元素为10的下标输出就是重复出现的整数
2. 使用bit-mao可以对不重复出现的数字序列进行排序，效率会比较高
3. 某个文件中包含一些电话号码，每个号码是8位数，统计不同号码的个数
方案：8位的电话号码最多可以表示99999999个电话号码，现在使用1bit对应一个电话号码，即99999999bit大约为10M+的内存，每个bit若为0则表示这个号码不存在，为1则表示这个号码存在。每个bit对应的下标就是电话号码对应的整数，最后遍历整个数组，统计元素为1的个数即可。
安防之家专注于各种家居的安防,监控,防盗,安防监控,安防器材,安防设备的新闻资讯和O2O电商导购服务，敬请登陆安防之家：http://anfang.jc68.com/
