布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好得多，缺点是有一定的误识别率和删除困难。基本概念 如果想要判断一个元素是不是在一个集合里，一般想到的...
复制代码在导入 Guava 库后,我们新建一个 BloomFilterDemo 类,在 main 方法中我们通过 BloomFilter.create 方法来创建一个布隆过滤器,接着我们初始化 1 百万条数据到过滤器中,然后在原有的基础上增加 10000 条数据并判断这些数据是否存在布隆过滤器中: 代码语言:javascript 复制 importcom.google.common.base.Charse...
需要注意的是,我这里的示例是为了演示布隆过滤器的实现原理的简单实现,实际上完善的布隆过滤器的算法还是比较复杂的,包括误判率,哈希计算方式等。 1. 构建集合 根据之前介绍的布隆过滤器的实现原理,布隆过滤器的实现主要包括可以存放二进制元素的 BitSet 以及多样性的哈希计算函数。下面通过实例演示布隆过滤器的实现。
使用布隆过滤器来做黑名单过滤,针对不同的用户是否存入白名单或者黑名单,虽然有一定的误判,但是在一定程度上还是很好的解决问题 缓存击穿场景,一般判断用户是否在缓存中,如果存在则直接返回结果,不存在则查询数据库,如果来一波冷数据,会导致缓存大量击穿,造成雪崩效应,这时候可以用布隆过滤器当缓存的索引,只有在布隆过滤...
Venti 文档存储系统也采用布隆过滤器来检测先前存储的数据。 SPIN 模型检测器也使用布隆过滤器在大规模验证问题时跟踪可达状态空间。 布隆过滤器的使用 google的Guava工具类已经做好了封装,可以直接使用: <dependency><groupId>com.google.guava</groupId><artifactId>guava</artifactId><version>23.0</version></depe...
我们可以看到数组中1、8、13这三个位置都是1,data1可能存在于该布隆过滤器。我们从添加的角度来看,我们知道data1是一定存在于该布隆过滤器的,为什么还要是说可能呢,是因为查询出来三个位置都为1不能代表这个三个1都是同一个元素添加的,下面我们看下元素data3的查询。 查询data3先根据添加时的三个hash函数计算分...
在之前讨论的几个经典分布式系统设计中(键值存储系统,URL缩短服务,高效的网络爬虫),好几次都用到了布隆过滤器(Bloom Filter)作为系统中的一个关键部件。在这些设计中,布隆过滤器只是作为一个系统部件大致的提到了使用场景和用途,但是对于其工作原理一直是一知半解,通过这篇笔记来深度探索一下其原理和更多的使用场景...
1、什么是布隆过滤器 可以把布隆过滤器理解为一个不怎么精确的set结构,当你使用它的contains方法判断某个对象是否存在时,它可能会误判。但是布隆过滤器也不是特别不精确,只要参数设置得合理,它的精确度也可以控制得相对足够精确,只会有小小的误判概率。
布隆过滤器是由 Burton Bloom 在 1970 年提出,因此也称为 Bloom Filter。 作用 判断一个元素是否在一个集合 实现 通过一个很长的二进制向量和一系列的随机映射函数实现 优点 插入/查询速度快,且有较好的时间和空间效率。时间/空间复杂度都是常量O(K) ...
布隆过滤器 (Bloom Filter)是由Burton Howard Bloom于1970年提出,它是一种space efficient的概率型数据结构,用于判断一个元素是否在集合中。在垃圾邮件过滤的黑白名单方法、爬虫(Crawler)的网址判重模块中等等经常被用到。哈希表也能用于判断元素是否在集合中,但是布隆过滤器只需要哈希表的1/8或1/4的空间复杂度就能...