其实高效解决海量数据处理面试难题：掌握关键策略与技巧的问题并不复杂，但是又很多的朋友都不太了解，因此呢，今天小编就来为大家分享高效解决海量数据处理面试难题：掌握关键策略与技巧的一些知识，希望可以帮助到大家，下面我们一起来看看这个问题的分析吧！
单机和集群问题，单机意味着只有有限数量的机器处理加载的数据（只考虑CPU、内存、硬盘的数据交互），而集群有多台机器，适合分布式处理和并行计算（更多考虑节点和节点间交互）。数据交互）。
处理海量数据问题的方法是分而治之/哈希映射+哈希统计+堆/快速/归并排序；双层斗划分；布隆过滤器/位图； Trie树/数据库/倒排索引；外部排序； Hadoop/Mapreduce 的分布式处理。
STL容器有两种类型，顺序容器（向量/列表/双端队列/堆栈/队列/堆）和关联容器。关联容器分为两类：set（集合）和map（映射表），以及它们的衍生品multiset（多键集合）和multimap（多键映射表）。这些容器都是基于RB-tree Finish的。另外，还有第三类关联容器，如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。
什么样的结构决定了它有什么样的属性，因为set/map/multiset/multimap都是基于RB-tree的，所以它们都有自动排序的功能，而hash_set/hash_map/hash_multiset/hash_multimap都是基于hashtable的，所以没有自动排序功能。至于添加前缀multi_，无非就是让键值重复。
学习交流群：462403503 处理海量数据问题的六大关键
关键1：分而治之/Hash Map + Hash_map统计+堆/快速/归并排序
1、利用海量日志数据，提取某天百度访问次数最多的IP。海量数据处理，说白了就是先映射，然后统计，最后排序：
分而治之/哈希映射：如果数据太大，内存又有限，唯一的解决办法就是将大文件转化为小文件（模块化映射），即16字策略：大、小，打破它们一一缩小规模，一一解决。
hash_map统计：当大文件转换为小文件时，那么我们可以使用常规的hash_map(ip, value)进行频率统计。
堆/快速排序：统计完成后，进行排序（可以使用堆排序），得到次数最多的IP。
具体来说就是：“首先，这一天，将访问百度的日志中的IP取出来，一一写入到一个大文件中。注意，IP是32位的，最多有2^还可以使用映射的方法，比如%1000，将整个大文件映射成1000个小文件，然后找出每个小文章中出现频率最高的IP（可以。使用hash_map对这1000个文件中的所有IP进行频率统计，然后依次找到每个文件中频率最高的IP）和对应的频率，然后在这1000个最大的IP中，找到频率最高的IP，这就是你想要的。”这个问题有几个问题，如下：
1. 哈希取模是一种等价映射。相同的元素不会分散到不同的小文件中。也就是这里使用的是mod1000算法，所以同一个IP经过hash取模后只能落到同一个位置。文件无法分散。因为如果两个IP相等，那么Hash(IP)之后的哈希值是相同的。对哈希值取模（例如对1000 取模），它仍然必须相等。
2. 那么什么是哈希映射呢？简单来说，就是为了方便计算机在有限的内存中处理大数据，让数据通过映射和哈希的方法均匀分布在相应的内存位置（例如将大数据映射成一棵小树）并通过求余的方法存储在内存中的一棵小树中，或者将一个大文件映射成多个小文件），而这种映射哈希方法就是我们通常所说的哈希函数。设计良好的哈希函数可以均匀分布数据并减少冲突。虽然数据被映射到一些不同的位置，但数据仍然是相同的数据，只是它替换和表示原始数据的形式发生了变化。
2. 查找热门查询，包括300 万个查询字符串中最热门的10 个查询。
原问题：搜索引擎会通过日志文件记录用户每次搜索时使用的所有搜索字符串。每个查询字符串的长度为1-255字节。假设目前有1000万条记录（这些查询字符串的重复度比较高，虽然总数是1000万条，但是如果去掉重复的话，不会超过300万条。一条查询的重复度越高string，表示查询字符串，用户越多越受欢迎）。请计算10 个最流行的查询字符串。所需内存不能超过1G。
答：从上面的问题1我们知道，如果数据很大，就会被分成小文件。例如，要查找1亿个IP中的前10名，可以先将IP分成1000个小文件，并保证一个文件中只能出现一种类型的IP，然后hashmap统计每个小文件中的IP并按数量排序，最后进行合并或最小堆处理每个小文件的前10个，得到最终结果。
但如果数据量比较小，可以一次性加载到内存中呢？比如问题2，虽然有1000万个Queries，但由于重复程度高，实际上只有300万个Queries，每个Queries都是255Byte。因此，我们可以考虑将它们全部放入内存中（假设300万个字符串不重复且都是最大长度，则最大占用内存为3M*1K/4=0.75G。因此，所有字符串都可以存放在内存中处理），现在我们只需要一个合适的数据结构。这里，HashTable绝对是我们的首选。
所以我们放弃分而治之/哈希映射步骤，直接进行哈希统计，然后排序。所以，对于这种典型的TOP K问题，采取的对策往往是：hashmap+堆。如下图：
Hash_map统计：首先对这批海量数据进行预处理。具体方法是：维护一个HashTable，其中Key为Query字符串，Value为Query出现的次数，即hash_map(Query, Value)。每次读取查询时，如果该字符串不在表中，则添加该字符串。并将Value值设置为1；如果该字符串在表中，则将该字符串的计数加一。最后，我们在O(N)的时间复杂度内，利用Hash表完成了统计；
堆排序：第二步是借助堆数据结构找到Top K。时间复杂度为N"logK。也就是说，借助堆结构，我们可以在log时间内找到并调整/移动。因此，维护一个大小为K（本题为10）的小根堆，然后遍历300 万个Query 来与根元素进行比较。所以，我们最终的时间复杂度是：O(N) + N’ * O(logK)，（N为1000万，N’为300万）。
当然，你也可以使用trie树。键字段存储查询字符串出现的次数。如果没有出现则为0。最后用最小推10个元素来对出现频率进行排序。
3、有一个1G大小的文件，里面每一行都是一个字，字的大小不超过16字节，内存限制为1M。返回100 个最常见的单词。
从上面两个例子，分而治之+哈希统计+堆/快速排序例程，我们已经开始感觉到它已经被尝试过了。接下来，再进行几次测试来验证它们。请看问题3：文件很大，内存有限。我应该怎么办？我还能做什么？无非是：
分而治之/哈希映射：顺序读取文件，对于每个单词x，取hash(x)%5000，然后将这个值存入5000个小文件中（记为x0,x1,x4999）。每个文件大约200k。如果部分文件大小超过1M，可以继续以类似的方式进行分割，直到分解后的小文件大小不超过1M。
hash_map统计：对于每个小文件，通过trie树/hash_map等来统计每个文件中出现的单词及其对应的频率。
堆/归并排序：取出频率最高的100个单词后（可以使用最小100个节点的堆），然后将这100个单词及其对应的频率存储到文件中，从而获得另外5000个文件。最后一步是合并这5000 个文件（类似于合并排序）。
学习交流群：462403503 重点二：多层划分
多级划分——本质还是分而治之的思想，重点是“分”的技巧！
适用范围：第k大、中位数、不重复或重复数
基本原理和要点：由于元素的范围很大，无法使用直接寻址表，因此通过多次划分逐步确定范围，最后在可接受的范围内进行。
问题示例：
4. 找出2.5 亿个整数中不重复整数的个数。内存空间不足以容纳这2.5亿个整数。
这有点像鸽巢原理。整数的个数是2^32。也就是说，我们可以将这2^32个数字分成2^8个区域（比如用单个文件来表示一个区域），然后将数据分成不同的区域，然后不同的区域可以直接使用bitmap来求解。也就是说，只要有足够的磁盘空间，就可以轻松解决。
5. 找到5 亿个整数的中位数。
这个例子比上面的例子更明显。首先我们将int分成2^16个区域，然后读取数据统计落入每个区域的数字个数。然后我们就可以根据统计结果来判断中位数落在哪个区域，同时知道这个区域的数量。几个大数恰好是中位数。然后对于第二次扫描，我们只计算落在该区域的数字。
事实上，如果不是int而是int64，经过3次这样的划分我们就可以将其降低到可以接受的水平。即可以先将int64划分为2^24个区域，然后确定该区域中最大的数，再将该区域划分为2^20个子区域，然后确定子区域中最大的数，然后确定子区域的数量。数量只有2^20，所以可以直接使用direct addr表进行统计。
关键三：布隆过滤器/Bitmap
布隆过滤器
适用范围：可以用来实现数据字典，判断数据的权重，或者求集合的交集。
基本原则和要点：
原理很简单，位数组+k个独立的哈希函数。将哈希函数对应的值的位数组设置为1。如果查找时发现哈希函数对应的位全部为1，则说明存在。显然，这个过程并不能保证搜索结果100%正确。同时，不支持删除插入的关键字，因为该关键字对应的位会影响其他关键字。所以一个简单的改进就是计数布隆过滤器，它使用计数器数组而不是位数组来支持删除。
如何根据输入元素的个数n来确定位数组m的大小和哈希函数的个数也是一个非常重要的问题。当哈希函数的个数k=(ln2)*(m/n)时，错误率最小。当错误率不大于E时，m必须至少等于n*lg(1/E)才能表示任意n个元素的集合。但m应该更大，因为位数组中至少有一半必须为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是元素个数的单位（准确的说是不同元素的个数）。通常单个元素的长度是很多位。因此，使用布隆过滤器通常可以节省内存。
学习交流群：462403503 重点4：Trie树/数据库/倒排索引
特里树
适用范围：数据量大，重复次数多，但小数据类型可以放入内存
基本原理和要点：实现方法、子节点的表示方法
扩展：压缩实现。
数据库索引
适用范围：大量数据的增删改查
基本原理和要点：利用数据设计和实现方法来处理海量数据的增删改查。
倒排索引
适用范围：搜索引擎、关键词查询
基本原理和要点：为什么叫倒排索引？一种索引方法，用于存储单词在文档或文档集中的存储位置的映射，以进行全文搜索。
以英文为例，需要索引的文本如下：
T0=“就是这样”
T1=“这是什么”
T2=“这是一根香蕉”
我们可以得到如下的反向文件索引：
“一”: {2}
“香蕉”: {2}
“是”: {0, 1, 2}
“它”: {0, 1, 2}
“什么”: {0, 1}
搜索条件“what”、“is”和“it”将对应于集合的交集。
开发前向索引是为了存储每个文档的单词列表。正向索引查询往往满足每个文档的有序、频繁的全文查询以及验证文档中每个单词的验证。在正向索引中，文档占据中心位置，每个文档都指向它包含的一系列索引条目。也就是说，文档指向它包含的单词，反向索引意味着单词指向包含它的文档。很容易看出这种反向关系。
关键5.外部排序
适用范围：大数据排序、去重
基本原理及要点：外排序的归并方法、替换选择loser树原理、最优归并树
问题示例：
1).有一个1G大小的文件，里面每一行都是一个字，字的大小不超过16字节，内存限制为1M。返回100 个最常见的单词。
这个数据有非常明显的特征。字大小为16字节，但内存只有1M，显然不足以用于散列，因此可以用于排序。内存可以用作输入缓冲区。
学习交流群：462403503 重点6：分布式处理的Mapreduce
MapReduce是一种简单地将大批量工作（数据）放入分解（MAP）执行，然后将结果合并为最终结果（REDUCE）的计算模型。这样做的好处是，任务分解后，可以在大量机器上进行并行计算，减少整个运算的时间。但如果你想让我介绍得更简单的话，那么，说白了，Mapreduce的原理就是归并排序。
适用范围：数据量大，但小数据类型可以放在内存中
基本原理和要点：将数据交给不同的机器处理，划分数据，归约结果。
问题示例：
MapReduce 的典型示例应用程序是一个计算一组文档中每个不同单词出现次数的过程：
海量数据分布在100台计算机中。想办法高效统计这批数据的TOP10。
总共有N台机器，每台机器上有N个数字。每台机器最多可以存储O(N) 个数字并对其进行操作。如何求N^2个数的中位数？
这篇文章的标题是瞬间杀掉99%的海量数据处理面试题，而不是100%。好啦，我们向读者展示最后一个问题，如下：
非常大的文件无法装入内存。每行包含一个int 类型数据，现在要求你随机选取100 个数字。
我们发现，以上任何一种模式/方法都不容易解决上述问题。那么还有哪些好的方法呢？我们可以看一下：操作系统内存分页系统设计（说白了就是映射+索引）。
Windows 2000 使用基于分页机制的虚拟内存。每个进程有4GB的虚拟地址空间。基于分页机制，4GB地址空间的某些部分被映射到物理内存，某些部分被映射到硬盘上的交换文件，而某些部分则不被映射到任何东西。程序中使用的所有虚拟地址都是4GB地址空间中的虚拟地址。要访问物理内存，需要使用物理地址。有关物理地址和虚拟地址的信息，请参阅：
物理地址（physical address） : 放置在寻址总线上的地址。将其放在寻址总线上。如果被读取，电路会根据该地址每一位的值，将对应地址的物理内存中的数据放入数据总线中进行传输。如果是写，电路根据该地址各位的值，将数据总线上的内容放入相应地址的物理内存中。物理内存以字节（8 位）为单位寻址。
虚拟地址（virtual address）: 4G虚拟地址空间中的地址。程序中使用了所有虚拟地址。使用分页机制后，4G地址空间被划分为固定大小的页面，每个页面要么映射到物理内存，要么映射到硬盘上的交换文件，要么不映射到任何东西。对于一般程序来说，只有一小部分4G地址空间映射到物理内存，大区域什么也不映射。物理内存也被分页以映射地址空间。对于32 位Win2k，页面大小为4K 字节。 CPU 用于将虚拟地址转换为物理地址的信息存储在称为页目录和页表的结构中。
物理内存分页，一个物理页的大小为4K字节，第0个物理页从物理地址0x00000000开始。由于页面大小为4KB，即0x1000 字节，因此页面1 从物理地址0x00001000 开始。第2 页从物理地址0x00002000 开始。可以看出，由于页大小为4KB，因此只需要32位地址的高20位即可对物理页进行寻址。
回到我们上面的主题：非常大的文件无法加载到内存中。每行包含一个int 类型数据，现在要求你随机选取100 个数字。为了解决这个问题，我们可以借鉴上述操作系统中的内存分页设计方法，做出如下解决方案：
【高效解决海量数据处理面试难题：掌握关键策略与技巧】相关文章：
2.米颠拜石
3.王羲之临池学书
8.郑板桥轶事十则
用户评论
这篇文章看起来超棒啊！感觉我马上就可以应付那些海量数据处理面试题啦！
有7位网友表示赞同！
终于有人能帮我解决这个难题了，每次面试遇到数据问题就头疼。
有17位网友表示赞同！
快速秒杀？我的目标是至少能及格通过面试题啊！
有12位网友表示赞同！
看了标题就想试试看，希望这篇文章很实用。
有17位网友表示赞同！
99%的数据处理问题我全都是不会的，希望能学到一些技巧提升自己。
有10位网友表示赞同！
数据处理确实很难，这本书好像可以解决我的痛点！
有19位网友表示赞同！
面试准备一直是难题，这篇文章能让我更有信心面对面试题了。
有19位网友表示赞同！
对海量数据的处理方式我一直不是很了解，这篇文章应该能给我一些启发。
有7位网友表示赞同！
快分享一下你的方法吧，我很急着想通过数据处理面试题！
有13位网友表示赞同！
看来要学习新技能啦，好好加油准备考试。
有5位网友表示赞同！
我最近也在学这个方面，希望这篇文章能给我一些新的思路。
有6位网友表示赞同！
文章看起来很专业，应该能让我掌握很多实用技巧，期待学习！
有10位网友表示赞同！
终于找到了一篇能够帮助我提高数据处理能力的文章！
有8位网友表示赞同！
不知道教程里面会不会讲到实际的工作案例，感觉会更生动一些。
有9位网友表示赞同！
准备面试了，这篇文章应该能帮我更快地掌握数据处理技巧！
有5位网友表示赞同！
我已经很熟悉一部分数据处理知识了，希望这篇文章也能给我带来新的收获！
有15位网友表示赞同！
最近面试遇到很多类似的数据处理问题，这本书很有帮助!
有10位网友表示赞同！
期待学习一些高效的方法，快速解决海量数据的处理难题。
有14位网友表示赞同！
看来要好好研读一下这篇教程了，希望能成为数据处理领域的专家！
有17位网友表示赞同！
我很想知道这篇文章里提到的技巧到底有哪些？
有19位网友表示赞同！