数据结构与算法（19）：海量数据处理

一、何谓海量数据处理？

所谓海量数据处理，其实很简单，海量，海量，何谓海量，就是数据量太大，所以导致要么是无法再较短时间内迅速解决，要么是数据太大，导致无法一次性装入内存。

那解决办法呢？针对时间，我们可以采用巧妙的算法搭配合适的数据结构，如Bloom Filter、Hash、Bit-map、堆、数据库或倒排索引、trie，针对空间，无非就一个办法：大而化小、分而治之、hash映射，你不是说规模太大嘛，那简单啊，就把规模大化为规模小的，各个击破不就完了嘛。

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

再者，通过本blog内的有关海量数据处理的文章，我们已经大致知道，处理海量数据问题无非就是：

分而治之、hash映射+hash统计+堆、快速、归并排序；
双层桶划分
Bloom Filter、bitmap
trie树、数据库、倒排索引；
外排序
分布式处理之Hadoop、Mapreduce

下面，本文第一部分、从Set、Map谈到hashtable、hash_map、hash_set，简要介绍下Set、Map、Multiset、Multimap，及hash_set、hash_map、hash_multiset、hash_multimap之区别，而第二部分，则针对上述6种方法模式结合对应的海量数据处理面试题分别具体阐述。

二、从Set、Map谈到hashtable、hash_map/hash_set

稍后本文第二部分将多次提到hash_map、hash_set，下面稍稍介绍下这些容器，以作为基础准备。一般来说，STL容器分为两种

序列式容器：vector、list、deque、stack、queue、heap
关联式容器：关联式容器又分为set（集合）和map（映射表）两大类，以及这两大类的衍生体（多键集合）和multimap（多键映射表），这些容器均以RB-tree完成。此外，还有第三类关联容器，如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），即所谓的Key-Value（键-值对）。当元素被插入到关联式容器中时，容器内结构（RB-Tree、hashtable）便依照其键值大小，以某种特定规则将这个元素放置于适当位置。

包括在非关联式数据库中，比如，在MongoDB内，文档（document）是最基本的数据组织形式，每个文档也是以Key-Value(键-值对)的方式组织起来。一个文档可以有多个Key-Value组合，每个Value可以是不同的类型，比如String、Integer、List等等。${“name”:”July”,”Sex”:”male”,”age”:23}$

2.1 关联式容器之集合：set/map/multimap/multimap

set，同map一样，所有元素都会根据元素的键值自动被排序，因为set、map两者的所有操作，都是调用RB-tree的操作行为，不过，值得注意的是，两者都不允许两个元素有相同的键值。

不同的是，set的元素不像map那样可以同时拥有实值（value）和键值（key），set元素的键值就是实值，实值就是键值，而map的所有元素都是pair，同时拥有实值（value）和键值（key），pair的第一个元素被视为键值，第二个元素被视为实值。

至于multiset、multimap，他们的特性及用法和set、map完全相同，唯一的差别就在于它们允许键值重复，即所有的插入操作基于RB-tree的insert——equal()而非insert_unique()。

2.2 关联式容器之映射表：hash_set/hash_map/hash_multiset/hash_multimap

hash_set/hash_map，两者的一切操作都是基于hashtable之上。hash_set同set一样，同时拥有实值和键值，且实质就是键值，键值就是实值，而hash_map同map一样，每一个元素同时拥有一个实值(value)和一个键值(key)，所以其使用方式，和上面的map基本相同。但由于hash_set/hash_map都是基于hashtable之上，所以不具备自动排序功能。为什么?因为hashtable没有自动排序功能。

至于hash_multiset/hash_multimap的特性与上面的multiset/multimap完全相同，唯一的差别就是它们hash_multiset/hash_multimap的底层实现机制是hashtable（而multiset/multimap，上面说了，底层实现机制是RB-tree），所以它们的元素都不会被自动排序，不过也都允许键值重复。

所以，综上，说白了，什么样的结构决定其什么样的性质，因为set/map/multiset/multimap都是基于RB-tree之上，所以有自动排序功能，而hash_set/hash_map/hash_multiset/hash_multimap都是基于hashtable之上，所以不含有自动排序功能，至于加个前缀multi_无非就是允许键值重复而已。

三、处理海量数据问题之六把密钥

密钥一：分而治之/Hash映射+Hash_map统计+堆/快/归并排序

这一部分介绍处理海量数据问题的第一把密钥：分而治之、哈希映射+Hash统计+堆、快速、归并排序

（1）海量日志数据，提取出某日访问

既然是海量数据处理，那么可想而知，给我们的数据那就一定是海量的。针对这个数据的海量，我们如何着手呢?对的，无非就是分而治之/hash映射 + hash统计 + 堆/快速/归并排序，说白了，就是先映射，而后统计，最后排序：

分而治之/hash映射：针对数据太大，内存受限，只能是：把大文件化成(取模映射)小文件，即16字方针：大而化小，各个击破，缩小规模，逐个解决
hash统计：当大文件转化了小文件，那么我们便可以采用常规的Hashmap(ip，value)来进行频率统计。
堆/快速排序：统计完了之后，便进行排序(可采取堆排序)，得到次数最多的IP

具体而论，“首先是这一天，并且是访问百度的日志的IP取出来，逐个写到一个大文件中。注意到IP是32位的，最多有个$2^{32}$个IP。同样可以采用映射的方法，比如%1000，把整个大文件映射为1000个小文件，再找出每个小文件中出现频率最大的IP（可以采用Hash_map对那1000个文件中的所以IP进行频率统计，然后依次找出各个文件中频率最大的那个IP）及相应的频率。然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。”

关于本题，还有几个问题：

Hash取模是一种等价映射，不会存在同一个元素分散到不同小文件中的情况，即这里采用的是mod1000算法，那么相同的IP在hash取模后，只可能落在同一个文件中，不可能被分散的。因为如果两个IP相等，那么经过Hash（IP）之后的哈希值是相同的，将此哈希值取模，必定仍然相等。
那到底什么是hash映射呢？简单来说，就是为了便于计算机在有限的内存中处理大数据，从而通过一种映射散列的方式让数据均匀分布在对应的内存位置（如大数据通过取余的方式映射城小数存放在内存中，或者大文件映射成多个小文件），而这个映射散列方式便是我们通常所说的hash函数，设计的好的hash函数能让数据均匀分布而减少冲突。尽管数据映射到了另外一些不同的位置，但数据还是原来的数据，只是代替和表示这些原始数据的形式发生了变化而已。

（2）寻找热门查询，300万个查询字符串中统计最热门的10个查询

原题：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1~255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门），请你统计最热门的10个查询串，要求使用的内存不能超过1G。

由上面那题可知，数据大则划分为小的，比如一亿个IP求Top10，可先%1000将IP分到1000个小文件中去，并保证一种IP只出现在一个文件中，再对每个小文件中的IP进行Hashmap计数统计并按数量排序，最后归并或者最小堆一次处理每个小文件的top10以得到最后的结。

但如果数据规模比较小，能一次性装入内存呢？比如这第二题，虽然有一千万个Query，但是由于重复度比较高，因此事实上只有300万的Query，每个Query255Byte，因此我们可以考虑把它们都放进内存中去（300万个字符串假设没有重复，都是最大长度，那么最多占用内存3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行处理），而现在只需要一个合适的数据结构，在这里，HashTable绝对是我们优先的选择。

所以我们放弃分而治之、Hash映射的步骤，直接上Hash统计，然后排序。所以，针对此类典型的Top K问题，采取的对策往往是：Hashmap+堆。如下所示：

Hash_map统计：先对这批海量数据预处理。具体方法是：维护一个Key为Query字符串，Value为该QUery出现次数的HashTable，即Hash_map(Query,Value)，每次读取一个Query，如果该字符串不在table内，则加入该字串，并且将Value值设为1；如果该字串在Table中，那么将该字串的计数加1即可。最终我们在O(N)的时间复杂度内用Hash表完成了统计。
堆排序：借助堆这个数据结构，找出Top K，时间复杂度为NlogK。即借助堆结构，我们可以在log量级的时间内查找和调整。因此，维护一个K（该题目中是10）大小的小根堆，然后遍历300万的Query，分别和根元素进行对比。所以，我们最终的时间复杂度是$O(N)+N·O(logK)$，（N为1000万，N’是300万）

这篇文章中所述的堆排序思路：“维护k个元素的最小堆，即用容量为K的最小堆存储最先遍历到的k个数，并假设它们即是最大的k个数，建堆费时$O(k)$，并调整堆，费时$O(logk)$，这样我们就有$k_1>k_2>…k_{min}$（kmin设为小顶堆中最小元素）。继续遍历数列，每次遍历一个元素x，与堆顶元素比较，若$x>k_{min}$，则更新堆（用时$log_k$），否则不更新堆。这样下来，总费时$O（klogk+（n-k）logk）=O（n*logk）$。此方法得益于在堆中，查找等各项操作时间复杂度均为logk。”

当然，你也可以采用trie树，关键字域存该查询串出现的次数，没有出现为0。最后用10个元素的最小推来对出现频率进行排序。

（3）有一个1G大小的文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小时1M。返回频数最高的100个词。

由上面那两个例题，分而治之 + hash统计 + 堆/快速排序这个套路，我们已经开始有了屡试不爽的感觉。下面，再拿几道再多多验证下。请看此第3题：又是文件很大，又是内存受限，咋办?还能怎么办呢?无非还是：

分而治之/hash映射：顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为x0,x1,…x4999）中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。
hash统计：对每个小文件，采用trie树、hash——map等统计每个文件中出现的词以及相应的频率。
堆、归并排序：取出出现频率最大的100个词（可以用含100个结点的最小堆），并把100个词及相应的频率存入文件，这样又得到了5000个文件。最后就是把这5000个文件进行归并（类似于归并排序）的过程了。

（4）海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。

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

堆排序：在每台电脑上求出TOP10，可以采用包含10个元素的堆完成（TOP10小，用最大堆，TOP10大，用最小堆，比如求TOP10大，我们首先取前10个元素调整成最小堆，如果发现，然后扫描后面的数据，并与堆顶元素比较，如果比堆顶元素大，那么用该元素替换堆顶，然后再调整为最小堆。最后堆中的元素就是TOP10大）。
求出每台电脑上的TOP10后，然后把这100台电脑上的TOP10组合起来，共1000个数据，再利用上面类似的方法求出TOP10就可以了。

但如果同一个元素重复出现在不同的电脑中呢，如下例子所述：就拿2台机器求top2的情况来说，第一台：a(50)、b(50)、c(49)、d(49)、e(0)、e(0)，第二台：a(0)、b(0)、c(49)、d(49)、e(50)、f(50)，这个时候，你可以有两种方法：
1. 遍历一遍所有数据，重新hash取摸，如此使得同一个元素只出现在单独的一台电脑中，然后采用上面所说的方法，统计每台电脑中各个元素的出现次数找出TOP10，继而组合100台电脑上的TOP10，找出最终的TOP10。
2. 暴力求解：直接统计统计每台电脑中各个元素的出现次数，然后把同一个元素在不同机器中的出现次数相加，最终从所有数据中找出TOP10。

（5）有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。

hash映射：顺序读取10个文件，按照hash(query)%10的结果将query写入到另外10个文件（记为）中。这样新生成的文件每个的大小大约也1G（假设hash函数是随机的）。
hash统计：找一台内存在2G左右的机器，依次对用hash_map(query, query_count)来统计每个query出现的次数。注：hash_map(query,query_count)是用来统计每个query的出现次数，不是存储他们的值，出现一次，则count+1。
堆/快速/归并排序：利用快速/堆/归并排序按照出现次数进行排序。将排序好的query和对应的query_cout输出到文件中。这样得到了10个排好序的文件。对这10个文件进行归并排序（内排序与外排序相结合）。

除此之外，此题还有以下两个方法：

一般query的总量是有限的，只是重复的次数比较多而已，可能对于所有的query，一次性就可以加入到内存了。这样，我们就可以采用trie树/hash_map等直接来统计每个query出现的次数，然后按出现次数做快速/堆/归并排序就可以了。
与方案1类似，但在做完hash，分成多个文件后，可以交给多个文件来处理，采用分布式的架构来处理（比如MapReduce），最后再进行合并。

（6）给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？

可以估计每个文件的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。

分而治之/hash映射：遍历文件a，对每个url求取，然后根据所取得的值将url分别存储到1000个小文件（记为$a_0,a_1…..,a_{999}$）中。这样每个小文件的大约为300M。遍历文件b，采取和a相同的方式将url分别存储到1000小文件中（记为$b_0,b_1……,b_{999}$）。这样处理后，所有可能相同的url都在对应的小文件（$a_0vsb_0,a_1vsb_1……a_{999}vsb_{999}$）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。
hash_set统计：求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。

（7）怎么在海量数据中找出重复次数最多的一个？

先做hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求（具体参考前面的题）。

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

上千万或上亿的数据，现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后利用堆取出前N个出现次数最多的数据。

（9）一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。

方案1：如果文件比较大，无法一次性读入内存，可以采用hash取模的方法，将大文件分解为多个小文件，对于单个小文件利用hash_map统计出每个小文件中10个最常出现的词，然后再进行归并处理，找出最终的10个最常出现的词。
方案2：通过hash取模将大文件分解为多个小文件后，除了可以用hash_map统计出每个小文件中10个最常出现的词，也可以用trie树统计每个词出现的次数，时间复杂度是$O(nle)$（le表示单词的平准长度），最终同样找出出现最频繁的前10个词（可用堆来实现），时间复杂度是$O(nlg10)$。

密钥二：双层桶划分

双层桶划分，其实本质上还是分而治之的思想，重在“分”的技巧上！

适用范围：第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进行统计了。

密钥三：Bloom filter/Bitmap

Bloom filter

海量数据处理之Bloom Filter详解

适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集

基本原理及要点：对于原理来说很简单，位数组+k个独立hash函数。将hash函数对应的值的位数组置1，查找时如果发现所有hash函数对应位都是1说明存在，很明显这个过程并不保证查找的结果是100%正确的。同时也不支持删除一个已经插入的关键字，因为该关键字对应的位会牵动到其他的关键字。所以一个简单的改进就是 counting Bloom filter，用一个counter数组代替位数组，就可以支持删除了。

还有一个比较重要的问题，如何根据输入元素个数n，确定位数组m的大小及hash函数个数。当hash函数个数$k=(ln2)(m/n)$时错误率最小。在错误率不大于E的情况下，m至少要等于$nlg(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，则大大简单了。

同时，上文的第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介绍

Bit-map详解

所谓的Bit-map就是用一个bit位来标记某个元素对应的Value，而Key即是该元素。由于采用了Bit为单位来存储数据，因此在存储空间方面，可以大大节省。

如果说了这么多还没明白什么是Bit-map，那么我们来看一个具体的例子，假设我们要对0-7内的5个元素(4,7,2,5,3)排序（这里假设这些元素没有重复）。那么我们就可以采用Bit-map的方法来达到排序的目的。要表示8个数，我们就只需要8个Bit（1Bytes），首先我们开辟1Byte的空间，将这些空间的所有Bit位都置为0，如下图：

然后遍历这5个元素，首先第一个元素是4，那么就把4对应的位置为1（可以这样操作 p+(i/8)|(0×01<<(i%8)) 当然了这里的操作涉及到Big-ending和Little-ending的情况，这里默认为Big-ending）,因为是从零开始的，所以要把第五位置为一，如下图：

然后再处理第二个元素7，将第八位置为1,，接着再处理第三个元素，一直到最后处理完所有的元素，将相应的位置为1，这时候的内存的Bit位的状态如下：

然后我们现在遍历一遍Bit区域，将该位是一的位的编号输出（2，3，4，5，7），这样就达到了排序的目的。下面的代码给出了一个BitMap的用法：排序。

//定义每个Byte中有8个Bit位  
#include ＜memory.h＞  
#define BYTESIZE 8  
void SetBit(char *p, int posi)  
{  
    for(int i=0; i ＜ (posi/BYTESIZE); i++)  
    {  
        p++;  
    }    
    *p = *p|(0x01＜＜(posi%BYTESIZE));//将该Bit位赋值1  
    return;  
}  
void BitMapSortDemo()  
{  
    //为了简单起见，我们不考虑负数  
    int num[] = {3,5,2,10,6,12,8,14,9};    
    //BufferLen这个值是根据待排序的数据中最大值确定的  
    //待排序中的最大值是14，因此只需要2个Bytes(16个Bit)  
    //就可以了。  
    const int BufferLen = 2;  
    char *pBuffer = new char[BufferLen];    
    //要将所有的Bit位置为0，否则结果不可预知。  
    memset(pBuffer,0,BufferLen);  
    for(int i=0;i＜9;i++)  
    {  
        //首先将相应Bit位上置为1  
        SetBit(pBuffer,num[i]);  
    }    
    //输出排序结果  
    for(int i=0;i＜BufferLen;i++)//每次处理一个字节(Byte)  
    {  
        for(int j=0;j＜BYTESIZE;j++)//处理该字节中的每个Bit位  
        {  
            //判断该位上是否是1，进行输出，这里的判断比较笨。  
            //首先得到该第j位的掩码（0x01＜＜j），将内存区中的  
            //位和此掩码作与操作。最后判断掩码是否和处理后的  
            //结果相同  
            if((*pBuffer&(0x01＜＜j)) == (0x01＜＜j))  
            {  
                printf("%d ",i*BYTESIZE + j);  
            }  
        }  
        pBuffer++;  
    }  
}    
int _tmain(int argc, _TCHAR* argv[])  
{  
    BitMapSortDemo();  
    return 0;  
}

可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下。
问题实例

在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题类似的方法，进行划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。”

给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

方案1：用位图/Bitmap的方法，申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。

密匙四：Trie树/数据库/倒排索引

Trie树

适用范围：数据量大，重复多，但是数据种类小，可以放入内存
基本原理及要点：实现方式，节点孩子的表示方式
扩展：压缩实现。

问题实例

密钥一（2）：寻找热门查询：查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个，每个不超过255字节。
密钥一（5）：有10个文件，每个文件1G，每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序。
密钥一（8）：一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词。其解决方法是：用trie树统计每个词出现的次数，时间复杂度是O(n*le)（le表示单词的平准长度），然后是找出出现最频繁的前10个词。
1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？

更多有关Trie树的介绍，请参见此文：从Trie树（字典树）谈到后缀树

数据库索引

适用范围：大数据量的增删改查
基本原理及要点：利用数据的设计实现方法，对海量数据的增删改查进行处理。

关于数据库索引及其优化，更多可参见此文：海量数据处理专题（七）——数据库索引及优化。同时，关于MySQL索引背后的数据结构及算法原理，这里还有一篇很好的文章：MySQL索引背后的数据结构及算法原理。

倒排索引(Inverted index)

适用范围：搜索引擎，关键字查询
基本原理及要点：为何叫倒排索引？一种索引方法，被用来存储在全文搜索下某个单词在一个文档或者一组文档中的存储位置的映射。

以英文为例，下面是要被索引的文本：

1
2
3

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”将对应集合的交集。

正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中，文档占据了中心的位置，每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词，而反向索引则是单词指向了包含它的文档，很容易看到这个反向的关系。

问题实例：文档检索系统，查询那些文件包含了某单词，比如常见的学术论文的关键字搜索。

密匙五：外排序

适用范围：大数据的排序，去重
基本原理及要点：外排序的归并方法，置换选择败者树原理，最优归并树

（1）有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词。

这个数据具有很明显的特点，词的大小为16个字节，但是内存只有1m做hash有些不够，所以可以用来排序。内存可以当输入缓冲区使用。

关于多路归并算法及外排序的具体应用场景，请参见：
如何给10000000个数据量的磁盘文件排序。

密匙六：分布式处理之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)？

四、海量数据处理题库搜集

如何在海量数据中查找给定部分数据最相似的top200向量，向量的维度也很高，因为之前了解过其他面蚂蚁金服的朋友，也有问到这个题目的，所以反应比较快，直接就说可以用KD树，聚类，hash，
如何在海量数据中查找给定部分数据最相似的top200向量，向量的维度也很高，实现一个分布式的topN算法
最后是一个海量数据处理题，给了个滴滴打车的背景，实质就是如何在海量数据中找到最大值。我按着分治思想说了一个解法，意思到了，他也就没往深处问。
要求手写海量数据topK的问题，手写个最小堆，之前没自己写过，幸亏ＴＴＦ同学临时指导了一下，都准备好了也没面到
海量数据问题，给定１０亿个数，统计出现次数最多的１００个数，如果把数换成字符串呢
给你1000个数，怎样随机抽取10个数
之后就是大数据题目，1KW句子算相似度（还是那套分块+hash/建索引，但是因为本人不是做这个的，文本处理根本说一片空白，所以就不误导大家了），之后就是一直围绕大数据的题目不断深化。
怎么在2G内存里找100TB数据的中位数
从大数据中找出topk
对大小在1-10000的1亿个数进行排序，你会怎么做？（友情提示，不要用基于比较的排序算法哦）
怎么在2G内存里找100TB数据的中位数，
10亿个整数，1G内存，O(n)算法，统计只出现一次的数。
N个数找K大数那个题,堆解释了一遍,比较满意,问还能怎么优化O(Nlogk)的方法，并行方面想
给$10^{10}$个64位数,100M内存的空间排序,感谢队长刚好在去的前一天教过我一个求中位数的方法.用文件操作来做了,像快排一样,二分选个数统计大于那个数的数量和小于那个数的数量,如果能用100M的空间排序就把那些数排了,如果不能继续.直到能排为止.
第k大之类的套路题
如何从很多的query中找出一个query （我开始想到hash，后来经提示我想到了前缀树）若允许有错误，可以再怎么解决（不知道，面试官提示了布隆过滤器）
百度二面那个query找相似的系统设计题，我先后说了前缀树，kd树等解决方案，虽然不对，但面试至少知道我了解这些东西