转自： http://www.cn blogs.com/jishu/archive/2011/04/27/2030921.html
大数据量问题是很多面试笔试中经常出现的问题，例如在百度谷歌腾讯这样处理大量数据的公司中经常出现。
以下方法对大量数据的处理方法进行了一般性总结。 当然，这些方法可能并不能完全涵盖所有问题，但这样的方法也能处理大多数问题。 以下几个问题基本上直接来源于公司的面试笔试问题，方法不一定最佳。 如果你有更好的处理方法的话，请和我讨论。
1.bloom过滤器
适用范围：可用于实现数据词典、进行数据判定、集体求交集
基本原理和要点：
原理很简单，是位数组的k个独立的散列函数。 将对应于散列函数的值的比特数组设为1，在检索时如果知道对应于所有的散列函数的比特为1就存在，但显然该过程并不保证检索结果100%正确。 此外，不支持删除已经插入的关键字。 因为与关键字对应的位会影响其他关键字。 因此，一个简单的改进是counting Bloom filter，使用counter数组而不是位数组可以支持删除。
另一个重要问题是如何基于输入元素的数量n确定比特数组m的大小和散列函数的数量。 散列函数个数k=(ln2 ) ) m/n )时，错误率最小。 错误率为e以下时，m至少要与n*LG(1/e )相等，才能表示任意n个元素的集合。 但是，m应该更大。 为确保至少一半的位数组为0，m=Nlg(1/e ) LGE应该约为m=Nlg(1/e )的1.44倍) LG表示以2为底的对数。
例如，假设错误率为0.01，则此时m应该是n的大约13倍。 这样k就8个左右了。
注意，m与n的单位不同，m是bit单位，n是元素的个数单位(准确地说是不同元素的个数)。 每个元素的长度通常有很多位。 因此，使用bloom过滤器内存通常会节约。
扩展：
Bloom filter将集合中的元素映射到位数组，k(k是散列函数的个数)个映射位是否都为1，表示该集合中不存在元素。 计数蓝牙过滤器(CBF )将位数组中的每个位扩展到一个counter，并支持元素删除操作。 spectralbloomfilter(SBF )将其与集合元素的出现次数相关联。 SBF用counter中的最小值近似要素的出现频率。
问题实例：给出a、b两个文件，每个文件存储50亿个URL，每个URL占用64字节，内存限制为4G，请用户找到a、b文件共有的URL。 如果是3个到n个文件呢？
根据这个问题计算内存的消费量，4G=2^32约40亿*8约为340亿，n=50亿，按错误率0.01计算，需要约650亿位。 现在可用的是340亿，没有那么大的差别，所以错误率有可能上升。 另外，如果这些urlip一一对应，就可以转换为ip，所以非常简单。
2 .哈shing
应用范围：快速搜索、删除的基本数据结构。 通常，需要能够存储在内存中的总数据量
基本原理和要点：
混列函数的选择是具体对应于字符串、整数、数组的混列方法。
碰撞处理，一种是open hashing，又称拉链法； 另一种是封闭隐藏，也称为开地址法、开放地址法。 (http://www.my400800.cn )
扩展：
d-left hashing的d是多个意思。 我们先简化这个问题，看看2-left hashing。 2-left hashing是指将一个散列表分为长度相等的两个，分别称为T1和T2。 T1和T2分别配备散列函数，h1和h2。 保存新key时，同时用两个散列函数进行计算，得到两个地址h1[key]和h2[key]。 此时，需要检查T1的h1[key]的位置和T2的h2[key]的位置，哪个位置已经存储(有冲突的) key较多，在负荷少的位置存储新的key。 如果两侧一样多，例如，两个位置都为空，或者包含一个key，则左侧的T1子表将包含新key，2-left也将从中派生。 查找一个key时，需要进行两次hash，同时查找两个位置。
问题示例：
1 )从海量的日志数据中提取某一天访问百度次数最多的IP。
因为IP的数量还仅限于2^32个，所以可以考虑使用混列将IP直接存储在内存中进行统计。
3 .位图
适用范围：可快速检索、判定、删除数据，一般数据范围不超过int的10倍
基本原理和要点：使用bit数组指示是否存在特定元素，如8位电话号码
扩展： bloom过滤器可以视为向位图的扩展
问题示例：
1 )知道某份文件中含有电话号码。 每个号码是8位数字，计数不同号码的个数。
8位最多99 999 999，大概需要99m个bit，大概10几m字节的内存即可。2)2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
将bit-map扩展一下，用2bit表示一个数即可，0表示未出现，1表示出现一次，2表示出现2次及以上。或者我们不用2bit来进行表示，我们用两个bit-map即可模拟实现这个2bit-map。
4.堆
适用范围：海量数据前n大，并且n比较小，堆可以放入内存
基本原理及要点：最大堆求前n小，最小堆求前n大。方法，比如求前n小，我们比较当前元素与最大堆里的最大元素，如果它小于最大元素，则应该替换 那个最大元素。这样最后得到的n个元素就是最小的n个。适合大数据量，求前n小，n的大小比较小的情况，这样可以扫描一遍即可得到所有的前n元素，效率很 高。
扩展：双堆，一个最大堆与一个最小堆结合，可以用来维护中位数。
问题实例：
1)100w个数中找最大的前100个数。
用一个100个元素大小的最小堆即可。
5.双层桶划分 ----其实本质上就是【分而治之】的思想，重在“分”的技巧上！
适用范围：第k大，中位数，不重复或重复的数字
基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。可以通过多次缩小，双层只是一个例子。
扩展：
问题实例：
1).2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为2^8个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区 域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。
2).5亿个int找它们的中位数。
这个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落 到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。
实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定 区域的第几大数，在将该区域分成2^20个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20，就可以直接利用direct addr table进行统计了。
6.数据库索引
适用范围：大数据量的增删改查
基本原理及要点：利用数据的设计实现方法，对海量数据的增删改查进行处理。
扩展：
问题实例：
7.倒排索引(Inverted index)
适用范围：搜索引擎，关键字查询
基本原理及要点：为何叫倒排索引？一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。
以英文为例，下面是要被索引的文本：
T0 = "it is what it is"
T1 = "what is it"
T2 = "it is a banana"
我们就能得到下面的反向文件索引：
"a": {2}
"banana": {2}
"is": {0, 1, 2}
"it": {0, 1, 2}
"what": {0, 1}
检索的条件"what", "is" 和 "it" 将对应集合的交集。
正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在 正向索引中，文档占据了中心的位置，每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词，而反向索引则是单词指向了包含它的 文档，很容易看到这个反向的关系。
扩展：
问题实例：文档检索系统，查询那些文件包含了某单词，比如常见的学术论文的关键字搜索。
8.外排序
适用范围：大数据的排序，去重
基本原理及要点：外排序的归并方法，置换选择 败者树原理，最优归并树
扩展：
问题实例：
1).有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词。
这个数据具有很明显的特点，词的大小为16个字节，但是内存只有1m做hash有些不够，所以可以用来排序。内存可以当输入缓冲区使用。
9.trie树
适用范围：数据量大，重复多，但是数据种类小可以放入内存
基本原理及要点：实现方式，节点孩子的表示方式
扩展：压缩实现。
问题实例：
1).有10个文件，每个文件1G， 每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序 。
2).1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？
3).寻找热门查询：查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个，每个不超过255字节。
10.分布式处理 mapreduce
适用范围：数据量大，但是数据种类小可以放入内存
基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约。
扩展：
问题实例：
1).The canonical example application of MapReduce is a process to count the appearances of
each different word in a set of documents:
void map(String name, String document):
// name: document name
// document: document contents
for each word w in document:
EmitIntermediate(w, 1);
void reduce(String word, Iterator partialCounts):
// key: a word
// values: a list of aggregated partial counts
int result = 0;
for each v in partialCounts:
result += ParseInt(v);
Emit(result);
Here, each document is split in words, and each word is counted initially with a "1" value by
the Map function, using the word as the result key. The framework puts together all the pairs
with the same key and feeds them to the same call to Reduce, thus this function just needs to
sum all of its input values to find the total appearances of that word.
2).海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。
3).一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)？
经典问题分析
上千万or亿数据（有重复），统计其中出现次数最多的前N个数据,分两种情况：可一次读入内存，不可一次读入。
可用思路：trie树+堆，数据库索引，划分子集分别统计，hash，分布式计算，近似统计，外排序
所谓的是否能一次读入内存，实际上应该指去除重复后的数据量。如果去重后数据可以放入内存，我们可以为数据建立字典，比如通过 map，hashmap，trie，然后直接进行统计即可。当然在更新每条数据的出现次数的时候，我们可以利用一个堆来维护出现次数最多的前N个数据，当 然这样导致维护次数增加，不如完全统计后在求前N大效率高。
如果数据无法放入内存。一方面我们可以考虑上面的字典方法能否被改进以适应这种情形，可以做的改变就是将字典存放到硬盘上，而不是内存，这可以参考数据库的存储方法。
当然还有更好的方法，就是可以采用分布式计算，基本上就是map-reduce过程，首先可以根据数据值或者把数据hash(md5)后的值，将 数据按照范围划分到不同的机子，最好可以让数据划分后可以一次读入内存，这样不同的机子负责处理各种的数值范围，实际上就是map。得到结果后，各个机子 只需拿出各自的出现次数最多的前N个数据，然后汇总，选出所有的数据中出现次数最多的前N个数据，这实际上就是reduce过程。
实际上可能想直接将数据均分到不同的机子上进行处理，这样是无法得到正确的解的。因为一个数据可能被均分到不同的机子上，而另一个则可能完全聚集 到一个机子上，同时还可能存在具有相同数目的数据。比如我们要找出现次数最多的前100个，我们将1000万的数据分布到10台机器上，找到每台出现次数 最多的前 100个，归并之后这样不能保证找到真正的第100个，因为比如出现次数最多的第100个可能有1万个，但是它被分到了10台机子，这样在每台上只有1千 个，假设这些机子排名在1000个之前的那些都是单独分布在一台机子上的，比如有1001个，这样本来具有1万个的这个就会被淘汰，即使我们让每台机子选 出出现次数最多的1000个再归并，仍然会出错，因为可能存在大量个数为1001个的发生聚集。因此不能将数据随便均分到不同机子上，而是要根据hash 后的值将它们映射到不同的机子上处理，让不同的机器处理一个数值范围。
而外排序的方法会消耗大量的IO，效率不会很高。而上面的分布式方法，也可以用于单机版本，也就是将总的数据根据值的范围，划分成多个不同的子文件，然后逐个处理。处理完毕之后再对这些单词的及其出现频率进行一个归并。实际上就可以利用一个外排序的归并过程。
另外还可以考虑近似计算，也就是我们可以通过结合自然语言属性，只将那些真正实际中出现最多的那些词作为一个字典，使得这个规模可以放入内存。