Article: 布隆过滤器

Live life to the fullest

布隆过滤器

Ryan · Published at 2026-09-03

基本原理

布隆过滤器是一种用于判断“某个元素是否可能存在”的概率型数据结构。它通常由以下两部分组成：

一个长度为 m 的位数组；
k 个彼此独立或近似独立的哈希函数。

添加元素时：

使用多个哈希函数计算多个哈希值；
将每个哈希值映射到位数组范围内；
把对应位置设置为 1。

text

offset = floorMod(hash(element, seed), size)

查询元素时，再次计算相同的多个位置：

只要有一个位置为 0，该元素就一定不存在；
如果所有位置均为 1，该元素就可能存在。

布隆过滤器可能产生假阳性（false positive），但不会产生假阴性，前提是元素只添加、不删除且实现正确。

为什么使用布隆过滤器

与 Set 相比，布隆过滤器不保存完整元素，因此内存占用更低，适合在正式访问数据库或下游服务之前快速过滤大量无效请求，例如：

防止缓存穿透；
判断用户名、URL 或内容 ID 是否可能存在；
大规模数据去重前置检查。

不过，布隆过滤器不能返回元素本身，也不能提供精确的元素数量。

使用 Redis Bitmap 实现

下面是一个便于理解的简化实现。哈希函数必须基于传入的 element 计算，并且同一个元素在不同时间必须得到相同结果。

java

import java.nio.charset.StandardCharsets;

import org.springframework.data.redis.core.StringRedisTemplate;

public class RedisBloomFilter {

    private final StringRedisTemplate redisTemplate;
    private final String filterKey;
    private final long size;
    private final int hashFunctionCount;

    public RedisBloomFilter(
            StringRedisTemplate redisTemplate,
            String filterKey,
            long size,
            int hashFunctionCount) {
        this.redisTemplate = redisTemplate;
        this.filterKey = filterKey;
        this.size = size;
        this.hashFunctionCount = hashFunctionCount;
    }

    public void add(String element) {
        for (int seed = 0; seed < hashFunctionCount; seed++) {
            redisTemplate.opsForValue()
                    .setBit(filterKey, offset(element, seed), true);
        }
    }

    public boolean mightContain(String element) {
        for (int seed = 0; seed < hashFunctionCount; seed++) {
            Boolean bit = redisTemplate.opsForValue()
                    .getBit(filterKey, offset(element, seed));

            if (!Boolean.TRUE.equals(bit)) {
                return false;
            }
        }
        return true;
    }

    private long offset(String element, int seed) {
        byte[] bytes = element.getBytes(StandardCharsets.UTF_8);
        long hash = 0xcbf29ce484222325L ^ seed;

        for (byte value : bytes) {
            hash ^= value & 0xff;
            hash *= 0x100000001b3L;
        }

        return Math.floorMod(hash, size);
    }
}

调用示例：

java

RedisBloomFilter filter = new RedisBloomFilter(
        redisTemplate,
        "bloom:example",
        1_000_000,
        7
);

filter.add("element1");
filter.add("element2");

System.out.println(filter.mightContain("element1")); // 可能为 true
System.out.println(filter.mightContain("element3")); // false 或假阳性的 true

这段代码主要用于解释原理。生产环境更适合使用经过验证的库或 RedisBloom 模块，并使用 pipeline/Lua 减少多次网络往返。

容量和误判率

布隆过滤器有三个关键参数：

n：预计插入的元素数量；
m：位数组长度；
k：哈希函数数量。

近似误判率为：

text

p ≈ (1 - e^(-kn/m))^k

在元素数量不变的情况下：

位数组越大，冲突通常越少；
哈希函数过少会增加冲突；
哈希函数过多也会让位数组过快填满，并增加计算成本。

给定 n 和目标误判率 p，可以近似计算：

text

m = -n × ln(p) / (ln 2)^2
k = (m / n) × ln 2

因此，不能只根据某一次哈希碰撞实验直接推导布隆过滤器的误判率；应结合容量、哈希函数数量和目标误判率进行设计。

MurmurHash 示例

如果项目中使用 MurmurHash，可以引入对应依赖：

xml

<dependency>
    <groupId>com.sangupta</groupId>
    <artifactId>murmur</artifactId>
    <version>1.0.0</version>
</dependency>

使用示例：

java

String value = UUID.randomUUID().toString();
byte[] bytes = value.getBytes(StandardCharsets.UTF_8);

long hash32 = Murmur3.hash_x86_32(bytes, bytes.length, 0);
long[] hash128 = Murmur3.hash_x64_128(bytes, bytes.length, 0);

x86_32 和 x64_128 指算法变体，并不简单等同于“只能在 32 位机器或 64 位机器上运行”。在 Java 中，两者都可以正常调用，应按散列质量、输出长度和性能需求选择。

Comments (0)

Loading comments...