布隆过滤器 bloom filter

应用场景

1. Google著名的分布式数据库Bigtable以及Hbase使用了布隆过滤器来查找不存在的行或列，以减少磁盘查找的ＩＯ次数。
2. 检查垃圾邮件地址
3. Google chrome 浏览器使用bloom filter识别恶意链接（能够用较少的存储空间表示较大的数据集合，简单的想就是把每一个URL都可以映射成为一个bit）
4. 文档存储检索系统也采用布隆过滤器来检测先前存储的数据
5. 爬虫URL地址去重
6. 犯罪记录查询
7. 机密度要求高的, 不允许存储数据的
8. 防止缓存穿透, request -> cache -> db 在cache前加一层过滤, request -> (bloom filter)cache -> db

传统的hash方式记录查询url的话, 假设10亿条记录, 每个url平均200个字符 就需要记录2000亿个字符 需要200GB内存
如果使用布隆过滤器来记录, 失误率不超过0.01%的情况下 ,只需要内存2.3GB
原理是布隆过滤器只计算hash之后 在 bit 数组上 把对应位置设置位1.
并且采用多个hash计算的方式, 所以判断的失误表现形式是 如果没存在 就一定没存在, 如果存在, 有可能没存在, 在失误率不高, 并且即使失误也没关系的地方 非常好用.
优点:

1. 空间/时间复杂度低, O(k) k为 hash算法的个数
2. 不保存数据本身, 机密性高
   缺点:
3. 没法执行删除操作 (有一种思路是把bit换乘int, 没有一次就+1, 删除就是 各个点-1, 判断是否>0, 感觉也没啥乱用)
4. 有一定的错误率

Python3的话可以使用pip3 install bloom_filter

from bloom_filter import BloomFilter
have_met = BloomFilter(filename='test_my_bloom.xx')

def have_i_met(name):
    met = name in have_met
    print('Have I met {} before: {}'.format(name, met))

def meet(name):
    have_met.add(name)
    print('Hello, {}'.format(name))

for name in ['Harry', 'Larry', 'Moe']:
    have_i_met(name)
    meet(name)
    have_i_met(name)

https://segmentfault.com/a/1190000015482091