BloomFilter&python支持
BloomFilter
布隆过滤器是一种概率空间高效的数据结构。它与hashmap非常相似，用于检索一个元素是否在一个集合中。
它在检索元素是否存在时，能很好地取舍空间使用率与误报比例。即Bloom Filter是会误判的，它只会把不存在于集合中的元素误判成存在于集合中，而不会把存在于集合中的元素误判成不存在集合中。
正是由于这个特性，它被称作概率性数据结构（probabilistic data structure）。
BloomFilter原理
布隆过滤器维护一个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地址去重
解决缓存穿透问题
python支持库BloomFilter
from
bloom_filter
import
BloomFilter
bloombloom = BloomFilter(max_elements=10000, error_rate=0.1
)
#
max_elements是布隆过滤器的容积，最多可以记录多少元素
#
error_rate是错判率
#
向bloom添加元素
bloombloom.add(
'
https://www.tianyancha.com/company/23402373
'
)
bloombloom.add(
'
https://www.tianyancha.com/company/23402372
'
)
bloombloom.add(
'
https://www.tianyancha.com/company/2340231
'
)
bloombloom.add(
'
https://www.tianyancha.com/company/23402
'
)
bloombloom.add(
'
https://www.tianyancha.com/company/234
'
)
bloombloom.add(
'
https://www.tianyancha.com/company/234023
'
)
#
判断URL是否在bloombloom.__contains__('https://www.tianyancha.com/company/23402373')
print
(bloombloom.
__contains__
(
'
https://www.tianyancha.com/company/23402373
'
))
s1
=
'
https://www.tianyancha.com/company/23402373
'
s2
=
"
1111
"
print
(s1
in
bloombloom)
print
(s2
in
bloombloom)
结果：
True
True
False
优点：
1.全量存储但是不存储元素本身，在某些对保密要求非常严格的场合有优势
2.空间高效率
3.插入/查询时间都是常数O(k),远远超过一般的算法
缺点：
1.存在误算率(False Positive)，随着存入的元素数量增加，误算率随之增加
布隆过滤器能确保某个元素“肯定不存在”，但是对于一些元素的判断会是“可能存在”
2.一般情况下不能从布隆过滤器中删除元素
3.数组长度以及hash函数个数确定过程复杂
4.无法得到元素本身
布隆过滤器并不会保存插入元素的内容，只能检索某个元素是否存在
