Bloom Filter

一个经典的问题：
有1000瓶药物，但是其中有一瓶是有毒的，小白鼠吃了一个星期以后就会死掉，请问，在一个星期内找出有毒的药物，最少需要多少只小白鼠？
如果一个人考虑问题是二进制的考虑方法，那么肯定好不犹豫的会说10只，为什么呢？因为小白鼠能够有两种状态，1代表生，0代表死，那么10只能表示2的10次方种状态，那么也就是说能表示1024种状态，那么答案也就是10只。关于小白鼠如何吃药，读者可以仔细去想想

bloom filter实际上也是一个m位的2进制，通过hash的算法来进行映射，从而判断是否存在的一种方法。

bloom filter能够节省大量的存储空间，这个存储空间是靠牺牲准确性获得的，它有可能将一个不存在其中的值判断为在其中，所以如果工程上需要零错误时并不使用这种方法。


http://blog.csdn.net/jiaomeng/article/details/1495500