源码：labs/foundations/bitmap-bitset-demo/src/BloomFilterDemo.java

• 原始路径：labs/foundations/bitmap-bitset-demo/src/BloomFilterDemo.java
• 类型：java

import java.util.Random;

public class BloomFilterDemo {
    static class Bloom {
        final long[] bits;
        final int k;
        Bloom(int bitCount, int k) { bits = new long[(bitCount + 63) >> 6]; this.k = k; }

        // 由 hashCode 双哈希派生 k 个伪独立位置
        private int[] positions(String s) {
            int h1 = s.hashCode();
            int h2 = (h1 >>> 16) | (h1 << 16);
            int mod = bits.length << 6;
            int[] p = new int[k];
            for (int i = 0; i < k; i++) p[i] = Math.floorMod(h1 + i * h2, mod);
            return p;
        }
        void add(String s) { for (int p : positions(s)) bits[p >> 6] |= 1L << (p & 63); }
        boolean mightContain(String s) {
            for (int p : positions(s)) if ((bits[p >> 6] & (1L << (p & 63))) == 0) return false;
            return true;
        }
    }

    public static void main(String[] args) {
        int n = 10_000;                       // 已录入 1 万条
        Bloom bf = new Bloom(96_000, 7);      // m≈96k bit, k≈7（p≈1%）
        Random r = new Random(42);
        String[] saved = new String[n];
        for (int i = 0; i < n; i++) { saved[i] = "1101" + r.nextInt(1_000_000); bf.add(saved[i]); }

        int miss = 0;
        for (String s : saved) if (!bf.mightContain(s)) miss++;
        System.out.println("已录入 1 万条，漏判数 = " + miss + "（应为 0，零漏判）");

        int fp = 0, total = 100_000;
        for (int i = 0; i < total; i++)
            if (bf.mightContain("9999" + r.nextInt(2_000_000))) fp++;
        System.out.printf("未录入随机 10 万条误判 %d 条（%.2f%%），理论 ≈ 1%%%n", fp, fp * 100.0 / total);
    }
}