一、十道海量数据处理面试题

♟️1、海量日志数据，提取出某日访问百度次数最多的那个IP。(分治思想 + 哈希表)

1. 首先，从日志中提取出所有访问百度的IP地址，将它们逐个写入一个大文件中，便于后续处理。

2. 考虑到IP地址是32位的，最多有 2^23 个不同IP。为了减少单个文件的处理压力，可以采用哈希或者取模的方式，将这些IP均匀分散到 1000个小文件 中。这样每个小文件的规模大幅缩小，更便于处理。

3. 对于每个小文件，使用 HashMap 统计每个IP的出现次数。HashMap的插入和查找操作都是 O(1) 的复杂度，能够高效地完成频率统计。然后从中找出出现频率最高的IP和对应的频率。

4. 最后，将这 1000个小文件 中统计出的最高频率IP和频率值汇总。再在这1000个IP中执行一次线性扫描，找到频率最高的IP，得到最终结果。

♟️2、在1千万个查询记录中，去重后不超过300万个，要求在内存不超过1G的情况下，统计出最热门的10个查询串。(典型的 Top K 问题)

该问题是典型的 Top K 问题，可以通过以下两种方法解决：

1. Hash + 小根堆方法：
首先，使用 Hash表 在 O(N) 的时间复杂度下统计所有查询串的出现次数。然后，使用一个大小为 K（10） 的 小根堆 来维护出现频率最高的查询串。在遍历300万个查询串的统计结果时，每次与堆顶元素比较，如果出现次数更高，则替换堆顶元素并重新调整堆。最终得到Top 10的查询串。总体时间复杂度为 O(N)+O(N′log⁡K)。

2. Trie树 + 小根堆方法：
构建一个 Trie树，将所有查询串插入其中，同时在Trie树的节点中记录每个查询串的出现次数。这样可以有效地管理和存储大量查询串。最后，再使用一个大小为 10 的小根堆，对Trie树中存储的查询串进行排序，找出出现次数最多的Top 10。该方法在查询串较长时，空间效率较高。

♟️3、有一个1G大小的一个文件，里面每一行是一个词，词的大小不超过16字节，内存限制大小是1M。返回频数最高的100个词。(分治思想 + 哈希表)

1. 顺序读取数据，对每个词 x 进行哈希操作 hash(x) % 5000，将词分配到5000个小文件中，每个文件约200KB。

2. 如果某个文件超过1MB，可继续使用类似的方法将其划分为更小的文件，直到所有小文件的大小都不超过1MB。

3. 对每个小文件，使用 Trie树 或 HashMap 统计词频，并通过维护一个100个节点的小根堆，选出出现频率最高的100个词，将结果存入文件。

4. 最终，对这5000个文件进行类似于 归并排序 的过程，整合并找到全局出现频率最高的词。

♟️4、有10个文件，每个文件1G，每个文件的每一行存放的都是用户的query，每个文件的query都可能重复。要求你按照query的频度排序。(典型的 Top K 问题)

该问题是典型的 Top K 问题，可以通过以下三种方案解决：

1. 分割+归并排序方案：
首先，将数据顺序读取，并根据 hash(query) % 10 将查询串分配到另外10个小文件中，每个文件约1G。然后在一台 内存2G 的机器上，使用 HashMap 统计每个查询串的出现次数，再通过 快速排序、堆排序 或 归并排序 进行排序。最终，将这10个排好序的文件进行归并排序，得到最终的结果。

2. 直接内存统计方案：
如果所有的查询串总量有限，可以直接将它们加载到内存中，使用 Trie树 或 HashMap 统计每个查询串的出现次数。之后，通过排序算法快速获取出现次数最多的查询串。

3. 分布式处理方案：
与方案1类似，数据分割后分配到多个小文件中，但进一步采用 分布式架构（如 MapReduce）进行并行处理。各节点分别统计和排序后，将结果合并，进一步提升处理效率。

♟️5、 给定a、b两个文件，各存放50亿个url，每个url各占64字节，内存限制是4G，让你找出a、b文件共同的url？(分治法/布隆过滤器)

该问题涉及 大规模数据去重和求交集，可通过以下两种方案解决：

1. 分治法方案：
由于数据量过大无法直接加载到内存中，采用 分治法。

• 第一步：对两个文件分别按 hash(url) % 1000 进行划分，生成1000对小文件。这样每个小文件的大约为300M，同一哈希值的URL存储在对应的小文件中。
• 第二步：对于每对小文件（如a0和b0），使用 HashSet 存储其中一个小文件的URL，再遍历另一个小文件，对比URL是否存在于HashSet中，找出共同的URL。

2. Bloom Filter方案：
如果允许一定的错误率，可以使用 Bloom Filter。

• 第一步：使用 4G内存（约340亿bit）将一个文件的URL映射到Bloom Filter中。
• 第二步：读取另一个文件的URL，逐个检查是否在Bloom Filter中，若存在则认为是可能的共同URL。由于Bloom Filter存在误判的可能性，结果需要进一步验证。

♟️6、在2.5亿个整数中找出不重复的整数，注，内存不足以容纳这2.5亿个整数。(Bitmap、分治法)

该问题涉及 大规模数据去重和查找唯一整数，可通过以下两种方案解决：

1. Bitmap方案：

• 原理：使用 Bitmap 为每个整数分配 2bit 来表示状态：
  • 00：不存在
  • 01：出现一次
  • 10：出现多次
  • 11：无意义
• 步骤：扫描整数文件，更新Bitmap状态。扫描完成后，再遍历Bitmap，输出所有状态为 01 的整数，即为不重复的整数。由于Bitmap占用内存较小，适用于数据量较大的场景。

2. 分治法方案：

• 原理：如果数据量过大，可以采用 分治法。
• 步骤：将数据按 hash(num) % N 进行划分，存入 N个小文件 中，确保同一整数存入同一个文件。对每个小文件使用HashMap或Bitmap统计整数出现次数。然后再排序和归并这些小文件，同时去重，最终输出不重复的整数。
  此方法在内存受限时非常有效。

♟️7、腾讯面试题：给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，如何快速判断这个数是否在那40亿个数当中？

该问题涉及 大规模数据查找和去重，可通过以下两种方案解决：

1. 位图法（Bitmap）方案：
申请 512M内存，使用 1bit 表示一个无符号整数的存在状态。读取40亿个数时，将对应位置的bit置为1。查询时，只需检查该位置的bit是否为1，即可判断数是否存在。此方法内存占用小，查询效率高。

2. 分治法（二分查找）方案：
根据数的 最高位 将数据划分为两个文件，一个存储最高位为0的数，另一个存储最高位为1的数。根据查询数的最高位，选择对应的文件继续查找。重复这一过程，每次根据下一位划分数据，类似 二分查找，最终以 O(log⁡n) 的时间复杂度定位查询数。此方法适用于超大数据集的查找。

♟️8、怎么在海量数据中找出重复次数最多的一个？

先做hash，然后求模映射为小文件，求出每个小文件中重复次数最多的一个，并记录重复次数。然后找出上一步求出的数据中重复次数最多的一个就是所求（具体参考前面的题）。

♟️9、上千万或上亿数据（有重复），统计其中出现次数最多的前N个数据。

上千万或上亿的数据，现在的机器的内存应该能存下。所以考虑采用hashmap/搜索二叉树/红黑树等来进行统计次数。然后就是取出前N个出现次数最多的数据了，可以用第2题提到的堆机制完成。

♟️10、一个文本文件，大约有一万行，每行一个词，要求统计出其中最频繁出现的前10个词，请给出思想，给出时间复杂度分析。

这题是考虑时间效率。用trie树统计每个词出现的次数，时间复杂度是O(nle)（le表示单词的平准长度）。然后是找出出现最频繁的前10个词，可以用堆来实现，前面的题中已经讲到了，时间复杂度是O(nlg10)。所以总的时间复杂度，是O(nle)与O(nlg10)中较大的那一个。

二、海量数据处理的十大方法总结

在面对超大数据时，无法一次性加载到内存中处理。这时就需要一些高效的算法和数据结构。以下是10个常用方法的详细总结，包含原理、适用场景和典型问题示例。

📌 1. Bloom Filter（布隆过滤器）

用途

• 判断某个数据是否存在于集合中。
• 适合快速去重、检测数据是否存在。

原理

• 使用一个位数组和多个哈希函数。
• 插入数据时，将数据用哈希函数计算多个位置，将这些位置的位设为1。
• 判断数据是否存在时，检查所有对应的位是否为1。
• 注意：布隆过滤器会有假阳性（误判为存在），但不会有假阴性。

优化

• Counting Bloom Filter：用计数器代替位数组，支持删除操作。
• Spectral Bloom Filter：支持统计元素的频次。

典型场景

• URL去重：检测某个网页是否已被爬取。
• 垃圾邮件检测：判断是否是已知垃圾邮件。
• 广告反欺诈：检测是否重复点击广告。

📌 2. Hashing（哈希）

用途

• 数据快速查找、统计和去重。

原理

• 使用哈希函数将数据映射到固定大小的哈希表中。
• 通过哈希表存储键值对，O(1)的时间复杂度完成查找和插入。
• 解决哈希冲突的方式：链地址法、开放地址法。

典型场景

• 统计某日访问量最大的IP地址。
• 判断两个大文件中是否有重复的记录。

📌 3. Bitmap（位图）

用途

• 占用极少的空间判断数据是否存在或进行数据去重。
• 适用于数据范围大但数据量相对较小的场景。

原理

• 用每一位（bit）表示一个数据的存在状态。
• 数据值直接映射到位数组中的索引位置，置1表示存在。

优化

• 使用多bit位图可以统计数据的出现次数。

典型场景

• 统计某个地区的所有电话号码。
• 2.5亿个整数中找出不重复的整数。

📌 4. Heap（堆）

用途

• 快速找出前N大的数据或前N小的数据。

原理

• 使用最小堆或最大堆。
• 当需要找前N大的数据时，用一个大小为N的最小堆。
• 每次遇到更大的数据时替换堆顶元素。

典型场景

• 找出100万个数中最大的前100个数。
• 实时监控系统中检测前N个异常事件。

📌 5. 分治法（双层桶划分）

用途

• 解决无法一次性加载到内存的大数据问题。
• 适合找中位数、第K大元素或去重等问题。

原理

• 通过哈希函数或简单取模的方式，将数据划分到多个桶中。
• 每个桶的大小控制在内存可处理的范围内。
• 在桶内继续执行相关操作。

典型场景

• 找出5亿个整数的中位数。
• 找出2.5亿个整数中不重复的整数。

📌 6. 数据库索引

用途

• 提高大规模数据的查询效率。

原理

• 数据库通过B+树或哈希索引等结构，为表中的字段创建索引。
• 查询时通过索引快速定位数据，而不是全表扫描。

典型场景

• 电商平台中商品的快速查询。
• 银行系统中的账户查询。

📌 7. 倒排索引（Inverted Index）

用途

• 用于关键词搜索场景。
• 搜索引擎等文本数据场景。

原理

• 每个单词对应一个文档列表，记录出现位置和频率。
• 搜索时将关键词对应的文档列表取交集，快速获取结果。

典型场景

• 搜索引擎中查找包含某个关键词的文章。
• 论文数据库中查找包含指定关键词的论文。

📌 8. 外排序

用途

• 对无法全部加载到内存中的数据进行排序。

原理

• 使用归并排序和分块排序的思想。
• 将数据分割为若干小块，每块在内存中排序后存储到磁盘。
• 最后使用多路归并排序合并结果。

典型场景

• 处理1G大小的文本文件，内存仅有1M的情况。
• 大型日志文件的排序与分析。

📌 9. Trie树

用途

• 快速查找和前缀匹配。
• 适用于海量字符串数据的存储与搜索。

原理

• 使用树状结构存储字符串，每个节点代表一个字符。
• 查询时根据字符逐层匹配，时间复杂度为O(L)，L为字符串长度。

优化

• 压缩Trie树：减少节点数量。

典型场景

• 搜索引擎的自动补全和联想词推荐。
• 查询重复的搜索关键词。

📌 10. 分布式处理（MapReduce）

用途

• 处理超大规模的数据集，常用于分布式环境。

原理

• Map阶段：将数据分割并分发到多台机器上进行并行计算。
• Reduce阶段：对Map阶段的结果进行归约，得到最终结果。

典型场景

• 日志分析：统计日志中不同类型的访问次数。
• 计算全网用户的行为数据。

🚀 总结与对比

三、海量数据中找出现次数最多的前N个数据的解决方案

在处理海量数据时，主要分为可一次读入内存和不可一次读入内存两种情况。针对这两种场景，有多种解决思路和优化策略。

情况一：数据可一次读入内存

当数据量经过去重后，可以一次性读入内存时，推荐使用HashMap或Trie树进行数据统计。HashMap通过键值对存储数据及其出现次数，Trie树在处理字符串类数据时尤为高效。

在统计完成后，可以利用小顶堆维护出现次数最多的前N个数据。每次比较当前数据与堆顶元素，如果当前数据出现次数更高，则替换堆顶元素。小顶堆的插入和删除操作的时间复杂度为 O(log⁡N)，在大数据量中表现优越。

如果数据存在较多重复，可以先使用**布隆过滤器（Bloom Filter）**进行判重，减少内存占用和计算量。对于需要进一步优化的场景，可以使用优先队列替代小顶堆，减少堆的维护成本。

情况二：数据无法一次读入内存

当数据量过大，无法全部加载到内存中时，有以下几种解决方案：

1. 分布式计算（MapReduce）

分布式计算是解决超大规模数据的常用方法。通过MapReduce将数据划分到多台机器，每台机器处理不同的数据分区。

在Map阶段，机器会对数据进行局部统计，得到当前分区内的Top N数据。随后在Reduce阶段，各个机器的结果会被汇总并合并，再次取Top N，最终得到全局前N个数据。

分布式计算适用于数据规模极大且需要快速响应的场景，常用于日志分析、搜索引擎等。

2. 数据分区 + 单机处理

如果没有分布式环境，可以手动进行数据分区。根据数据的特征，可以选择哈希取模或按数据范围划分，将数据写入不同的子文件。

对于每个子文件，采用与内存场景类似的方法进行统计和堆排序。最后再对这些中间结果执行归并排序，取前N个数据。

这种方法充分利用了磁盘存储能力，解决了内存不足的问题，且相较于分布式计算更加经济。

3. 近似统计

在某些场景下，获取一个近似的Top N结果即可满足需求。这时可以使用Count-Min Sketch等概率统计方法，快速估算数据的出现频率。

Count-Min Sketch采用哈希映射，将数据映射到一个二维数组中。通过多次哈希计算，得到数据的频率估计值。虽然有一定误差，但在流式数据处理中非常高效。

此外，如果只需要热门数据，还可以通过LRU缓存或滑动窗口等方法进行实时监控，适合日志监控和异常检测等场景。