1 什么叫海量数据处理？

所谓海量数据处理，无非就是基于海量数据上的存储、处理、操作。何谓海量，就是数据量太大，所以导致要么是无法在较短时间内迅速解决，要么是数据太大，导致无法一次性装入内存。

解决办法呢？针对时间，需要采用巧妙的算法配合合适的数据结构，如Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie树。针对空间，大而化小，分而治之（hash映射可以做到）。

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

2 海量数据处理需要的数据结构

2.1 序列式容器

vector/list/deque/stack/queue/heap

2.2 关联式容器

• set/map：底层以红黑树为基础实现
• hashtable/hash_set/hash_map：hash_set和hash_map底层以hashtable实现

所谓关联式容器，类似关联式数据库。每个元素都有一个键值(key)和一个实值(value)，即所谓的Key-Value(键-值对)。当元素被插入到关联式容器中时，容器内部结构(红黑树/hashtable)便依照其键值大小，以某种特定规则将这个元素放置于适当位置。

2.3 set/map/multiset/multimap

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

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

至于multiset/multimap，他们的特性及用法和set/map完全相同，唯一的差别就在于它们允许键值重复，即所有的插入操作基于红黑树的insert_equal()而非insert_unique()。

2.4 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都是基于红黑树之上，所以有自动排序功能；而hash_set/hash_map/hash_multiset/hash_multimap都是基于hashtable之上，所以不含有自动排序功能；至于加个前缀multi无非就是允许键值重复而已。

3 处理海量数据问题的思路

3.1 分而治之/Hash映射 + Hash_map统计 + 堆/快速/归并排序

示例问题：海量日志数据，提取出某日访问百度次数最多的那个IP。

针对海量数据，我们需要先映射，后统计，最后排序。

• 分而治之/Hash映射：针对数据太大、内存受限，把大文件化成小文件。具体方法有取模映射等。对IP进行Hash取模运算，那么相同的IP在Hash取模后，只可能落在同一个文件中。因为如果两个IP相等，那么经过Hash(IP)之后的哈希值是相同的，取模之后，必然也相等。
• Hash_map统计：当大文件化成了小文件，我们便可以使用Hash_map来进行频率统计。
• 堆/快速/归并排序：统计完了之后，采用排序算法，得到访问次数最多的IP。

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

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

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

但是此时数据规模比较小，能一次性装入内存。我们可以考虑将其全部装进内存中去，利用Hashmap进行统计。

• Hash_map统计：先对数据进行处理，每次读取一个query，如果query在Table中，加入该query至Hashmap中，并设value为1；否则，原先的value + 1。
• 堆排序：借助堆来找出Top K个query，时间复杂度为N’logK。维护一个K大小的小根堆，然后遍历300万的query，分别和根元素进行对比。所以，我们最终的时间复杂度是：O（N） + N’ * O（logK），（N为1000万，N’为300万）。
• 上述Hash_map也可以采用Trie树来统计每个query出现的次数。

3.2 多层划分

本质上还是分而治之，但是“分”的技巧又有所不同。

适用范围：第K大、中位数、不重复或重复的数字。

基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。

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

有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为2^8个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。 整数为32位，通过不同的位划分。

5亿个int找它们的中位数。

这个例子比上面那个更明显。首先我们将int划分为2^16个区域，然后读取数据统计落到各个区域里的数的个数，之后我们根据统计结果就可以判断中位数落到那个区域，同时知道这个区域中的第几大数刚好是中位数。然后第二次扫描我们只统计落在这个区域中的那些数就可以了。

实际上，如果不是int是int64，我们可以经过3次这样的划分即可降低到可以接受的程度。即可以先将int64分成2^24个区域，然后确定区域的第几大数，在将该区域分成2^20个子区域，然后确定是子区域的第几大数，然后子区域里的数的个数只有2^20，就可以直接利用direct addr table进行统计了。

3.3 Bloom filter/Bitmap

Bloom fliter

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

给你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，则大大简单了。

Bitmap

在2.5亿个整数中找出不重复的整数。注：内存不足以容纳这2.5亿个整数。

方案1：采用2-Bitmap（每个数分配2bit，00表示不存在，01表示出现一次，10表示多次，11无意义）进行，共需内存2^32 * 2 bit = 1GB内存，还可以接受。然后扫描这2.5亿个整数，查看Bitmap中相对应位，如果是00变01，01变10，10保持不变。所描完事后，查看bitmap，把对应位是01的整数输出即可。

方案2：也可采用与第1题类似的方法，进行划分小文件的方法。然后在小文件中找出不重复的整数，并排序。然后再进行归并，注意去除重复的元素。

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

Trie树

适用范围：数据量大，重复多，但是数据种类小可以放入内存。

基本原理及要点：实现方式，节点孩子的表示方式。

数据库索引

适用范围：大数据量的增删查改。

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

倒排索引

适用范围：搜索引擎，关键字查询。

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

3.5 外排序

适用范围：大数据的排序，去重。

基本原理及要点：外排序的归并方法，置换选择败者树原理，最优归并树。

3.6 MapReduce

MapReduce是一种计算模型，简单的说就是将大批量的工作（数据）分解（MAP）执行，然后再将结果合并成最终结果（REDUCE）。这样做的好处是可以在任务被分解后，可以通过大量机器进行并行计算，减少整个操作的时间。但如果你要我再通俗点介绍，那么，说白了，Mapreduce的原理就是一个归并排序。

适用范围：数据量大，但是数据种类小可以放入内存。

基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约。