如何快速检测超大字符串列表中的重复字符串

以下是三种可落地的高效实现方案，按需选择即可：

方案1：外部分桶法（100%无误差，生产环境首选） #

核心逻辑是通过哈希分桶把大数据集拆分为多个内存可容纳的小数据集，逐个检测：

• 遍历全量8GB字符串列表，对每个字符串计算MurmurHash3/XXHash这类高性能非加密哈希值，对哈希值取模N，N的取值满足 8GB / N ≤ 可用内存上限，比如你有1GB可用内存就取N=16，单个分桶平均大小仅500MB，完全可以放入内存。
• 每个字符串按哈希取模结果写入对应编号的磁盘分桶文件，相同字符串必然会落到同一个分桶中，不会出现跨桶漏检。
• 依次加载每个分桶文件到内存，用HashSet直接检测桶内重复项即可，汇总所有桶的重复结果就是全量重复集合。
• 额外优化：分桶写入时用二进制格式存储，减少序列化/反序列化开销，可提升30%以上的IO速度。

方案2：Bloom Filter二次校验法（适合重复率极低的场景，内存开销最小） #

符合你提到的初筛+二次校验的思路，内存开销可控制在300MB以内：

• 先计算Bloom Filter参数：8GB数据按每条64字符算约1.3亿条，设置误判率为0.01%的话，仅需要250MB左右的内存空间即可完成Bloom Filter初始化。
• 第一遍遍历全量列表：每个字符串先查询Bloom Filter，不存在就写入Bloom Filter；存在就将该字符串写入「疑似重复候选文件」。
• 第二遍处理：由于你预期绝大多数字符串唯一，候选文件的大小通常只有几MB到几百MB，直接全量加载到HashSet中即可检测出真实的重复项，排除哈希碰撞导致的误判。
• 额外优化：第一遍遍历时同时记录疑似重复字符串的磁盘偏移量，第二遍不需要全量扫描原文件，直接按偏移量读取对应字符串即可，速度可提升数倍。

方案3：外部归并排序法（适合极端规避哈希风险的场景） #

• 对全量字符串做字典序外部归并排序，排序完成后仅需遍历一次，对比相邻字符串是否相等即可找出所有重复项。
• 优势是完全不需要计算哈希，不存在任何哈希碰撞风险，劣势是IO开销比外部分桶法高1~2倍，速度更慢。

选型参考 #

• 可用内存≥1GB，优先选外部分桶法，全程仅2次全量IO，无误差，速度最快。
• 可用内存不足1GB且重复率极低，优先选Bloom Filter二次校验法，内存占用最低。

内容的提问来源于stack exchange，提问作者Bugmaster