大数据处理题汇总——通用框架 + 10 道高频题

一句话结论

海量数据处理题的共同套路只有五板斧：哈希分桶（把大数据切成能装进内存的小文件）、位图（用 bit 位压缩状态，适合整数范围已知的场景）、堆（求 TopK 用小顶堆 / 大顶堆）、多路归并（合并多个有序序列）、分治二分（通过逐次遍历收敛范围）。拿到题先走一遍「建模 → 方案对比 → 实现 → 边界扩展」框架，基本都能落地。

解题通用框架

① 问题背景理解（Clarify）

先确认约束，体现工程思维：

• 数据规模是多少？
• 内存限制？
• 单机还是分布式？
• 允许多次遍历吗？
• 精度要求？

② 抽象问题模型（Model）

将问题转化为已知算法模型：

• TopK → 有限内存下的选择问题
• 重复判断 → 去重 / 位图问题
• 大规模匹配 → 分治 + 哈希

③ 方案选型对比（Decision）

给出至少 2~3 种方案，分析复杂度和适用性，明确选择理由。

④ 边界 & 复杂情况（Edge Case）

• 数据倾斜怎么办？
• 节点宕机怎么办？
• 精度不够怎么办？

⑤ 单机 → 分布式演进

单机方案 → 分片 → 局部聚合 → 全局合并 → 考虑数据倾斜和网络开销

1. 从大量 URL 中找出相同的 URL

题目： 文件 a、b 各存放 50 亿个 URL，每个 64B，内存限制 4G，找出共同 URL。

① 问题规模： 50 亿 × 64B ≈ 320GB，远超内存，无法一次加载。

② 模型抽象： 集合求交集问题，内存受限 → 分治哈希。

③ 方案对比：

④ 最优方案（分治哈希）：

1. 对 a、b 文件各按 hash(URL) % 1000 分成 1000 个小文件
2. 相同 URL 的哈希值相同，必然在相同编号的小文件中
3. 对每对同编号小文件用 HashSet 求交集

⑤ 优化： 在小文件基础上构建前缀树（Trie），压缩公共前缀，减少存储并提高查询效率。

边界扩展：

• 数据倾斜（某个 URL 特别热）→ 对 hash 冲突的大桶再次分桶
• 分布式场景 → Map-Reduce：Map 阶段按 URL 分发，Reduce 阶段聚合

想一想：为什么按 hash(URL) % 1000 分桶后，相同的 URL 一定落在同一个编号的小文件里？

因为哈希函数是确定性的——同一个 URL 每次算出的 hash 值都一样，取模 1000 后余数也一样，自然进同一个桶。反过来，落在不同桶里的 URL 一定不同，所以只需在「同编号的桶对」之间求交集，把 320GB 的全局问题切成 1000 个可装入内存的小问题。

2. 从大量数据中找出高频词（Top 100）

题目： 1GB 文件，每行一个词（≤16B），内存限制 1MB，返回频数最高的 100 个词。

① 问题规模： 1GB 文件，1MB 内存，无法整体加载。

② 模型抽象： 频率统计 + 有限内存 TopK 问题。

③ 方案：

阶段一：分治哈希

• 按 hash(word) % N 将文件拆分为 N 个小文件（每个 < 1MB）
• 相同词必然进入同一个小文件

阶段二：局部统计

• 对每个小文件用 HashMap 统计词频
• 维护一个大小为 100 的小顶堆，只保留当前最大的 100 个

阶段三：全局合并

• 合并所有小文件的局部 Top 100，再用堆做一次全局排序

求解最大 TopK → 用小顶堆（堆顶维护最小值，淘汰更小的）
求解最小 TopK → 用大顶堆

⑤ 分布式演进： 多机并行统计 → 各机输出 Top 100 → 汇总节点合并排序。

想一想：求最大的 TopK，为什么用小顶堆（堆顶是最小值）而不是大顶堆？

因为我们要保留的是「当前最大的 100 个」。小顶堆的堆顶始终是这 100 个里最小的那个；新词进来只要和堆顶比：比堆顶大就淘汰堆顶、放入新词并调整，比堆顶小就直接丢弃。这样堆里永远只保留 100 个，空间 O(K)。大顶堆的堆顶是最大的，没法做「淘汰最小」这个操作。

3. 找出某天访问百度最多的 IP

题目： 海量日志，文件超大，找出某天访问最多的 IP。

方案：

1. 过滤：先按日期过滤出目标天的日志
2. 哈希分桶：hash(IP) % N 分成小文件
3. 局部 HashMap 统计：对每个小文件统计 IP 出现次数
4. 堆求 Top1：维护小顶堆，找出频率最高的 IP

核心工具： HashMap 统计 + 小顶堆 求 TopK

4. 在大量数据中找出不重复的整数

题目： 2.5 亿个整数，内存不足以全部装入，找出不重复的整数。

① 模型抽象： 数字状态判断问题 → 位图法（Bitmap）

② 位图法原理：

• 用 2 个 bit 表示每个整数的状态：00（未出现）、01（出现一次）、10（出现多次）
• 2^32 个整数 × 2 bit = 2^33 bit = 1GB，内存可接受

③ 方案对比：

想一想：判断「没出现 / 出现一次 / 出现多次」三种状态，为什么每个整数要用 2 个 bit，而不是 1 个 bit？

1 个 bit 只有 0/1 两种状态，只能表达「出现 / 没出现」，区分不出「出现一次」还是「多次」。2 个 bit 有 00/01/10 三种状态，正好对应三种。这是「状态数决定 bit 数」的通用规律：$k$ 个 bit 能编码 $2^k$ 种状态。

5. 判断一个数是否在 40 亿个整数中

题目： 40 亿个不重复 unsigned int 整数，判断给定数是否存在。

① 模型抽象： 集合成员查询 → 位图法

② 分析：

• unsigned int 范围 0 ~ 2^32 - 1 ≈ 43 亿
• 位图大小 = 2^32 bit = 512MB（可接受）
• 遍历 40 亿个数，将对应 bit 置 1
• 查询时直接检查目标数的 bit 位

时间复杂度： O(n) 预处理，O(1) 查询。

想一想：40 亿个整数，位图为什么只要 512MB 就能 O(1) 查询任意一个数是否存在？

因为位图不是「存数字本身」，而是「用数组下标当数字、用 bit 值当存在标志」。unsigned int 范围 0~$2^{32}-1$，一共 $2^{32}$ 个下标，每个下标只需 1 bit 记录在不在，共 $2^{32}$ bit = 512MB。查询时直接算下标读 bit，是 O(1) 随机访问，和「遍历查找」完全不同。

6. 查询最热门的 10 个查询串

题目： 1000 万条查询串（去重后 ≤ 300 万），统计最热的 10 个，内存 ≤ 1G。

① 问题特点： 字符串频率统计，有大量重复。

② 方案：

方案一：HashMap + 小顶堆

• 直接用 HashMap 统计每个 query 的频率（300 万条，每条 ≤ 255B，约 300MB × 2 = 600MB，可接受）
• 维护大小为 10 的小顶堆，遍历 HashMap 保留 Top 10

方案二：前缀树（Trie）

• 适合字符串统计，节点维护计数
• 节省重复前缀的存储空间，查询高效

③ 推荐方案：

• 内存充足 → HashMap + 小顶堆，实现简单
• 内存紧张 → Trie + 堆，压缩存储

7. 统计不同电话号码的个数

题目： 文件中包含大量 8 位数字电话号码，统计不同号码个数。

① 模型抽象： 8 位数字范围 00000000 ~ 99999999，总计 10^8 = 1 亿个可能值。

② 位图法：

• 位图大小 = 10^8 bit = 12.5MB（极小）
• 遍历所有电话号码，对应 bit 置 1
• 最后统计 1 的个数即为不同号码数

8. 从 5 亿个数中找出中位数

题目： 5 亿个数，找出中位数。

① 问题分析： 无法全部加载内存，不能直接排序。

② 方案：分治二分

1. 遍历一次，统计各数字范围内的数量（如按 bit 位分组）
2. 根据计数，确定中位数落在哪个范围（类似二分）
3. 对该范围再次遍历精确统计

③ 具体做法（内存限制版）：

• 第一次：统计每个数字 32 个 bit 的最高位，确定中位数在哪半段
• 逐步细化范围，每次二分，O(log V) 次遍历即可

④ 分布式演进：

• Map 阶段：各节点统计局部数据的值域分布
• Reduce 阶段：汇总各节点分布，确定全局中位数范围
• 再次 Map 精确统计

想一想：5 亿个数找中位数，为什么不能先排序，为什么「二分值域」能行得通？

排序需要 O(N log N) 且要能装下全量数据，内存不允许。而中位数只关心「第 2.5 亿大的值落在哪个区间」，所以可以先用最高 bit 把数分成两半、数一数各半有多少，确定中位数在哪半段，再对那半段递归二分。每轮只需遍历一次、记录计数，不用排序，O(log V) 次遍历就能锁定位次。

9. 按 Query 频度排序

题目： 10 个文件，每个 1G，每行是用户 query，按频度排序。

① 两种场景：

内存足够：

• 直接 HashMap 统计所有 query 频率，排序输出

内存不够（推荐方案）：

1. 哈希分桶：hash(query) % 10 将同一 query 归到同一小文件
2. 局部排序：对每个小文件内单独 HashMap 统计 + 排序
3. 外部排序归并：对 10 个已排序小文件执行多路归并排序

② 时间复杂度： O(N log N)，其中 N 为去重后 query 数量。

10. 找出排名前 500 的数

题目： 20 个有序数组，每个 500 个元素，找出 20 × 500 = 10000 个数中的前 500。

① 模型抽象： 多路有序序列的 TopK 问题。

② 最优方案：多路归并 + 小顶堆

1. 初始化：取每个数组的最大值（末尾元素），构建大小为 20 的大顶堆
2. 每次从堆顶取出最大值，记录结果，并将该数组的下一个元素入堆
3. 重复 500 次

时间复杂度： O(500 × log 20) = O(500 × 4.3) ≈ O(2150)，极快。

⑤ 分布式演进： 各节点先取本地 Top 500 → 汇总节点合并 20 × 500 个候选 → 再次 Top 500。

想一想：20 个有序数组找全局前 500，为什么用「大顶堆」而不是「小顶堆」？

因为要找的是最大的 500 个，且输入是 20 个各自有序的数组。把每个数组当前最大的元素放进堆，堆顶就是「20 个候选里的全局最大」，弹出它、再把它所在数组的下一个元素补进来，重复 500 次。这里堆扮演的是「动态选出当前最大候选」的角色，所以用大顶堆。注意：这和 Top100 那题用小顶堆的用法相反，区别在于一个是「维护保留集」、一个是「维护候选集」。

附录：常用算法工具箱

章末提问

1. 「哈希分桶后某个桶还是太大（数据倾斜）怎么办？」

结论：对热点桶再做二次哈希，把大桶切成更小的子桶（二级分桶），或对倾斜 key 单独加随机前缀打散后再聚合。因为倾斜的本质是少数 key 的 hash 值集中，继续分桶就能把它摊开。

2. 「位图法在什么场景下不适用？」

结论：当数值范围未知、跨度极大（如 64 位整数或任意长字符串）时不适用。因为位图空间与「值域大小」成正比、与数据量无关，值域大到 $2^{64}$ 时位图根本无法分配，此时改用哈希分桶或布隆过滤器。

3. 「为什么求最大 TopK 用小顶堆，求最小 TopK 用大顶堆？」

结论：因为堆顶是「可被淘汰的那个」。求最大 TopK 时用小顶堆，堆顶是当前 K 个里最小的，新元素比堆顶大才替换；求最小 TopK 反之用大顶堆。核心是让堆顶成为「进门槛」的哨兵。

4. 「布隆过滤器能替代位图吗？它的误判从哪来？」

结论：不能完全替代。布隆过滤器用多个哈希函数映射到 bit 数组，能 O(1) 判「可能存在」，但会有误判（把不存在的判成存在），因为多个 key 可能共享同一组 bit 位。它只适合「允许少量误判、追求极小内存」的存在性判断，不能用于精确计数或精确去重。

5. 「中位数分治二分的最坏遍历次数是多少？和排序比优势在哪？」

结论：每轮按一个 bit 或一个值域段二分，共约 O(log V) 轮（V 是值域跨度，32 位整数约 32 轮），每轮遍历一次全量数据。优势在于不用排序、内存 O(1)，只需多次顺序扫描，适合单机内存装不下全量数据的场景。