| 转自：http://i.yoho.cn/473260/logview/1816730.htmlhtml 大数据量的问题是不少面试笔试中常常出现的问题，好比baidu google 腾讯 这样的一些涉及到海量数据的公司常常会问到。
下面的方法是我对海量数据的处理方法进行了一个通常性的总结，固然这些方法可能并不能彻底覆盖全部的问题，可是这样的一些方法也基本能够处理绝大多数遇到的问题。下面的一些问题基本直接来源于公司的面试笔试题目，方法不必定最优，若是你有更好的处理方法，欢迎与我讨论。
1.Bloom filter
适用范围：能够用来实现数据字典，进行数据的判重，或者集合求交集
基本原理及要点：
对 于原理来讲很简单，位数组+k个独立hash函数。将hash函数对应的值的位数组置1，查找时若是发现全部hash函数对应位都是1说明存在，很明显这 个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，由于该关键字对应的位会牵动到其余的关键字。因此一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就能够支持删除了。
还有一个比较重要的问题，如 何根据输入元素个数n，肯定位数组m的大小及hash函数个数。当hash函数个数k=(ln2)*(m/n)时错误率最小。在错误率不大于E的状况 下，m至少要等于n*lg(1/E)才能表示任意n个元素的集合。但m还应该更大些，由于还要保证bit数组里至少一半为0，则m应 该>=nlg(1/E)*lge 大概就是nlg(1/E)1.44倍(lg表示以2为底的对数)。
举个例子咱们假设错误率为0.01，则此时m应大概是n的13倍。这样k大概是8个。
注意这里m与n的单位不一样，m是bit为单位，而n则是以元素个数为单位(准确的说是不一样元素的个数)。一般单个元素的长度都是有不少bit的。因此使用bloom filter内存上一般都是节省的。
扩展：
Bloom filter将集合中的元素映射到位数组中，用k（k为哈希函数个数）个映射位是否全1表示元素在不在这个集合中。Counting bloom filter（CBF）将位数组中的每一位扩展为一个counter，从而支持了元素的删除操做。Spectral Bloom Filter（SBF）将其与集合元素的出现次数关联。SBF采用counter中的最小值来近似表示元素的出现频率。
问题实例：给你A,B两个文件，各存放50亿条URL，每条URL占用64字节，内存限制是4G，让你找出A,B文件共同的URL。若是是三个乃至n个文件呢？
根 据这个问题咱们来计算下内存的占用，4G=2^32大概是40亿*8大概是340亿，n=50亿，若是按出错率0.01算须要的大概是650亿个bit。 如今可用的是340亿，相差并很少，这样可能会使出错率上升些。另外若是这些urlip是一一对应的，就能够转换成ip，则大大简单了。
2.Hashing
适用范围：快速查找，删除的基本数据结构，一般须要总数据量能够放入内存
基本原理及要点：
hash函数选择，针对字符串，整数，排列，具体相应的hash方法。
碰撞处理，一种是open hashing，也称为拉链法；另外一种就是closed hashing，也称开地址法，opened addressing。
扩展：
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，就把新key 存储在左边的T1子表中，2-left也由此而来。在查找一个key时，必须进行两次hash，同时查找两个位置。
问题实例：
1).海量日志数据，提取出某日访问百度次数最多的那个IP。
IP的数目仍是有限的，最多2^32个，因此能够考虑使用hash将ip直接存入内存，而后进行统计。
3.bit-map
适用范围：可进行数据的快速查找，判重，删除，通常来讲数据范围是int的10倍如下
基本原理及要点：使用bit数组来表示某些元素是否存在，好比8位电话号码
扩展：bloom filter能够看作是对bit-map的扩展
问题实例：
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，效率不会很高。而上面的分布式方法，也能够用于单机版本，也就是将总的数据根据值的范围，划分红多个不一样的子文件，而后逐个处理。处理完毕以后再对这些单词的及其出现频率进行一个归并。实际上就能够利用一个外排序的归并过程。
另外还能够考虑近似计算，也就是咱们能够经过结合天然语言属性，只将那些真正实际中出现最多的那些词做为一个字典，使得这个规模能够放入内存。
转载请注明出处：http://bbs.xjtu.edu.cn
做者phylips@bmy
参考文献：
http://blog.csdn.net/jiaomeng/archive/2007/03/08/1523940.aspx d-Left Hashing
http://blog.csdn.net/jiaomeng/archive/2007/01/27/1495500.aspx
http://en.wikipedia.org/wiki/Bloom_filter
http://hi.baidu.com/xdzhang_china/blog/item/2847777e83fb020229388a15.html 应用Bloom Filter的几个小技巧
http://zh.wikipedia.org/wiki/%E5%80%92%E6%8E%92%E7%B4%A2%E5%BC%95面试 |