布隆过滤器是用来判断一个元素是否出现在给定集合中,具有快速,比哈希表更节省空间等优点,而缺点在于有一定的误识别率。布隆过滤器能够明确指出元素绝对不存在于一个集合中,或是可能存在于一个集合中。
布隆过滤器是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多,缺点是有一定的误识别率和删除困难。
布隆过滤器以下面的方式工作:
添加元素到过滤器。
对元素进行几次哈希运算,当索引匹配哈希的结果时,将该位设置为1的。
原理:S集合中有n个元素,利用k个哈希函数,将S中的每个元素映射到一个长度为m的位数组B中不同的位置上,这些位置上的二进制数均置为1,如果待检测的元素经过这k个哈希函数的映射后,发现其k个位置上的二进制数不全是1,那么这个元素一定不在集合S中,反之,该元素可能是S中的某一个元素。
Guava 11.0版本中增加了BloomFilter类,它使用了Funnel和Sink的设计,增强了泛化的能力,使其可以支持任何数据类型,其利用murmur3 hash来做哈希映射函数,不过它底层并没有使用传统的java.util.BitSet来做bit数组,而是用long型数组进行了重新封装,大部分操作均基于位的运算,因此能达到一个非常好的性能。
public class BloomFilterTest { public static void main(String[] args) { //预期插入数, 允许的错误率 BloomFilter<String> filter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 1000, 0.0001); filter.put("121"); filter.put("122"); filter.put("123"); System.out.println(filter.mightContain("12321")); //元素可能存在 BloomFilter<String> filter2 = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 1000, 0.0001); filter2.put("aba"); filter2.put("abb"); filter2.put("abc"); filter2.putAll(filter); System.out.println(filter2.mightContain("123")); } }
相关推荐
布隆过滤器是一种数据结构,主要用于判断一个元素是否可能在一个集合中存在。它可以在插入和查询数据时快速地判断一个元素是否可能在这个集合中,比如在缓存中查询一个元素是否存在。 它的原理是使用多个哈希函数对...
自制布隆过滤器,采用八种不同哈希函数来获取随机数,错误率低
布隆过滤器Bloom Filters的一个简单Java库
Bloomfilter布隆过滤器技术分享PPT。 介绍了布隆过滤器的使用方法与适用场景等。 适合用于技术分享。
使用java实现的布隆过滤器算法,jdk-1.7,使用java实现的布隆过滤器算法,jdk-1.7,使用java实现的布隆过滤器算法,jdk-1.7,
C++实现的布隆过滤器,其中使用到的bitset也是自己简单实现的一个BitContainer。可以处理千万条到亿条记录的存在性判断。做成dll可以在很多场合使用,如自己写爬虫,要判断一个url是否已经访问过,判断一个单词是否...
布隆过滤器,大家学过数据结构的应该都清楚,一般的字典树要实现嵌入和查找都内存的消耗非常大,布隆过滤器有BloomFilter,string, BKDRHash, APHash, DJBHash> bf五个参数你要查找的元素个数,查找元素类型,三个...
布隆过滤器C源码
布隆去重工具类,感兴趣的了解一下。
bloom filter布隆过滤器学习资料大全,收集了很多相关的论文,并总结了各种布隆过滤器的变种
硬核 - Redis 布隆(Bloom Filter)过滤器原理与实战.doc
布隆过滤器的一个Go实现,参考bloomfilter.js
布隆过滤器在网页去重中的应用 , 海量数据处理中的一个绝好应用
主要介绍了布隆过滤器(bloom filter)介绍以及php和redis实现布隆过滤器实现方法,非常不错,具有一定的参考借鉴价值,需要的朋友可以参考下
介绍Bloom Filter(布隆过滤器)原理、实现及具体应用,包含9个不同PPT及PDF文档资料,对Bloom Filter感兴趣、想学习的同学可以下载查看下
bloom filter 布隆过滤器,这是源码,简单易学易用
下面小编就为大家带来一篇布隆过滤器(Bloom Filter)的Java实现方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多...
23_布隆过滤器BloomFilter理论知识 24_布隆过滤器理论复习 25_缓存雪崩 26_缓存穿透和bloomFilter-helloworld 27_Guava解决缓存穿透 28_Redis布隆过滤器解决缓存穿透 29_docker安装rebloom 30_缓存击穿简介 31_高...
本质上布隆过滤器( BloomFilter )是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。 相比于传统的 Set、...