首页分享布鲁姆过滤器

布鲁姆过滤器

来源：花匠小妙招时间：2024-12-16 13:59

布隆过滤器是一种数据结构，快速和节省内存，能用于判定一个元素是否存在于一个集合中。
这种效率的代价是Bloom filter是一种概率数据结构，元素不是绝对的在组里或可能在组里。

Bloom filter的基本数据结构是一个位向量。

图1：布鲁姆过滤器散列图

如图1：布鲁姆过滤器，由一个长度为m（=18）的数组（初始值都为0）和k（=3）个hash 函数组成，图中的元素x,y,z，判断为“可能”存在于集合中；而元素w一定不在集合中。由于元素x，y，z通过k个hash函数计算后，发现对应的桶中的元素都是1。而w计算后在15号桶为0。

添加元素：将一个元素添加到Bloom Filter中，只需要计算k个hash函数，并将散列的位置都置为1。（因此多个元素，散列到同一个桶中是有可能的）

删除元素：对于simple BF由于多个元素，散列到同一个桶中是有可能的，一个桶值为1不代表这个桶只表示某单个元素的散列信息，可能有其他的元素也散列到这个桶。因此，无法进行删除操作。（增加一个BF存储删除的元素，完成删除操作）

假阳性率：当m和k足够大，或者选取的hash函数足够好的时候，一个元素如果不在集合中，通过hash计算时，得到的值很可能为0（冲突变小），假阳性率越低。当假阳性率太高，会导致很多无效的读取磁盘操作，会很浪费时间。因此，当假阳性率太高时，需要重构BF。

时间和空间分析：添加，删除，查找都为O(k)。对于m长的BF，有n个元素，k个hash函数。当k值取最优时，对于1%假阳性，每个元素只需要消耗9.6bits。每个元素增加4.8bits可以完全解决1%假阳性问题。