布隆过滤器原理简介

布隆过滤器原理简介目录1.布隆过滤器简介2.布隆过滤器的实现思路3.布隆过滤器的公式4.实际应用场景1.布隆过滤器简介布隆过滤器(BloomFilter)是由一个很长的bit数组和一系列哈希函数组成的。本质上是一种数据结构,比较巧妙的概率型数据结构。它的特点是高效地插入和查询,并且根据查询结果可以知道某样东西一定不存在或者可能存在。相比于传统的List、Set、Map等数据结构,它更高效、占用空间更少,但是缺点是其返回的结果是概率性的,而不是确切的,同时布隆过滤器还有一个缺陷就是数据只..

目录

 

1.布隆过滤器简介

2. 布隆过滤器的实现思路

3.布隆过滤器的公式

4.实际应用场景 


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

(0)
编程小号编程小号

相关推荐

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注