bitset 不能直接实现布隆过滤，但可高效完成非负整数去重；需手动添加多个哈希函数才能模拟布隆过滤，其本质是位容器而非过滤器。
BitSet 本身不能直接做布隆过滤，但可以高效实现整数去重；布隆过滤需要额外哈希逻辑，不能只靠 BitSet 原生方法。
用 BitSet 实现大量整数的去重（适合范围明确、非负整数）
BitSet 底层是动态扩容的 long 数组，每个 bit 代表一个非负整数是否存在，空间效率极高（1 bit/数），比 HashSet 节省内存约 64 倍（对比 64 位引用）。
适用前提：待去重整数是非负的，且最大值可控（比如 ≤ 10⁷）。超出范围会触发 huge BitSet 扩容，影响性能。
- 创建 BitSet：`BitSet seen = new BitSet();`
- 标记存在：`seen.set(x);` // x ≥ 0，自动扩容
- 判断是否重复：`if (!seen.get(x)) { seen.set(x); /* 处理新数 */ }`
- 遍历所有唯一值：用 `seen.nextSetBit(0)` 循环获取下标，即原始整数值
BitSet 模拟简易布隆过滤（需手动哈希，非标准实现）
标准布隆过滤器要求多个独立哈希函数映射到同一 BitSet，Java 的 BitSet 不提供哈希能力，必须自己实现。它只是“位容器”，不是“过滤器”。
关键点：
- 预估容量 n 和误判率 ε，计算最优 bit 数 m ≈ −n·lnε / (ln2)²，哈希函数个数 k ≈ m/n·ln2
- 用 2–3 个不同哈希（如 `x`, `x * 2654435761`, `x ^ (x >>> 16)`）对 m 取模，得到 k 个位置
- 插入时：`bitSet.set(hash1 % m); bitSet.set(hash2 % m); ...`
- 查询时：`bitSet.get(hash1 % m) && bitSet.get(hash2 % m) && ...`，全为 true 才认为“可能存在”
⚠️ 注意：BitSet 不处理并发，多线程需外加 `synchronized` 或用 `ConcurrentHashMap` + 分段 BitSet；也不支持删除（标准布隆不支持）。
和 HashSet / LongAdder / RoaringBitmap 对比选型建议
不是所有场景都该用 BitSet：
- 数据稀疏且跨度极大（如只有 1、10000000、2000000000）→ 用 HashSet 更省空间
- 需要统计频次或支持负数 → BitSet 不适用，改用 IntOpenHashSet（Trove）或 fastutil 的 IntSet
- 内存敏感 + 范围集中（如用户 ID ∈ [0, 500w)）→ BitSet 是首选
- 需要更高压缩率与随机访问速度 → 考虑 RoaringBitmap（对连续段自动压缩，比原生 BitSet 快且更省空间）
一个轻量布隆过滤工具类示意（基于 BitSet）
以下代码仅作逻辑示意，生产环境建议用 Guava 的 BloomFilter 或 Apache Commons Collections 的 BloomFilter：
public class SimpleBloomFilter {
private final BitSet bits;
private final int size;
private final List<tointfunction>> hashes;
<pre class="brush:java;toolbar:false;">public SimpleBloomFilter(int expectedN, double fpp) {
this.size = (int) Math.ceil(-expectedN * Math.log(fpp) / (Math.log(2) * Math.log(2)));
this.bits = new BitSet(size);
this.hashes = Arrays.asList(
x -> Math.abs(x) % size,
x -> Math.abs(x * 2654435761) % size,
x -> Math.abs((x ^ (x >>> 16)) * 1540483477) % size
);
}
public void put(int x) {
hashes.forEach(h -> bits.set(h.applyAsInt(x)));
}
public boolean mightContain(int x) {
return hashes.stream().allMatch(h -> bits.get(h.applyAsInt(x)));
}
}
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
