简单点说,这是基于hash算法思想的一个拓展算法。
一般的hash实现都是用以存储数据的;但如果用于检查某个东西是否存在的场合,那么仅需存储一个占用标记(1个二进制位)即可,通用的实现就太浪费空间了——尤其是上亿甚至几十亿数据(如google的email黑名单)的情况。
但如果仅存储一个二进制位,又怎样识别碰撞?
一种办法是:做8个hash表,用8个不同的散列函数;选择得当的话,一个词在8种hash方案中都有碰撞的概率就极小了。
如果你完全理解了hash算法,那么下一步优化就是理所当然的了:
为了减小碰撞,除了选择好算法,我们还必须保证hash地址空间足够大;但为了减少内存占用,hash地址还不能太大。
怎么办?
布隆过滤器的思路是:用一个16倍大的地址空间;但让所有8个hash函数都映射到这个地址空间里面。
这样,对设计良好的hash函数来说,碰撞的概率几乎小到可以忽略不计;虽然同时多了8个散列函数相互影响的问题,但总碰撞会比8个不同hash函数在独立的2倍大小地址中的碰撞少得多。
于是,这个算法就不仅大幅度降低了时间、空间消耗,又保证了足够的准确率。
对于检查用户名有否重复这种应用来说,一方面数据量肯定要比垃圾邮件地址少得多;另一方面,即使发生了碰撞,也不过是导致极少几个用户名无法使用而已,完全不必理会。
综合起来,这个算法不过是8个无碰撞检测的散列和8次通过下标的数组访问而已;不考虑页错误,即使在pc机上跑,时间消耗也不会超过微秒级。
-----
分享到:
相关推荐
自制布隆过滤器,采用八种不同哈希函数来获取随机数,错误率低
布隆过滤器Bloom Filters的一个简单Java库
布隆过滤器是一种数据结构,主要用于判断一个元素是否可能在一个集合中存在。它可以在插入和查询数据时快速地判断一个元素是否可能在这个集合中,比如在缓存中查询一个元素是否存在。 它的原理是使用多个哈希函数对...
Redis集成布隆过滤器需要使用Redis 4.0以上版本,或者使用Redis 6.x版本,使用官方提供的插件机制或编译安装RedisBloom模块。使用布隆过滤器可以解决大量数据去重问题,提高系统性能和效率。 布隆过滤器的优点是: ...
Bloomfilter布隆过滤器技术分享PPT。 介绍了布隆过滤器的使用方法与适用场景等。 适合用于技术分享。
布隆过滤器C源码
布隆去重工具类,感兴趣的了解一下。
布隆过滤器,大家学过数据结构的应该都清楚,一般的字典树要实现嵌入和查找都内存的消耗非常大,布隆过滤器有BloomFilter,string, BKDRHash, APHash, DJBHash> bf五个参数你要查找的元素个数,查找元素类型,三个...
C++实现的布隆过滤器,其中使用到的bitset也是自己简单实现的一个BitContainer。可以处理千万条到亿条记录的存在性判断。做成dll可以在很多场合使用,如自己写爬虫,要判断一个url是否已经访问过,判断一个单词是否...
使用java实现的布隆过滤器算法,jdk-1.7,使用java实现的布隆过滤器算法,jdk-1.7,使用java实现的布隆过滤器算法,jdk-1.7,
bloom filter布隆过滤器学习资料大全,收集了很多相关的论文,并总结了各种布隆过滤器的变种
布隆过滤器的一个Go实现,参考bloomfilter.js
介绍Bloom Filter(布隆过滤器)原理、实现及具体应用,包含9个不同PPT及PDF文档资料,对Bloom Filter感兴趣、想学习的同学可以下载查看下
bloom filter 布隆过滤器,这是源码,简单易学易用
布隆过滤器在网页去重中的应用 , 海量数据处理中的一个绝好应用
主要介绍了布隆过滤器(bloom filter)介绍以及php和redis实现布隆过滤器实现方法,非常不错,具有一定的参考借鉴价值,需要的朋友可以参考下
下面小编就为大家带来一篇布隆过滤器(Bloom Filter)的Java实现方法。小编觉得挺不错的,现在就分享给大家,也给大家做个参考。一起跟随小编过来看看吧
布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多...
布隆过滤器(Bloom filter)是一种空间效率高的概率性数据结构,用于测试元素是否存在于集合中。LevelDB 中使用布隆过滤器来判断指定的 key 值是否存在于 sstable 中,从而减少调用 DB::Get() 时的访存次数。 布隆...