基本介绍

  • 一种适用于大数据量场景下，判断元素是否在某个集合中的一种算法
  • 不用存储全量数据，空间效率和时间效率很高
  • 但是牺牲了准确率(False绝对正确，True相对正确，可能有误)
  • 基本原理是位数组和Hash函数的联合使用

  • 只能插入元素，不能删除元素

    典型应用

  • 网络爬虫，判断这个网址是否之前爬取过，没去过，那么一定要去爬取，并更新布隆过滤器

  • 过滤邮件的场景，要把垃圾邮件的信箱邮件地址存储起来，缓存判断并过滤的话，资源耗费巨大；使用布隆过滤器，可以大大节省存储占用
  • 大数据存取系统上的应用。
    • 每一个分区上维护一个可持久化的布隆过滤器
    • 数据插入到某个分区时，更新布隆过滤器
    • 数据查询时，hash算法定位到这个分区 ，并根据布隆过滤器的结果处理
    • 如果返回false，那么数据不在这个分区，直接返回
    • 如果返回true，那么数据可能在这个分区，执行查询
    • 这样规避了外部随意编造查询请求的问题(因为编造的 请求 ，大概率都会被布隆过滤器过滤 )

gauva中有现成的布隆过滤器的实现

参考