关于 布隆过滤器（Bloom Filter）

简单点说，这是基于hash算法思想的一个拓展算法。

一般的hash实现都是用以存储数据的；但如果用于检查某个东西是否存在的场合，那么仅需存储一个占用标记（1个二进制位）即可，通用的实现就太浪费空间了——尤其是上亿甚至几十亿数据（如google的email黑名单）的情况。

但如果仅存储一个二进制位，又怎样识别碰撞？

一种办法是：做8个hash表，用8个不同的散列函数；选择得当的话，一个词在8种hash方案中都有碰撞的概率就极小了。




如果你完全理解了hash算法，那么下一步优化就是理所当然的了：

为了减小碰撞，除了选择好算法，我们还必须保证hash地址空间足够大；但为了减少内存占用，hash地址还不能太大。

怎么办？

布隆过滤器的思路是：用一个16倍大的地址空间；但让所有8个hash函数都映射到这个地址空间里面。

这样，对设计良好的hash函数来说，碰撞的概率几乎小到可以忽略不计；虽然同时多了8个散列函数相互影响的问题，但总碰撞会比8个不同hash函数在独立的2倍大小地址中的碰撞少得多。

于是，这个算法就不仅大幅度降低了时间、空间消耗，又保证了足够的准确率。



对于检查用户名有否重复这种应用来说，一方面数据量肯定要比垃圾邮件地址少得多；另一方面，即使发生了碰撞，也不过是导致极少几个用户名无法使用而已，完全不必理会。

综合起来，这个算法不过是8个无碰撞检测的散列和8次通过下标的数组访问而已；不考虑页错误，即使在pc机上跑，时间消耗也不会超过微秒级。



-----