转自http://blog.csdn.net/v_july_v/article/details/7382693
题目为十道海量处理面试题和十个大方法总结（突然回过神来，这是july的博文，想起来自己还参加过他办的机器学习班）
方法模式论--解决方法的抽象总结：
海量数据处理包括：海量数据上的存储、处理、操作。海量数据--由于数据量太大，无法短时间内完成，无法一次性载入内存。
解决方法：巧妙的算法+合适的数据结构。如Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie树，针对空间，无非就一个办法：大而化小，分而治之（hash映射），你不是说规模太大嘛，那简单啊，就把规模大化为规模小的，各个击破不就完了嘛。进而使用集群替代单机，实现分布式并行计算。
理海量数据问题，无非就是：
1. 分而治之/hash映射 + hash统计 + 堆/快速/归并排序；
2. 双层桶划分
3. Bloom filter/Bitmap；
4. Trie树/数据库/倒排索引；
5. 外排序；
6. 分布式处理之Hadoop/Mapreduce。
第一部分、从set/map谈到hashtable/hash_map/hash_set
一般来说STL容器一般分为两类：
1. 序列式容器（vector | List | deque | stack | queue| heap）
2. 关联式容器（set集合和map映射表-->multiset和multimap这些容器均以RB-tree完成）第三类关联式容器hashtable（散列表--以hashtable为底层机制hashset，hashmap...）
非关联式数据库：比如MongoDB，文档（document）是最基本的组织形式，每个文档也是以key-value的方式组织起来。一个文档可以有多个key-value组合，每个value可以是不同类型
set/map/multiset/multimap
set同map一样，所有元素都会根据元素的键值自动被排序，因为set/map两者的所有操作，都是调用RB-tree的操作行为。都不允许元素有相同的键值
区别：
set的元素不像map同时拥有键和值，set元素的键值就是实值，实值就是键值
而map所有的元素都是成对出现，同时拥有key和value
至于multiset和multimap特性与用法和set/map相同，唯一差别就是它们允许键值重复，所有的操作都是基于RB_tree的insert_equal()而非inset_unique()
hash_set/hash_map/hash_multiset/hash_multimap
hashset/hashmap，两者的一切操作都是基于hashtable之上。不同的是，hashset同set一样，同时拥有实值和键值，hashmap同map一样每个元素同时拥有一个实值和键值，但都是因为基于hashtable所以不具有自动排序功能。
关于hash | 关于红黑树 | hashmap的应用 | hashset的应用
处理海量数据之6把秘密钥匙
1、海量日志数据，提取出某日访问百度次数最多的那个IP
既然是海量数据处理，那么可想而知，给我们的数据那就一定是海量的。针对这个数据的海量，我们如何着手呢?对的，无非就是分而治之/hash映射 + hash统计 + 堆/快速/归并排序。先映射，后统计，最后排序：
1） 分而治之 | hash映射：针对数据量太大，内存受限，只能是把大文件（取模映射）成小文件：大而化小，各个击破，缩小规模，逐个解决
2） hashmap统计：当大文件转化成了小文件，那么我们便采取常规的haspmap（ip，count）来进行频率统计
3）堆/快速排序：统计完了之后，采用堆排序，得到次数最多的ip
解：首先得到这一天的日志，将访问百度的ip提取出来，逐个写入到一个大文件中。注意到ip是32位的，最多有2^32个ip。采用映射的方法，比如%1000，将大文件映射到1000个小文件中，再找出每个小文件中出现频率最大的ip（使用hashmap对ip出现的频率进行统计）。最后使用堆排序进行排序，得到出现次数最多的ip
关于本题，还有如下几个问题：
（1）hash取模是一种等价映射，不会存在同一个元素分散到不同小文件中的情况。那么相同ip只能落在同一个小文件中。因此如果两个ip相等，那么经过hash（ip）后值也必然相同。
（2） 到底什么是hash映射？简单来说就是为了便于计算机在有限的内存中处理大数据，从而通过一种映射散列的方式让数据均匀地分布在对应的内存位置（比如大文件映射成小文件），而这个散列方式就是我们说的hash函数
2、寻找热门查询，300万个查询字符串中统计最热门的10个查询（微博热搜）
原题：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门），请你统计最热门的10个查询串，要求使用的内存不能超过1G。
解：根据上面的第一题，我们知道一亿个ip地址太大，无法一次性载入内存，因此我们需要散列。但如果数据规模比较小，能够一次性载入内存呢？虽然有1千万个查询，但是由于重复次数比较高，事实上只有300w的查询，每个查询255byte，假设将它们都载入内存(300w假设没有重复，都是最大长度，那么最多占用内存3M*1k/4 = 0.75G)，所以现在需要一个合适的数据结构，hashtable绝对是最优选择。
所以这道题不用映射，直接hash统计，然后排序。对于此类经典的topK问题，采取的对策是hashmap+堆：
1) hashMap统计：先对这批海量数据进行预处理。具体方法是维护一个key为query字段，value为该字段出现次数的hashtable。每次读取一个query，如果该字符串不在table中，那么加入该字符串，并且将value设为1，如果该字符串在table中那么该子串计数+1。时间复杂度O(N)
2）堆排序：第二步、借助堆这个数据结构，找出Top K，时间复杂度为N‘logK。即借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此，维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比。所以，我们最终的时间复杂度是：O（N） + N' * O（logK），（N为1000万，N’为300万）。
别忘了这篇文章中所述的堆排序思路：“维护k个元素的最小堆，即用容量为k的最小堆存储最先遍历到的k个数，并假设它们即是最大的k个数，建堆费时O（k），并调整堆(费时O（logk）)后，有k1>k2>...kmin（kmin设为小顶堆中最小元素）。继续遍历数列，每次遍历一个元素x，与堆顶元素比较，若x>kmin，则更新堆（x入堆，用时logk），否则不更新堆。这样下来，总费时O（k*logk+（n-k）*logk）=O（n*logk）。此方法得益于在堆中，查找等各项操作时间复杂度均为logk。”--Top K算法问题的实现。
3、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
解：分析，此题的问题关键是文件很大，内存受限。
1）hash映射：顺序读文件，对于每个词，取%5000，存到5000个小文件中，每个文件大概是200k左右，如果有文件大小超过1m，继续按类似方法往下分，直到所以文件大小不超过1m
2）hashmap统计：对于每个文件采用trie树/hashmap统计每个词，及其出现的频率。
3）堆/归并排序：取出现频率最大的100个词（含100个节点的最小堆），再把100个词及对应的频率存入文件，这样又得到5000个文件，最后再把5000个文件归并
4、海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。
如果每个元素只出现一次，而且只出现在某一台机器中，那么采取下面步骤统计top10
1. 堆排序：在每台电脑上求出Top10。包含10个元素的堆（top10小，用大项堆，top10大。比如求top10大，我们首先取出前十个元素调整成最小堆，如果发现后面扫描的元素比根元素大，则用该元素替换根元素最后再调整最小堆）
2. 求出每台电脑上的top10后，然后把100台电脑上的top10组合起来，共1000个数据，继续按照方法1排序
如果同一个元素重复出现在不同电脑？
这种情况下有两种方法：遍历一遍所有数据，重新hash取模，使得同一个数据只出现在同一台电脑中，然后按照上述方法处理。
或者暴力求解，统计出所有元素的出现次数，把不同机器的出现次数相加，统一求解
5、有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。
方法1：直接上
1）hash映射：顺序读取10个文件，按照hash（query）%10将query结果写入另外10个文件，这样新生成的文件每个的大小也约为1G
2） hashmap统计找一台内存在2G左右的机器，依次来统计每个query出现的次数
3）堆/快速/归并排序：按照出现的次数进行排序，这样得到10个排好序的文件，最后将10个文件归并
---python快排实现
rbtree PK hashtable
据朋友№邦卡猫№的做的红黑树和hash table的性能测试中发现：当数据量基本上int型key时，hash table是rbtree的3-4倍，但hash table一般会浪费大概一半内存。
因为hash table所做的运算就是个%，而rbtree要比较很多，比如rbtree要看value的数据 ，每个节点要多出3个指针（或者偏移量） 如果需要其他功能，比如，统计某个范围内的key的数量，就需要加一个计数成员。
且1s rbtree能进行大概50w+次插入，hash table大概是差不多200w次。不过很多的时候，其速度可以忍了，例如倒排索引差不多也是这个速度，而且单线程，且倒排表的拉链长度不会太大。正因为基于树的实现其实不比hashtable慢到哪里去，所以数据库的索引一般都是用的B/B+树，而且B+树还对磁盘友好(B树能有效降低它的高度，所以减少磁盘交互次数)。比如现在非常流行的NoSQL数据库，像MongoDB也是采用的B树索引。关于B树系列，请参考本blog内此篇文章：从B树、B+树、B*树谈到R 树。更多请待后续实验论证。
密匙二、多层划分
适用范围：第k大，中位数，不重复或重复的数字
基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。
13、2.5亿个整数中找出不重复的整数的个数，内存空间不足以容纳这2.5亿个整数。
有点像鸽巢原理，整数个数为2^32,也就是，我们可以将这2^32个数，划分为2^8个区域(比如用单个文件代表一个区域)，然后将数据分离到不同的区域，然后不同的区域在利用bitmap就可以直接解决了。也就是说只要有足够的磁盘空间，就可以很方便的解决。
14、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，请参看blog内此文：
适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集
基本原理及要点：
对于原理来说很简单，位数组+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内存上通常都是节省的。
密匙四、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。
密匙五、外排序
适用范围：大数据的排序，去重
基本原理及要点：外排序的归并方法，置换选择败者树原理，最优归并树
问题实例：
1).有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16个字节，内存限制大小是1M。返回频数最高的100个词。
这个数据具有很明显的特点，词的大小为16个字节，但是内存只有1M做hash明显不够，所以可以用来排序。内存可以当输入缓冲区使用。
关于多路归并算法及外排序的具体应用场景，请参见blog内此文：
密匙六、分布式处理之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内：
