Java处理50G单列CSV去重：求比Set更省内存的O(1)元素存在校验方案

适用方案：布隆过滤器 #

你需要的是布隆过滤器（Bloom Filter），完全匹配你的需求：基于哈希实现、插入和查询时间复杂度均为O(1)、内存占用远低于普通HashSet，不需要存储全量ID数据。

核心原理 #

布隆过滤器底层是一个bit数组搭配多个独立的哈希函数：

• 插入元素时，每个哈希函数分别对元素计算哈希值，将bit数组中对应下标的位置设为1
• 查询存在性时，检查所有哈希值对应下标的bit位：只要有一位是0，元素一定不存在；所有位都是1，元素大概率存在（存在可控的误判率）

适配性说明 #

你的场景仅需要校验ID是否已访问、不需要回读已存储ID，完全适配布隆过滤器的特性。按1亿唯一ID、万分之一误判率计算，仅需要230MB左右内存，完全可以支撑50GB CSV文件的去重需求。
如果完全不能接受误判，可以在布隆过滤器返回存在时，额外对该ID做二次校验（比如存入小容量Set或临时文件比对），即可实现100%准确去重，整体内存占用依然极低。

Java 实现示例 #

可以直接使用Guava库提供的开箱即用实现，代码示例如下：

import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
import java.nio.charset.StandardCharsets;

public class CsvDeduplication {
    public static void main(String[] args) {
        // 预估唯一ID总数量，可根据实际数据规模调整
        long expectedUniqueIdCount = 100_000_000L;
        // 可接受的误判率，数值越小内存占用越高，此处为0.01%
        double falsePositiveProbability = 0.0001;

        // 初始化字符串类型布隆过滤器
        BloomFilter<String> visitedIdFilter = BloomFilter.create(
                Funnels.stringFunnel(StandardCharsets.UTF_8),
                expectedUniqueIdCount,
                falsePositiveProbability
        );

        // 操作示例
        visitedIdFilter.put("1");
        visitedIdFilter.put("2");

        System.out.println(visitedIdFilter.mightContain("1")); // 输出 true
        System.out.println(visitedIdFilter.mightContain("3")); // 输出 false
    }
}

注意事项 #

• 预估唯一ID总量尽量贴合实际值，若实际插入量大幅超过预估值，误判率会快速升高
• 误判率可根据业务场景灵活调整，不需要100%准确的场景可以适当调高误判率进一步降低内存占用

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