布隆过滤器

布隆过滤器是一种基于 Hash 高效查找结构，能够快速（常数时间内）回答“某个元素是否在一个集合内”的问题。布隆过滤器因为其高效性大量应用于网络和安全领域，例如信息检索（ BigTable HBase ）、垃圾邮件规则、注册管理等。

1. 基于 Hash 的快速查找

在布隆过滤器之前，先来看基于 Hash 的快速查找算法。Hash 可以将任意内容映射到一个固定长度的字符串，而且不同内容映射到相同串的概率很低。因此，这就构成了一个很好的“内容→索引”的生成关系。

试想，如果给定一个内容和存储数组，通过构造 Hash 函数，让映射后的 Hash 值总数不超过数组的大小，则可以实现快速的基于内容的查找。例如，内容“hello world”的 Hash 如果是“100”，则存放到数组的第 100 个单元上去。如果需要快速查找任意内容，如“ hello world”，字符串是否在存储系统中，只需要将其在常数时间内计算 Hash 值，并用 Hash 值查看系统中对应元素即可。该系统“完美地”实现了常数时间内的查找。

然而，令人遗憾的是，当映射后的值限制在一定范围（如总数组的大小）内时，会发现 Hash 冲突的概率会变高，而且范围越小，冲突概率越大。很多时候，存储系统的大小又不能无限扩展，这就造成算法效率的下降。为了提高空间利用率，后来人们基于 Hash 算法的思想设计出了布隆过滤器结构。

2. 更高效的布隆过滤器

布隆过滤器采用了多个 Hash 函数来提高空间利用率。对同一个给定输入来说，多个 Hash 函数计算出多个地址，分别在位串的这些地址上标记为1。进行查找时，进行同样的计算过程，并查看对应元素，如果都为1，则说明较大概率是存在该输入。如下图：

布隆过滤器相对单个 Hash 算法查找，大大提高了空间利用率，可以使用较少的空间来表示较大集合的存在关系。

实际上，无论是 Has 算法，还是布隆过滤器，基本思想是一致的，都是基于内容的编址 Hash 函数存在冲突，布隆过滤器也存在冲突。这就造成了两种方法都存在着误报（false positive）的情况，但绝对不会漏报（ false negative）。

布隆过滤器在应用中误报率往往很低，例如，在使用7个不同Hash函数的情况下，记录100 万个数据， 采用2MB 大小的位串，整体的误判率将低于1% 。而传统的 Hash 查找算法的误报率将接近 10%。