海量 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 中接着按出现次数排序即可。内存是否够用可以参照同系列题目 如何查询最热门的查询串 中给出的估算方法查询串平均长度 255B1000w 条记录去重后不超过 300w 个则 HashMap 占用约300w × (255 4) ≈ 777M4 为整型出现次数占用的字节数。也就是说只要去重后 key 的数量与平均长度之积在内存预算之内HashMap 法就是最直接的方案。实现步骤遍历 10 个文件逐行读取 query若 query 不在 map 中map.put(query, 1)若已存在则map.put(query, map.get(query) 1)这一步时间复杂度为O(N)N 为文件总行数统计完成后将 map 中所有 (query, count) 取出按 value 进行排序输出排序后的完整结果。参考实现JavaMapString, Integer counter new HashMap(); // 遍历 10 个 1G 文件逐行统计 for (Path file : files) { Files.lines(file).forEach(query - counter.merge(query, 1, Integer::sum)); } // 按频度降序排序 ListMap.EntryString, 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 条、去重后 ≤300wTop10HashMap 统计 大小为 10 的小顶堆找出高频词 Top1001G 文件、内存 1MBTop100哈希分治 HashMap 统计 小顶堆找出排名前 500 的数20 个有序数组 × 500Top500大顶堆PriorityQueue统计不同电话号码的个数8 位号码全集 1 亿去重计数位图bitmap对比可见本题“全量排序”是系列题目中收尾最重的一环需要把分治后的各路子结果通过外排序合并而其余多数题目只需求 TopN用小顶堆即可在O(N log k)内完成这也正是 TopK 问题常用套路 中强调“堆排序在做 TopK 时的优势在于只需维护 k 个元素”的原因。总结面对“10 个 1G 文件、按 query 频度排序”这类海量数据处理题核心决策链是先评估重复度与内存预算 → 内存充足则 HashMap 直排内存不足则hash(query) % m分治 → 逐文件 HashMap 统计并按频度排序 → 多路归并外排序得到全局有序结果。掌握了这条链路连同哈希分治、HashMap 统计、小顶堆/大顶堆、外排序归并这一整套组合拳即可举一反三地解决 海量数据处理 专题下的全部同类问题。【免费下载链接】advanced-java Core Interview Questions Answers For Experienced Java(Backend) Developers | 互联网 Java 工程师进阶知识完全扫盲涵盖高并发、分布式、高可用、微服务、海量数据处理等领域知识项目地址: https://gitcode.com/doocs/advanced-java创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考 
长河君 · 2026/9/18 9:29:32 · 阅读 1.2k 海量 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 中接着按出现次数排序即可。内存是否够用可以参照同系列题目 如何查询最热门的查询串 中给出的估算方法查询串平均长度 255B1000w 条记录去重后不超过 300w 个则 HashMap 占用约300w × (255 4) ≈ 777M4 为整型出现次数占用的字节数。也就是说只要去重后 key 的数量与平均长度之积在内存预算之内HashMap 法就是最直接的方案。实现步骤遍历 10 个文件逐行读取 query若 query 不在 map 中map.put(query, 1)若已存在则map.put(query, map.get(query) 1)这一步时间复杂度为O(N)N 为文件总行数统计完成后将 map 中所有 (query, count) 取出按 value 进行排序输出排序后的完整结果。参考实现JavaMapString, Integer counter new HashMap(); // 遍历 10 个 1G 文件逐行统计 for (Path file : files) { Files.lines(file).forEach(query - counter.merge(query, 1, Integer::sum)); } // 按频度降序排序 ListMap.EntryString, 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 条、去重后 ≤300wTop10HashMap 统计 大小为 10 的小顶堆找出高频词 Top1001G 文件、内存 1MBTop100哈希分治 HashMap 统计 小顶堆找出排名前 500 的数20 个有序数组 × 500Top500大顶堆PriorityQueue统计不同电话号码的个数8 位号码全集 1 亿去重计数位图bitmap对比可见本题“全量排序”是系列题目中收尾最重的一环需要把分治后的各路子结果通过外排序合并而其余多数题目只需求 TopN用小顶堆即可在O(N log k)内完成这也正是 TopK 问题常用套路 中强调“堆排序在做 TopK 时的优势在于只需维护 k 个元素”的原因。总结面对“10 个 1G 文件、按 query 频度排序”这类海量数据处理题核心决策链是先评估重复度与内存预算 → 内存充足则 HashMap 直排内存不足则hash(query) % m分治 → 逐文件 HashMap 统计并按频度排序 → 多路归并外排序得到全局有序结果。掌握了这条链路连同哈希分治、HashMap 统计、小顶堆/大顶堆、外排序归并这一整套组合拳即可举一反三地解决 海量数据处理 专题下的全部同类问题。【免费下载链接】advanced-java Core Interview Questions Answers For Experienced Java(Backend) Developers | 互联网 Java 工程师进阶知识完全扫盲涵盖高并发、分布式、高可用、微服务、海量数据处理等领域知识项目地址: https://gitcode.com/doocs/advanced-java创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考