布隆过滤器

作用：用来判断某个元素是否在一个集合中
优点：占用内存空间少，是使用哈希表的空间的1/8；
缺点：有一定的误判率(但不会漏判)；不可删除集合中的元素；
原理：使用M个bit的数组表示集合，将待查询的元素进行Md5摘要后生成128位串，然后分成K个字串，分别和1...k结合后，再传给hash函数生成不同的数，这些生成的数作为索引查找bit数组中的值，如果都是1，则代表元素存在于集合中；
空间占用分析：以1亿个8byte的集合为例
(1)使用Hash表作为集合，需要8*10^8*2 byte=1.6GB，乘以2，是因为Hash表的空间利用率超过50%后，查找的时间复杂度比较高（使用open addressing避免hash冲突的情况下：参考http://whitesock.iteye.com/blog/707708）
(2)使用布隆过滤，选k=8，当空间利用率为1/2时的误判率为万分之一，空间占用为8*10^8*2=200MB，为Hash表的1/8
参数调整：只要设置添加的元素数n和预期的误判率p，则可计算出bit数M和k