布隆过滤器俗称BloomFilter,是一个非常简单好用的编程小工具，主要作用是用来判断两件事:
-
一个元素在集合中不存在 -
一个元素在集合中可能存在
BloomFilter 工作原理
原理很简单，我先上个图演示一下.
一点逻辑
这里, 涉及一个逻辑小常识, 充分条件,必要条件.
知道这个, 基本就可以理解布隆过滤器了.
染色
如果把布隆过滤器当成一块白布,往里插入A就把其中[7,8,22]这3块格子染黑.那么很明显,这里p (A存在)和q(7,8,22)为黑色,就构成了一个 的关系.
这里, 如果:
-
把 白布换成m个bit的集合 -
把一个元素对应位置列表,换成k个 哈希函数 -
把染色,换成把对应位置设置为1.
好了, 你已经知道了关于布隆过滤器的一切了.
-
一个元素对应的格子没有全被染色, 说明这个元素一定不存在, -
如果全部被染色, 说明这个元素可能存在.
这是小朋友的逻辑题.
一点中学数学
我们已经知道了, 布隆过滤器判断不存在是100%准确的. 判断存在, 却只是可能. 那么这个犯错概率是多大呢?这个值其实可以算出来.
一个元素不存在,但是他对应的几个格子被染色,这种情况称为假阳性(false positive),下面来计算这个假阳性概率.
布隆过滤器的参数
一个布隆过滤器有3个核心参数.
-
bit数 m, m决定了,总的格子容量是多少. -
哈希函数数量 k, k决定了, 一个值会被映射到几个格子. -
元素数n, n是当前已被放入布隆过滤器的元素数.
假阳性的概率
如果我们随机挑选一个格子染黑，那么每个格子被染黑的概率都是 ,不被染黑的概率是 .
染色进行了k次，那么k次都不染黑的概率是 ,如果我们往布隆过滤器里放入n个元素，那么相当于进行了 次染色。一个格子这么多次都不被染色的概率是 次方,被染色的概率应该为
而假阳性,指的一个元素不在,但是他对应的k个格子都被染色, 则假阳性概率为 .
函数图像
这个函数看着有点复杂, 他有3个变量(m,n,k),直接画出图像是不太可能了.不过我们可以做一点小假定, 因为初始化以后m值就不能变了.这里可以考虑把m设置成一个固定值.比如采用m=1000,式子变为: . 借助工具可以画出这个图像.
最理想的k值
已经有大佬求过这里的极值点了,我就直接上结论了. 最理想的k值是 ,这时候,假阳性的概率约为 .
看官要是想知道这里的值是怎么求出来的, 可以去看这里: programming.guide[1] . 这个网站的作者是一个是Oracle的JDK开发者, 一个是计算机教授.相信我,点开一定不虚此行.
后话
yep, 今天又这么没头没脑的结束了.就当成我的目的是推荐这个网站吧.
今天原本是准备画好gif发出来的,结果查参考资料时候搜到了这个网站.有点崩溃,我想静一静.
作者的几个动画都非常漂亮, 甚至可以交互,请一定多把玩一会.
参考资料
programming.guide: https://programming.guide/bloom-filter.html
原文始发于微信公众号（K字的研究）：布隆过滤器是什么原理?
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/24789.html
