当前位置：首页 > backend >正文

布隆过滤器（Bloom Filter）简介

backend 2025/5/7 10:45:37

布隆过滤器是一种空间效率高、概率型的数据结构，用于快速判断一个元素是否可能存在于集合中。它的特点是：

优点：占用内存极少，查询效率高（O(k)，k为哈希函数数量）。
缺点：有一定的误判率（False Positive，可能误报存在），且不支持删除元素。

核心应用场景

缓存穿透防护：快速过滤掉不存在的数据请求，避免直接查询数据库。
爬虫URL去重：判断URL是否已爬取过。
垃圾邮件过滤：判断邮件是否在黑名单中。

布隆过滤器的实现步骤

以下是手动实现布隆过滤器的关键步骤（以Java为例）：

1. 初始化布隆过滤器

定义一个位数组（Bit Array），初始所有位为0。
选择多个哈希函数（如MurmurHash、SHA-1），确保均匀分布。

import java.util.BitSet;
import java.util.function.ToIntFunction;public class BloomFilter {private final BitSet bitSet;private final int size;private final ToIntFunction<String>[] hashFunctions;public BloomFilter(int size, ToIntFunction<String>... hashFunctions) {this.bitSet = new BitSet(size);this.size = size;this.hashFunctions = hashFunctions;}
}

2. 添加元素

对元素执行所有哈希函数，将对应的位数组位置设为1。

public void add(String element) {for (ToIntFunction<String> hashFunction : hashFunctions) {int hash = Math.abs(hashFunction.applyAsInt(element)) % size;bitSet.set(hash);}
}

3. 判断元素是否存在

对元素执行所有哈希函数，检查对应位是否均为1。
- 若有一位为0：元素一定不存在。
- 若全部为1：元素可能存在（可能有误判）。

public boolean mightContain(String element) {for (ToIntFunction<String> hashFunction : hashFunctions) {int hash = Math.abs(hashFunction.applyAsInt(element)) % size;if (!bitSet.get(hash)) {return false; // 一定不存在}}return true; // 可能存在（可能有误判）
}

4. 选择哈希函数和位数组大小

哈希函数数量（k）：通常取 k = (m/n) * ln(2)，其中 m 是位数组大小，n 是预期元素数量。
位数组大小（m）：越大误判率越低，但占用内存越多。公式：
m = - (n * ln(p)) / (ln(2)^2)
（p 为可接受的误判率，如0.01）

示例：用布隆过滤器解决缓存穿透

// 初始化布隆过滤器（假设预期存储10000个元素，误判率1%）
BloomFilter bloomFilter = new BloomFilter(95850,  // m ≈ -10000 * ln(0.01) / (ln(2)^2)str -> str.hashCode(),str -> MurmurHash.hash32(str)
);// 预热数据：将所有存在的键加入布隆过滤器
database.getAllKeys().forEach(bloomFilter::add);// 查询前先检查布隆过滤器
public Employee getEmployee(int id) {String key = "emp_" + id;if (!bloomFilter.mightContain(key)) {return null; // 直接返回，避免查询数据库}return cache.get(key, () -> database.query(id));
}