如何使用 Redis 快速实现布隆过滤器？

【核心定义】
布隆过滤器是一种基于位数组和多个哈希函数的概率型数据结构，用于快速判断一个元素是否“可能存在”于集合中（可能存在误判）或“一定不存在”于集合中（零误判）。

【关键要点】

数据结构：Redis 中通过 BIT 位数组实现，结合多个哈希函数将元素映射到位数组的不同位置。
核心算法：
- 添加元素：对元素进行 k 次哈希，将位数组中对应位置设为 1。
- 查询元素：对元素进行 k 次哈希，若所有对应位均为 1，则判断为“可能存在”；若任一位为 0，则“一定不存在”。
扩容/保护机制：布隆过滤器本身不支持动态扩容，需在初始化时根据预期数据量（n）和可接受误判率（p）计算位数组大小（m）和哈希函数个数（k）。
线程安全：Redis 单线程模型保证原子性操作，多客户端并发时通过 SETBIT 和 GETBIT 命令实现安全访问。
版本差异：
- Redis 4.0 前需通过 SETBIT 和自定义哈希函数手动实现。
- Redis 4.0+ 提供 BF.RESERVE、BF.ADD、BF.EXISTS 等命令，内置布隆过滤器模块（需加载 RedisBloom）。

【深度推导/细节】

误判率推导：
- 设位数组大小为 m，哈希函数个数为 k，插入 n 个元素后，某一位仍为 0 的概率为：
  [ (1 - \frac{1}{m})^{kn} \approx e^{-kn/m} ]
- 误判率 p 近似为：
  [ p \approx (1 - e^{-kn/m})^k ]
- 最优 k 和 m 的计算公式（给定 n 和 p）：
  [ m = -\frac{n \ln p}{(\ln 2)^2}, \quad k = \frac{m}{n} \ln 2 ]
临界点设计：
- 位数组越大，误判率越低，但内存占用越高。
- 哈希函数过多（k 过大）会导致位数组快速饱和，增加误判；过少则冲突增高。通常 k 取 3-10。
不支持删除：因多个元素可能共享同一位，直接置 0 会导致其他元素误判。变体 Counting Bloom Filter 用计数器支持删除，但 Redis 标准布隆过滤器不支持。

【关联/对比】

与 HashSet 对比：
- 布隆过滤器内存占用固定且极小（如 1亿元素仅需约 114MB，误判率 1%），HashSet 存储全量数据，内存随数据线性增长。
- 布隆过滤器有误判，HashSet 无误判。
与 HyperLogLog 对比：
- HyperLogLog 用于基数估计（去重计数），布隆过滤器用于存在性判断。
Redis 与 Guava BloomFilter：
- Guava 在 JVM 内存中实现，性能更高；Redis 为分布式服务，数据共享但需网络开销。

『面试官追问』

【实现步骤（Redis 4.0+）】
Step 1: 加载 RedisBloom 模块启动 Redis。
Step 2: 初始化布隆过滤器（指定容量和误判率）：

BF.RESERVE myfilter 0.01 1000000

Step 3: 添加元素：

BF.ADD myfilter "user123"

Step 4: 判断元素是否存在：

BF.EXISTS myfilter "user123"  # 返回 1（可能存在）或 0（一定不存在）

Step 5: 批量操作（BF.MADD、BF.MEXISTS）提升吞吐量。

# 如何使用 Redis 快速实现布隆过滤器？