布隆过滤器详解：原理、误判率与实战应用

1
public class SimpleBloomFilter {
2

3
    private final long[] bits;          // 位数组，用 long[] 实现
4
    private final int size;             // 位数组总位数 m
5
    private final int hashCount;        // 哈希函数个数 k
6

7
    public SimpleBloomFilter(int size, int hashCount) {
8
        this.size = size;
9
        this.hashCount = hashCount;
10
        this.bits = new long[(size + 63) / 64];
11
    }
12

13
    /** 插入元素 */
14
    public void add(String value) {
15
        for (int i = 0; i < hashCount; i++) {
16
            int pos = hash(value, i);
17
            bits[pos / 64] |= (1L << (pos % 64));   // 置 1
18
        }
19
    }
20

21
    /** 查询元素：存在返回 true（可能误判），不存在返回 false（100% 准确） */
22
    public boolean contains(String value) {
23
        for (int i = 0; i < hashCount; i++) {
24
            int pos = hash(value, i);
25
            if ((bits[pos / 64] & (1L << (pos % 64))) == 0) {
26
                return false;   // 有一位是 0 → 一定不存在
27
            }
28
        }
29
        return true;            // 全 1 → 可能存在
30
    }
31

32
    /** 用同一个字符串哈希 + 盐值，派生出 k 个独立哈希 */
33
    private int hash(String value, int seed) {
34
        int h = value.hashCode() + seed * 0x9E3779B9;
35
        h = Integer.rotateLeft(h, seed & 31);
36
        return Math.floorMod(h, size);
37
    }
38

39
    public static void main(String[] args) {
40
        // 位数组 1 万位，4 个哈希函数（演示用）
41
        SimpleBloomFilter bf = new SimpleBloomFilter(10_000, 4);
42
        bf.add("apple");
43
        bf.add("banana");
44

45
        System.out.println(bf.contains("apple"));   // true（真实存在）
46
        System.out.println(bf.contains("cherry"));  // 大概率 false（不存在，100% 拦截）
47
    }
48
}

1
import com.google.common.hash.BloomFilter;
2
import com.google.common.hash.Funnels;
3

4
public class BloomFilterDemo {
5

6
    public static void main(String[] args) {
7
        // 预估 100 万个元素，期望误判率 1%
8
        BloomFilter<String> bloom = BloomFilter.create(
9
                Funnels.stringFunnel(StandardCharsets.UTF_8),
10
                1_000_000, 0.01);
11

12
        // 初始化：把所有存在的商品 id 放进去
13
        for (Long id : productService.getAllIds()) {
14
            bloom.put(String.valueOf(id));
15
        }
16

17
        // 查询
18
        boolean maybeExist = bloom.mightContain("10086");
19
        System.out.println(maybeExist);
20
    }
21
}