100万个电话号码在文件里，找出重复的；内存不足以放下所有数据。 - ITeye问答
各位有什么好的方法？
100万个电话号码在文件里，找出重复的；内存不足以放下所有数据。
将电话号码转为数值型
数值代表位图的偏移量
创建一个100,000,000/8+1大小的byte数组作为位图
num/8表示偏移量
num%8表示在该byte的第几位
如果该位是0，置为1
如果是1，已经重复
假设电话号码是8位的（有些城市是7位的，如果带区号的话自己根据这个思想做变换即可）
那么不管存在不存在，所有的电话号码一共有10^8个
建立一个int类型的数组，数组大小为3125000，共需要不到12M的内存
可以存储10^8个布尔类型的值（一个int占32位，没一位相当于一个布尔值），每个布尔类型的值对应一个号码，初始化的时候让数组里的每个值都为0
也就是说现在数组里所有的布尔值都为false
然后从文件里读出第一个号码，假设号码是，那么就将数组里第0个值的第二位设置为1，也就将这个号码标识为存在，下次再读入时就根据标识判断是否重复
说简单点，就相当于你将10^8个二进制数排队站着，然后将所有的电话号码排队站着，把他们看成是一对一的关系，如果一个号码发现自己的位置被比人占了，那么这个号码一定是重复的
当然因为电话号码并不可能是，所以可以针对电话号码的情况做一些优化，而不必要申请3125000个int大小的内存。
有几个方案：
Bloom Filter
文件多路归并排序
自己百度或者请人做吧
多文件，排序，去重，也是个选择！
将所有号码分类在多个文件里嘛，比如说号码有八位，前四位相同存放在一个文件
&& 可以考虑使用二个BitSet（长度为电话号码的最大值）设为bitSet1,bitSet2,利用clear()将所有位都置为false。
&& 读取一个电话号码后（先读入多条记录到缓冲区），判断其数值对应bitSet1位置，若为false,则置为true，否则将bitSet2中相应位置置为true,以此类推……
&& 所有电话号码处理完后，bitSet2中的为true的位置即为重复的电话号码。
不用数据库的话，可以参考BitSet的思路，自己设计一个类似的位序列bucket，根据号码映射到位序列中，置位 ，保证不同的号码映射到不同的位置就行了，可以对号码做个优化处理或者位序列够大就行
《编程珠玑》中有这个算法
一般都是导入数据库再update telcode= trim(telcode);
然后再select distinct telcode from table_
你知道berkeleydb嵌入式数据库吗？从数据结构的角度来看那就是一个哈希表，而且它还有个优点是随时和硬盘相联系的，这样你的数据再多也不用担心内存溢出问题，或者用布隆过滤器一样可以解决的
大数据处理，可以参考hadoop的设计
放到数据库里&&&&&& ，一个sql就搞定了
布隆过滤器
Bloom Filter
文件多路归并排序
tire 树 估计内存放不下
但是可以考虑前6位trie树 后面文件
BloomFilter是最简单的..但是不一定准确
如果我做..我选择归排序吧...
/art/690.htm
Java中用内存映射处理大文件
根据号码的前1位或两位来切分文件，文件切的够小，那你在插入到新的文件中的时候，就可以在有限的内存中排除重复的数据了。
这个问题有两个棘手的地方：
1、这个100w条号码文件肯定不能一次读到内存中来的，应该分片段读取，方法是什么？
利用java.nio中的内存映射文件可以分段读取数据与处理数据，可以解决java.io中对大文件处理的不足。
2、接着上一步分段读取到内存中来之后，肯定不能放内存中，应该将刚读好的数据片段立即转移到其他存储介质中，以释放内存空间，否则这就和一次性读到内存没什么差别了，这里可以根据需要可以选择传统的关系数据库如MySQL和K-V数据库如Redis等等(后者属于NOSQLk-v型数据库,IO性能极高，做count也很容易)
Bloom过滤应该可以解决！
《编程珠玑》就在开篇里边讲了一个类似问题的精妙解答，具体算法我要在里说的话，就显得卖弄了。呵呵。
《编程珠玑》上对这个问题有精彩的解答。推荐你看看
hashMap是个不错的思路，根据内存决定一次读入内存多少数据，key为号码，value为出现次数，若hashmap里已经有了该号码，则value+1,
存入数据库再进行处理此方法确实不错。数组排序我不大赞同，哈希集合不过倒是可以考虑。
不是做数据库的，只说一下我的想法：
1.将100万电话按照前两位进行分组，例如18*****、15*****、19*****分组
2.对每个分组内电话号码进行去重操作（现在内存能跑的开了吧）
考DS的问题，好题
才100W电话号 直接放内存里跑。
一.借助数据库
1.先分割成几个一定大小文件,使用多线程(可选)再将一个个小文件导入到一张表中
2.使用order by 电话号码
3.统计数据库总行 - 再使用"distinct"去重复=重复的行数
二.使用google
将其做成一个网页,再使用"google自定义搜索"ok(有计数功能)
三.使用Apache lucene全文检索
这个命题有点像电信计费系统从交换机上去下载二进制文件，然后根据文件中的数据进行用户计费的。
如果是相似需求的话，可以找一找相关计费资料看看的，那个计费效率很高的。
如果电话号码包括手机号，或者带有区号呢？
就有11位，12位，8位。。。。。。
linux下sort和uniq命令
hash-&boolean 滤波器
玩过map-reduce的话，做这个题应该是没问题！
简单处理：对文件进行分片(N)，& hash code % N --&分发到不同的reduce，这样相同号码肯定在一个reduce中
100万条，存到数据库里做查询也并不夸张嘛！
根据你计算机的运算能力，把电话号码比如说以前3位为过滤分组依据，可把一个大文件分为最多999个小文件，小文件内大概平均也就是1000个电话号，顶多也就是8位-3位=5位，也就是说所分的这些小文件里，最大的极限值，也就是99999个电话号码，在内存是不成问题的，这也就解决了内存不足的问题，至于怎么去筛选，自己想把
定义int二维数组，电话号码前4位作一维数组下标，4位后面的做二维下标，相同号码在对应下标数组值加1，二次循环就能完全找出重复号码个数，重复次数&&&&& 除了占CUP外，内存占用相当少
归类再进行分析，
假设电话号码是8位的（有些城市是7位的，如果带区号的话自己根据这个思想做变换即可）
那么不管存在不存在，所有的电话号码一共有10^8个
建立一个int类型的数组，数组大小为3125000，共需要不到12M的内存
可以存储10^8个布尔类型的值（一个int占32位，没一位相当于一个布尔值），每个布尔类型的值对应一个号码，初始化的时候让数组里的每个值都为0
也就是说现在数组里所有的布尔值都为false
然后从文件里读出第一个号码，假设号码是，那么就将数组里第0个值的第二位设置为1，也就将这个号码标识为存在，下次再读入时就根据标识判断是否重复
说简单点，就相当于你将10^8个二进制数排队站着，然后将所有的电话号码排队站着，把他们看成是一对一的关系，如果一个号码发现自己的位置被比人占了，那么这个号码一定是重复的
当然因为电话号码并不可能是，所以可以针对电话号码的情况做一些优化，而不必要申请3125000个int大小的内存。
思路：多线程利用map-&reduce算法
分片：
0.遍历文件，目的是“采样”，找到最大值和最小值，并且掌握数据的大概分布。
1.分割文件：将大文件分割为小文件。比如总共10G。分割为100个文件。每个文件100M
3.计算当前需要的线程数。比如总共数据10G。分割为100个文件。当前可用内存为1G。那么线程数据数就是10（1G/100M).需要处理10轮。
map：
4.每个线程遍历分割后的数据，按照采样点将其保持到不同的输出文件中。
reduce
5.依次遍历所有输出文件。找出相同的数据。
先把号码 存到数据库里，然后再查询，一个sql就搞掂了。
楼上的本来是我要说的，可是系统让我做什么答题小测试。。。。就让你说了。很赞同你说的。另外你说话言简意赅，值得学习
已解决问题
未解决问题巧用MapReduce+HDFS，海量数据去重的五大策略
发表于 22:00|
来源HadoopSphere|
作者HadoopSphere
摘要：随着收集到数据体积的激增，去重无疑成为众多大数据玩家面对的问题之一。重复数据删除在减少存储、降低网络带宽方面有着显著的优势，并对扩展性有所帮助。在存储架构中，删除重复数据的常用方法包括哈希、二进制比较和增量差分；而本文专注的是使用MapReduce和HDFS对数据进行去重。
随着存储数据信息量的飞速增长，越来越多的人开始关注存储数据的缩减方法。数据压缩、单实例存储和重复数据删除等都是经常使用的存储数据缩减技术。
重复数据删除往往是指消除冗余子文件。不同于压缩，重复数据删除对于数据本身并没有改变，只是消除了相同的数据占用的存储容量。重复数据删除在减少存储、降低网络带宽方面有着显著的优势，并对扩展性有所帮助。
举个简单的例子：在专门为电信运营商定制的呼叫详单去重应用程序中，我们就可以看到删除重复数据的影子。同样的，对于包含相同数据包的通信网络，我们可以使用这种技术来进行优化。
在存储架构中，删除重复数据的一些常用的方法包括：哈希、二进制比较和增量差分。在
，将专注于如何利用MapReduce和HDFS来消除重复的数据。（下面列出的方法中包括一些学者的实验方法，因此把术语定义为策略比较合适）。
策略1：只使用HDFS和MapReduce
Owen O’Malley在一个论坛的帖子中建议使用以下方法：
让你的历史数据按照MD5值进行排序。 运行一个MapReduce的作业，将你的新数据按照MD5进行排序。需要注意的是：你要做所有数据的整体排序，但因为MD5是在整个密钥空间中是均匀分布的，排序就变得很容易。
基本上，你挑选一个reduce作业的数量（如256），然后取MD5值的前N位数据来进行你的reduce作业。由于这项作业只处理你的新数据，这是非常快的。
接下来你需要进行一个map-side join，每一个合并的输入分块都包含一个MD5值的范围。RecordReader读取历史的和新的数据集，并将它们按照一定方式合并。（你可以使用map-side
join库）。你的map将新数据和旧数据合并。这里仅仅是一个map作业，所以这也非常快。&
&当然，如果新的数据足够小，你可以在每一个map作业中将其读入，并且保持新记录（在RAM中做了排序）在合适的数量范围内，这样就可以在RAM中执行合并。这可以让你避免为新数据进行排序的步骤。类似于这种合并的优化，正是Pig和Hive中对开发人员隐藏的大量细节部分。
策略2：使用HDFS和Hbase
在一篇名为“
”的论文中，Zhe Sun, Jun Shen, Jianming Young共同提出了一种使用HDFS和Hbase的方法，内容如下：
使用MD5和SHA-1哈希函数计算文件的哈希值，然后将值传递给Hbase
将新的哈希值与现有的值域比较，如果新值已经存在于Hbase去重复表中，HDFS会检查链接的数量，如果数量不为零时，哈希值对应的计数器将增加1。如果数量是零或哈希值在之前的去重复表中不存在，HDFS会要求客户端上传文件并更新文件的逻辑路径。
HDFS将存储由用户上传的源文件，以及相应的链接文件，这些链接文件是自动生成的。链接文件中记录了源文件的哈希值和源文件的逻辑路径。
要注意使用这种方法中的一些关键点：
文件级的重复数据删除需要保持索引数量尽可能小，这样可以有高效的查找效率。
MD5和SHA-1需要结合使用从而避免偶发性的碰撞。
策略3：使用HDFS，MapReduce和存储控制器
由Netapp的工程师AshishKathpal、GauravMakkar以及Mathew John三人联合，在一篇名为“
”的文章中，提出通过使用HadoopMapReduce的重复检测机制来替代Netapp原有的重复检测环节，文中提到的基于重复检测的Hadoop工作流包含如下几个环节：
将数据指纹（Fingerprint）由存储控制器迁移到HDFS
生成数据指纹数据库，并在HDFS上永久存储该数据库
使用MapReduce从数据指纹记录集中筛选出重复记录，并将去重复后的数据指纹表保存回存储控制器。
数据指纹是指存储系统中文件块经过计算后的哈希索引，通常来说数据指纹要比它代表的数据块体积小的多，这样就可以减少分布式检测时网络中的数据传输量。
策略4：使用Streaming，HDFS，MapReduce
对于Hadoop和Streaming的应用集成，基本上包含两种可能的场景。以IBM Infosphere Streams和BigInsights集成为例，场景应该是：
1. Streams到Hadoop的流程：通过控制流程，将Hadoop MapReduce模块作为数据流分析的一部分，对于Streams的操作需要对更新的数据进行检查并去重，并可以验证MapReduce模型的正确性。&
众所周知，在数据摄入的时候对数据进行去重复是最有效的，因此在Infosphere Streams中对于某个特定时间段或者数量的记录会进行去重复，或者识别出记录的增量部分。接着，经过去重的数据将会发送给Hadoop
BigInsights用于新模型的建立。
2. Hadoop到Streams的流程：在这种方式中，Hadoop MapReduce用于移除历史数据中的重复数据，之后MapReduce模型将会更新。MapReduce模型作为Streams中的一部分被集成，针对mid-stream配置一个操作符（operator），从而对传入的数据进行处理。
策略5：结合块技术使用MapReduce
在莱比锡大学开发的一个原型工具（Deduplication with Hadoop）中，MapReduce应用于大数据中的实体解析处理，到目前为止，这个工具囊括了MapReduce在重复数据删除技术中最为成熟的应用方式。
基于实体匹配的分块是指将输入数据按照类似的数据进行语义分块，并且对于相同块的实体进行限定。
实体解析处理分成两个MapReduce作业：分析作业主要用于统计记录出现频率，匹配作业用于处理负载均衡以及近似度计算。另外，匹配作业采用“贪婪模式”的负载均衡调控，也就是说匹配任务按照任务处理数据大小的降序排列，并做出最小负载的Reduce作业分配。
Dedoop还采用了有效的技术来避免多余的配对比较。它要求MR程序必须明确定义出哪个Reduce任务在处理哪个配对比较，这样就无需在多个节点上进行相同的配对比较。
原文链接：
&（编译/兴宝 审校/仲浩）
”将于-7日在北京国家会议中心隆重举行。猛击！
相关活动已经火热启动：
，欢迎研发者、团队和创业企业参加！
推荐阅读相关主题：
CSDN官方微信
扫描二维码,向CSDN吐槽
微信号：CSDNnews
相关热门文章所谓海量数据处理，就是基于海量数据上的存储、处理、操作。
&&&&&&&&海量就是数据量太大，所以导致要么是无法在较短时间内迅速解决，要么是无法一次性装入内存。
（1）针对时间，可以采用巧妙的算法搭配合适的数据结构，如Hash/bit-map/堆/数据库或倒排索引/trie树；
（2）针对空间，大而化小：分而治之/hash映射，把规模大化为规模小的，各个击破。
处理海量数据问题，有6种方法模式：
分而治之/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
&&& 一般来说，STL容器分两种，
序列式容器(vector / list / deque / stack / queue / heap)，关联式容器。关联式容器又分为set(集合)和map(映射表)两大类，以及这两大类的衍生体multiset(多键集合)和multimap(多键映射表)，这些容器均以RB-tree完成。此外，还有第3类关联式容器，如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)便依照其键值大小，以某种特定规则将这个元素放置于适当位置。&&&&&
（1）set/map/multiset/multimap
& & set，同map一样，所有元素都会根据元素的键值自动被排序，因为set/map两者的所有各种操作，都只是转而调用RB-tree的操作行为，不过，值得注意的是，两者都不允许两个元素有相同的键值。
&&&&至于multiset/multimap，他们的特性及用法和set/map完全相同，唯一的差别就在于它们允许键值重复，即所有的插入操作基于RB-tree的insert_equal()而非insert_unique()。
（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统计 + 堆/快速/归并排序
1、海量日志数据，提取出某日访问百度次数最多的那个IP。
&&&&& 分而治之/hash映射 + hash统计 + 堆/快速/归并排序，就是先映射，后统计，最后排序：
分而治之/hash映射：针对数据太大，内存受限，只能是：把大文件化成(取模映射)小文件，即16字方针：大而化小，各个击破，缩小规模，逐个解决hash统计：当大文件转化了小文件，那么我们便可以采用常规的hash_map(ip，value)来进行频率统计。堆/快速排序：统计完了之后，便进行排序(可采取堆排序)，得到次数最多的IP。
& &具体则是： “首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把整个大文件映射为1000个小文件，再找出每个小文中出现频率最大的IP（可以采用hash_map对那1000个文件中的所有IP进行频率统计，然后依次找出各个文件中频率最大的那个IP）及相应的频率。然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。”--。
2、寻找热门查询，300万个查询字符串中统计最热门的10个查询
&&&&原题：搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门），请你统计最热门的10个查询串，要求使用的内存不能超过1G。
&& &解答：数据大则划为小的，但如果数据规模比较小，能一次性装入内存呢? 比如此题，虽然有一千万个Query，但是由于重复度比较高，因此事实上只有300万的Query，每个Query255Byte，因此我们可以考虑把他们都放进内存中去（300万个字符串假设没有重复，都是最大长度，那么最多占用内存3M*1K/4=0.75G。所以可以将所有字符串都存放在内存中进行处理），而现在只是需要一个合适的数据结构，在这里，HashTable绝对是我们优先的选择。
&& &所以我们放弃分而治之/hash映射的步骤，直接上hash统计，然后排序。针对此类典型的TOP K问题，采取的对策往往是：hashmap + 堆。如下所示：
hash统计：先对这批海量数据预处理。具体方法是：维护一个Key为Query字串，Value为该Query出现次数的HashTable，即hash_map(Query，Value)，每次读取一个Query，如果该字串不在Table中，那么加入该字串，并且将Value值设为1；如果该字串在Table中，那么将该字串的计数加一即可。最终我们在O(N)的时间复杂度内用Hash表完成了统计；堆排序：第二步、借助堆这个数据结构，找出Top K，时间复杂度为N‘logK。即借助堆结构，我们可以在log量级的时间内查找和调整/移动。因此，维护一个K(该题目中是10)大小的小根堆，然后遍历300万的Query，分别和根元素进行对比。所以，我们最终的时间复杂度是：O（N）
+ N' * O（logK），（N为1000万，N’为300万）。
3、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。
&&&&&& 文件很大且内存受限
分而治之/hash映射：顺序读文件中，对于每个词x，取hash(x)%5000，然后按照该值存到5000个小文件（记为x0,x1,...x4999）中。这样每个文件大概是200k左右。如果其中的有的文件超过了1M大小，还可以按照类似的方法继续往下分，直到分解得到的小文件的大小都不超过1M。hash统计：对每个小文件，采用trie树/hash_map等统计每个文件中出现的词以及相应的频率。堆/归并排序：取出出现频率最大的100个词（可以用含100个结点的最小堆）后，再把100个词及相应的频率存入文件，这样又得到了5000个文件。最后就是把这5000个文件进行归并（类似于归并排序）的过程了。
4、海量数据分布在100台电脑中，想个办法高效统计出这批数据的TOP10。
& & 此题与上面第3题类似，
堆排序：在每台电脑上求出TOP10，可以采用包含10个元素的堆完成（TOP10小，用最大堆，TOP10大，用最小堆）。求出每台电脑上的TOP10后，然后把这100台电脑上的TOP10组合起来，共1000个数据，再利用上面类似的方法求出TOP10就可以了。&&&&&&&
5、有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。
& &方案1：直接上：
hash映射：顺序读取10个文件，按照hash(query)%10的结果将query写入到另外10个文件（记为a0,a1,..a9）中。这样新生成的文件每个的大小大约也1G（假设hash函数是随机的）。hash统计：找一台内存在2G左右的机器，依次对用hash_map(query, query_count)来统计每个query出现的次数。堆/快速/归并排序：利用快速/堆/归并排序按照出现次数进行排序，将排序好的query和对应的query_cout输出到文件中，这样得到了10个排好序的文件（记为）。最后，对这10个文件进行归并排序（内排序与外排序相结合）。根据此方案1，这里有一份实现：。
& & &除此之外，此题还有以下两个方法：
&&& 方案2：一般query的总量是有限的，只是重复的次数比较多而已，可能对于所有的query，一次性就可以加入到内存了。这样，我们就可以采用trie树/hash_map等直接来统计每个query出现的次数，然后按出现次数做快速/堆/归并排序就可以了。
&&& 方案3：与方案1类似，但在做完hash，分成多个文件后，可以交给多个文件来处理，采用分布式的架构来处理（比如MapReduce），最后再进行合并。
6、 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？
& & 可以估计每个文件的大小为5G×64=320G，远远大于内存限制的4G。所以不可能将其完全加载到内存中处理。考虑采取分而治之的方法。
分而治之/hash映射：遍历文件a，对每个url求取，然后根据所取得的值将url分别存储到1000个小文件（记为，这里漏写个了a1）中。这样每个小文件的大约为300M。遍历文件b，采取和a相同的方式将url分别存储到1000小文件中（记为）。这样处理后，所有可能相同的url都在对应的小文件（）中，不对应的小文件不可能有相同的url。然后我们只要求出1000对小文件中相同的url即可。hash统计：求每对小文件中相同的url时，可以把其中一个小文件的url存储到hash_set中。然后遍历另一个小文件的每个url，看其是否在刚才构建的hash_set中，如果是，那么就是共同的url，存到文件里面就可以了。&&&
7、怎么在海量数据中找出重复次数最多的一个？
& & 方案1：先做hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求
8、上千万或上亿数据（有重复），统计其中出现次数最多的前N个数据。
& & 方案1：上千万或上亿的数据，现在的机器的内存应该能存下。所以考虑采用hash_map/搜索二叉树/红黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了，可以用堆完成。
9、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。
& & &方案1：这题是考虑时间效率。用trie树统计每个词出现的次数，时间复杂度是O(n*le)&（le表示单词的平均长度）。然后是找出出现最频繁的前10个词，可以用堆来实现，前面的题中已经讲到了，时间复杂度是O(n*lg10)。所以总的时间复杂度，是O(n*le)与O(n*lg10)中较大的一个。
10. 1000万字符串，其中有些是重复的，需要把重复的全部去掉，保留没有重复的字符串。请怎么设计和实现？
方案1：这题用trie树比较合适，hash_map也行。方案2：1000w的数据规模插入操作完全不现实，以前试过在stl下100w元素插入set中已经慢得不能忍受，觉得基于hash的实现不会比红黑树好太多，使用vector+sort+unique都要可行许多，建议还是先hash成小文件分开处理再综合。
&&&&set/map，与hash_set/hash_map的性能比较：&&&
RBtree PK hashtable(未完待续)
密匙二、双层桶划分
双层桶划分----其实本质上还是分而治之的思想，重在“分”的技巧上！
　　适用范围：第k大，中位数，不重复或重复的数字
　　基本原理及要点：因为元素范围很大，不能利用直接寻址表，所以通过多次划分，逐步确定范围，然后最后在一个可以接受的范围内进行。可以通过多次缩小，双层只是一个例子。
12、5亿个int找它们的中位数。
思路一：这个例子比上面那个更明显。首先我们将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应该&n/2（2.5亿）。而k+1 - 65535的计数和也&n/2，第二遍统计同上面的方法类似，但这次只统计处于区间k的情况，也就是说(x / 65536) + 32768 = k。统计只统计低16位的情况。并且利用刚才统计的sum，比如sum = 2.49亿，那么现在就是要在低16位里面找100万个数(2.5亿-2.49亿)。这次计数之后，再统计一下，看中位数所处的区间，最后将高位和低位组合一下就是结果了。
密匙三：Bitmap
&&&14/11题、在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：用位图/Bitmap的方法，申请512M的内存，一个bit位代表一个unsigned int值。读入40亿个数，设置相应的bit位，读入要查询的数，查看相应bit位是否为1，为1表示存在，为0表示不存在。
密匙四、Trie树/数据库/倒排索引
　　适用范围：数据量大，重复多，但是数据种类小可以放入内存
　　基本原理及要点：实现方式，节点孩子的表示方式
　　扩展：压缩实现。
　　问题实例：
上面的第2题：寻找热门查询：查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个，每个不超过255字节。
上面的第5题：有10个文件，每个文件1G，每个文件的每一行都存放的是用户的query，每个文件的query都可能重复。要你按照query的频度排序。1000万字符串，其中有些是相同的(重复),需要把重复的全部去掉，保留没有重复的字符串。请问怎么设计和实现？上面的第8题：一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词。其解决方法是：用trie树统计每个词出现的次数，时间复杂度是O(n*le)（le表示单词的平准长度），然后是找出出现最频繁的前10个词。
&&&&数据库索引
　　适用范围：大数据量的增删改查
　　基本原理及要点：利用数据的设计实现方法，对海量数据的增删改查进行处理。
倒排索引(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&将对应集合的交集。
　　正向索引开发出来用来存储每个文档的单词的列表。正向索引的查询往往满足每个文档有序频繁的全文查询和每个单词在校验文档中的验证这样的查询。在正向索引中，文档占据了中心的位置，每个文档指向了一个它所包含的索引项的序列。也就是说文档指向了它包含的那些单词，而反向索引则是单词指向了包含它的文档，很容易看到这个反向的关系。
　　扩展：
　　问题实例：文档检索系统，查询那些文件包含了某单词，比如常见的学术论文的关键字搜索。
密匙五、外排序
　　适用范围：大数据的排序，去重
　　基本原理及要点：外排序的归并方法，置换选择败者树原理，最优归并树
　　扩展：
　　问题实例：
　　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)？
&其它模式/方法论，结合操作系统知识
& & 至此，六种处理海量数据问题的模式/方法已经阐述完毕。据观察，这方面的面试题无外乎以上一种或其变形，然题目为何取为是：秒杀99%的海量数据处理面试题，而不是100%呢。OK，给读者看最后一道题，如下：
& &&非常大的文件，装不进内存。每行一个int类型数据，现在要你随机取100个数。
& & 我们发现上述这道题，无论是以上任何一种模式/方法都不好做，那有什么好的别的方法呢？我们可以看看：操作系统内存分页系统设计(说白了，就是映射+建索引)。
& & Windows 2000使用基于分页机制的虚拟内存。每个进程有4GB的虚拟地址空间。基于分页机制，这4GB地址空间的一些部分被映射了物理内存，一些部分映射硬盘上的交换文 件，一些部分什么也没有映射。程序中使用的都是4GB地址空间中的虚拟地址。而访问物理内存，需要使用物理地址。
关于什么是物理地址和虚拟地址，请看：
物理地址 (physical address): 放在寻址总线上的地址。放在寻址总线上，如果是读，电路根据这个地址每位的值就将相应地址的物理内存中的数据放到数据总线中传输。如果是写，电路根据这个 地址每位的值就将相应地址的物理内存中放入数据总线上的内容。物理内存是以字节(8位)为单位编址的。&虚拟地址 (virtual address): 4G虚拟地址空间中的地址，程序中使用的都是虚拟地址。&使用了分页机制之后，4G的地址空间被分成了固定大小的页，每一页或者被映射到物理内存，或者被映射到硬盘上的交换文件中，或者没有映射任何东西。对于一 般程序来说，4G的地址空间，只有一小部分映射了物理内存，大片大片的部分是没有映射任何东西。物理内存也被分页，来映射地址空间。对于32bit的 Win2k，页的大小是4K字节。CPU用来把虚拟地址转换成物理地址的信息存放在叫做页目录和页表的结构里。&
& & 物理内存分页，一个物理页的大小为4K字节，第0个物理页从物理地址 0x 处开始。由于页的大小为4KB，就是0x1000字节，所以第1页从物理地址 0x 处开始。第2页从物理地址 0x 处开始。可以看到由于页的大小是4KB，所以只需要32bit的地址中高20bit来寻址物理页。&
& & 返回上面我们的题目：非常大的文件，装不进内存。每行一个int类型数据，现在要你随机取100个数。针对此题，我们可以借鉴上述操作系统中内存分页的设计方法，做出如下解决方案：
& & 操作系统中的方法，先生成4G的地址表，在把这个表划分为小的4M的小文件做个索引，二级索引。30位前十位表示第几个4M文件，后20位表示在这个4M文件的第几个，等等，基于key value来设计存储，用key来建索引。
& & 但如果现在只有10000个数，然后怎么去随机从这一万个数里面随机取100个数？请读者思考。更多海里数据处理面试题，请参见此文第一部分：。
2012百度实习生招聘笔试题：。
& & 不过，相信你也早就意识到，若单纯论海量数据处理面试题，本blog内的有关海量数据处理面试题的文章已涵盖了你能在网上所找到的70~80%。但有点，必须负责任的敬告大家：无论是这些海量数据处理面试题也好，还是算法也好，面试时，70~80%的人不是倒在这两方面，而是倒在基础之上(诸如语言，数据库，操作系统，网络协议等等)，所以，无论任何时候，基础最重要，没了基础，便什么都不是。如果你问我什么叫做掌握了基础，很简单，我可以举个例子，如到这里：，如果你几乎能解决那里的全部问题，那么你的c/c++基础便够了。
参考知识库
* 以上用户言论只代表其个人观点，不代表CSDN网站的观点或立场
访问：25221次
排名：千里之外
原创：17篇
转载：51篇
(1)(1)(5)(14)(16)(18)(4)(3)(2)(5)