海量 query 按频度排序实战：HashMap 直排、哈希分治与外排序归并（advanced-java 海量数据处理）-育师

海量 query 按频度排序实战：HashMap 直排、哈希分治与外排序归并（advanced-java 海量数据处理）

【免费下载链接】advanced-java😮 Core Interview Questions & Answers For Experienced Java(Backend) Developers | 互联网 Java 工程师进阶知识完全扫盲：涵盖高并发、分布式、高可用、微服务、海量数据处理等领域知识项目地址: https://gitcode.com/doocs/advanced-java

导读

本篇文章基于 advanced-java 项目「海量数据处理」专题中的经典设计题：有 10 个 1G 大小的文件，每行存放一条用户的 query（可重复），要求按 query 出现的频度排序。文章将从数据规模估算入手，依次讲解“内存充足时直接读入 HashMap 排序”与“内存不足时哈希分治 + 外排序归并”两条完整解决路径，并结合 TopK 问题常用套路、最热门查询串、高频词 Top100 等同系列题目，给出可复用的分治、统计、排序方法论，帮助你在面试与工程实践中从容应对“海量数据 + 重复统计 + 全量排序”这一类问题。

题目描述与数据规模分析

有 10 个文件，每个文件大小为 1G，每个文件的每一行存放的都是用户的 query，每个文件的 query 都可能重复。要求按照 query 的频度排序。

先对数据规模做一个基础估算：

总数据量约10 × 1G = 10G，按 1 个字符 1 字节计算，总行数取决于单条 query 的平均长度；
query 是搜索引擎/日志系统中常见的“短字符串”，重复度往往较高（同一批用户在相近时间段内检索的关键词高度相似）；
题目要求的是全量排序：即把所有去重后的 (query, 出现次数) 二元组按频度从高到低（或从低到高）完整输出，而不只是找出 TopK 个最热门的。

正是“按频度排序”与“找出最热门 TopN”这两种需求差异，决定了本题的解法和如何查询最热门的查询串（只求 Top10）有所不同：后者最后一步用一个固定大小的小顶堆即可收尾，而本题需要对全量频度数据做完整排序。

解题思路总览：先判断数据特征，再决定方案

题目的核心矛盾是10G 数据 vs 可用内存。解答思路取决于一个关键前提——query 的重复度：

如果 query 的重复度比较大，说明去重后的不同 query 总数较小，可以一次性把所有（去重后的）query 读入内存处理，对应方法一：HashMap 法；
如果 query 的重复率不高，去重后数量依然庞大，可用内存不足以容纳全部 query，就必须采用分治法先化整为零，再逐个小文件处理，对应方法二：分治法。

这一“先评估数据特征、再决定内存/分治策略”的思路，与同专题下从 5 亿个数中找出中位数、找出相同 URL 等题目一脉相承：数据量级与重复度决定数据结构，数据结构决定算法。

方法一：HashMap 法（内存充足场景）

适用前提与内存估算

如果 query 重复率高，说明不同 query 的总数比较小，可以把所有 query 都加载到内存中的 HashMap 中，接着按出现次数排序即可。

内存是否够用，可以参照同系列题目如何查询最热门的查询串中给出的估算方法：查询串平均长度 255B，1000w 条记录去重后不超过 300w 个，则 HashMap 占用约300w × (255 + 4) ≈ 777M（4 为整型出现次数占用的字节数）。也就是说，只要去重后 key 的数量与平均长度之积在内存预算之内，HashMap 法就是最直接的方案。

实现步骤

遍历 10 个文件，逐行读取 query；
若 query 不在 map 中，map.put(query, 1)；若已存在，则map.put(query, map.get(query) + 1)，这一步时间复杂度为O(N)（N 为文件总行数）；
统计完成后，将 map 中所有 (query, count) 取出，按 value 进行排序；
输出排序后的完整结果。

参考实现（Java）：

Map<String, Integer> counter = new HashMap<>(); // 遍历 10 个 1G 文件，逐行统计 for (Path file : files) { Files.lines(file).forEach(query -> counter.merge(query, 1, Integer::sum)); } // 按频度降序排序 List<Map.Entry<String, Integer>> list = new ArrayList<>(counter.entrySet()); list.sort((a, b) -> b.getValue().compareTo(a.getValue())); // 输出排序结果 list.forEach(e -> System.out.println(e.getKey() + " : " + e.getValue()));

说明：上述代码为教学演示用途，实际生产环境建议使用BufferedReader逐行读取，避免一次性将大文件全部载入内存。

复杂度分析

时间复杂度：统计阶段O(N)，排序阶段取决于排序算法（O(M log M)，M 为去重后 query 数量），整体仍以排序复杂度为主；
空间复杂度：O(M × (avgLen + 4))，核心瓶颈是去重后 query 的规模是否放得进内存。

方法一的局限

当 query 重复率不高、去重后数量依然巨大（例如上千万甚至上亿个不同 query）时，HashMap 的内存开销会迅速膨胀，此时必须退而求其次，采用分治法。

方法二：分治法（内存不足场景）

分治法的核心是根据数据量大小以及可用内存的大小来确定问题划分的规模，把“一个装不下的问题”拆成“多个装得下的子问题”。

第 1 步：哈希取模，划分小文件

顺序遍历 10 个文件中的 query，通过 Hash 函数hash(query) % 10把这些 query 划分到 10 个小文件中。

要点：

取模基数取 10，与文件数对应，目的是让同一个 query 始终落到同一个小文件，从而保证“某个 query 的全部出现次数只会在一个小文件中被统计”，后续归并时不会重复统计；
实际工程中应使用稳定的哈希函数（如MurmurHash、FNV等），避免同一 query 在不同批次计算时落到不同文件；
划分后每个小文件的大小约为 1G（假设哈希分布均匀），恰好等于单文件原始规模；如果单文件仍超出可用内存，则应增大取模基数（如hash(query) % 100、% 1000），进一步切小，直到每个小文件可以整体读入内存为止。这一点在从大量 URL 中找出相同的 URL 中体现为hash(URL) % 1000切出 1000 个小文件、每个约 300MB。

第 2 步：逐个小文件统计并排序

对每个小文件，使用 HashMap 统计其中每个 query 的出现次数，然后按次数排序，并写入到另外一个单独文件中（即每个小文件对应一个“已排序的频度结果文件”）。

这一步与如何从大量数据中找出高频词中“对每个小文件用 HashMap 统计词频”的做法完全一致：map.put(x, map.get(x) + 1)逐行累加，得到该小文件内的完整频度表。

第 3 步：多路归并（外排序）

最后，对所有“小文件频度结果”按 query 次数进行整体排序。由于此时仍无法把所有 query 读入内存，因此需要使用外排序（external sort），典型实现就是多路归并（k-way merge sort）：

依次打开每个已排序的小文件（每路一个读指针）；
每次从各路的当前元素中选出最小（或最大）的一个，写入最终输出文件；
移动该路读指针，重复直至所有路耗尽。

多路归并每一轮只需在内存中维护 k 个元素（k 为小文件路数），内存占用极低，非常适合“数据放不下内存”的场景；其总时间复杂度为O(N log k)，其中 N 为总行数、k 为归并路数。

方法总结

本题的核心方法论可以浓缩为两句话：

内存若够，直接读入进行排序（HashMap 法）；
内存不够，先划分为小文件，小文件排好序后，再使用外排序进行归并（分治法）。

将其推广到同专题的一系列题目，可以得到一套可复用的“海量数据处理三板斧”：

分而治之，进行哈希取余：hash(x) % m把大文件切分为 m 个可载入内存的小文件，保证相同 key 落在同一小文件（参见高频词 Top100、找出相同 URL、找出最多访问 IP）；
使用 HashMap 统计频数：对小文件逐行merge(x, 1, sum)，得到精确频度表；
按需求收尾：
- 求最大的 TopN 个，用小顶堆；求最小的 TopN 个，用大顶堆（详见 TopK 问题常用套路与找出排名前 500 的数中的PriorityQueue实现）；
- 求全量排序，则对每路已排序结果做多路归并/外排序；
- 若只求唯一一个极值（如出现次数最多的 IP），则无需堆，直接用一个变量max维护即可（参见找出最多访问 IP）。

延伸：与其他海量数据处理题目的对比

题目	数据规模	目标	收尾手段
按 query 频度排序（本篇）	10 × 1G	全量按频度排序	小文件排序 + 外排序归并
查询最热门的查询串	1000w 条、去重后 ≤300w	Top10	HashMap 统计 + 大小为 10 的小顶堆
找出高频词 Top100	1G 文件、内存 1MB	Top100	哈希分治 + HashMap 统计 + 小顶堆
找出排名前 500 的数	20 个有序数组 × 500	Top500	大顶堆（PriorityQueue）
统计不同电话号码的个数	8 位号码全集 1 亿	去重计数	位图（bitmap）

对比可见：本题“全量排序”是系列题目中收尾最重的一环，需要把分治后的各路子结果通过外排序合并；而其余多数题目只需求 TopN，用小顶堆即可在O(N log k)内完成，这也正是 TopK 问题常用套路中强调“堆排序在做 TopK 时的优势在于只需维护 k 个元素”的原因。

总结

面对“10 个 1G 文件、按 query 频度排序”这类海量数据处理题，核心决策链是：先评估重复度与内存预算 → 内存充足则 HashMap 直排；内存不足则hash(query) % m分治 → 逐文件 HashMap 统计并按频度排序 → 多路归并（外排序）得到全局有序结果。掌握了这条链路，连同哈希分治、HashMap 统计、小顶堆/大顶堆、外排序归并这一整套组合拳，即可举一反三地解决海量数据处理专题下的全部同类问题。

创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考