布隆过滤器详解

背景介绍

布隆过滤器（Bloom Filter）是1970年由布隆提出的，它实际上是由一个很长的二进制向量和一系列随意映射函数组成。布隆过滤器使用场景一般是防止redis缓存穿透，使用布隆过滤器可以更好的节省空间，并且快速定位元素是否存在。

布隆过滤器通过 hash key 来定位 位图（Bitmap，其实就是bit数组）中对应的下标，并且在这个数组中每一个位置只有0和1两种状态，每个位置只占用1个字节，其中0表示没有元素存在，1表示有元素存在。

注意：两个不同的key哈希出来所对应的下标位可能存在部分重复，这样可以减少内存的占用，但也有概率会出现哈希碰撞，原本不存在的key哈希之后位图中都为1的情况。

所以通过上面的现象，我们从布隆过滤器的角度可以得出布隆过滤器主要有2大特点：

1、如果布隆过滤器判断一个元素存在，那么这个元素可能存在。

2、如果布隆过滤器判断一个元素不存在，那么这个元素一定不存在。

因为布隆过滤器中总是会存在误判率，因为哈希碰撞是不可能百分百避免的。布隆过滤器对这种误判率称之为假阳性概率，即：False Positive Probability，简称为fpp。

为避免fpp，我们可以加大位图长度或者多次哈希来减少冲突概率，但加大位图需要更多的内存空间，多次哈希又需要更多的cpu资源，需要做好对应的资源开销预算，选择合适的方式。

如何进行删除对应key ？

上面的布隆过滤器我们知道，判断一个元素存在就是判断对应下标位置是否为1来确定的，但是如果要删除掉一个元素是不能直接把1改成0的，因为这个位置可能存在其他元素，所以原始的布隆过滤器是无法支持删除操作的，如果需要支持删除，那我们应该怎么做呢？最简单的做法就是加一个计数器，就是说位数组的每个位如果不存在就是0，存在几个元素就存具体的数字，而不仅仅只是存1，那么这就有一个问题，本来存1就是一位就可以满足了，但是如果要存具体的数字比如说2，那就需要2位了，所以带有计数器的布隆过滤器会占用更大的空间。