BloomFilter&python支持

BloomFilter&python支持

布隆过滤器是一种概率空间高效的数据结构。它与hashmap非常相似，用于检索一个元素是否在一个集合中。

它在检索元素是否存在时，能很好地取舍空间使用率与误报比例。即Bloom Filter是会误判的，它只会把不存在于集合中的元素误判成存在于集合中，而不会把存在于集合中的元素误判成不存在集合中。

正是由于这个特性，它被称作概率性数据结构（probabilistic data structure）。

布隆过滤器维护一个N位的位数组，其中N是位数组的大小。它还有另一个参数k，表示使用哈希函数的个数。这些哈希函数用来设置位数组的值。当往过滤器中插入元素x时，h1(x), h2(x), ..., hk(x)所对应索引位置的值被置“1”，索引值由各个哈希函数计算得到。注意，如果我们增加哈希函数的数量，误报的概率会趋近于0.但是，插入和查找的时间开销更大，布隆过滤器的容量也会减小。

为了用布隆过滤器检验元素是否存在，我们需要校验是否所有的位置都被置“1”，与我们插入元素的过程非常相似。如果所有位置都被置“1”，那也就意味着该元素很有可能存在于布隆过滤器中。若有位置未被置“1”，那该元素一定不存在。

记录元素

下面我们看一下向Bloom Filter插入字符串的具体过，就是把这个字符串str经过K个不同的hash函数计算得到的结果h1、h2、、、hK。然后在BitArrray的第h1、h2、、、hK的位置上置1。

判断元素

 那么如何判断一个字符串是否存在呢

 把这个字符串经过K个hash函数计算得到h1、h2、、、hK，然后逐个判断BitArray的第h1、h2、、、hK个位置是否是1

　Google著名的分布式数据库Bigtable以及Hbase使用了布隆过滤器来查找不存在的行或列，以及减少磁盘查找的IO次数

　文档存储检查系统也采用布隆过滤器来检测先前存储的数据

　Goole Chrome浏览器使用了布隆过滤器加速安全浏览服务

　垃圾邮件地址过滤

　爬虫URL地址去重

　解决缓存穿透问题

结果：

优点：

　　　　1.全量存储但是不存储元素本身，在某些对保密要求非常严格的场合有优势

　　　　2.空间高效率

　　　　3.插入/查询时间都是常数O(k),远远超过一般的算法

缺点：

　　　　1.存在误算率(False Positive)，随着存入的元素数量增加，误算率随之增加

　　　　布隆过滤器能确保某个元素“肯定不存在”，但是对于一些元素的判断会是“可能存在”

　　　　2.一般情况下不能从布隆过滤器中删除元素

　　　　3.数组长度以及hash函数个数确定过程复杂

　　　　4.无法得到元素本身

　　　　布隆过滤器并不会保存插入元素的内容，只能检索某个元素是否存在