海量数据专题

《海量数据专题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、海量数据Bloomfilter适用范围：可以用来实现数据字典，进行数据的判重，或者集合求交集.当hash函数个数k=(ln2)*(m/n)时错误率最小;m应该>=nlg(1/E)*lge;Hashing适用范围：快速查找，删除的基本数据结构，通常需要总数据量可以放入内存Bit-map适用范围：可进行数据的快速查找，判重，删除，一般来说数据范围是int的10倍以下堆适用范围：海量数据前n大，并且n比较小，堆可以放入内存倒排索引适用范围：搜索引擎，关键字查询外排序适用范围：大数据的排序，去重基本原理及要点：外排序的归并方法，置换选择败者树原理

2、，最优归并树Trie适用范围：数据量大，重复多，但是数据种类小可以放入内存基本原理及要点：实现方式，节点孩子的表示方式分布式处理适用范围：数据量大，但是数据种类小可以放入内存基本原理及要点：将数据交给不同的机器去处理，数据划分，结果归约。何谓海量数据处理？  所谓海量数据处理，其实很简单，海量，海量，何谓海量，就是数据量太大，所以导致要么是无法在较短时间内迅速解决，要么是数据太大，导致无法一次性装入内存。  那解决办法呢?针对时间，我们可以采用巧妙的算法搭配合适的数据结构，如Bloomfilter/Hash/bit-map/堆/数据库或倒

3、排索引/trie/，针对空间，无非就一个办法：大而化小：分而治之/hash映射，你不是说规模太大嘛，那简单啊，就把规模大化为规模小的，各个击破不就完了嘛。  至于所谓的单机及集群问题，通俗点来讲，单机就是处理装载数据的机器有限(只要考虑cpu，内存，硬盘的数据交互)，而集群，机器有多辆，适合分布式处理，并行计算(更多考虑节点和节点间的数据交互)。  再者，通过本blog内的有关海量数据处理的文章，我们已经大致知道，处理海量数据问题，无非就是：分而治之/hash映射+hash统计+堆/快速/归并排序；双层桶划分Bloomfilter/Bit

4、map；Trie树/数据库/倒排索引；外排序；分布式处理之Hadoop/Mapreduce。  本文接下来的部分，便针对这6种方法模式结合对应的海量数据处理面试题分别具体阐述。处理海量数据问题之六把密匙密匙一、分而治之/Hash映射+Hash统计+堆/快速/归并排序1、海量日志数据，提取出某日访问百度次数最多的那个IP。  既然是海量数据处理，那么可想而知，给我们的数据那就一定是海量的。针对这个数据的海量，我们如何着手呢?对的，无非就是分而治之/hash映射+hash统计+堆/快速/归并排序，说白了，就是先映射，而后统计，最后排序：分而治

5、之/hash映射：针对数据太大，内存受限，只能是：把大文件化成(取模映射)小文件，即16字方针：大而化小，各个击破，缩小规模，逐个解决hash统计：当大文件转化了小文件，那么我们便可以采用常规的Hashmap(ip，value)来进行频率统计。堆/快速排序：统计完了之后，便进行排序(可采取堆排序)，得到次数最多的IP。  具体而论，则是：“首先是这一天，并且是访问百度的日志中的IP取出来，逐个写入到一个大文件中。注意到IP是32位的，最多有个2^32个IP。同样可以采用映射的方法，比如模1000，把整个大文件映射为1000个小文件，再找出

6、每个小文中出现频率最大的IP（可以采用Hash_map进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这1000个最大的IP中，找出那个频率最大的IP，即为所求。”--十道海量数据处理面试题与十个方法大总结。2、搜索引擎会通过日志文件把用户每次检索使用的所有检索串都记录下来，每个查询串的长度为1-255字节。  假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是1千万，但如果除去重复后，不超过3百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门。），请你统计最热门的10个查询串，要求使用的内存不能超

7、过1G。  由上面第1题，我们知道，数据大则划为小的，但如果数据规模比较小，能一次性装入内存呢?比如这第2题，虽然有一千万个Query，但是由于重复度比较高，因此事实上只有300万的Query，每个Query255Byte，因此我们可以考虑把他们都放进内存中去，而现在只是需要一个合适的数据结构，在这里，HashTable绝对是我们优先的选择。所以我们摒弃分而治之/hash映射的方法，直接上hash统计，然后排序。So，hash统计：先对这批海量数据预处理(维护一个Key为Query字串，Value为该Query出现次数的HashTable

8、，即Hashmap(Query，Value)，每次读取一个Query，如果该字串不在Table中，那么加入该字串，并且将Value值设为1；如果该字串在Table中，那么将该字串的计数加一即可