`
xpenxpen
  • 浏览: 731750 次
  • 性别: Icon_minigender_1
  • 来自: 上海
社区版块
存档分类
最新评论

布隆过滤器(Bloom Filter)

阅读更多
    布隆过滤器(Bloom Filter)是一种空间效率很高的随机数据结构,它利用位数组很简洁地表示一个集合,并能判断一个元素是否属于这个集合。Bloom Filter的这种高效是有一定代价的:在判断一个元素是否属于某个集合时,有可能会把不属于这个集合的元素误认为属于这个集合(false positive)。因此,Bloom Filter不适合那些“零错误”的应用场合。而在能容忍低错误率的应用场合下,Bloom Filter通过极少的错误换取了存储空间的极大节省.
    布隆过滤器里面的哈希算法很重要,必须是独立且均匀分布的,而且必须要快(密码杂凑比如SHA1不是一个好的选择)。
    介绍:http://billmill.org/bloomfilter-tutorial/
这个网址有动画演示。底部有一些实现的网址。
    guava也有一个实现,https://github.com/google/guava/wiki/HashingExplained#BloomFilter
分享到:
评论

相关推荐

    利用Java手写一个布隆过滤器Bloom Filter

    布隆过滤器是一种数据结构,主要用于判断一个元素是否可能在一个集合中存在。它可以在插入和查询数据时快速地判断一个元素是否可能在这个集合中,比如在缓存中查询一个元素是否存在。 它的原理是使用多个哈希函数对...

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

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

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

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

    布隆过滤器-BloomFilter

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

    java实现的布隆过滤器算法

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

    布隆过滤器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)`用于...

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

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

    bloom filter布隆过滤器学习资料大全

    布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否可能在一个集合中。在大数据处理、缓存系统、分布式存储等领域有着广泛的应用。这个压缩包文件“bloom filter布隆过滤器学习...

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

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

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

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

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

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

    布隆过滤器之C++实现

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

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

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

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

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

    布隆过滤器python库

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

    布隆过滤器在网页去重中的应用

    布隆过滤器在网页去重中的应用 , 海量数据处理中的一个绝好应用

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

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

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

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

    布隆过滤器-详说布隆过滤器.pdf

    在Java中,布隆过滤器的实现非常便捷,尤其是利用了Guava库提供的BloomFilter类。开发者可以非常简单地通过调用put方法添加元素,通过mayContain方法来检查元素是否存在。不仅如此,布隆过滤器还允许开发者自定义...

    布隆过滤器的实现,以及测试用例,简单易懂并做了一些注释

    布隆过滤器是一种概率型数据结构,用于判断一个元素是否可能在一个集合中。它是由Burton Howard Bloom在1970年提出的,主要用于解决大数据集的存储和查询问题,尤其在空间效率上有着显著优势。在数据库、搜索引擎、...

Global site tag (gtag.js) - Google Analytics