简介

Bloom 过滤器是一种概率性数据结构，用于以较大的把握判断某一个元素是否在集合中。若 Bloom 过滤器认为某一个元素在集合中，则此元素小概率不在集合中，即可能存在假阳性；若 Bloom 过滤认为某一个元素不在集合中，则此元素一定不在集合中，即不存在假阴性。常见的应用场景有：判断用户名是否被占用、判断银行卡是否已挂失、判断用户是否看过广告等等。相比于确定性的数据结构，Bloom 过滤器占用更小的存储空间。

前置说明

• 某时刻下元素个数为 $n$。
• 底层数据结构是一个大小为 $m$ 的比特数组。
• 包含 $k$ 个相互独立的散列函数，可将元素映射到某个数组位置。

操作与算法

初始化

1. 确定 $m$ 的大小。
2. 将数组所有位置置为 0。

时间复杂度：$O(m)$。

添加元素

1. 依次用 $k$ 个散列函数映射元素到 $k$ 个数组位置。
2. 将这些数组位置置为 1。

时间复杂度：$O(k)$。

判断元素是否在集合中

1. 依次用 $k$ 个散列函数映射元素到 $k$ 个数组位置。
2. 这些数组位置是否存在值为 0：
   • 若是，则元素一定不在集合中。
   • 若否，则元素有可能在集合中。

时间复杂度：$O(k)$。

局限性

• 添加后的元素无法从模糊集合中移除。
• $m$ 较小或 $k$ 设置不当的情况下，会导致假阳性概率较大。
  • 假阳性概率：$p_{fp}=(1-\exp(-\frac{kn}{m}))^k$。
  • 最优设置：$k\approx 0.7\frac{m}{n}\log{2}$。

拓展阅读

• https://brilliant.org/wiki/bloom-filter
• https://arxiv.org/abs/2106.12189