海量数据处理：分治、位图、堆与外排序的十大经典题

导语：海量数据题的本质只有一个矛盾——数据规模远超内存容量。所有解法都是围绕「如何让每个处理单元的数据量降到内存装得下」展开。本篇先给出通用武器库（分治、位图、堆、Trie、外排序）与选型对照，再逐一拆解 10 道经典题：找出相同 URL、高频词 Top100、访问最多的 IP、不重复整数、判断数是否存在、最热门查询串、不同电话号码计数、中位数、按频度排序、Top500。

零、先掌握武器库（通用方法论）

这类题目不需要死记答案，只需要记住 5 件武器，以及「什么场景用哪一件」。

武器	核心思想	适用场景	关键点
① 哈希分治	hash(x) % N 把数据均匀分流到 N 个小文件	万能兜底，几乎所有题都能用	相同的值必然落入同一个小文件——这是分治正确的前提；a、b 两个文件要用同一个 hash 函数和同一个 N
② 位图 Bitmap	用 1 个 bit 表示一个整数的存在与否	整数判重、判存在、去重计数	空间与取值范围有关，与数据量无关；2^32 个数只需 512MB
③ 堆	维护 K 个元素的堆，逐个比较替换	求 TopK、中位数	求最大的 TopK 用「小顶堆」，求最小的 TopK 用「大顶堆」
④ Trie 前缀树	共享公共前缀，压缩存储	字符串统计、前缀匹配	大量公共前缀时省内存，但依赖数据分布，不如分治稳定
⑤ 外排序	小文件各自排序，再多路归并	全量排序、内存装不下	归并时只需在内存里维护各文件的当前最小值

两个必须会算的换算：

2^32 个 bit = 4,294,967,296 bit ÷ 8 ≈ 512 MB
1 亿个 bit  =   100,000,000 bit ÷ 8 ≈ 12.5 MB

一条选型心法：

---

一、如何从大量 URL 中找出相同的 URL？

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

答：

规模估算：50 亿 × 64B ≈ 320GB，远超 4G 内存，必须分治。

解法：哈希分治

步骤：

1. 遍历文件 a，对每个 URL 计算 hash(URL) % 1000，存入 a0 ~ a999（每个约 320MB）
2. 用相同的 hash 函数和相同的 N 遍历文件 b，存入 b0 ~ b999
3. 对每个 i：把 ai 全部读入 HashSet，再遍历 bi，命中即为共同 URL

为什么正确：相同的 URL 哈希值必然相同，取模后必然落入同一下标的小文件。所以 ai 只可能与 bi 有交集，与 bj (j≠i) 不可能有交集——这是分治法成立的理论基石。

优化与补充：

点	说明
小文件仍超内存	换一个 hash 函数二次分流，直到每个文件小于可用内存
hash 不均匀	若某桶过大，可单独对该桶再拆分
Trie 可行吗？	理论上可行（URL 公共前缀多，能压缩），但极度依赖数据分布，最坏情况下单机仍无法解析。可作为分治之后的补充：用 Trie 替代 HashSet 存储单个小文件，用时间换空间

总结：分而治之 + 哈希取余 + 子文件 HashSet 判重。

---

二、如何从大量数据中找出高频词？

题目：有一个 1GB 大小的文件，每行是一个词，每个词不超过 16B，内存限制 1MB，要求返回频数最高的 100 个词（Top 100）。

答：

解法：分治 + HashMap 统计 + 小顶堆

步骤：

1. 遍历大文件，对每个词 x 执行 hash(x) % 5000，分到 5000 个小文件（每个约 200KB < 1MB）。若仍有文件超过 1MB，继续拆分
2. 对每个小文件用 HashMap<词, 次数> 统计词频
3. 维护一个大小为 100 的小顶堆遍历所有词：若词的频次 > 堆顶频次，则替换堆顶并重新下沉

为什么用小顶堆：堆顶是当前 Top100 中最小的那个。新词只有比堆顶大，才有资格进入 Top100。这样全程只需维持 100 个元素，无需全量排序。

总结：分治 → HashMap 统计 → 小顶堆求 TopK。记住口诀：最大的 TopK 用小顶堆，最小的 TopK 用大顶堆。

---

三、如何找出某天访问网站最多的 IP？

题目：海量日志保存在超大文件中，无法直接读入内存，要求提取某天访问网站次数最多的那个 IP。

答：

解法：先过滤，再分治

步骤：

1. 先做一次过滤：只保留目标日期的日志，写入单独文件——题目只关心某一天，这一步能砍掉绝大部分数据
2. 对过滤后的文件按 hash(IP) % N 分流
3. 每个小文件用 HashMap 统计 IP 出现次数
4. 合并各文件的局部最大值

关键简化：本题只求 1 个最大值，不是 TopK，所以不需要堆，用一个变量 max 边统计边比较即可。

总结：先过滤缩小数据规模，再分治统计；求单一最大值不必用堆。

---

四、如何在大量数据中找出不重复的整数？

题目：在 2.5 亿个整数中找出不重复的整数。注意：内存不足以容纳这 2.5 亿个整数。

答：

规模估算（先算清楚，这是本题的题眼）：

2.5 亿个 int（4B）= 2.5e8 × 4B = 1e9 B ≈ 0.93 GB

注意：网上流传的「2.5 亿整数占 3.72GB」是错误的，3.72GB 对应的是 10 亿个整数。正确值约 0.93GB。

---

方法一：分治法（本题的正解）

---

方法二：2-bit 位图法（内存足够时最优）

用 2 个 bit 表示一个整数的状态：

状态	含义
00	未出现过
01	出现过 1 次（即题目要找的不重复整数）
10	出现过多次

遍历整数：遇 00→01，遇 01→10，遇 10→保持不变。最后输出所有 01 位对应的整数。

但本题能用位图吗？——不能。

int 取值范围 = 2^32 个数
位图占用 = 2^32 × 2 bit = 2^33 bit ÷ 8 ≈ 1 GB

• 题目给定：内存 < 0.93GB（装不下原始数据）
• 位图法需要：≈ 1GB

1GB > 0.93GB，位图法同样放不下。所以本题的正解是分治法。

结论：位图法只有在内存 ≥ 1GB 时才适用。它空间开销取决于取值范围而非数据量，这正是它与分治法的核心差异——数据稀疏时位图很亏，数据稠密时位图很赚。

总结：判断数字重复/去重，优先考虑位图法；内存不够就退回分治法。

---

五、如何在大量数据中判断一个数是否存在？

题目：给定 40 亿个不重复的、未排序的 unsigned int 整数，再给定一个数，如何快速判断这个数是否在 40 亿个数中？

答：

解法：位图法（本题最优）

推算：

unsigned int 范围：[0, 2^32)  →  共 4,294,967,296 ≈ 42.95 亿个可能值
40 亿 < 42.95 亿，可以完整覆盖
位图占用 = 2^32 bit ÷ 8 ≈ 512 MB

步骤：

1. 申请 512MB 的位图，所有 bit 初始化为 0
2. 遍历 40 亿个整数，把对应下标的 bit 置为 1
3. 查询时直接看目标数对应 bit：为 1 则存在，为 0 则不存在

维度	表现
时间复杂度	构建 O(N)，查询 O(1)
空间复杂度	512MB（与数据量 40 亿无关，只与取值范围有关）

备选方案：

方案	适用
分治法	内存 < 512MB 时使用
布隆过滤器	允许极低的误判率（「存在」可能误报，「不存在」一定准确）换取更小空间

总结：判断数字是否存在、是否重复，位图法是首选。

---

六、如何查询最热门的查询串？

题目：搜索引擎记录了用户每次检索的查询串，每个串不超过 255B。现有 1000 万条记录（重复度高，去重后不超过 300 万个），请统计最热门的 10 个查询串，内存不超过 1G。

答：

规模判断（关键一步）：

去重后 300 万个串，每串 255B + 计数值 4B
占用 = 3e6 × 259 B = 7.77e8 B ≈ 740 MB  <  1 GB  ✓ 装得下

因为去重后能装进内存，所以不必分治，这是本题与前面几题的关键区别。

---

方法一：HashMap 法（本题最优）

• 第一步遍历统计：O(N)
• 第二步小顶堆求 Top10：O(N log10)
• 整体只需 一趟扫描 + 一个 740MB 的 HashMap，内存 1G 够用

---

方法二：分治法（通用兜底）

若去重后仍超过内存，则 hash(串) % N 分流 → 每个小文件统计 Top10 → 汇总时再用小顶堆求全局 Top10。

方法三：Trie 前缀树法

当查询串存在大量公共前缀时，用 Trie 统计次数比 HashMap 更省内存（节点保存该串出现次数），最后同样用小顶堆取 Top10。

总结：先判断「去重后能否装进内存」——能装就用 HashMap（最简洁），装不下再分治；字符串有大量公共前缀时考虑 Trie。

---

七、如何统计不同电话号码的个数？

题目：已知某个文件内包含一些电话号码，每个号码为 8 位数字，统计不同号码的个数。

答：

解法：位图法

推算：

8 位号码取值范围：00000000 ~ 99999999，共 10^8 = 1 亿个
位图占用 = 1e8 bit ÷ 8 = 1.25e7 B ≈ 12.5 MB

步骤：

1. 申请长度为 1 亿的位图，初始化为 0
2. 遍历所有电话号码，把号码对应下标置为 1
3. 统计 bit 为 1 的数量，即为不同号码的个数

优势	说明
空间极小	只需 12.5MB，与文件中号码的条数无关
天然去重	重复号码只会重复置 1，不会多占空间
速度快	一次遍历 O(N)

总结：求解数据重复/去重计数类问题，首先考虑位图法。

---

八、如何从 5 亿个数中找出中位数？

题目：从 5 亿个数中找出中位数（排序后位置最中间的数；偶数个时取中间两个的平均值）。

答：

方法一：双堆法（仅适用于数据量小、内存够）

维护一个大顶堆（存较小的一半）和一个小顶堆（存较大的一半），保证：

• 大顶堆的最大值 ≤ 小顶堆的最小值
• 两个堆的元素个数差不超过 1

则中位数 = 两堆顶的平均值（偶数个）或元素较多那个堆的堆顶（奇数个）。

5 亿个数 × 4B = 2e9 B ≈ 2 GB

需要全部载入内存，约 2GB。内存不足时不可用，因此本题要用方法二。

---

方法二：按二进制位分治（本题正解）

步骤：

1. 按最高位（有符号 int 的符号位）把数分成两堆：f1（负数，较小）、f0（非负数，较大）
2. 根据两堆的元素个数判断中位数落在哪一堆，把问题转化为规模更小的子问题
3. 对目标文件按次高位继续二分，递归下去
4. 当文件大小能被内存容纳时，直接排序取中位数

举例：5 亿个数的中位数是排序后第 2.5 亿个与第 2.5 亿+1 个的平均值。若 f1 有 1 亿个数，则中位数落在 f0，且是 f0 中第 2.5亿 - 1亿 = 1.5亿 个数与它后一个数的平均值。

优势	说明
无需全量载入	每次只需顺序读写文件
复杂度	每个数被读写 O(log 值域) 轮（int 约 32 轮），时间 O(32N)

总结：大数据量求中位数 = 按二进制位分治；数据量小则可用双堆法流式维护。

---

九、如何按照 query 的频度排序？

题目：有 10 个文件，每个 1G，每行存放一个用户的 query，query 可能重复。要求按 query 的频度排序。

答：

先判断 query 的重复度，据此二选一。

方法一：HashMap 法（重复度高时）

不同 query 总数较小，直接全部读入 HashMap 统计次数，再按次数排序。

方法二：分治 + 外排序（重复度低时）

1. 遍历 10 个文件，用 hash(query) % 10 把 query 分流，保证相同 query 必然落入同一文件
2. 每个小文件用 HashMap 统计频度，按频度排序后写入磁盘
3. 对 10 个已按频度有序的文件做多路归并，得到全局有序结果

为什么必须分流而不能直接归并：因为同一个 query 可能散落在不同文件中，不分流就无法把它的次数累加完整。

总结：内存够就全量读入排序；内存不够就先分流统计、再外排序归并。

---

十、如何找出排名前 500 的数？

题目：有 20 个数组，每个数组有 500 个元素，且有序排列。如何在这 20 × 500 = 10000 个数中找出前 500 个数？

答：

解法：多路归并 + 大顶堆（堆大小 = 数组个数 = 20）

思路：

本题是经典的多路归并——20 个数组各自有序，要取全局最大的 500 个。

1. 建立大顶堆，大小为 20（数组个数）
2. 初始把每个数组的最大值（降序数组的首元素）放入堆，堆中元素需记录 (值, 来自哪个数组, 在该数组的索引)
3. 弹出堆顶（当前全局最大）存入结果数组
4. 从该元素所属的数组取下一个元素补入堆
5. 重复 500 次，即得前 500 个数

class DataWithSource implements Comparable<DataWithSource> {
    int value;    // 数值
    int source;   // 来自哪个数组
    int index;    // 在该数组中的下标

    DataWithSource(int value, int source, int index) {
        this.value = value; this.source = source; this.index = index;
    }

    // PriorityQueue 默认小顶堆，反转比较逻辑得到大顶堆
    @Override
    public int compareTo(DataWithSource o) {
        return Integer.compare(o.value, this.value);
    }
}

static int[] getTop(int[][] data) {
    int rowSize = data.length;              // 20
    int columnSize = data[0].length;        // 500
    int[] result = new int[columnSize];

    PriorityQueue<DataWithSource> maxHeap = new PriorityQueue<>();
    for (int i = 0; i < rowSize; i++) {
        maxHeap.add(new DataWithSource(data[i][0], i, 0));   // 各数组首元素入堆
    }

    int num = 0;
    while (num < columnSize) {
        DataWithSource d = maxHeap.poll();  // 弹出当前全局最大
        result[num++] = d.value;
        if (num >= columnSize) break;
        if (d.index + 1 < columnSize) {
            maxHeap.add(new DataWithSource(
                data[d.source][d.index + 1], d.source, d.index + 1));  // 补入同数组的下一个
        }
    }
    return result;
}

维度	复杂度
时间复杂度	O(500 × log20) —— 共弹出 500 次，每次堆操作 log20
空间复杂度	O(20) —— 堆中始终只有 20 个元素

注意：堆中元素必须记录来源数组和索引，否则弹出后不知道该从哪个数组补下一个元素。

总结：TopK 问题先想堆；多个有序序列取 TopK = 多路归并 + 大顶堆。

---

附录：十道题速查表

#	题目	核心武器	关键结论
1	找出相同 URL	哈希分治 + HashSet	相同值必入同一桶，a/b 用同一个 hash
2	高频词 Top100	分治 + HashMap + 小顶堆	最大的 TopK 用小顶堆
3	访问最多的 IP	先过滤 + 分治	只求 1 个最大值，不必用堆
4	不重复整数	分治（位图内存不够）	2.5 亿 int ≈ 0.93GB；2-bit 位图需 1GB
5	判断数是否存在	位图 ≈ 512MB	2^32 bit = 512MB，查询 O(1)
6	最热门查询串	HashMap（去重后装得下）	先判断「去重后能否进内存」
7	不同电话号码个数	位图 ≈ 12.5MB	10^8 bit = 12.5MB
8	5 亿数的中位数	按二进制位分治	双堆法需全量载入（2GB），内存不够
9	按 query 频度排序	分治 + 外排序归并	不分流就无法累加完整次数
10	前 500 个数	多路归并 + 大顶堆	堆大小 = 数组个数；需记录来源

记住这三句话，就能应对绝大多数变体：

1. 内存不够就分治——hash(x) % N，相同值必入同一桶；
2. 整数判重/判存在用位图——空间只与取值范围有关；
3. 求 TopK 用堆——最大用小顶堆，最小用大顶堆。