P16 内存 200M 读取 1G 文件并统计重复内容

面试题：给你 200MB 内存，要统计一个 1GB 文件里重复的内容（如重复的 URL/ID），怎么处理？

核心约束

文件（1G）> 内存（200M），所以不能一次性把文件全部读进内存，也不能用普通 HashMap 存全部数据。

方案一：分治 + 哈希取模（通用做法）

text

1. 把大文件按行读取，对每条记录 hash 后取模（如 % 10）分到 10 个小文件
2. 同一 hash 的记录一定落在同一个文件，重复项不会跨文件
3. 对每个小文件单独用 HashMap 统计
4. 合并各文件结果

text

hash(key) % N → file_i

小文件大小约 100MB，内存装得下；
保证相同 key 进同一文件（哈希一致性），不会漏统计。

方案二：外部排序 / 归并

先对文件做外部排序（分块排序后归并）；
排完序后相同的值相邻，一次扫描即可统计重复；
适合"还要输出有序结果"的场景。

方案三：基于数据的特性优化

如果数据是整数/URL 等

BitMap：数据范围有限（如 int）时，用位图标记出现次数；
BloomFilter：先过滤明显不重复的，减少统计量（有误判，需权衡）；
Trie/前缀树：URL 前缀重复度高时省内存。

利用"去重统计"和"计数统计"的区别

只问"有没有重复"：BloomFilter / HashSet 分片；
问"每个重复了几次"：分治后 HashMap 计数。

加分点

分治的 N 根据内存定：保证单文件 < 可用内存的 1/3~1/2；
处理要流式逐行读（BufferedReader），不要一次 readAll；
哈希函数要均匀，避免某个小文件过大（内存溢出）；
大数据集经典思路总结：外部排序 / 哈希分片 / 位图 / 布隆过滤器，面试官想听的就是这些。

一句话总结

1G 文件、200M 内存：先哈希分片成内存装得下的小文件（相同数据必落同片），再逐片 HashMap 统计合并；或用外部排序让相同元素相邻后一次扫描；配合位图/布隆过滤器进一步省内存。