一、什么是布隆过滤器？

一个用于标识数据的字节数组，通过将数据 hash 运算，将hash 值对应到数组中，进而通过数组元素的值判断数据是否存在。可以用来解决缓存穿透、白名单等问题。

缓存穿透的问题，使用普通的过滤器也能解决，可以将需要缓存的 key 存入缓存，然后通过对比 key 是否存在，来拦截或放过请求。但是如果把 key 完整的存到内存会占据较大的空间。

所以，在缓存穿透问题上，使用布隆过滤器不仅是为了拦截请求，也是为了节省空间，因为布隆过滤器只是个字节数组，通过 hash 来判断是否存在 key，省空间，但是相应的代价就是存在误判。

二、布隆算法

首先需要初始化一个字节数组，当需要标记一个数据时，会先经过若干次 hash 运算，返回一个值，这个值就代表数组的 index，就会将这个 index 的位置数组元素值修改为 1，用来标识这条数据已经存在；之后查找这条数据也是一样，将数据 hash 运算，得到对应的 hash 值，如果该值对应的数组元素值为 1，则判定为数据存在，否则判定为数据不存在。

hash 函数需要满足两个条件：
1.hash 值完在数组 index 范围内
2.需要达到足够的散列程度

由于 hash 算法会出现 hash 碰撞，也就是不同的数据经过 hash 运算可能会得到相同的值，这就会导致布隆算法的误判，而解决这个问题需要提升 hash 值的散列程度，办法有两种：
1.数组足够长
选择更多，重复性就会降低
2.增加 hash 运算次数
每次 hash 运算都返回一个 hash 值，同时将这几个 hash 值对应的数组元素标识为 1，也就是用多个 hash 值标识一条数据
hash 函数的个数并不是越多越好，应参考数组长度，避免 hash 函数产生的 hash 值过多，也会导致误报增加

缺点

删除数据困难，因为 hash 碰撞问题，导致难以精确定位。
解决办法是可以为每个数组元素对应的增加一个计数器。存数据时，将有数据 hash 运算之后对应的位置设置为 1，对应的计数器也设为 1，并且之后发生 hash 碰撞就在原来基础上加 1；反之，在删除时，hash 运算后的位置，每个计数器大于 1 的，就在原来基础上减 1，当计数器为 0 时，就将该字节数组元素设为 0.