如何理解Bloomfilter(布隆过滤器)?

南风 2020年10月30日 147次浏览

面试官问你:如果我有100G的数据,我的电脑只有16G,你什么帮我快速判断一个数据是否在这个100G的数据里?

 一般的做法是将数据切分成各个小块,然后循环加入内存遍历比对是否存在,这种方法就是我们平时所说的暴力解法,耗时耗力...

一、Bloomfilter是什么?

 布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量(位图)和一系列随机映射函数(哈希函数)。
 布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。
 假设你学过bitmap,那么你应该听说过布隆过滤器,BoomFilter是一个可以快速确定数据不存在和判断数据可能存在的数据结构,底层就是bitmap,它的原理就是维护一个bit列表,然后将数据经过基层的Hash函数,得到的k为数字一次映射到对应bit列表上,将其对应的位置设置成1,数据量越大的时候,由于HASH冲突的原因就有可能存在更多的数据重叠在同一个bit位里面,导致数据判断出现误判,所以BommFilter只能判断数据可能存在而不是一定存在,为了减少HASH的冲突率,我们可以通过几轮的HASH算法优化误判率,但是数据增大时误判率也会随之增大,查询时只要有一个HASH对不上,说明数据不存在。

布隆过滤器

二、什么是布隆过滤器的误判率?

假设输入对象个数为n,bitarray大小(也就是布隆过滤器大小)为m,所容忍的误判率p和哈希函数的个数k。计算公式如下:
布隆过滤器的误判率

三、布隆过滤器的应用实例

  • 1、分布式系统中防止缓存击穿
  • 2、大规模数据系统数据去重逻辑
  • 3、Google Gmail垃圾邮件过滤
  • 4、黑名单网站过滤
  • 5、Google 著名的分布式数据库 Bigtable 使用了布隆过滤器来查找不存在的行或列,以减少磁盘查找的IO次数
  • 6、Squid 网页代理缓存服务器在 cache digests 中使用了也布隆过滤器
  • 7、Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据
  • 8、SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间
  • 9、Google Chrome浏览器使用了布隆过滤器加速安全浏览服务