缓存问题(二) 布隆过滤器(Bloom Filter) 介绍和原理

代码地址: https://gitee.com/crazyliyang/video-teaching.git
视频地址: https://www.bilibili.com/video/BV1Ha411c7hB

 

1. 什么情况下需要布隆过滤器？

先来看几个比较常见的例子

• 检查一个用户是否在白名单中
• 在 FBI，一个嫌疑人的名字是否已经在嫌疑名单上
• 在网络爬虫里，一个网址是否被访问过
• yahoo, gmail等邮箱垃圾邮件过滤功能

这几个例子有一个共同的特点： 如何判断一个元素是否存在一个集合中？

 

 

2. 哈希函数  Hash Function

 

3.布隆过滤器

 

 

 

4.总结:

 

布隆过滤器判断   不存在   准确率100%

布隆过滤器判断   存在      准确率不是100%,  也就是说存在误差, 不准确, 由过滤器的误判率 fpp设置调节

 

布隆过滤器 可以判断某样东西 一定不存在  

或者  

布隆过滤器 可以判断某样东西 可能存在