一文了解布隆过滤器(Bloom Filter)：原理、优缺点及使用场景

布隆过滤器（Bloom filter）是1970年由布隆提出的，是一个很长的二进制向量和一系列随机映射函数。布隆过滤器本质上是一种数据结构，比较巧妙的概率型数据结构，特点是高效地插入和查询，可以用来告诉你 “某样东西一定不存在或者可能存在”。

为什么需要布隆过滤器

在软件设计时，我们经常要判断一个元素是否在一个集合中。一个直接的方法是，将集合中的所有元素都存储在计算机中（如保存在链表、树、哈希表等数据结构）。

当要判断一个新元素的时候，直接跟集合中的已存储元素对比即可判断元素是否在集合中。

但是，当随着加入的数据量增加，我们需要存储元素的空间就越来越大，而且检索速度也会开始变慢。

为了解决这个问题，就引入了布隆过滤器。

布隆过滤器的原理

布隆过滤器是一个基于m位的比特向量B（b1,b2…,bm），这些比特向量的初始值为0。同时还有一系列的哈希函数（h1,h2…,hk），这些哈希函数运算后的哈希值范围在[1, m]内。

如下图，就是x、y、z三个元素插入到布隆过滤器中，并判断w值是否在集合中的示意图。

布隆过滤器原理

如图，布隆过滤器由m=18位向量，k=3个哈希函数组成。h1、h2和h3是三个哈希函数将输入值分别映射成比特向量上的某个位置上。

假设输入的数据集合X={x, y, z}，插入x值（对应红线），则将经过h1、h2和h3三个哈希函数映射到的比特向量上的值改为1。同理，y（对应绿线）和z（对应蓝线）值也一样操作。

X集合中元素分别经过三个哈希函数运算后映射为h1(x)=2，h2(x)=6，h3(x)=14，即H（x）=（2，6，14）。同理得，H（y）=（5，17，12），H（z）=（4，6，12）。

如果要查找x、y、z，通过布隆过滤器可以找到对应的比特向量都为1，我们只能确定x、y、z可能在集合中。

由此可以发现，x和z在h2哈希函数映射后映射到的是同一个比特向量位置（第6个），同时y和z在经过h3映射后也是同一个比特向量位置（第12个）。

也就是说，当我们通过布隆过滤器判断一个元素是否在集合中时，即使对应的比特向量位置全为1，也可能是其他元素映射后导致的。

如果要查找w值，经过哈希映射后，可以发现有一个比特向量上的值不为1，那就可以判断，w值一定不在集合中。

比如，查询数据 H（y0）=（1，6，14）和 H（y1）=（2，6，17），可以发现 H（y0）对应的第一个位置为0，因此y0肯定不在集合X中；而 y1 对应的第2，6，17位置均为1，因此y1可能在（而实际不在）集合X中。这种情况称为假阳性五保（False Positive）。

显然，随着输入集合X的增大，各位置上为1的概率增大，布隆过滤器将因为逐渐被“填满”而提高假阳性误报率。可从理论上证明，当比特向量B的半数空间被填满时，布隆过滤器的假阳性误报率将达到最低值。

布隆过滤器的优缺点

优点

相比于其它的数据结构，布隆过滤器在空间和时间方面都有巨大的优势。

空间效率

布隆过滤器在空间效率方面表现出色，与其他数据结构相比，它只需要一小部分内存，这在内存有限的环境中至关重要。

隐私增强

能混淆准确数据，有助于增强用户隐私，这是隐私是首要关注的区块链环境中的基石。

速度

能快速查询会员，显著提高了数据检索速度，这对于维持数字系统的高性能水平至关重要。

缺点

布隆过滤器的缺点和优点一样明显。

误算率（False Positive）

随着存入的元素数量增加，误算率随之增加。但是如果元素数量太少，则使用散列表足矣。

不能删除元素

一般情况下，不能从布隆过滤器中删除元素。

我们很容易想到把位列阵变成整数数组，每插入一个元素相应的计数器加1，这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。

首先，必须保证删除的元素的确在布隆过滤器里面.这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

布隆过滤器在区块链中的应用

布隆过滤器在区块链生态系统中发挥着重要作用，特别是对于轻型或 SPV（简单支付验证）客户端而言。

在比特币网络中的应用

在比特币网络中，轻客户端查找自己账户地址相关的UTXO时，由于轻客户端没有完整的区块数据，无法直接查找，需要向全节点发送相关请求，全节点返回结果。

如果轻客户端向全节点直接发送自己的地址获取UTXO，则其他全节点都知道该轻客户端绑定的账户地址，泄露了隐私。

轻客户端通过以布隆过滤器的形式告诉全节点自己的地址信息，全节点返回结果可能相关的UTXO，通过布隆过滤器过滤不属于改地址的UTXO，既保护了隐私，又节省了带宽。

在以太坊中的应用

在以太坊中，发送一个交易来调用智能合约时，调用的返回值只有交易的哈希，当一个交易被打包，智能合约通过事件产生日志发送到区块链上以便用户界面处理。

以太坊中的事件有三个功能：返回智能合约执行过程的值到用户界面；触发前端用户界面事件，异步通信；便宜的存储。

以太坊中用特殊的可索引的数据结构来存储日志，这种数据结构为布隆过滤器，合约创建之后无法访问日志数据，以太坊的每个区块头包含当前前区块中所有的收据的日志的布隆过滤器。

这样可以从链外高效访问日志数据，高效安全下载和搜搜日志，减少了私盘随机访问量，用户可以通过调用对交易或者区块进行过滤，然后持续的获取结果。