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 Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。由布隆在1970年提出,它不像传统的数据结构如哈希表那样保证不误判,而是允许有一定的错误率。这种特性使得...
布隆过滤器是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。它是由 Burton Howard Bloom 在1970年提出的,主要应用于大数据存储和检索,尤其在数据库、缓存系统和网络搜索等领域有广泛...
布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。在Java开发中,特别是在处理大数据、内存限制或需要快速查询是否存在某个元素的场景下,布隆过滤器是一个...
例如,`bf_create(size_t capacity, uint8_t num_hashes)`用于创建一个布隆过滤器,`bf_insert(bloom_filter* filter, const void* item)`用于插入元素,`bf_query(bloom_filter* filter, const void* item)`用于...
布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。在大数据处理、缓存系统、分布式存储等领域有着广泛的应用。这个压缩包文件“bloom filter布隆过滤器学习...
布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否在一个集合中。它可能会误判,但不会漏判,即如果它说一个元素在集合中,那可能是错误的,但如果它说一个元素不在集合中,那么...
Cuckoo 过滤器是近似集合成员查询的布隆过滤器替代品。虽然 Bloom 过滤器是众所周知的节省空间的数据结构,可以服务于“如果项目 x 在一个集合中?”之类的查询,但它们不支持删除。它们启用删除的差异(如计算 ...
- `Intersection(other *BloomFilter)`: 计算两个布隆过滤器的交集,创建一个新的布隆过滤器,只保留同时存在于两个过滤器中的元素的位。 4. **优化策略**: - **位数组大小**:位数组的大小直接影响误判率,需要...
Redis集成布隆过滤器需要使用Redis 4.0以上版本,或者使用Redis 6.x版本,使用官方提供的插件机制或编译安装RedisBloom模块。使用布隆过滤器可以解决大量数据去重问题,提高系统性能和效率。 布隆过滤器的优点是: ...
布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。它可能会误判,但不会漏判,即可能存在假阳性(False Positive),但绝不会有假阴性(False Negative)。...
布隆过滤器,大家学过数据结构的应该都清楚,一般的字典树要实现嵌入和查找都内存的消耗非常大,布隆过滤器有BloomFilter,string, BKDRHash, APHash, DJBHash> bf五个参数你要查找的元素个数,查找元素类型,三个...
布隆过滤器是一种高效的空间节省的数据结构,用于判断一个元素是否可能在一个集合中,但可能会产生一定的误判率。它由一个很长的二进制向量和多个独立的哈希函数组成。布隆过滤器的基本原理是,当一个元素被添加到...
`bloomfilter.js`可能是JavaScript版本的布隆过滤器实现,而"Go-布隆过滤器的一个Go实现参考bloomfilter.js"则表明该Go版本的实现是借鉴了JavaScript版本的设计思路或代码结构。 Go实现布隆过滤器的关键组件包括: ...
布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。在C++中实现布隆过滤器,可以有效地处理大量数据,尤其是在内存有限的情况下。这个压缩包文件"Bloom_filter...
在PHP和Redis中实现布隆过滤器,可以利用PHP的扩展库,如BloomFilter库,或者直接在Redis中使用BF.ADD、BF.MEMBERS和BF.EXISTS等命令操作布隆过滤器。Redis的布隆过滤器模块提供了方便的操作接口,能够在分布式环境...
**布隆过滤器(Bloom Filter)**是一种空间效率极高的概率型数据结构,用于测试一个元素是否在一个集合中。由Burton Howard Bloom在1970年提出,主要用于节省存储空间,尤其在大数据场景下,它能有效地解决大规模...
在Python中,有多个库实现了布隆过滤器,其中一个就是我们这里提到的"python-bloomfilter-master"。 这个Python库提供了对布隆过滤器的简单接口,使得开发者可以方便地在项目中应用布隆过滤器。安装过程非常直观,...
C++实现的布隆过滤器,其中使用到的bitset也是自己简单实现的一个BitContainer。可以处理千万条到亿条记录的存在性判断。做成dll可以在很多场合使用,如自己写爬虫,要判断一个url是否已经访问过,判断一个单词是否...
【布隆过滤器(Bloom Filter)的Java实现】 布隆过滤器是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。它可能会产生误报(false positive),但不会产生漏报(false negative)。在Java...