[面试口话]一： 布隆过滤器-浅谈
0 / 0 / 创建于 1年前 /
wangchunbo 的个人博客
原理浅谈
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. 应用场景
- 缓存穿透， 把条件存入布隆过滤器。 如果确定这个条件没有， 那就百分比没有。直接查数据库
- 判断超大数据中，某一条，指定数据是否存在，也是存入布隆过滤器，如果存在，再查数据库。
感谢
感谢柏的讲解。
本作品采用《CC 协议》，转载必须注明作者和本文链接
关于 LearnKu
粤公网安备 44030502004330号