原理
- 利用了hash函数的特性：若经过同一函数的hash值不同，则该hash函数的输入也不同
- hash碰撞：若经同一hash函数计算两个hash值相同，则两个输入值可能相同，也可能不同，若不同则为碰撞
数据结构
BloomFilter 是由一个固定大小的二进制向量或者位图（bitmap）和一系列映射函数组成的
初始状态时，对于长度为m的位数组，所有位均被置0
当有变量被加入集合时，通过K个映射函数将该变量映射到数组中的K个位，并将对应的位置1
下图表示两个变量和三个映射函数的情况
查询某个变量是否存在时，只需要查看其对应位上的值是否全为1，若其中一个位为0，则被查询的值一定不存在，若所有位均为1，则变量很可能存在
- 为什么是很可能存在：hash函数本身存在碰撞
误判率
- 误判指的是多个输入经过哈希之后在相同的bit位置1了，这样就无法判断究竟是哪个输入产生的，因此误判的根源在于相同的 bit 位被多次映射且置 1
由于布隆过滤器所有的位并不是独占的，很可能很多元素均共享了数组中的某一位，若直接对该为进行删除，很可能影响其他的元素（如上图中的第三位）
特性
- 一个元素如果判断结果为存在的时候元素不一定存在，但是判断结果为不存在的时候则一定不存在
- 布隆过滤器可以添加元素，但是不能删除元素，因为删掉元素会导致误判率增加
添加和查询元素步骤
- 添加元素
- 将要添加的元素给 k 个哈希函数
- 得到对应于位数组上的 k 个位置
- 将这k个位置设为 1
- 查询元素
- 将要查询的元素给k个哈希函数
- 得到对应于位数组上的k个位置
- 如果k个位置有一个为 0，则肯定不在集合中
- 如果k个位置全部为 1，则可能在集合中
优缺点
- 优点：
布隆过滤器存储空间和插入/查询时间都是常数O(K)
另外，散列函数相互之间没有关系，方便由硬件并行实现
布隆过滤器不需要存储元素本身，在某些对保密要求非常严格的场合有优势
布隆过滤器可以表示全集，其它任何数据结构都不能
- 缺点：
存在误判率，误判率随元素的增加而提高
若元素足够少，可以直接使用散列表，无需布隆过滤器
一般情况下不能从布隆过滤器中删除元素（确保安全删除元素非常难，需要确保元素绝对在内，这个条件布隆过滤器无法做到）
场景与应用实例
- 数据库防止穿库：Google Bigtable，HBase 和 Cassandra 以及 Postgresql 使用BloomFilter来减少不存在的行或列的磁盘查找，避免代价高昂的磁盘查找会大大提高数据库查询操作的性能
- 业务场景中判断用户是否阅读过某视频或文章，比如抖音或头条，当然会导致一定的误判，但不会让用户看到重复的内容
- 缓存宕机、缓存击穿场景，一般判断用户是否在缓存中，如果在则直接返回结果，不在则查询db，如果来一波冷数据，会导致缓存大量击穿，造成雪崩效应，这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则穿透到db。如果不在布隆器中，则直接返回
- WEB拦截器，如果相同请求则拦截，防止重复被攻击。用户第一次请求，将请求参数放入布隆过滤器中，当第二次请求时，先判断请求参数是否被布隆过滤器命中。可以提高缓存命中率，Squid 网页代理缓存服务器在 cache digests 中就使用了布隆过滤器。Google Chrome浏览器使用了布隆过滤器加速安全浏览服务
- Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据
- SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间