布隆过滤器

布隆过滤器（Bloom Filter，下文简称BF）

由Burton Howard Bloom在1970年提出，是一种空间效率高的概率型数据结构。它专门用来检测集合中是否存在特定的元素。听起来是很稀松平常的需求，为什么要使用BF这种数据结构呢？

做过一个互联网商城的秒杀项目，有一个问题，就是如果用户恶意请求数据库里，缓存中不存在的数据，也就是产生所谓的缓存穿透，这时候，BF就是一个很好的选择

它的原理如下：
首先，BF是一个bit数组，当一个数值要映射到BF的时候，先通过多个hash函数，计算出多个hash值，再对数组长度取余，就能算出对应的数组位置，然后将相应bit数组位置1，当再存入数值也是如此，那么如果有数据映射的时候发现对应的bit位不为1，那么就认为这个数据不存在，但是同时也会带来一些问题，当增加的数据越来越多，会有更多的bit位被置为1，那么意味着，一些不存在的数值来判断，也会认为数据存在。

当然会存在命中率的问题，取决于hash函数的个数和BF的长度
BF太短，那么查询任何值都会返回“可能存在”，起不到过滤的目的，太长的话，又会带来太多的内存占用。
Hash函数个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。
有这样一张图反应了hash个数与BF长度对效率的影响：

总结：
BF认为不存在，一定不存在。
BF认为存在，有可能存在。