图文解析布隆过滤器大小的算法公式

来源：脚本之家时间：2022-04-05 14:47:53

1. 简介

客户端：这个key存在吗？

服务器：不存在/不知道

本质上，布隆过滤器是一种数据结构，是一种比较巧妙的概率型数据结构。它的特点是高效地插入和查询。但我们要检查一个key是否在某个结构中存在时，通过使用布隆过滤器，我们可以快速了解到「这个key一定不存在或者可能存在」。相比于传统的List、Set、Map这些数据结构，它更加高效、占用的空间也越少，但是它返回的结果是概率性的，是不确切的。

布隆过滤器仅用于测试集合中的成员资格。使用布隆过滤器的经典示例是减少对不存在的密钥的昂贵磁盘（或网络）查找。正如我们看到的那样，布隆过滤器可以在O（k）恒定时间内搜索密钥，其中k是哈希函数的数量，测试密钥的不存在将非常快。

2. 应用场景

2.1 缓存穿透

为了提高访问效率，我们会将一些数据放在Redis缓存中。当进行数据查询时，可以先从缓存中获取数据，无需读取数据库。这样可以有效地提升性能。
在数据查询时，首先要判断缓存中是否有数据，如果有数据，就直接从缓存中获取数据。
但如果没有数据，就需要从数据库中获取数据，然后放入缓存。如果大量访问都无法命中缓存，会造成数据库要扛较大压力，从而导致数据库崩溃。而使用布隆过滤器，当访问不存在的缓存时，可以迅速返回避免缓存或者DB crash。

2.2 判断某个数据是否在海量数据中存在

HBase中存储着非常海量数据，要判断某个ROWKEYS、或者某个列是否存在，使用布隆过滤器，可以快速获取某个数据是否存在。但有一定的误判率。但如果某个key不存在，一定是准确的。

3. HashMap的问题

要判断某个元素是否存在其实用HashMap效率是非常高的。HashMap通过把值映射为HashMap的Key，这种方式可以实现O(1)常数级时间复杂度。
但是，如果存储的数据量非常大的时候（例如：上亿的数据），HashMap将会耗费非常大的内存大小。而且也根本无法一次性将海量的数据读进内存。

4. 理解布隆过滤器

工作原理图：

布隆过滤器是一个bit数组或者称为一个bit二进制向量
这个数组中的元素存的要么是0、要么是1
k个hash函数都是彼此独立的，并将每个hash函数计算后的结果对数组的长度m取模，并将对一个的bit设置为1（蓝色单元格）
我们将每个key都按照这种方式设置单元格，就是「布隆过滤器」

5. 根据布隆过滤器查询元素

假设输入一个key，我们使用之前的k个hash函数求哈希，得到k个值
判断这k个值是否都为蓝色，如果有一个不是蓝色，那么这个key一定不存在
如果都有蓝色，那么key是可能存在（布隆过滤器会存在误判）
因为如果输入对象很多，而集合比较小的情况，会导致集合中大多位置都会被描蓝，那么检查某个key时候为蓝色时，刚好某个位置正好被设置为蓝色了，此时，会错误认为该key在集合中
示例：

6. 可以删除么

传统的布隆过滤器并不支持删除操作。但是名为 Counting Bloom filter 的变种可以用来测试元素计数个数是否绝对小于某个阈值，它支持元素删除。详细理解可以参考文章Counting Bloom Filter 的原理和实现，写的很详细。

7. 如何选择哈希函数个数和布隆过滤器长度

很显然，过小的布隆过滤器很快所有的 bit 位均为 1，那么查询任何值都会返回“可能存在”，起不到过滤的目的了。布隆过滤器的长度会直接影响误报率，布隆过滤器越长其误报率越小。

另外，哈希函数的个数也需要权衡，个数越多则布隆过滤器 bit 位置位 1 的速度越快，且布隆过滤器的效率越低；但是如果太少的话，那我们的误报率会变高。

从上图可以看出，增加哈希函数k的数量将大大降低错误率p。

好像是WTF？不用担心，实际上我们实际上需要确定我们的m和k。因此，如果我们自己设置容错值p和元素数n，则可以使用以下公式来计算这些参数：

我们可以根据过滤器的大小m，哈希函数的数量k和插入的元素的数量n来计算误报率p，公式如下：由上面，又怎么选择适合业务的 k 和 m 值呢？
公式：

k 为哈希函数个数，m 为布隆过滤器长度，n 为插入的元素个数，p 为误报率。
至于如何推导这个公式，我在知乎发布的文章有涉及，感兴趣可以看看，不感兴趣的话记住上面这个公式就行了。

我还要在这里提到另一个重要的观点。由于使用Bloom筛选器的唯一目的是搜索速度更快，所以我们不能使用慢速哈希函数，对吗？加密散列函数（例如Sha-1，MD5）对于bloom过滤器不是一个好选择，因为它们有点慢。因此，从更快的哈希函数实现中更好的选择是murmur，fnv系列哈希，Jenkins哈希和HashMix。

目录