海量数据处理：一个框架解决所有面试题

一句话结论（30s）

海量数据处理的通用框架是「哈希分桶分治」——因为相同 key 的哈希值相同、必然落到同一个桶里，把超内存的大文件拆成可单机处理的小文件，再叠加位图去重、小顶堆求 TopK、多路归并排序这几个工具，就能覆盖绝大多数面试题。

核心原理（2min）

• 哈希分桶：hash(key) % N 把数据均分，相同 key 落在同桶；热点桶做二次哈希防倾斜。为什么”相同 key 落同桶”是解题的钥匙？ 因为一旦相同内容被分到同一小文件，全局问题就拆成了 N 个互不干扰的局部问题，每个都能装进内存——分治的第一步就是让”有关联的数据先聚到一起”。
• 位图法：1 bit 表示一个整数是否存在，O(1) 查询；2-bit 位图可区分 0/1/多次。
• TopK：HashMap 统计频率 + 大小为 K 的小顶堆保留最大 K 个。
• 多路归并：各文件内部排序后，用 N 元素堆合并 N 个有序序列。
• 回答套路：先确认约束 → 抽象为已知模型 → 给 2-3 种方案 → 讨论边界。

底层深入（5-10min）

核心矛盾

数据量远超可用内存，无法一次加载全部数据。但解题模板适用于所有变体。

工具一：哈希分桶（分治）

核心思想：相同 key 的哈希值相同 → 必然在同一个小文件中。将大文件拆分为 N 个小文件，每个文件可单独处理。

场景: 文件 a、b 各 50 亿个 URL，每个 64B = 320GB，内存 4G，找相同 URL

步骤:
1. 对 a 按 hash(URL) % 1000 → 分 1000 个小文件 (a0~a999)
2. 对 b 按相同哈希函数 → 同样分 1000 个小文件 (b0~b999)
3. 相同 URL 必然在相同编号的 a_i 和 b_i 中
4. 对每对 (a_i, b_i) 用 HashSet 求交集 → 每个小文件 ~320MB，可接受

数据倾斜处理：如果某个桶特别大（热点 URL），对这个桶内部做二次哈希再分桶。为什么直接 % N 不一定够？ 因为真实数据常有热点，某几个 key 会占绝对多数，落到同一个桶就又把桶撑爆；对热点桶换一个哈希函数再分一层，是”分治”思想在同一桶内的递归复用。

💭 思考：看到什么信号该想到「哈希分桶」？—— 海量题的第一信号永远是「数据量 > 内存，装不下」。装不下就不能全局算，只能拆。怎么拆才能让全局问题退化成「互不干扰的局部问题」？靠一条性质：相同 key 的哈希值相同，必然落进同一个桶。于是「找相同 URL」这种全局配对问题，就变成「每个桶内部单独配对」——桶与桶之间不用交互。这一下把「超内存」降维成「每个桶能装进内存」。所以步骤永远是：先分桶（分治），再在每个桶里用常规内存算法。

工具二：位图法（Bitmap）

核心思想：用 1 个 bit 表示一个整数是否存在（或 2 bit 表示 0/1/多次）。

场景: 40 亿个 unsigned int 整数，判断给定数是否存在

unsigned int 范围 0 ~ 2^32-1 ≈ 43 亿
位图大小 = 2^32 bit = 512 MB

遍历 40 亿个数 → 对应 bit 置 1
查询时: bitmap[target] == 1? → 存在
时间复杂度: O(n) 预处理, O(1) 查询

变体（2-bit 位图）：00 = 未出现, 01 = 出现一次, 10 = 多次。2.5 亿个整数找不重复的数 → 2^32 × 2 bit = 1 GB。

💭 思考：为什么「判存在 / 去重」这种题，一个 bit 就能表示一个数？—— 这类题只关心「出现过没有」，是个「是 / 否」问题，一个 bit 恰好装得下。整数本身是 4 字节（32 bit），而它的存在性只要 1 bit，于是用「下标 = 数，值 = 存在性」的位图，内存直接缩 32 倍。看到「整数、范围有限、只判存在 / 去重 / 重复次数」，就别建 HashSet 存整数值，问一句「能不能用位图按 bit 记」。2-bit 位图只是把「是 / 否」扩展成「0 / 1 / 多次」的计数版。

工具三：HashMap + 小顶堆（TopK）

核心思想：HashMap 统计频率，大小为 K 的小顶堆保留最大的 K 个。

场景: 1GB 文件，每行一个词(≤16B)，1MB 内存，找 Top 100 高频词

阶段一: 哈希分桶 → hash(word) % 5000 → 每个小文件 ~200KB
阶段二: 每个小文件内部 HashMap 统计 + 大小为 100 的小顶堆
阶段三: 合并 5000 个文件的局部 Top 100 → 全局排序取 Top 100

为什么 TopK 用小顶堆？

找最大 Top K → 用小顶堆
  堆顶 = 当前"候选人"中的最小值
  新元素 > 堆顶 → 淘汰堆顶，新元素入堆
  新元素 ≤ 堆顶 → 不够格，跳过

找最小 Top K → 用大顶堆（同理，反向）

工具四：多路归并（外部排序）

核心思想：每个小文件内部排序，然后用大小为 N 的堆合并 N 个有序序列。

场景: 10 个文件，各 1G，按 query 频度全局排序

步骤:
1. 哈希分桶 → hash(query) % 10 归入同一文件
2. 各文件内部 HashMap 统计 + 排序
3. 多路归并: 10 个指针各指向文件头 → 10 元素的小顶堆 → 每次取堆顶输出

💭 思考：多路归并和「合并 K 个链表」其实是同一个套路，怎么一眼认出？—— 只要看到「多个有序序列，要合成一个全局有序序列」，就想到归并：N 路各放一个指针，取「所有序列当前头」里的最小值输出，再用一个 N 元素的小顶堆维护这些头。这里的「头」就是各文件第一个元素，「取堆顶」就是输出全局最小。本质就是「堆 + 归并」：堆负责「谁最小」，指针负责「下一步补谁」。所以外部排序 = 内部排序 + 多路归并。

常用算法工具箱

面试回答框架

1. 先确认约束：数据量、内存限制、单机/分布式、精排要求
2. 抽象为已知模型：TopK / 去重 / 求交 / 排序
3. 给出 2-3 种方案：从简单到优化，说明复杂度取舍
4. 讨论边界：数据倾斜、节点宕机、精度不足

💭 思考：拿到一道海量数据题，脑子里该先走哪几步？—— 别急着背答案，先按框架反推：第一步「确认约束」，因为「内存 4G」和「内存 1MB」解法完全不同，数据量决定能不能一次装下；第二步「抽象模型」，把题面翻译成已知类型（TopK / 去重 / 求交 / 排序），翻译对了才能套工具箱；第三步「给方案」，从暴力到优化层层递进，展示复杂度取舍；第四步「谈边界」，主动说出数据倾斜、机器故障这些坑，体现你考虑过真实环境。这四步不是背模板，是「先问清问题 → 再归类 → 再给解 → 再兜底」的工程思维。

章末提问

1. 为什么求 TopK 用大小为 K 的小顶堆，而不是大顶堆？ 结论：因为小顶堆的堆顶是当前 K 个候选里的最小值，新元素只要大于堆顶就能”淘汰最小值、自己进堆”；这样堆始终只保留最大的 K 个，空间和每次操作都控制在 O(log K)。

2. 位图法解决”40 亿整数判存在”为什么只要 512MB？ 结论：因为用 1 个 bit 表示一个整数是否存在，40 亿个整数对应 2^32 个 bit 位即 512MB；相比存整数值，内存缩小了 32 倍，且查询是 O(1) 的直接下标访问。

3. 哈希分桶后，两个大文件找相同 URL 为什么”对应桶”之间一定配对？ 结论：因为两边用的是同一个哈希函数，相同 URL 的哈希值相同、落到同一个桶编号；所以只需比较 a_i 和 b_i 这两个对应桶，跨桶的一定不相等。