布隆过滤器（Bloom Filter）初探

傷城~ 2023-07-21 13:28 55阅读 0赞

### 布隆过滤器介绍 ###

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

产生的契机

回想一下，我们平常在检测集合中是否存在某元素时，都会采用比较的方法。考虑以下情况：

*  如果集合用线性表存储，查找的时间复杂度为O(n)。
 *  如果用平衡BST（如AVL树、红黑树）存储，时间复杂度为O(logn)。
 *  如果用哈希表存储，并用链地址法与平衡BST解决哈希冲突（参考JDK8的HashMap实现方法），时间复杂度也要有O\[log(n/m)\]，m为哈希分桶数。
    
    ![format_png][]

总而言之，当集合中元素的数量极多时，不仅查找会变得很慢，而且占用的空间也会大到无法想象。BF就是解决这个矛盾的利器。

### 设计思想 ###

BF是由一个**长度为m比特的位数组（bit array）**与**k个哈希函数（hash function）**组成的数据结构。位数组均初始化为0，所有哈希函数都可以分别把输入数据尽量均匀地散列。

当要**插入**一个元素时，将其数据分别输入k个哈希函数，产生k个哈希值。以哈希值作为位数组中的下标，将所有k个对应的比特置为1。

当要**查询**（即判断是否存在）一个元素时，同样将其数据输入哈希函数，然后检查对应的k个比特。如果有任意一个比特为0，表明该元素一定不在集合中。如果所有比特均为1，表明该集合有（较大的）可能性在集合中。为什么不是一定在集合中呢？因为一个比特被置为1有可能会受到其他元素的影响，这就是所谓“假阳性”（false positive）。相对地，“假阴性”（false negative）在BF中是绝不会出现的。

下图示出一个m=18, k=3的BF示例。集合中的x、y、z三个元素通过3个不同的哈希函数散列到位数组中。当查询元素w时，因为有一个比特为0，因此w不在该集合中。

![format_png 1][]

优缺点与用途

BF的优点是显而易见的：

*  不需要存储数据本身，只用比特表示，因此空间占用相对于传统方式有巨大的优势，并且能够保密数据；
 *  时间效率也较高，插入和查询的时间复杂度均为O(k)；
 *  哈希函数之间相互独立，可以在硬件指令层面并行计算。

但是，它的缺点也同样明显：

*  存在假阳性的概率，不适用于任何要求100%准确率的情境；
 *  只能插入和查询元素，不能删除元素，这与产生假阳性的原因是相同的。我们可以简单地想到通过计数（即将一个比特扩展为计数值）来记录元素数，但仍然无法保证删除的元素一定在集合中。

所以，BF在对查准度要求没有那么苛刻，而对时间、空间效率要求较高的场合非常合适，本文第一句话提到的用途即属于此类。另外，由于它不存在假阴性问题，所以用作“不存在”逻辑的处理时有奇效，比如可以用来作为缓存系统（如Redis）的缓冲，防止缓存穿透。

### *假阳性率的计算 \** ###

假阳性是BF最大的痛点，因此有必要权衡，比如计算一下假阳性的概率。为了简单一点，就假设我们的哈希函数选择位数组中的比特时，都是等概率的。当然在设计哈希函数时，也应该尽量满足均匀分布。

在位数组长度m的BF中插入一个元素，它的其中一个哈希函数会将某个特定的比特置为1。因此，在插入元素后，该比特仍然为0的概率是：

![format_png 2][]

现有k个哈希函数，并插入n个元素，自然就可以得到该比特仍然为0的概率是：

![format_png 3][]

反过来讲，它已经被置为1的概率就是：

![format_png 4][]

也就是说，如果在插入n个元素后，我们用一个不在集合中的元素来检测，那么被误报为存在于集合中的概率（也就是所有哈希函数对应的比特都为1的概率）为：

![format_png 5][]

当n比较大时，根据重要极限公式，可以近似得出假阳性率：

![format_png 6][]

所以，在哈希函数的个数k一定的情况下：

*  位数组长度m越大，假阳性率越低；
 *  已插入元素的个数n越大，假阳性率越高。

转载链接：https://www.jianshu.com/p/bef2ec1c361f

[format_png]: /images/20230528/af43fc656b534103bd3802238388634c.png
[format_png 1]: /images/20230528/ef6d5c7618aa4070a01858f3dec80548.png
[format_png 2]: /images/20230528/38ae64610c01458e9ef225d5173d01e2.png
[format_png 3]: /images/20230528/1f15ca7ccd4d415b9c24094305daa811.png
[format_png 4]: /images/20230528/6c8a3e3325d2442e90700b69f6329bab.png
[format_png 5]: /images/20230528/277aef62c34b4241803b8f5d3b701264.png
[format_png 6]: /images/20230528/a24b7c057eec4f98bad320c35a692d24.png