[面试口话]一: 布隆过滤器-浅谈

原理浅谈

1. 拿一块牌子记录。

假设这是一个数组,数组的,这个数组的每一个元素都是布尔类型,然后这个数组的长度是8。你相当于这一个数组一共就占了一个字节。
每1个元素就是表示0和1

2. 有数据来了。使用算法生成一个标记,记录到牌子

比如:“爱迪奥特曼”,是要存入的。 我们采用md5,后的结果在mod 4(随便你mod几)。现在结果是4,我就把这个数组的第四个元素由0设置为1。

紧接着, “雷欧奥特曼”:来了,我们采集同样的计算,得到结果是5,那就把第五个,设置为1.

到目前为止,都是不同的位,变为1.
结论: 布隆过滤器说不一样,这两个单词肯定是不一样的

3. 算法生成标记,记录到牌子,冲突了。

“宇宙英雄奥特曼”来了, 结果为6,
“奥特曼”来了,结果也是6.
(根据圆谷设定,宇宙英雄奥特曼就是 最初的奥特曼)

那么现在出现一个情况,这两个值,可能是同一个。

结论:这个单词有概率是一样的,有概率我不能100%确定,但反正就是有概率。
就比如说,土豆 马铃薯, 番茄与西红柿。

4. 人太多,牌子需要升级

之前,只是用了1个数组,才8个位数。
那么精度太低,容易撞位。

我们可以整个1024字节,甚至1024M。 这就是把牌子变大。提升精度。

5. 牌子太大了,还不够,我们做三个牌子

那么 第一个牌子,md5,mod 4。
第二个,雪花算法, mod5,
第三个,hash算法,mod6.

这样子又提升了精度。时间复杂度,仅仅是3n

6. 前面结论小结:

结论:如果我用三个算法,我想我这个精度又提升了,最重要的思想就是提升精度的思想。
我不能保证说100%的确认是否重复,但是我可以做到精度。你想想我给你1万亿条数据,我可能只需要几个数组,几个离散算法,然后数组的长度大概是一个我给他干一亿个,对吧?

我基本上能把一个我就从内存从磁盘里面一点点读出来,然后往刚刚几个数组里面,那时候我再把他们单独拎出来,到最后再过滤一遍,这样的话我就能用很低的内存开销,然后把所有的一一个数据过滤一遍,这个就是布隆过滤器

7. 应用场景

  1. 缓存穿透, 把条件存入布隆过滤器。 如果确定这个条件没有, 那就百分比没有。直接查数据库
  2. 判断超大数据中,某一条,指定数据是否存在,也是存入布隆过滤器,如果存在,再查数据库。

感谢

感谢柏的讲解。

本作品采用《CC 协议》,转载必须注明作者和本文链接
嗨,我是波波。曾经创业,有收获也有损失。我积累了丰富教学与编程经验,期待和你互动和进步! 公众号:上海PHP自学中心 付费知识星球:破解面试:程序员的求职导师
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!
司机 @ 欣昊玉
文章
272
粉丝
335
喜欢
555
收藏
1096
排名:65
访问:12.0 万
私信
所有博文
社区赞助商