布隆过滤器

发表于 更新于 分类于 本文字数： 1.4k 阅读时长 ≈ 5 分钟

在处理海量数据时，我们常常面临一个核心问题：如何高效判断某个数据是否存在于集合中？ 这个问题在缓存穿透、数据去重等场景中尤为常见。布隆过滤器（Bloom Filter）正是为了解决这类问题而设计的一种概率型数据结构。它以极低的空间复杂度和时间复杂度，提供了高效的解决方案，尽管其结果存在一定的误差率。

本文将从布隆过滤器的原理、使用场景到实战实现（包括 Java 手动实现、Guava 库和 Redis 实现）进行全面解析，帮助你快速掌握这一实用工具。

布隆过滤器是什么？

核心概念

布隆过滤器由 Burton Howard Bloom 于 1970 年提出，是一种基于 位数组（bit array） 和 多个哈希函数 的概率型数据结构。它的核心思想是通过哈希函数将元素映射到位数组中的多个位置，并将这些位置标记为 1。当判断元素是否存在时，只需检查所有对应的位是否为 1。

优点与局限

  • 优点：
    • 空间效率极高（例如存储 100 万个元素仅需约 122 KB）。
    • 时间复杂度低（插入和查询均为 O(k)，其中 k 为哈希函数数量）。
  • 局限：
    • 存在误判率：可能错误地判断一个不存在的元素存在（但不会漏判）。
    • 不可删除元素：直接删除会破坏其他元素的哈希标记。

布隆过滤器的工作原理

数据结构组成

布隆过滤器由两个核心部分组成：

  1. 位数组（Bitset）：初始时所有位均为 0。
  2. 哈希函数集合：通常使用多个不同的哈希函数（如 6 个）。

插入与查询流程

插入元素

  1. 使用多个哈希函数对元素进行计算，得到一组哈希值。
  2. 将位数组中对应位置的位设置为 1。

查询元素

  1. 对元素进行相同的哈希计算，得到哈希值。
  2. 检查所有哈希值对应的位是否为 1：
    • 如果全部为 1，则认为元素可能存在（可能误判）。
    • 如果存在任意一个为 0，则元素一定不存在。

误判率分析

布隆过滤器的误判率与以下因素相关：

  • 位数组大小（m）：越大，误判率越低。
  • 哈希函数数量（k）：过多或过少都会影响性能。
  • 插入元素数量（n）：元素越多，误判率越高。

公式估算误判率：

P≈(1−e−knm)kP \approx \left(1 - e^{-\frac{kn}{m}}\right)^k

布隆过滤器的典型应用场景

存在性检测

  • 缓存穿透防护：防止恶意请求绕过缓存直接访问数据库。
  • 垃圾邮件过滤：判断邮箱地址是否在黑名单中。
  • URL 去重：爬虫中避免重复抓取相同 URL。

数据去重

  • 订单号/手机号去重：海量数据中快速判断是否已存在。
  • 社交网络好友推荐：避免重复推荐已关注的用户。

布隆过滤器的实战实现

Java 手动实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
import java.util.BitSet;

public class MyBloomFilter {
    private static final int DEFAULT_SIZE = 2 << 24; // 位数组大小
    private static final int[] SEEDS = {3, 13, 46, 71, 91, 134}; // 哈希种子

    private BitSet bits = new BitSet(DEFAULT_SIZE);
    private SimpleHash[] func = new SimpleHash[SEEDS.length];

    public MyBloomFilter() {
        for (int i = 0; i < SEEDS.length; i++) {
            func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]);
        }
    }

    public void add(Object value) {
        for (SimpleHash f : func) {
            bits.set(f.hash(value), true);
        }
    }

    public boolean contains(Object value) {
        if (value == null) return false;
        boolean ret = true;
        for (SimpleHash f : func) {
            ret = ret && bits.get(f.hash(value));
        }
        return ret;
    }

    static class SimpleHash {
        private int cap;
        private int seed;

        public SimpleHash(int cap, int seed) {
            this.cap = cap;
            this.seed = seed;
        }

        public int hash(Object value) {
            int h = value.hashCode();
            return Math.abs((cap - 1) & (seed * ((h ^ (h >>> 16)))));
        }
    }
}

测试代码

1
2
3
4
MyBloomFilter filter = new MyBloomFilter();
System.out.println(filter.contains("https://blog.hezi.space/")); // false
filter.add("https://blog.hezi.space/");
System.out.println(filter.contains("https://blog.hezi.space/")); // true

使用 Guava 库实现

Guava 提供了开箱即用的布隆过滤器实现，适合单机场景。

Maven 依赖

1
2
3
4
5
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.1-jre</version>
</dependency>

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
BloomFilter<Integer> filter = BloomFilter.create(
    Funnels.integerFunnel(),
    1500,
    0.01); // 容量 1500，误判率 1%

filter.put(123);
System.out.println(filter.mightContain(123)); // true
System.out.println(filter.mightContain(456)); // false
```xml
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.1-jre</version>
</dependency>

代码示例

1
2
3
4
5
6
7
8
9
10
11
12
13
14
BloomFilter<Integer> filter = BloomFilter.create(
    Funnels.integerFunnel(),
    1500,
    0.01); // 容量 1500，误判率 1%

filter.put(123);
System.out.println(filter.mightContain(123)); // true
System.out.println(filter.mightContain(456)); // false
```xml
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.1-jre</version>
</dependency>

代码示例

1
2
3
4
5
6
7
8
BloomFilter<Integer> filter = BloomFilter.create(
    Funnels.integerFunnel(), 
    1500, 
    0.01); // 容量 1500，误判率 1%

filter.put(123);
System.out.println(filter.mightContain(123)); // true
System.out.println(filter.mightContain(456)); // false

Redis 分布式布隆过滤器

Redis 通过 RedisBloom 模块 支持分布式布隆过滤器，适用于高并发、分布式场景。

安装 RedisBloom

1
docker run -p 6379:6379 --name redis-redisbloom redislabs/rebloom:latest

常用命令

1
2
3
4
5
6
7
8
9
# 初始化布隆过滤器（容量 10000，误判率 0.001）
BF.RESERVE myFilter 0.001 10000

# 添加元素
BF.ADD myFilter "user123"

# 查询元素是否存在
BF.EXISTS myFilter "user123"  # 1（存在）
BF.EXISTS myFilter "user456"  # 0（不存在）

布隆过滤器的优化与注意事项

降低误判率

  • 增大位数组：增加容量以容纳更多哈希位。
  • 调整哈希函数数量：通过公式 $ k = \frac{m}{n} \ln 2 $ 选择最优值。

可删除场景的解决方案

标准布隆过滤器不支持删除，但可通过以下方式改进：

  • 计数布隆过滤器（Counting Bloom Filter）：将位数组替换为计数器数组，支持减操作。
  • RoaringBitmap + 布隆过滤器：结合其他数据结构实现动态更新。