# 华丽的数据结构之Bloom Filter

- URL: https://www.yidoo.xyz/bloom-filter
- 作者: 核动力蜗牛
- 发布时间: 2013-11-02
- 更新时间: 2013-11-02
- 分类: 华丽的数据结构

# Bloom Filter 简介

Bloom Filter（中文译作：布隆过滤器）是 1970 年由 Bloom 提出的。它实际上是由一个很长的二进制位数组和一系列 Hash 函数组成。

Bloom Filter 是一种空间效率很高的随机数据结构，它利用位数组很简洁地表示一个集合，并能判断一个元素是否属于这个集合。Bloom Filter 的这种高效是有一定代价的：在判断一个元素是否属于某个集合时，有可能会把不属于这个集合的元素误认为属于这个集合（false positive）。因此，Bloom Filter 不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下，Bloom Filter 通过极少的错误换取了存储空间的极大节省。

# Bloom Filter 算法

创建一个 m 位 BitSet，先将所有位初始化为 0，然后选择 k 个独立的哈希函数。第 i 个哈希函数对字符串 str 哈希的结果记为 hash,,i,,(str)，且 i 的范围是 0 到 m-1 。有关 Bloom Filter 的操作的过程可以参考<http://billmill.org/bloomfilter-tutorial/>

## 添加字符串

对于字符串 str，分别计算 hash,,1,,(str)，hash,,2,,(str)…… hash,,k,,(str)。然后将 BitSet 的第 hash,,1,,(str)，hash,,2,,(str)…… hash,,k,,(str)位设为 1。就此，就完成了将字符串 str 映射到 BitSet 中的 k 个二进制位。

![image](https://www.yidoo.xyz/images/16d00c1fb5323ae8fecbce0313f01e2a.png)

## 查找字符串

下面是检索字符串 str 是否在 BitSet 中：

对于字符串 str，分别计算 hash,,1,,(str)，hash,,2,,(str)…… hash,,k,,(str)。然后检查 BitSet 的第 hash,,1,,(str)，hash,,2,,(str)…… hash,,k,,(str)位是否全为 1。

若一个字符串对应的 bit 位不全为 1，则可以肯定该字符串一定没有被 Bloom Filter 记录过。

但是若一个字符串对应的 Bit 全为 1，实际上是不能 100%的肯定该字符串被 Bloom Filter 记录过的。因为有可能该字符串的所有位都刚好是被其他字符串所对应，这种将该字符串划分错的情况，称为 false positive 。

## 删除字符串

在基本的 Bloom Filter 中，字符串加入了就被不能删除了，因为删除会影响到其他字符串。实在需要删除字符串的可以使用<a title="http://en.wikipedia.org/wiki/Bloom_filter#Counting_filters" href="http://en.wikipedia.org/wiki/Bloom_filter#Counting_filters">Counting Bloom Filter(CBF)</a>，这是一种基本 Bloom Filter 的改进，CBF 将基本 Bloom Filter 每一个 Bit 改为一个计数器，这样就可以实现删除字符串的功能了。

# Bloom Filter 参数选择

## hash 函数选择

hash 函数的选择对性能影响比较大，一个优秀的 hash 函数应该做到将字符串等概率的映射到各个 bit。与此同时，选择 k 个不同的 hash 比较繁琐，一种简单的策略就是采用同一个 hash 函数然后传入 k 不同的参数。下面列举的是一些软件框架中 BloomFilter 所使用的 hash 函数。

- Cassandra  使用的*Murmur hashes*
- Hadoop  默认使用 _Jenkins and Murmur hashes_
- python-bloomfilter  使用*cryptographic hashes*
- Plan9  使用*Mitzenmacher 2005*
- Sdroege Bloom filter  使用*fnv*
- Squid  使用*MD5*

## Bloom Filter 参数\*

哈希函数个数 k、位数组大小 m、加入的字符串数量 n 的关系可以参考<http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html>。该文献证明了对于给定的 m、n，当

![image](https://www.yidoo.xyz/images/5945a519f1f096a795dde542a87ffa3b.gif)

时出错的概率是最小的。

同时参考文献中也给出了 false positive 概率与 m、n 的关系。false postive 概率等于

![image](https://www.yidoo.xyz/images/11290a331249182f7915343465f38683.gif)

完整的参数关系推导请参考<http://pages.cs.wisc.edu/~cao/papers/summary-cache/node8.html>

# Bloom Filter vs HashMap

Bloom Filter 跟 HashMap 不同之处在于：Bloom Filter 使用了 k 个哈希函数，每个字符串跟 k 个 bit 对应，从而降低了冲突的概率。

# Bloom Filter 代码实现

GitHub: <https://github.com/zhenlohuang/BloomFilter">https://github.com/zhenlohuang/BloomFilter>

# 参考资料

布隆过滤器: <http://zh.wikipedia.org/wiki/%E5%B8%83%E9%9A%86%E8%BF%87%E6%BB%A4%E5%99%A8">

BloomFilter——大规模数据处理利器: <http://www.cnblogs.com/heaad/archive/2011/01/02/1924195.html>

Bloom Filter 概念和原理: <http://blog.csdn.net/jiaomeng/article/details/1495500>