布隆过滤器

工作原理

布隆过滤器由一个位数组和多个哈希函数组成。插入元素时，将元素经过 k 个哈希函数，将 k 个位置的位设为 1。查询时，若全为 1 则可能存在（假阳性），若有 0 则一定不存在。

应用场景

数据库查询加速、网页爬虫去重、缓存穿透防护。Redis 4.0 起内置 Bloom Filter 模块。