`
daniel_tu
  • 浏览: 184601 次
  • 性别: Icon_minigender_1
  • 来自: 深圳
社区版块
存档分类
最新评论

布隆过滤器:Bloom Filter

 
阅读更多

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的优点是空间效率和查询时间都远远超过一般的算法,然而这种高效是有一定代价的:在判断一个元素是否属于某个集合时,虽然不可能把属于这个集 合的元素误判为不属于这个集合,但有可能会把不属于这个集合的元素误认为属于这个集合。下面我们看下这个误判率到底有多大。

  1. 一个元素被K次哈希后,该特定位仍然为0的概率为(1-1/M)K
  2. 在集合A的N个元素都被哈希完之后,该特定位为1的概率为1-(1-1/M)NK
  3. 判断一个元素是否属于这个集合,考察的是映射的K个位是否都是1。K个位都是1的概率,即误判率P为[1-(1-1/M)NK]K。当x趋于无穷大时,(1+1/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是实现详见这里

分享到:
评论

相关推荐

    布隆过滤器-BloomFilter

    布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。由布隆在1970年提出,它不像传统的数据结构如哈希表那样保证不误判,而是允许有一定的错误率。这种特性使得...

    bloom filter(C#版自制布隆过滤器)

    布隆过滤器是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。它是由 Burton Howard Bloom 在1970年提出的,主要应用于大数据存储和检索,尤其在数据库、缓存系统和网络搜索等领域有广泛...

    布隆过滤器BloomFilters的一个简单Java库

    布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。在Java开发中,特别是在处理大数据、内存限制或需要快速查询是否存在某个元素的场景下,布隆过滤器是一个...

    布隆过滤器C源码-bloomfilter.rar

    例如,`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布隆过滤器学习...

    java实现的布隆过滤器算法

    布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否在一个集合中。它可能会误判,但不会漏判,即如果它说一个元素在集合中,那可能是错误的,但如果它说一个元素不在集合中,那么...

    Cuckoo过滤器:实际上比 Bloom 更好_Go语言_代码_相关文件_下载

    Cuckoo 过滤器是近似集合成员查询的布隆过滤器替代品。虽然 Bloom 过滤器是众所周知的节省空间的数据结构,可以服务于“如果项目 x 在一个集合中?”之类的查询,但它们不支持删除。它们启用删除的差异(如计算 ...

    Go-一个简单的golang布隆过滤器

    - `Intersection(other *BloomFilter)`: 计算两个布隆过滤器的交集,创建一个新的布隆过滤器,只保留同时存在于两个过滤器中的元素的位。 4. **优化策略**: - **位数组大小**:位数组的大小直接影响误判率,需要...

    硬核 - Redis 布隆(Bloom Filter)过滤器原理与实战.doc

    Redis集成布隆过滤器需要使用Redis 4.0以上版本,或者使用Redis 6.x版本,使用官方提供的插件机制或编译安装RedisBloom模块。使用布隆过滤器可以解决大量数据去重问题,提高系统性能和效率。 布隆过滤器的优点是: ...

    布隆过滤器(利用布隆过滤器实现文字的嵌入和查找功能)

    布隆过滤器,大家学过数据结构的应该都清楚,一般的字典树要实现嵌入和查找都内存的消耗非常大,布隆过滤器有BloomFilter,string, BKDRHash, APHash, DJBHash> bf五个参数你要查找的元素个数,查找元素类型,三个...

    【技术分享】Bloomfilter布隆过滤器.pptx

    布隆过滤器是一种高效的空间节省的数据结构,用于判断一个元素是否可能在一个集合中,但可能会产生一定的误判率。它由一个很长的二进制向量和多个独立的哈希函数组成。布隆过滤器的基本原理是,当一个元素被添加到...

    Go-布隆过滤器的一个Go实现参考bloomfilter.js

    `bloomfilter.js`可能是JavaScript版本的布隆过滤器实现,而"Go-布隆过滤器的一个Go实现参考bloomfilter.js"则表明该Go版本的实现是借鉴了JavaScript版本的设计思路或代码结构。 Go实现布隆过滤器的关键组件包括: ...

    Bloom_filter_(C).zip_bloom_bloom filter_c++布隆_布隆过滤器

    布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。在C++中实现布隆过滤器,可以有效地处理大量数据,尤其是在内存有限的情况下。这个压缩包文件"Bloom_filter...

    布隆过滤器(bloom filter)及php和redis实现布隆过滤器的方法

    在PHP和Redis中实现布隆过滤器,可以利用PHP的扩展库,如BloomFilter库,或者直接在Redis中使用BF.ADD、BF.MEMBERS和BF.EXISTS等命令操作布隆过滤器。Redis的布隆过滤器模块提供了方便的操作接口,能够在分布式环境...

    Java版本的BloomFilter (布隆过滤器)

    **布隆过滤器(Bloom Filter)**是一种空间效率极高的概率型数据结构,用于测试一个元素是否在一个集合中。由Burton Howard Bloom在1970年提出,主要用于节省存储空间,尤其在大数据场景下,它能有效地解决大规模...

    介绍Bloom Filter(布隆过滤器)原理、实现及具体应用

    布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。它可能会误判,但不会漏判,即可能存在假阳性(False Positive),但绝不会有假阴性(False Negative)。...

    布隆过滤器python库

    在Python中,有多个库实现了布隆过滤器,其中一个就是我们这里提到的"python-bloomfilter-master"。 这个Python库提供了对布隆过滤器的简单接口,使得开发者可以方便地在项目中应用布隆过滤器。安装过程非常直观,...

    布隆过滤器之C++实现

    C++实现的布隆过滤器,其中使用到的bitset也是自己简单实现的一个BitContainer。可以处理千万条到亿条记录的存在性判断。做成dll可以在很多场合使用,如自己写爬虫,要判断一个url是否已经访问过,判断一个单词是否...

    布隆过滤器(Bloom Filter)的Java实现方法

    【布隆过滤器(Bloom Filter)的Java实现】 布隆过滤器是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。它可能会产生误报(false positive),但不会产生漏报(false negative)。在Java...

Global site tag (gtag.js) - Google Analytics