BitSet位图实现高效去重过滤方法

BitSet位图算法虽能以极低内存（如625KB替代200MB）实现海量非负整数的高效去重，但其本质是“索引即值”的紧凑布尔标记，仅适用于数据范围可控、无哈希冲突风险的场景；误用负数、字符串或盲目哈希将引发越界、覆盖或精度丢失，而真正可靠的去重必须遵循“先get再set”的原子逻辑，并结合分片锁或分层过滤策略应对并发与稀疏分布挑战——它不是万能容器，而是需要精准匹配业务数据特征的高性能工具。

BitSet 去重只适用于非负整数，且索引即值

BitSet 不是通用去重容器，它内部不存原始数据，而是把 bitSet.set(100) 直接理解为“整数 100 存在”。这意味着：原始数据必须是 非负整数，且你得能接受用它的数值本身当数组下标。传入负数会触发隐式类型转换（比如 -1 变成很大的正数），导致越界写或静默覆盖；传入字符串、UUID、浮点数会直接编译报错或需手动哈希映射——而哈希后可能冲突，此时 BitSet 单独用就不可靠。

常见误用场景：

• 把用户手机号字符串 "13812345678" 直接 parseLong 后塞进 BitSet —— 超出 Integer.MAX_VALUE，自动扩容但浪费大量空闲位
• 用 userId % 1000000 做哈希后 set，却没校验哈希冲突，导致两个不同 ID 映射到同一位，一个覆盖另一个

set() + get() 组合才是安全去重的关键路径

别直接无脑调 bitSet.set(x) 就完事。去重的核心逻辑是「先查再设」，否则重复数据会反复 set 同一位，cardinality() 仍正确，但你自己维护的计数器就崩了。

正确写法示例：

if (!bitSet.get(userId)) {
    bitSet.set(userId);
    uniqueCount++;
}

注意三点：

• bitSet.get(i) 对 i >= bitSet.length() 返回 false，不抛异常，容易掩盖越界问题（比如 userId 是 long 且 > 2³¹）
• cardinality() 是 O(n) 扫描整个 long 数组，高频插入时自己维护 uniqueCount 更快；但多线程环境下它更安全（避免竞态漏加）
• 如果只是最终统计，用 cardinality() 省心；如果中间要实时看去重进度，建议自己计数并加 volatile 或 AtomicInteger

内存省在哪？算清楚再决定用不用

BitSet 省的是「存储值」的开销。比如标记 [0, 5_000_000) 内哪些 ID 出现过：

• HashSet：每个 Integer 对象至少 16 字节（对象头+字段），加上哈希表负载因子和指针，实测约 40~60 字节/元素 → 总内存 ≥ 200 MB
• BitSet：5e6 ÷ 8 = 625 KB，不到前者的 0.3%

但这个优势有前提：

• 数据跨度不能太大。若 ID 分布在 [0, Long.MAX_VALUE) 里稀疏分布，BitSet 会分配超大数组直接 OOM
• 实际使用中，bitSet.length() 返回最高置位索引+1，不是已分配内存大小；bitSet.size() 才是底层 long 数组长度（单位是 long）
• 如果最大 ID 是 1000 万，但只用了其中 10 万个，BitSet 仍占 ~1.25 MB —— 这是固定成本，无法压缩

并发场景下 BitSet 不是线程安全的

多个线程同时调 set(x) 和 get(x)，可能出现位丢失：A 线程刚读到 false，B 线程立刻 set 成 true，A 还没来得及 set，结果该位就漏了。现象是 cardinality() 比预期小几个，且每次运行结果不一致。

不要用 synchronized(bitSet) 全局锁——吞吐量断崖下跌。可行方案：

• 按 ID 取模分片：比如 bitSets[i % 64]，每片配独立锁，降低竞争
• 换用 ConcurrentHashMap，内存稍高但语义清晰、无须额外同步
• 纯读多写少场景，可用 CopyOnWriteArraySet，但写操作代价高，慎用于高频清洗

真正大规模实时清洗，BitSet 往往只做第一层快速筛（比如拦截 95% 明显重复请求），剩下 5% 再交由带锁的 HashMap 或数据库去重 —— 单一结构很难兼顾速度、精度和并发安全。

今天带大家了解了的相关知识，希望对你有所帮助；关于文章的技术知识我们会一点点深入介绍，欢迎大家关注golang学习网公众号，一起学习编程~