Bloom Filter 布隆过滤器

2024-03-31 09:25:36

Bloom Filter 是由伯顿.布隆（Burton Bloom）在1970年提出的一种多hash函数映射的快速查找算法。它实际上是一个很长的二进制向量和一些列随机映射函数.应用在数据量很大的情况下。

算法

初始化一个m比特的值全为0的向量。选择k个不同的散列函数，散列函数的产生的值域范围是0~m-1.

1）元素加入过滤器

对于元素e1,通过k个散列函数分别产生了值为 h₁ ,h₂, ..., h_k ；

将二进制向量的第 h₁ ,h₂, ..., h_k位分别置为1；

2)查找元素

将元素通过k个散列函数分别产生值为h₁ ,h₂, ..., h_k ；

查找二进制向量的第 h₁ ,h₂, ..., h_k位_，检查这些位是否都为1，如果都为1，那么该元素有可能存在，如果不全是1，那么元素一定不存在。

上面提到如果二进制向量的第h₁ ,h₂, ..., h_k位都为1，那么元素有可能存在，是因为产生散列值时有可能发生散列碰撞。这种将不再集合中的元素错判为存在集合中的情况称为fals positive.

3)删除元素

元素加入二进制向量就不方便删除了，因为多个元素的某一个散列值有可能一样，删除的话，会影响其他元素的判断。这里可以对二进制向量的位置采用计数的方式，如要删除，将计数减1即可。

最新文章

热门文章