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个部分，每个部分交给一个单独的线程来执行，最后由一个线程来合并结果
相关题目：
参考《程序员面试笔试宝典》中的示例
1、10亿个数中找出最大的10000个数
2、有10000000个记录，这些查询串的重复度比较高，如果除去重复后，不超过3000000个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。请统计最热门的10个查询串，要求使用的内存不能超过1GB。
3、有10个文件，每个文件1GB，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。按照query的频度排序。
4、有一个1GB大小的文件，里面的每一行是一个词，词的大小不超过16个字节，内存限制大小是1MB。返回频数最高的100个词。
5、提取某日访问网站次数最多的那个IP。
6、10亿个整数找出重复次数最多的100个整数。
7、搜索的输入信息是一个字符串，统计300万条输入信息中最热门的前10条，每次输入的一个字符串为不超过255B，内存使用只有1GB。
8、有1000万个身份证号以及他们对应的数据，身份证号可能重复，找出出现次数最多的身份证号。
9、给你A、B两个文件，各放50亿条URL，每条URL占64字节，内存限制为4G，让你找出A、B之间相同的URL，如果是3个甚至n个文件呢？
10、海量数据日志，提取出某日访问百度次数最多的IP，且IP的数目是有限的。
11、已知某个文件包含一些电话号码，每个电话号码为8位数字，统计不同的号码个数
12、2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
13、100w个数中求前最大的100个数。
14、2.5亿个int求它们的中位数。
一个最大堆+一个最小堆
15、1G的数据，找出里面出现次数最少的3组数据
参考：《程序员面试笔试宝典》
想学习大数据或者想学习大数据的朋友，我整理了一套大数据的学习视频免费分享给大家，从入门到实战都有，大家可以加微信：Lxiao_28获取，还可以入微信群交流！（备注领取资料，真实有效）。
网友评论