Bloom Filter是由 Howard Bloom在 1970 年提出的一种多哈希函数映射的快速查找算法,包括一个很长的二进制向量和K个哈希函数。每个哈希函数将某元素映射成二进制向量中的某一位。
Bloom Filter常见的应用场景是判断某元素是否属于某个集合A。假设二进制向量共有M位,使用K个哈希函数,集合A的大小为N,其中M往往远大于K和N:
【1】首先需要事先将A中的每个元素被K个哈希函数映射的K个位全部赋为真,令相应位上的值等于1。例如下图表示的是M=16,K=2的Bloom Filter。集合A中只包含a和b,a和b的哈希值分别为(3, 6)和(10, 3),所以我们就将位3、6、10标记为真。
【2】然后,我们查看待查元素的哈希值。如果有一位不为真,那么这个元素肯定不在集合A中。如果该元素被K个哈希函数映射的K个位全部为真,那么我们认为这 元素在这一个集合中,这时存在一定的误判率。所谓误判(False Positive)就是某元素不在Bloom Filter中,但是它所有哈希值的位置均被设为真,我们仍认为集合包含该元素。例如,上一步中,我们的集合A中只含元素a和b,但我们的判断是d也在集 合A中,应为d的哈希值对应的位都为真。
Bloom Filter的优点是空间效率和查询时间都远远超过一般的算法,然而这种高效是有一定代价的:在判断一个元素是否属于某个集合时,虽然不可能把属于这个集 合的元素误判为不属于这个集合,但有可能会把不属于这个集合的元素误认为属于这个集合。下面我们看下这个误判率到底有多大。
- 一个元素被K次哈希后,该特定位仍然为0的概率为(1-1/M)K;
- 在集合A的N个元素都被哈希完之后,该特定位为1的概率为1-(1-1/M)NK。
- 判断一个元素是否属于这个集合,考察的是映射的K个位是否都是1。K个位都是1的概率,即误判率P为[1-(1-1/M)NK]K。当x趋于无穷大时,(1+1/x)x = e,故误判率P=[1-(1-1/M)NK]K = (1-e-KN/M)K。
那么对于给定的M、N,那么应该选择几个哈希函数才能使元素查询时的错误率P降到最低呢?数学上可以证明,当K为ln2*M/N,约为0.7*M/N时,误判率最小为P=0.5K=0.6185M/N。最小值往往不能达到,因为实际中K为整数。
在不同M/N和K的情况下,误判率的概率情况详见这里。
BloomFilter的Python是实现详见这里。
相关推荐
自制布隆过滤器,采用八种不同哈希函数来获取随机数,错误率低
布隆去重工具类,感兴趣的了解一下。
布隆过滤器Bloom Filters的一个简单Java库
主要介绍了布隆过滤器(bloom filter)介绍以及php和redis实现布隆过滤器实现方法,非常不错,具有一定的参考借鉴价值,需要的朋友可以参考下
布隆过滤器,大家学过数据结构的应该都清楚,一般的字典树要实现嵌入和查找都内存的消耗非常大,布隆过滤器有BloomFilter,string, BKDRHash, APHash, DJBHash> bf五个参数你要查找的元素个数,查找元素类型,三个...
Bloomfilter布隆过滤器技术分享PPT。 介绍了布隆过滤器的使用方法与适用场景等。 适合用于技术分享。
布隆过滤器C源码
下面小编就为大家带来一篇布隆过滤器(Bloom Filter)的Java实现方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
bloom filter布隆过滤器学习资料大全,收集了很多相关的论文,并总结了各种布隆过滤器的变种
布隆过滤器的一个Go实现,参考bloomfilter.js
C++实现的布隆过滤器,其中使用到的bitset也是自己简单实现的一个BitContainer。可以处理千万条到亿条记录的存在性判断。做成dll可以在很多场合使用,如自己写爬虫,要判断一个url是否已经访问过,判断一个单词是否...
使用java实现的布隆过滤器算法,jdk-1.7,使用java实现的布隆过滤器算法,jdk-1.7,使用java实现的布隆过滤器算法,jdk-1.7,
介绍Bloom Filter(布隆过滤器)原理、实现及具体应用,包含9个不同PPT及PDF文档资料,对Bloom Filter感兴趣、想学习的同学可以下载查看下
布隆过滤器是一种数据结构,主要用于判断一个元素是否可能在一个集合中存在。它可以在插入和查询数据时快速地判断一个元素是否可能在这个集合中,比如在缓存中查询一个元素是否存在。 它的原理是使用多个哈希函数对...
bloom filter 布隆过滤器,这是源码,简单易学易用
硬核 - Redis 布隆(Bloom Filter)过滤器原理与实战.doc
布隆过滤器在网页去重中的应用 , 海量数据处理中的一个绝好应用
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多...
本质上布隆过滤器( BloomFilter )是一种数据结构,比较巧妙的概率型数据结构(probabilistic data structure),特点是高效地插入和查询,可以用来告诉你 “某样东西一定不存在或者可能存在”。 相比于传统的 Set、...