介绍海量数据的处理方法。

适用范围:可用于实现数据字典、判断数据重复或设置交集。

基本原则和要点:

原理很简单，位数组+k个独立哈希函数。如果哈希函数对应的值的位数组设置为1，如果发现哈希函数对应的所有位都是1，显然这个过程并不能保证搜索结果是100%正确。同时不支持删除插入的关键字，因为该关键字对应的位会影响其他关键字。因此，一个简单的改进是计数布隆过滤器，它可以通过用计数器数组替换位数组来支持删除。

还有一个重要的问题，比如如何根据输入元素的个数n来确定比特数组m的大小和哈希函数的个数，当哈希函数个数k=(ln2)*(m/n)时，错误率最小。如果错误率不大于E，m必须至少等于n*lg(1/E)才能表示任意一组n个元素。但m要大一些，因为要保证位数组至少有一半是0，所以m要>；=nlg(1/E)*lge大概是nlg(1/E)1.44倍(lg代表以2为底的对数)。

比如我们假设错误率是0.01，那么m应该是n的13倍左右，所以k大概是8。

这里注意m和n的单位是不同的，m是比特的单位，n是元素个数的单位(准确的说是不同元素的个数)。通常，单个元素的长度有许多位。所以在内存中使用bloom filter通常比较经济。

扩展:

Bloom filter将集合中的元素映射到一个位数组，所有映射位是否都是1带k(k是哈希函数的个数)表示元素是否在这个集合中。计数布隆过滤器(CBF)将位数组中的每一位扩展成一个计数器，从而支持元素的删除。光谱布鲁姆过滤器(SBF)将其与收集元素的出现次数相关联。SBF使用计数器中的最小值来估计元素出现的频率。

问题举例:我给你两个文件，A和B，每个文件有50亿个URL，每个URL占用64个字节，内存限制为4G，这样你就可以找出和A、B文件相同的URL。如果是三档甚至n档呢？

根据这个问题，我们来计算一下内存占用。4g = 2 32约为40亿*8约为340亿，n = 50亿。如果误码率为0.01，大约需要650亿比特。现在可用的是340亿，差不了多少，可能会增加错误率。另外，如果这些urlip和ip一一对应，就可以转换成IP，这就大大简化了。

2.散列法

适用范围:可以快速查找和删除的基本数据结构，通常需要可以放入内存的数据总量。

基本原则和要点:

哈希函数选择，针对字符串，整数，排列，具体对应哈希方法。

碰撞处理，一种是开散列法，也叫拉链法；另一种是封闭式散列，也称为开放式寻址。

扩展:

左哈希中的d表示倍数。让我们先简化这个问题，看看2-left哈希。2左哈希是指将一个哈希表分成长度相等的两半，分别称为T1和T2，并为T1和T2分别提供一个哈希函数h1和h2。存储新密钥时，同时使用两个哈希函数进行计算，得到两个地址h1[key]和h2[key]。此时，需要检查T1中h1[key]的位置和T2中h2[key]的位置，哪个位置存储了更多(碰撞)的密钥，然后在负载较少的位置存储新的密钥。如果有多少边就有多少边，比如两个位置都是空的或者存储了一个键，新的键存储在左边的T1子表中，2-left由此而来。当查找一个键时，必须散列两次，同时查找两个位置。

问题举例:1)。海量日志数据，提取某一天访问百度次数最多的IP。

IP的数量还是有限的，最多2 ^ 32，可以考虑使用hash直接将IP存储在内存中，然后进行统计。

3 .位图

适用范围:可以快速查找、复制和删除数据。一般来说，数据范围小于int的10倍。

基本原理和要点:用位数组表示某些元素是否存在，如8位电话号码。

扩展:bloom filter可以看作是位图的扩展。

问题示例:

1)已知一个文件包含一些电话号码，每个号码为8位，统计不同号码的个数。

8位最多99 999 999，需要99m位左右，或者10 MB左右的内存。

2)找出2.5亿个整数中不重复的整数个数，内存空间不足以容纳这2.5亿个整数。

展开2位图，就用2位表示一个数，0表示不出现，1表示出现一次，2表示出现两次以上。或者我们不用2bit来表示，可以用两个位图来模拟实现这个2 bit的位图。

堆积

适用范围:海量数据的前n个大，n个比较小，可以放入内存堆。

基本原理和要点:最大堆小于前n，最小堆大于前n .方法，比如求前n小，我们把当前元素和最大堆中最大的元素进行比较，如果小于最大的元素，就要替换那个最大的元素。这样，最后的n个元素就是最小的n个元素。适用于大数据量，前n个小，n的大小比较小，这样一次扫描就可以得到前n个元素的全部，效率很高。

扩展:双堆，一个最大堆结合一个最小堆，可以用来维护中间值。

问题示例:

1)在100个w数中找出最大的前100数。

使用至少100个元素的堆。

5.双筒分割

适用范围:k个最大、中间、不重复或重复的数字

基本原理和要点:由于元素范围太大，无法使用直接寻址表，所以通过多次划分逐步确定范围，然后最终在可接受的范围内进行。可以缩小很多倍，双层只是一个例子。

扩展:

问题示例:

1). 2.5亿个整数求不重复整数的个数，内存空间不够容纳这2.5亿个整数。

有点像鸽子窝原理，整数是2 ^ 32，也就是我们可以把2 ^ 32的数分成2 ^ 8个区域(比如单个文件代表一个区域)，然后把数据分成不同的区域，然后不同的区域可以直接用位图求解。也就是说，只要有足够的磁盘空间，就可以轻松解决。

2) .5亿个int找到他们的中值。

这个例子比上面那个更明显首先我们把int分成2个16的区域，然后读取数据统计落入每个区域的数字个数。那么我们就可以根据统计结果来判断中位数落在哪个区域，知道这个区域最大的数正好是中位数。然后，在第二次扫描中，我们只需要计算落在这个区域的那些数字。

其实如果不是int而是int64，经过三次这样的划分，我们可以降低到可以接受的程度。即可以将int64划分为2 ^ 24个区域，然后确定区域的最大个数，再将区域划分为2 ^ 20个子区域，再确定子区域的最大个数，然后子区域的个数只有2 ^ 20，这样就可以直接使用直接addr表进行统计。

6.数据库索引

适用范围:增加、删除、修改、查询大数据。

基本原理和要点:利用数据的设计和实现方法，处理海量数据的添加、删除和查询。

扩展:

问题示例:

7.倒排索引

适用范围:搜索引擎，关键词查询

基本原理和要点:为什么叫倒排索引？在全文搜索下，使用索引方法来存储单词在一个文档或一组文档中的存储位置的映射。

以英语为例，下面是要索引的文本:

T0 = "事情就是这样"

T1 = "这是什么"

T2 =“这是一根香蕉”

我们可以得到下面的反向文件索引:

" a": {2}

“香蕉”:{2}

"是":{0，1，2}

"它":{0，1，2}

"什么":{0，1}

检索条件“什么”、“是”和“它”将对应于集合的交集。

为存储每个文档而发展到索引中的单词列表。前向索引的查询经常会遇到每个文档的有序频繁全文查询的查询和验证文档中每个单词的验证。在前向索引中，文档占据中心位置，每个文档指向它所包含的一系列索引项。也就是说，文档指向它所包含的词，而倒排索引指向包含它的文档的词，所以很容易看出这种倒排关系。

扩展:

问题举例:文献检索系统，查询哪些文献包含某个词，比如常见学术论文的关键词搜索。

8.外部排序

适用范围:大数据的排序和去重。

基本原理和要点:外部排序的归并方法，替换选择失败者树原理，最优归并树。

扩展:

问题示例:

1).有一个文件，大小为1G，其中每行是一个字，字长不超过16字节，内存限制大小为1M。返回频率最高的100个单词。

这个数据特征明显，字长16字节，但内存只有1m，不够哈希用，可以用来排序。内存可以用作输入缓冲器。

9 .圣诞树

适用范围:数据量大，重复多，但小类型的数据可以放入内存。

基本原则和要点:实现方式，节点子节点的表示方式。

扩展:压缩实现。

问题示例:

1).有10个文件，每个文件是1G，每个文件的每一行都存储了用户的查询，每个文件的查询都可能重复。我要你按照查询频率排序。

2) .10万个字符串，有些是相同的(重复的)，所以需要去掉所有重复的字符串，保留不重复的字符串。如何设计和实现？

3)搜索热门查询:查询字符串的重复率比较高。虽然总数是10万，但是如果去掉重复，也不会超过300万，每个查询字符串也不会超过255字节。

10.分布式处理mapreduce

适用范围:数据量大，但小类型的数据可以放入内存。

基本原理和要点:把数据交给不同的机器处理，划分数据，归约结果。

扩展:

问题示例:

1).MapReduce的典型示例应用程序是一个计算

一组文档中的每个不同的单词:

无效映射(字符串名称，字符串文档):

//名称:文档名称

//文档:文档内容

对于文档中的每个单词w:

EmitIntermediate(w，1)；

void reduce(字符串字，迭代器部分计数):

//键:一个字

//值:聚合部分计数的列表

int result = 0；

对于部分计数中的每个v:

result+= parse int(v)；

发出(结果)；

在这里，每个文档都被拆分成单词，每个单词最初都用“1”值进行计数

Map函数，使用单词作为结果键。该框架将所有配对放在一起

同一个键，并将它们馈送到同一个调用来减少，因此这个函数只需要

对所有输入值求和，找出该单词的总出现次数。

2).海量数据分布在100台计算机上。想办法高效的统计出这批数据的TOP10。

3).一个* * *有n台机器，每台机器有n个数。每台机器最多可以存储O(N)个数字并对其进行操作。如何求n 2个数的中位数？

经典问题分析

几千万或几十亿的数据(有重复)，统计出现频率最高的前n个数据，分两种情况:一次可以读入内存，一次不行。

可用思路:trie树+堆、数据库索引、分区子集统计、hash、分布式计算、近似统计、外部排序。

能否一次性读入内存，其实应该是指去除重复后的数据量。如果去重后的数据可以放入内存，我们可以为数据建立一个字典，比如map，hashmap，trie，然后直接统计。当然，在更新每条数据的出现次数时，我们可以用堆来维护出现次数最多的前n条数据。但是这样会导致维护次数增加，不如完全统计后找到前n个数据效率高。

如果数据放不进内存。一方面可以考虑是否可以改进上述字典法以适应这种情况。我们可以做的改变是将词典存储在硬盘上，而不是内存上，可以参考数据库的存储方式。

当然还有更好的办法，就是可以采用分布式计算，基本上就是一个map-reduce的过程。第一，数据可以根据数据值或者hash(md5)后的值按照范围划分到不同的计算机上，最好是让数据划分后一次性读入内存，让不同的计算机负责处理各种数值范围，其实就是一个映射。得到结果后，每台计算机只需要把出现频率最高的前n个数据拿出来，然后在所有数据中汇总选择出现频率最高的前n个数据，这其实就是reduce过程。

其实你可能是想把数据直接分布到不同的电脑上进行处理，所以得不到正确的解。因为一个数据可能均匀分布到不同的计算机上，而另一个数据可能完全聚合到一台计算机上，可能仍然有相同数量的数据。比如我们要找次数最多的前100，我们就把10万的数据分布到10台机器上，找到次数最多的前100。合并后不能保证找到真正的100，因为比如可能会找到次数最多的100。但是分为10台机器，所以每台机器上只有1000台机器。假设那些排在1000之前的机器全部单独分布在一台机器上，比如有1001台机器，那么这一台有1000的就会被淘汰，即使如此，我们也不能把数据随机划分到不同的计算机上，而是根据哈希值映射到不同的计算机上进行处理，这样不同的计算机就可以处理一个范围的值。

外部排序的方式会消耗大量的IO，效率不会很高。上面的分布式方法也可以用于单机版，即把总数据按照取值范围分成几个不同的子文件，然后逐个处理。处理后，合并单词及其出现频率。事实上，您可以使用外部排序合并过程。

此外，还可以考虑近似计算，即结合自然语言属性，只把那些在现实实践中出现次数最多的词作为字典，这样就可以把这个尺度记忆进去。