01

60 秒回答模板

我会先确认两个文件大小、内存上限、单词编码、是否区分大小写、结果是去重交集还是带频次交集。精确方案一是按 hash(word) 对两个文件使用同一规则分桶，相同单词一定落到同编号桶，再逐桶把较小桶读入集合，与另一个桶流式求交；如果单桶仍过大，就增加桶数或二次分桶。方案二是外部排序后用双指针归并求交，适合需要有序输出或同时统计频次的场景。

考点 核心机制与工程取舍
难度 中高频面试题
回答目标 按定义、机制、场景讲清楚
02

深入解析

01

先问约束

不能直接说 HashSet。要明确文件是否能流式读取、内存上限、字符归一化、重复单词怎么处理、结果是否需要排序，以及能否接受 Bloom Filter 这类近似结构。

02

哈希分桶

对两个文件用相同 hash 函数和桶数拆分，保证相同单词只会出现在同编号桶。这样全局问题变成多个小交集问题，峰值内存由最大桶决定。

03

桶内求交

逐个处理同编号桶，通常把较小桶读入 HashSet，另一个桶流式扫描并输出命中的单词。若要去重结果，输出侧也要控制重复；若要频次，则集合需要改成计数表。

04

倾斜处理

高频词或 hash 偏斜会让某些桶过大。可以增加桶数、对超大桶二次分桶、对高频词单独处理，或改用外部排序避免单桶内存爆掉。

05

外部排序备选

分别对两个文件做外部排序，再用两个有序流双指针扫描：相等则输出并移动，较小者前进。它 I/O 成本较高，但边界清晰，适合需要有序结果、范围合并或频次统计的场景。

03

易错点

  • 直接把一个文件全部读进 HashSet，没有处理内存上限。
  • 两个文件分桶规则不一致，导致相同单词可能落到不同桶。
  • 不说明重复单词是去重、计数还是保留原始出现次数。
  • 忽略桶倾斜，认为 hash 后每个桶一定均匀且能放进内存。
04

面试官追问

如果只要求判断某个词是否可能在另一个文件出现？

可以用 Bloom Filter 节省内存，但它有误判率，适合预过滤，不适合直接产出精确交集。

分桶后某个桶还是很大怎么办？

增加桶数或对该桶二次分桶；如果是极端高频词，还可以单独记录并特殊处理，避免拖垮整个任务。

如何处理重复单词？

如果结果是去重交集，只输出一次；如果要共同出现次数，则要分别统计频次，交集频次通常取两个文件计数的最小值。

哈希分桶和外部排序怎么选？

哈希分桶实现简单、平均 I/O 少，适合无序精确交集；外部排序更稳定，适合有序输出、范围处理和频次归并。