1、常见海量数据处理方法

hash、bit-map（位图法）、bllomfilter、数据库优化、倒排索引、外排序、Trie树、堆、双层桶、mapReduce法、分治

2、hash法

在海量数据处理中，Hash法一般可以快速存取、统计某些数据，将大量数据进行分类，例如，提取某日网站次数最多的IP地址

3、bit-map位图法

又叫位图法，基本原理是使用位数组来表示某些元素是否存在，它适用于海量数据的快速查找、判重、删除等。基本步骤：首先扫描一遍数据集合，找出集合中的最大元素；然后按照最大元素Max创建一个长度为Max+1的新数组，接着再次扫描原数组中的数据集合，每遇到一个元素就将新数组中下标为元素值的位上置1或加1

可以通过位图法来对海量数据集进行排序、查重或者判断某数是否存在，时间复杂度位O（N），但是是以空间来换时间

4、bllomfilter

Bit-map与hash的结合

5、堆

堆适用于海量数据求前N大（最小堆）、前N小（最大堆）、中位数（双堆）问题，其中N一般比较小

6、MapReduce

Map（映射）Reduce（化简是云计算的核心技术之一，是一种简化并行计算的分布式编程模型。它为并行的数据处理提供了一个简单、高效的解决方案，其主要目的是为了大型集群的系统能在大数据集上进行并行工作，并用于大规模数据的并行运算

海量数据的处理，分布式的计算方式会导致网络间大量频繁的数据交换，在这种情况下，网络带宽相对属于稀缺资源

海量数据处理的最大难题在于数据规模巨大，使得传统处理方式面临计算能力不足和存储能力不足的瓶颈问题，而基于Hadoop可以非常轻松和方便地完成处理海量数据的分布式并行程序，并运行于大规模集群上

MapReduce实例：

See《程序员面试笔试宝典》P405

7、单位换算

    1G=1024M、1M=1024KB、1KB=1024B（Byte）、1Byte=8bit

    //为了换算方便，可近似将1024取为1000

8、海量数据处理主要分类

三类：top K问题、重复问题、排序问题，一般三个问题会有交叉，尤其是在top K问题里，先计算需要的内存，然后是根据具体问题选择一个解决方法

9、重复问题

一般用位图法解决

10、排序问题

     分治、位图法排序（前提是没有重复数据）、桶排

11、top K问题（5种方法）

1）将所有数据全部加入内存，在内存中用快排等常规排序算法

2）用一个容器保存前K个数，然后依次将剩余的数与容器中这K个数里的最小/大数进行比较，更新容器里的数，最后输出容器里的数

3）分治

     比如，将1亿个数分为100份，每份100万个数据，找出每份中最大的K个，最后再在这100*K个数中招最大的K个。其中，在100万个数里找最大的K个可以使用快排：一次快排将数据分为两堆，如果大的那堆个数大于K，则再快排大堆这堆，小的那一堆则直接排除去掉；若大的那堆个数N小于K，则对小的那堆再做快排，直到找到第K-N大的那个数字。这样就找到了最大的K个。

4）hash法

通过hash法对这1亿个数去重，然后再通过分治或最小堆来查找最大的K个数

5）最小/最大堆

为了避免方法2中每次都遍历这个容器，可以用最大堆或最小堆来存这K个数据，替换这个容器

12、对于多核计算机top K问题

可以先用hash分成n个部分，每个部分交给一个单独的线程来执行，最后由一个线程来合并结果