大家好,又见面了,我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。
Jetbrains全系列IDE稳定放心使用
目录
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%。
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/185000.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...