海量数据处理面试题全解析：涵盖99%高频考题

时间：11-08 神话故事提交错误

大家好，今天小编来为大家解答海量数据处理面试题全解析：涵盖99%高频考题这个问题，很多人还不知道，现在让我们一起来看看吧！

作者：七月

资料来源：结构定律与算法之道博客

前言

一般来说，含有“秒杀”、“99%”、“史上最全/最强”等字眼的标题往往有煽情之嫌，但更进一步说，如果读者读完这篇文章，他将一无所获。那么，我愿意承受这样的罪：-)。同时，这篇文章也可以看作是对这篇文章的总体抽象总结：海量数据处理的十道面试题和十种方法的总结。

毕竟，由于文章和理论的限制，本文将放弃大部分细节，只谈论方法/模型理论，并专注于用最流行、最直白的语言来解释相关问题。最后，必须强调的一件事是，全文是基于面试问题的分析。在实际的实践过程中，具体情况仍然需要具体分析，并且每个场景需要考虑的细节远远大于本文所描述的任何细节。一种解决方案要复杂得多。

好的，如果您有任何疑问，请随时告诉我。谢谢。

什么是海量数据处理？

所谓海量数据处理，无非是对海量数据的存储、处理和运算。海量是指数据量太大，要么无法在短时间内快速解决，要么数据太大，无法一次性加载到内存中。

解决办法是什么？时间上，我们可以使用巧妙的算法和适当的数据结构，例如布隆过滤器/哈希/位图/堆/数据库或倒排索引/trie树。对于空间来说，解决办法无外乎一种：大而缩小规模，分而治之（哈希映射），你不是说规模太大了吗？很简单，只要把大尺度缩小到小尺度，把每一个都打败就结束了。

至于所谓的单机和集群问题，通俗地说就是单机处理加载数据的机器有限（只要考虑CPU、内存、硬盘的数据交互），而单机则处理加载数据的机器有限（只要考虑CPU、内存、硬盘的数据交互）集群有多台机器，适合分布式处理和并行计算（更多考虑节点以及节点之间的数据交互）。

另外，通过这篇博客《大数据处理》中关于海量数据处理的文章，我们已经大致知道，处理海量数据问题无非是：

分而治之/哈希映射+哈希统计+堆/快速/归并排序；

双斗分工

布隆过滤器/位图；

Trie树/数据库/倒排索引；

外部排序；

Hadoop/Mapreduce 的分布式处理。

接下来，在本文第一部分，我们从set/map讲hashtable/hash_map/hash_set，简单介绍一下set/map/multiset/multimap和hash_set/hash_map/hash_multiset/hash_multimap的区别（基础是最当高层建筑拔地而起时很重要）。本文第二部分将结合相应的海量数据处理面试题对上述六种方法模型进行详细阐述。

第一部分，从set/map到hashtable/hash_map/hash_set

Hash_map/hash_set 会在本文第二部分中多次提到。我们简单介绍一下这些容器作为基本的准备工作。一般来说，STL容器有两种类型，

顺序容器（向量/列表/双端队列/堆栈/队列/堆），

关联容器。关联容器分为两类：set（集合）和map（映射表），以及它们的衍生品multiset（多键集合）和multimap（多键映射表）。这些容器都是基于RB-tree Finish的。另外，还有第三类关联容器，如hashtable（哈希表），以及以hashtable为完成的hash_set（哈希集）/hash_map（哈希映射表）/hash_multiset（哈希多键集）/底层机制。 hash_multimap（哈希多键映射表）。换句话说，set/map/multiset/multimap都包含RB-tree，hash_set/hash_map/hash_multiset/hash_multimap都包含hashtable。

所谓关系型容器类似于关系型数据库。每一条数据或者每一个元素都有一个键和一个真实的值，这就是所谓的Key-Value（键值对）。当一个元素插入到关联容器中时，容器的内部结构（RB树/哈希表）会根据其键值的大小，按照一定的规则将元素放置在适当的位置。

包括在非关系型数据库中，例如在MongoDB中，文档是最基本的数据组织形式，每个文档也是以Key-Value（键值对）的方式组织的。一个文档可以有多个Key-Value组合，每个Value可以是不同的类型，如String、Integer、List等。

{ "名称" : "七月",

‘性别’:‘男性’，

“年龄”: 23}

集/贴图/多重集/多重贴图

set和map一样，所有的元素都会根据元素的key值自动排序，因为set/map的所有各种操作都只是调用了RB-tree的操作行为。不过，值得注意的是，它们中的两个None 允许两个元素具有相同的键值。

区别在于：与map不同的是，set的元素可以同时具有真实值和键值。 set元素的键值是真实值，真实值是键值，而map的所有元素都是对。无论是真实值（value）还是键值（key），该对的第一个元素被视为键值，第二个元素被视为真实值。

至于multiset/multimap，它们的特点和用法与set/map完全相同。唯一的区别是它们允许键值重复，即所有插入操作都是基于RB-tree的insert_equal()而不是insert_unique()。

hash_set/hash_map/hash_multiset/hash_multimap

hash_set/hash_map，两者的所有操作都是基于hashtable。区别在于，hash_set和set一样，既有实值，也有键值，本质是键值，键值就是实值，而hash_map和map一样，每个元素都有实值（value））和一个关键值。 (key)，所以它的用法与上图基本相同。但由于hash_set/hash_map是基于hashtable的，所以它们不具备自动排序功能。为什么？因为hashtable没有自动排序功能。

至于hash_multiset/hash_multimap的特性，与上面的multiset/multimap完全相同。唯一的区别是，他们的hash_multiset/hash_multimap底层实现机制是hashtable（而multiset/multimap，如上所述，底层实现机制是RB-tree），所以他们的元素都不会自动排序，而是重复key值是允许的。

所以，总结一下，说白了，什么样的结构决定了它有什么样的属性，因为set/map/multiset/multimap都是基于RB-tree的，所以它们都有自动排序功能，而hash_set/hash_map /hash_multiset/hash_multimap 都是基于hashtable的，所以没有自动排序功能。至于添加前缀multi_，无非就是让键值重复。

还，

关于什么hash，请阅读博客中的这篇文章；

关于红黑树，可以参考博客中的系列文章，

关于hash_map的具体应用：请看这里，关于hash_set：请看这篇文章。

好，接下来请阅读本文第二部分，处理海量数据问题的六大关键。

第二部分：处理海量数据问题的六大关键

关键1、分而治之/Hash映射+Hash_map统计+堆/快速/归并排序

1、利用海量日志数据，提取某天百度访问次数最多的IP。

既然是海量数据处理，可想而知，给我们的数据一定是海量的。我们如何开始处理如此大量的数据？是的，无非就是分而治之/哈希映射+哈希统计+堆/快速/归并排序。说白了就是先映射，再统计，最后排序：

分而治之/哈希映射：如果数据太大，内存又有限，唯一的解决办法就是将大文件转化为小文件（模块化映射），即16字策略：大、小，打破它们一一缩小规模，一一解决。

hash_map统计：当大文件转换为小文件时，那么我们可以使用常规的hash_map(ip, value)进行频率统计。

堆/快速排序：统计完成后，进行排序（可以使用堆排序），得到次数最多的IP。

具体来说就是：“首先，这一天，将访问百度的日志中的IP取出来，一一写入到一个大文件中。注意，IP是32位的，最多有2^ 32个IP。也可以用映射的方法，比如%1000，把整个大文件映射成1000个小文件，然后找到每条小文章中出现频率最高的IP（可以用hash_map来频查所有）。那1000个文件中的IP）统计，然后找到每个文件中频率最高的IP）以及对应的频率，然后在最大的1000个IP中找到频率最高的IP，这就是你想要的数据处理的摘要。面试题及十种方法。

关于这个话题还有几个问题，如下：

1. 哈希取模是一种等价映射。相同的元素不会分散到不同的小文件中。也就是这里使用的是mod1000算法，所以同一个IP经过hash取模后只能落到同一个位置。文件无法分散。因为如果两个IP相等，那么Hash(IP)之后的哈希值是相同的。对哈希值取模（例如对1000 取模），它仍然必须相等。

2. 那么什么是哈希映射呢？简单来说，就是为了方便计算机在有限的内存中处理大数据，让数据通过映射和哈希的方法均匀分布在相应的内存位置（例如将大数据映射成一棵小树）并通过求余的方法存储在内存中的一棵小树中，或者将一个大文件映射成多个小文件），而这种映射哈希方法就是我们通常所说的哈希函数。设计良好的哈希函数可以均匀分布数据并减少冲突。虽然数据被映射到一些不同的位置，但数据仍然是相同的数据，只是它替换和表示原始数据的形式发生了变化。

OK，如果你有兴趣，还可以进一步了解一致性哈希算法。本文第五部分见博客：http://blog.csdn.net/v_july_v/article/details/6879101。

2. 查找热门查询，包括300 万个查询字符串中最热门的10 个查询。

原问题：搜索引擎会通过日志文件记录用户每次搜索时使用的所有搜索字符串。每个查询字符串的长度为1-255字节。假设目前有1000万条记录（这些查询字符串的重复度比较高，虽然总数是1000万条，但是如果去掉重复的话，不会超过300万条。一条查询的重复度越高string，表示查询字符串，用户越多越受欢迎）。请计算10 个最流行的查询字符串。所需内存不能超过1G。

答：从上面的问题1我们知道，如果数据很大，就会被分成小文件。例如，要查找1亿个IP中的前10名，可以先将IP分成1000个小文件，并保证一个文件中只能出现一种类型的IP，然后hashmap统计每个小文件中的IP并按数量排序，最后进行合并或最小堆处理每个小文件的前10个，得到最终结果。

但如果数据量比较小，可以一次性加载到内存中呢？比如问题2，虽然有1000万个Queries，但由于重复程度高，实际上只有300万个Queries，每个Queries都是255Byte。因此，我们可以考虑将它们全部放入内存中（假设300万个字符串不重复且都是最大长度，则最大占用内存为3M*1K/4=0.75G。因此，所有字符串都可以存放在内存中处理），现在我们只需要一个合适的数据结构。这里，HashTable绝对是我们的首选。

所以我们放弃分而治之/哈希映射步骤，直接进行哈希统计，然后排序。所以，对于这种典型的TOP K问题，采取的对策往往是：hashmap+堆。如下图：

Hash_map统计：首先对这批海量数据进行预处理。具体方法是：维护一个HashTable，其中Key为Query字符串，Value为Query出现的次数，即hash_map(Query, Value)。每次读取查询时，如果该字符串不在表中，则添加该字符串。并将Value值设置为1；如果该字符串在表中，则将该字符串的计数加一。最后，我们在O(N)的时间复杂度内，利用Hash表完成了统计；

堆排序：第二步是借助堆数据结构找到Top K。时间复杂度为N"logK。也就是说，借助堆结构，我们可以在log时间内找到并调整/移动。因此，维护一个大小为K（本题为10）的小根堆，然后遍历300 万个Query 来与根元素进行比较。所以，我们最终的时间复杂度是：O(N) + N" * O(logK)，（N为1000万，N"为300万）。

不要忘记本文描述的堆排序思想：“维护一个包含k个元素的最小堆，即用一个容量为k的最小堆来存储遍历到的前k个数，并假设它们是最大的k个” Number，构建堆需要O(k)，调整堆后（需要O(logk)），有k1k2.kmin（kmin设置为小顶堆中的最小元素）。继续遍历序列，一次遍历一个元素x。与堆顶元素相比，如果xkmin，则更新堆（x放入堆中，需要logk），否则堆不更新。这样，总耗时为O(k*logk+(n-k)*logk)=O(n*logk) 。该方法受益于搜索和其他操作的时间复杂度为logk这一事实。 ”——第三章继续，Top K算法问题的实现。

当然，你也可以使用trie树。键字段存储查询字符串出现的次数。如果没有出现则为0。最后用最小推10个元素来对出现频率进行排序。

3、有一个1G大小的文件，里面每一行都是一个字，字的大小不超过16字节，内存限制为1M。返回100 个最常见的单词。

从上面两个例子我们已经开始感觉到，用分而治之+哈希统计+堆/快速排序的套路已经屡试不爽了。接下来，再进行几次测试来验证它们。请看问题3：文件很大，内存有限。我应该怎么办？我还能做什么？无非是：

分而治之/哈希映射：顺序读取文件，对于每个单词x，取hash(x)%5000，然后将这个值存入5000个小文件中（记为x0,x1,x4999）。每个文件大约200k。如果部分文件大小超过1M，可以继续以类似的方式进行分割，直到分解后的小文件大小不超过1M。

hash_map统计：对于每个小文件，通过trie树/hash_map等来统计每个文件中出现的单词及其对应的频率。

堆/归并排序：取出频率最高的100个单词后（可以使用最小100个节点的堆），然后将这100个单词及其对应的频率存储到文件中，从而获得另外5000个文件。最后一步是合并这5000 个文件（类似于合并排序）。

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

如果每个数据元素只出现一次并且只在某台机器上出现，那么可以采取以下步骤来统计出现的前10个数据元素：

堆排序：要查找每台计算机上的TOP10，可以使用包含10个元素的堆来完成（TOP10小，使用最大的堆，TOP10大，使用最小的堆，例如查找TOP10，我们先取出前10个元素，调整为最小堆，如果找到，则扫描后面的数据，与堆顶元素比较，如果大于堆顶元素，则替换堆顶。堆与元素，然后将其调整为最小堆（堆中最终元素为TOP10最大）。

找到每台计算机上的TOP10后，然后将这100台计算机上的TOP10合并起来，总共得到1000条数据，然后使用与上面类似的方法来找到TOP10。

但是，如果相同的元素在不同的计算机中重复出现怎么办，如下例所示：

这时，你可以有两种方法：

遍历所有数据并重新散列它，以便相同的元素仅出现在一台计算机中。然后用上面提到的方法统计每个元素在每台计算机中出现的次数来找到TOP10，然后将每台计算机上的100个TOP10组合起来找到最终的TOP10。

或者，暴力解决：直接统计每个元素在每台计算机中出现的次数，然后将相同元素在不同机器中出现的次数相加，最后从所有数据中找到TOP10。

5.共有10个文件，每个文件1G。每个文件的每一行都存储用户的查询。每个文件的查询可以重复。系统会要求您按查询频率排序。

选项1：直接转至：

哈希映射：顺序读取10个文件，根据hash(query)%10的结果将查询写入另外10个文件（记为a0,a1,a9）。这样，每个新生成的文件大小约为1G左右（假设哈希函数是随机的）。

hash_map统计：找一台内存2G左右的机器，依次使用hash_map(query,query_count)统计每个query出现的次数。注意：hash_map(query,query_count) 用于统计每个查询出现的次数，而不是存储它们的值。如果出现一次，计数+1。

堆/快速/归并排序：使用快速/堆/归并排序按照出现次数进行排序，并将排序后的查询和对应的query_cout输出到文件中，从而得到10个排序文件（记为

）。最后，对这10个文件进行合并排序（内部排序和外部排序相结合）。根据这个选项1，这里是一个实现：https://github.com/ooooola/sortquery/blob/master/querysort.py。

另外，这道题还有另外两种方法：

方案二：一般查询总量有限，但重复次数比较多。可能所有查询都可以一次添加到内存中。这样我们就可以利用trie树/hash_map等直接统计每个查询出现的次数，然后根据出现的次数进行快速/堆/归并排序。

方案3：与方案1类似，但是散列后分成多个文件，可以交给多个文件处理，采用分布式架构（如MapReduce），最后合并。

6.给定两个文件a和b，每个文件存储50亿个url，每个url占用64字节，内存限制为4G，要求你找到文件a和b的公共url？

可以估算出每个文件的大小为5G64=320G，远大于4G的内存限制。所以不可能完全加载到内存中进行处理。考虑分而治之的方法。

分而治之/哈希映射：遍历文件a，获取各个URL

，然后将URL存储到1000个小文件中（表示为

，此处省略a1)中的写入。每个小文件大约300M。遍历文件b，将url按照a同样的方式存储在1000个小文件中（记为

）。经过这样的处理，所有可能的相同URL都在对应的小文件中（

），不对应的小文件不能有相同的URL。那么我们只需要在1000对小文件中找到相同的URL即可。

hash_set统计：当在每对小文件中找到相同的URL时，可以将其中一个小文件的URL存储在hash_set中。然后遍历另一个小文件的每个URL，看是否在刚刚构造的hash_set中。如果是，则它是一个通用URL，可以保存在文件中。

OK，这第一种方法：分而治之/哈希映射+哈希统计+堆/快速/归并排序，然后看最后四题，如下：

7、如何在海量数据中找到重复次数最多的那一个？

解决方案：先做哈希，然后找到模块映射成小文件，在每个小文件中找到重复次数最多的那个，记录重复次数。然后在上一步得到的数据中找出重复次数最多的就是你想要的（具体参考上一题）。

8、千万或上亿的数据（有重复），统计出现次数最多的前N个数据。

解决方案：当前机器的内存中应该能够存储数千万或数亿的数据。因此，可以考虑使用hash_map/搜索二叉树/红黑树等来统计次数。然后使用堆检索出现次数最多的前N 个数据。

9. 一个文本文件大约有10,000行，每行一个单词。要求统计出现频率最高的前10 个单词。请给出你的想法和时间复杂度分析。

方案一：如果文件比较大，无法一次性读入内存，可以使用哈希取模的方法，将大文件分解为多个小文件。对于单个小文件，使用hash_map统计每个小文件中最常见的10个文件。然后将出现的单词合并起来，找到最后10 个最常出现的单词。

方案二：通过hash模将一个大文件分解为多个小文件后，除了使用hash_map统计每个小文件中出现频率最高的10个单词外，还可以使用trie树统计每个单词出现的次数。时间复杂度为O(n*le)（le代表单词的平均长度）。最后还找到出现频率最高的前10个单词（可以用堆实现），时间复杂度为O(n*lg10)。

10. 有1000 万个字符串，其中一些是重复的。有必要删除所有重复项并保留没有重复项的字符串。如何设计和实现？

方案一：这道题用trie树比较合适，hash_map也可以。

方案二：从xjbzju:开始，1000万的数据规模插入操作完全不现实。我之前尝试过在stl下向集合中插入100万个元素，但速度慢得难以忍受。我感觉基于hash的实现不会比红黑树好多少。使用向量+排序+唯一可行得多。建议将其散列成小文件并在合成之前单独处理它们。

上述解决方案2中读者xbzju的方法让我想到了一些问题，那就是set/map和hash_set/hash_map的性能比较？总共有3个问题，如下：

1、在hash_set有千万级数据的情况下，insert操作是不是比set更好？这位博主：http://t.cn/zOibP7t提供的实际数据可靠吗？

2、map和hash_map的性能对比怎么样？谁做过相关实验？

3. 那么查询操作呢，如下一段所述？

或者当数据量较小时，使用map，构造速度较快，当数据量较大时，使用hash_map？

rbtree PK 哈希表

根据朋友邦卡毛做的红黑树和哈希表的性能测试发现，当数据量基本都是int类型key时，hashtable是rbtree的3-4倍，但是hashtable一般浪费大约一半的记忆。

因为hashtable执行的操作是%，而rbtree需要大量的比较。例如，rbtree需要查看值数据，每个节点还需要3个指针（或偏移量）。如果需要其他功能，比如统计某个范围内的按键数量，就需要一个计数成员。

并且1srbtree可以执行大约500,000+次插入，hashtable可以执行大约200万次。不过，在很多情况下，它的速度还是可以接受的。比如倒排索引，速度几乎一样，而且是单线程，倒排表的拉链长度也不会太大。正是因为基于树的实现其实并不比hashtable慢，所以数据库索引一般都使用B/B+树，而且B+树也是磁盘友好的（B树可以有效降低其高度，从而减少磁盘交互次数）。例如，非常流行的NoSQL数据库（例如MongoDB）也使用B树索引。关于B树系列可以参考本博客的这篇文章：从B树、B+树、B*树到R树。请等待进一步的实验演示。

11. 找到一个文本文件中前10个经常出现的单词，但是这次的文件比较长，比如说几亿或者几十亿行。简而言之，无法一次读入内存。求最优解。

方案一：首先，使用哈希和取模将文件分解为多个小文件。对于单个文件，使用上一个问题中的方法查找每个文件中出现频率最高的10 个单词。然后将它们合并以找到最后10 个最常出现的单词。

12. 找出100 万个数字中最大的100 个数字。

选项1：使用部分消除法。选择前100个元素进行排序，记为序列L。然后每次扫描剩余的元素x，与这100个已排序元素中最小的元素进行比较。如果大于最小元素，则删除最小元素，插入L进去。依次循环，直到扫描完所有元素。复杂度为O(100w*100)。

方案二：使用快速排序的思想。每次划分后，仅考虑大于轴的部分。当大于轴的部分超过100个时，使用传统排序算法排序，取前100个，复杂度为O(100w*100)。

选项3：在上一个问题中，我们已经提到它是用包含100个元素的最小堆来完成的。复杂度为O(100w*lg100)。

接下来我们看第二种方法，双层划分。

关键2、多层划分

多级划分——其实本质上还是分而治之的思想，重点是“分”的技巧！

适用范围：第k大、中位数、不重复或重复数

基本原理和要点：由于元素的范围很大，无法使用直接寻址表，因此通过多次划分逐步确定范围，最后在可接受的范围内进行。

问题示例：

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

这有点像鸽巢原理。整数的个数是2^32。也就是说，我们可以将这2^32个数字分成2^8个区域（比如用单个文件来表示一个区域），然后将数据分成不同的区域，然后不同的区域可以直接使用bitmap来求解。也就是说，只要有足够的磁盘空间，就可以轻松解决。

14.5 亿个整数来查找中位数。

想法1：这个

个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定区域的第几大数，在将该区域分成2^20个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20，就可以直接利用direct addr table进行统计了。思路二@绿色夹克衫：同样需要做两遍统计，如果数据存在硬盘上，就需要读取2次。方法同基数排序有些像，开一个大小为65536的Int数组，第一遍读取，统计Int32的高16位的情况，也就是0-65535，都算作0,65536 - 131071都算作1。就相当于用该数除以65536。Int32 除以 65536的结果不会超过65536种情况，因此开一个长度为65536的数组计数就可以。每读取一个数，数组中对应的计数+1，考虑有负数的情况，需要将结果加32768后，记录在相应的数组内。第一遍统计之后，遍历数组，逐个累加统计，看中位数处于哪个区间，比如处于区间k，那么0- k-1的区间里数字的数量sum应该密匙三：Bloom filter/Bitmap Bloom filter 关于什么是Bloom filter，请参看blog内此文：海量数据处理之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中的最小值来近似表示元素的出现频率。可以看下上文中的第6题： “6、给你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，则大大简单了。同时，上文的第5题：给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？如果允许有一定的错误率，可以使用Bloom filter，4G内存大概可以表示340亿bit。将其中一个文件中的url使用Bloom filter映射为这340亿bit，然后挨个读取另外一个文件的url，检查是否与Bloom filter，如果是，那么该url应该是共同的url（注意会有一定的错误率）。” Bitmap 关于什么是Bitmap，请看blog内此文第二部分：http://blog.csdn.net/v_july_v/article/details/6685962。下面关于Bitmap的应用，可以看下上文中的第13题，以及另外一道新题： “13、在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。方案1：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32 * 2 bit=1 GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。

方案2：也可采用与第1题类似的方法，进行划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。” 15、给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？方案1：frome oo，用位图/Bitmap的方法，申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。密匙四、Trie树/数据库/倒排索引 Trie树适用范围：数据量大，重复多，但是数据种类小可以放入内存基本原理及要点：实现方式，节点孩子的表示方式扩展：压缩实现。问题实例：上面的第2题：寻找热门查询：查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个，每个不超过255字节。上面的第5题：有10个文件，每个文件1G，每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序。 1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？上面的第8题：一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词。其解决方法是：用trie树统计每个词出现的次数，时间复杂度是O(n*le)（le表示单词的平准长度），然后是找出出现最频繁的前10个词。更多有关Trie树的介绍，请参见此文：从Trie树（字典树）谈到后缀树。数据库索引适用范围：大数据量的增删改查基本原理及要点：利用数据的设计实现方法，对海量数据的增删改查进行处理。关于数据库索引及其优化，更多可参见此文：http://www.cnblogs.com/pkuoliver/archive/2011/08/17/mass-data-topic-7-index-and-optimize.html；关于MySQL索引背后的数据结构及算法原理，这里还有一篇很好的文章：http://blog.codinglabs.org/articles/theory-of-mysql-index.html；关于B 树、B+ 树、B* 树及R 树，本blog内有篇绝佳文章：http://blog.csdn.net/v_JULY_v/article/details/6530142。倒排索引(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"将对应集合的交集。正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中，文档占据了中心的位置，每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词，而反向索引则是单词指向了包含它的文档，很容易看到这个反向的关系。扩展：问题实例：文档检索系统，查询那些文件包含了某单词，比如常见的学术论文的关键字搜索。关于倒排索引的应用，更多请参见：第二十三、四章：杨氏矩阵查找，倒排索引关键词Hash不重复编码实践，第二十六章：基于给定的文档生成倒排索引的编码与实践。密匙五、外排序适用范围：大数据的排序，去重基本原理及要点：外排序的归并方法，置换选择败者树原理，最优归并树问题实例： 1).有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词。这个数据具有很明显的特点，词的大小为16个字节，但是内存只有1M做hash明显不够，所以可以用来排序。内存可以当输入缓冲区使用。关于多路归并算法及外排序的具体应用场景，请参见blog内此文：第十章、如何给10^7个数据量的磁盘文件排序密匙六、分布式处理之Mapreduce MapReduce是一种计算模型，简单的说就是将大批量的工作（数据）分解（MAP）执行，然后再将结果合并成最终结果（REDUCE）。这样做的好处是可以在任务被分解后，可以通过大量机器进行并行计算，减少整个操作的时间。但如果你要我再通俗点介绍，那么，说白了，Mapreduce的原理就是一个归并排序。适用范围：数据量大，但是数据种类小可以放入内存基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约。问题实例： The canonical example application of MapReduce is a process to count the appearances of each different word in a set of documents: 海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。一共有N个机器，每个机器上有N个数。每个机器最多存O(N)个数并对它们操作。如何找到N^2个数的中数(median)？更多具体阐述请参见blog内：从Hadhoop框架与MapReduce模式中谈海量数据处理，及MapReduce技术的初步了解与学习。其它模式/方法论，结合操作系统知识至此，六种处理海量数据问题的模式/方法已经阐述完毕。据观察，这方面的面试题无外乎以上一种或其变形，然题目为何取为是：秒杀99%的海量数据处理面试题，而不是100%呢。OK，给读者看最后一道题，如下：非常大的文件，装不进内存。每行一个int类型数据，现在要你随机取100个数。我们发现上述这道题，无论是以上任何一种模式/方法都不好做，那有什么好的别的方法呢？我们可以看看：操作系统内存分页系统设计(说白了，就是映射+建索引)。 Windows 2000使用基于分页机制的虚拟内存。每个进程有4GB的虚拟地址空间。基于分页机制，这4GB地址空间的一些部分被映射了物理内存，一些部分映射硬盘上的交换文件，一些部分什么也没有映射。程序中使用的都是4GB地址空间中的虚拟地址。而访问物理内存，需要使用物理地址。关于什么是物理地址和虚拟地址，请看：物理地址 (physical address): 放在寻址总线上的地址。放在寻址总线上，如果是读，电路根据这个地址每位的值就将相应地址的物理内存中的数据放到数据总线中传输。如果是写，电路根据这个地址每位的值就将相应地址的物理内存中放入数据总线上的内容。物理内存是以字节(8位)为单位编址的。虚拟地址 (virtual address): 4G虚拟地址空间中的地址，程序中使用的都是虚拟地址。使用了分页机制之后，4G的地址空间被分成了固定大小的页，每一页或者被映射到物理内存，或者被映射到硬盘上的交换文件中，或者没有映射任何东西。对于一般程序来说，4G的地址空间，只有一小部分映射了物理内存，大片大片的部分是没有映射任何东西。物理内存也被分页，来映射地址空间。对于32bit的 Win2k，页的大小是4K字节。CPU用来把虚拟地址转换成物理地址的信息存放在叫做页目录和页表的结构里。物理内存分页，一个物理页的大小为4K字节，第0个物理页从物理地址 0x00000000 处开始。由于页的大小为4KB，就是0x1000字节，所以第1页从物理地址 0x00001000 处开始。第2页从物理地址 0x00002000 处开始。可以看到由于页的大小是4KB，所以只需要32bit的地址中高20bit来寻址物理页。返回上面我们的题目：非常大的文件，装不进内存。每行一个int类型数据，现在要你随机取100个数。针对此题，我们可以借鉴上述操作系统中内存分页的设计方法，做出如下解决方案：操作系统中的方法，先生成4G的地址表，在把这个表划分为小的4M的小文件做个索引，二级索引。30位前十位表示第几个4M文件，后20位表示在这个4M文件的第几个，等等，基于key value来设计存储，用key来建索引。但如果现在只有10000个数，然后怎么去随机从这一万个数里面随机取100个数？请读者思考。更多海里数据处理面试题，请参见此文第一部分：http://blog.csdn.net/v_july_v/article/details/6685962。参考文献十道海量数据处理面试题与十个方法大总结；海量数据处理面试题集锦与Bit-map详解；十一、从头到尾彻底解析Hash表算法；海量数据处理之Bloom Filter详解；从Trie树（字典树）谈到后缀树；第三章续、Top K算法问题的实现；第十章、如何给10^7个数据量的磁盘文件排序；从B树、B+树、B*树谈到R 树；第二十三、四章：杨氏矩阵查找，倒排索引关键词Hash不重复编码实践；第二十六章：基于给定的文档生成倒排索引的编码与实践；从Hadhoop框架与MapReduce模式中谈海量数据处理；第十六~第二十章：全排列，跳台阶，奇偶排序，第一个只出现一次等问题； http://blog.csdn.net/v_JULY_v/article/category/774945； STL源码剖析第五章，侯捷著； 2012百度实习生招聘笔试题：http://blog.csdn.net/hackbuteer1/article/details/7542774。后记经过上面这么多海量数据处理面试题的轰炸，我们依然可以看出这类问题是有一定的解决方案/模式的，所以，不必将其神化。然这类面试题所包含的问题还是比较简单的，若您在这方面有更多实践经验，欢迎随时来信与我不吝分享：zhoulei0907@yahoo.cn。当然，自会注明分享者及来源。不过，相信你也早就意识到，若单纯论海量数据处理面试题，本blog内的有关海量数据处理面试题的文章已涵盖了你能在网上所找到的70~80%。但有点，必须负责任的敬告大家：无论是这些海量数据处理面试题也好，还是算法也好，面试时，70~80%的人不是倒在这两方面，而是倒在基础之上(诸如语言，数据库，操作系统，网络协议等等)，所以，无论任何时候，基础最重要，没了基础，便什么都不是。最后，推荐国外一面试题网站：http://www.careercup.com/，以及个人正在读的Redis/MongoDB绝佳站点：http://blog.nosqlfan.com/。