《六招秒杀99%海量数据处理面试题前言》由会员分享，可在线阅读，更多相关《六招秒杀99%海量数据处理面试题前言（11页珍藏版）》请在金锄头文库上搜索。
1、六招秒杀六招秒杀 99%海量数据处理面试题海量数据处理面试题前言前言一般而言，标题含有“秒杀”，“99%”，“史上最全/最强”等词汇的往往都脱不了哗众取宠之嫌，但进一步来讲，如果读者读罢此文，却无任何收获，那么，我也甘愿背负这样的罪名，:-)，同时，此文可以看做是对这篇文章：十道海量数据处理面试题与十个方法大总结的一般抽象性总结。毕竟受文章和理论之限，本文将摒弃绝大部分的细节，只谈方法/模式论，且注重用最通俗最直白的语言阐述相关问题。最后，有一点必须强调的是，全文行文是基于面试题的分析基础之上的，具体实践过程中，还是得具体情况具体分析，且场景也远比本文所述的任何一种情况复杂得多。OK，若有任何
2、问题，欢迎随时不吝赐教。谢谢。何谓海量数据处理？何谓海量数据处理？所谓海量数据处理，无非就是基于海量数据上的存储、处理、操作。何谓海量，就是数据量太大，所以导致要么是无法在较短时间内迅速解决，要么是数据太大，导致无法一次性装入内存。那解决办法呢?针对时间， 我们可以采用巧妙的算法搭配合适的数据结构， 如 Bloom filter/Hash/bit-map/堆/数据库或倒排索引/trie 树，针对空间，无非就一个办法：大而化小：分而治之/hash 映射，你不是说规模太大嘛，那简单啊，就把规模大化为规模小的，各个击破不就完了嘛。至于所谓的单机及集群问题，通俗点来讲，单机就是处理装载数据的机器有限(
3、只要考虑 cpu，内存，硬盘的数据交互)，而集群，机器有多辆，适合分布式处理，并行计算(更多考虑节点和节点间的数据交互)。再者，通过本 blog 内的有关海量数据处理的文章：Big Data Processing，我们已经大致知道，处理海量数据问题，无非就是：分而治之/hash 映射 + hash 统计 + 堆/快速/归并排序；双层桶划分Bloom filter/Bitmap；Trie 树/数据库/倒排索引；外排序；分布式处理之 Hadoop/Mapreduce。下面，本文第一部分、从 set/map 谈到 hashtable/hash_map/hash_set，简要介绍下set/map/mu
4、ltiset/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)，关联式容器。 关联
5、式容器又分为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/ha
6、sh_multimap 都内含一个 hashtable。所谓关联式容器，类似关联式数据库，每笔数据或每个元素都有一个键值(key)和一个实值(value)。当元素被插入到关联式容器中时，容器内部结构(RB-tree/hashtable)便依照其键值大小，以某种特定规则将这个元素放置于适当位置。set/map/multiset/multimapset，同 map 一样，所有元素都会根据元素的键值自动被排序，因为 set/map 两者的所有各种操作，都只是转而调用 RB-tree 的操作行为，不过，值得注意的是，两者都不允许两个元素有相同的键值。不同的是：set 的元素不像 map 那样可以同时拥
7、有实值(value)和键值(key)，set 元素的键值就是实值，实值就是键值，而 map 的所有元素都是 pair，同时拥有实值(value)和键值(key)，pair 的第一个元素被视为键值，第二个元素被视为实值。至于 multiset/multimap，他们的特性及用法和 set/map 完全相同，唯一的差别就在于它们允许键值重复，即所有的插入操作基于 RB-tree 的 insert_equal()而非 insert_unique()。hash_set/hash_map/hash_multiset/hash_multimaphash_set/hash_map，两者的一切操作都是基于 h
8、ashtable 之上。不同的是，hash_set 同 set 一样，同时拥有实值和键值， 且实质就是键值， 键值就是实值， 而 hash_map 同 map 一样， 每一个元素同时拥有一个实值(value)和一个键值(key)，所以其使用方式，和上面的 map 基本相同。但由于 hash_set/hash_map 都是基于 hashtable之上，所以不具备自动排序功能。为什么?因为 hashtable 没有自动排序功能。至于 hash_multiset/hash_multimap 的特性与上面的 multiset/multimap 完全相同，唯一的差别就是它们的底层实现机制是 hashta
9、ble，所以它们的元素都不会被自动排序，不过也都允许键值重复。所以， 综上， 说白了， 什么样的结构决定其什么样的性质， 因为 set/map/multiset/multimap 都是基于 RB-tree之上，所以有自动排序功能，而 hash_set/hash_map/hash_multiset/hash_multimap 都是基于 hashtable之上，所以不含有自动排序功能，至于加个前缀 multi_无非就是允许键值重复而已。此外，关于什么 hash，请看此篇文章：http:/ blog 内系列文章：http:/ 的具体使用，可看看此篇文章：http:/ 映射映射 + Hash 统计统计
10、 + 堆堆/快速快速/归并排序归并排序1、海量日志数据，提取出某日访问百度次数最多的那个、海量日志数据，提取出某日访问百度次数最多的那个 IP。既然是海量数据处理，那么可想而知，给我们的数据那就一定是海量的。针对这个数据的海量，我们如何着手呢?对的，无非就是分而治之/hash 映射 + hash 统计 + 堆/快速/归并排序，说白了，就是先映射，而后统计，最后排序：分而治之/hash 映射：针对数据太大，内存受限，只能是：把大文件化成(取模映射)小文件，即 16字方针：大而化小，各个击破，缩小规模，逐个解决hash 统计：当大文件转化了小文件，那么我们便可以采用常规的 hash_map(ip，
11、value)来进行频率统计。堆/快速排序：统计完了之后，便进行排序(可采取堆排序)，得到次数最多的 IP。具体而论，则是： “首先是这一天，并且是访问百度的日志中的 IP 取出来，逐个写入到一个大文件中。注意到 IP 是 32 位的，最多有个 232 个 IP。同样可以采用映射的方法，比如模 1000，把整个大文件映射为1000 个小文件，再找出每个小文中出现频率最大的 IP（可以采用 hash_map 进行频率统计，然后再找出频率最大的几个）及相应的频率。然后再在这 1000 个最大的 IP 中，找出那个频率最大的 IP，即为所求。”-十道海量数据处理面试题与十个方法大总结。注：Hash 取
12、模是一种等价映射，不会存在同一个元素分散到不同小文件中去的情况，即这里采用的是mod1000 算法，那么相同的 IP 在 hash 后，只可能落在同一个文件中，不可能被分散的。那到底什么是 hash 映射呢？我换个角度举个浅显直白的例子，如本文的 URL 是：http:/ URL 发表在微博上，便被映射成了：http:/ URL 本身的长度被缩短了，但这两个 URL 对应的文章的是同一篇即本文。OK，有兴趣的，还可以再了解下一致性 hash 算法，见此文第五部分：http:/ 1-255 字节。字节。假设目前有一千万个记录（这些查询串的重复度比较高，虽然总数是 1 千万，但如果除去重复后，不超
13、过3 百万个。一个查询串的重复度越高，说明查询它的用户越多，也就是越热门），请你统计最热门的 10 个查询串，要求使用的内存不能超过 1G。由上面第 1 题，我们知道，数据大则划为小的，但如果数据规模比较小，能一次性装入内存呢?比如这第 2题， 虽然有一千万个 Query， 但是由于重复度比较高， 因此事实上只有 300 万的 Query， 每个 Query255Byte，因此我们可以考虑把他们都放进内存中去，而现在只是需要一个合适的数据结构，在这里，Hash Table 绝对是我们优先的选择。所以我们摒弃分而治之/hash 映射的方法，直接上 hash 统计，然后排序。So，hash 统计：
14、先对这批海量数据预处理(维护一个 Key 为 Query 字串，Value 为该 Query 出现次数的HashTable，即 hash_map(Query，Value)，每次读取一个 Query，如果该字串不在 Table 中，那么加入该字串，并且将 Value 值设为 1；如果该字串在 Table 中，那么将该字串的计数加一即可。最终我们在 O(N)的时间复杂度内用 Hash 表完成了统计；堆排序：第二步、借助堆这个数据结构，找出 Top K，时间复杂度为 NlogK。即借助堆结构，我们可以在 log 量级的时间内查找和调整/移动。因此，维护一个 K(该题目中是 10)大小的小根堆，然后遍
15、历 300 万的 Query， 分别和根元素进行对比所以， 我们最终的时间复杂度是： O （N）+ N*O（logK），（N 为 1000 万，N为 300 万）。别忘了这篇文章中所述的堆排序思路：“维护 k 个元素的最小堆，即用容量为 k 的最小堆存储最先遍历到的k 个数， 并假设它们即是最大的 k 个数， 建堆费时 O （k），并调整堆 （费时 O （logk） ）后， 有 k1k2.kmin（kmin 设为小顶堆中最小元素）。继续遍历数列，每次遍历一个元素 x，与堆顶元素比较，若 xkmin，则更新堆（用时 logk），否则不更新堆。这样下来，总费时 O（k*logk+（n-k）*logk）=O（n*logk）。此方法得益
