目录
1.布隆过滤器简介
布隆过滤器(Bloom Filter)是由一个很长的bit数组和一系列哈希函数组成的
。本质上是一种数据结构,比较巧妙的概率型数据结构
。它的特点是高效地插入和查询,并且
根据查询结果可以知道某样东西一定不存在或者可能存在。
相比于传统的 List、Set、Map 等数据结构,它更高效、占用空间更少,但是缺点是其返回的结果是概率性的,而不是确切的,同时布隆过滤器还有一个缺陷就是数据只能插入不能删除。
2. 布隆过滤器的实现思路
①设数据集合A={a1,a2,a3,…,an},含有n个元素作为待操作的集合;
②Bloom Filter用一个长度为m的位向量V表示集合中的元素,位向量初始值全为0;
③k个具有均匀分布特性的散列函数h1,h2,…,hk;
④对于要加入的元素,首先经过k个散列函数%m,产生k个随机数h1,h2,…,hk,使向量V的相应位置h1,h2,…,hk均
置位为1。集合中其他元素也通过类似的操作,将向量V的若干位置为1;
⑤对于新要加入的元素的检查,首先将该元素经过上步中类似的操作,获取k个随机数h1,h2,…,hk,然后查看向量V
的相应位置h1,h2,…,hk上的值,若全为1,则该元素已经在之前的集合中;若至少有一个0存在,表明此元素不在之前
的集合中,为新元素。
特点:
对于已经在集合中的元素,通过⑤中的查找方法,一定可以判定该元素在集合中;对于不在集合中的元素,可能会被误判
在集合中。
3.布隆过滤器的公式
布隆过滤器的大小m公式,其中n为样本个数,p为误判率:
哈希函数的个数k公式:
布隆过滤器真实失误率p公式:
4.实际应用场景
背景:
现在有个100亿个黑名单网页数据,每个网页的URL占用64字节。现在想要实现一种网页过滤系统,可以根据网页的URL判断该网站是否在黑名单上,请设计该系统。
需求:
可以允许有0.01%以下的判断失误率,并且使用的总空间不要超过200G。
提取关键信息:100亿条黑名单数据
,每条数据占64个字节
,万分之一的失误率
,总空间不要超过200G
。
分析:如果不考虑不布隆过滤器,那么这里存储100亿条数据就需要 100亿 * 64字节 = 596G 显然超过300G
解题:
在满足有 100亿条数据 并且允许 万分之一的失误率 的布隆过滤器需要多大的bit数组呢?
- 设bit数组大小为m,样本数量为n,失误率为p。
- 由题可知 n = 100亿,p = 0.01%
- 根据布隆过滤器的大小m公式,求得 m = 19.19n,向上取整为 20n。所以2000亿bit,约为186G。
- 根据哈希函数的个数k公式,求得 k = 14,即需要14个哈希函数。
- 通过 上述计算得到的 m = 20n, k = 14 ,根据布隆过滤器真实失误率p公式,求得 p = 0.006%。
今天的文章布隆过滤器原理简介分享到此就结束了,感谢您的阅读。
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
如需转载请保留出处:https://bianchenghao.cn/6206.html