当前位置: 首页 > 科技观察

什么是布隆过滤器?你学会了吗?

时间:2023-03-13 21:59:09 科技观察

前言如果要判断一个元素是否在集合中,一般的思路是保存集合中的所有元素,然后通过比较来确定。链表、树、哈希表(也叫哈希表、哈希表)等数据结构都是这种方式,存储位置要么是磁盘,要么是内存。很多时候,要么时间换空间,要么空间换时间。在对响应时间要求严格的情况下,如果我们有inside,那么随着集合中元素数量的增加,我们需要更多的存储空间和更长的检索时间,导致内存开销过大,时间效率变低。这时候需要考虑的问题是,在数据量比较大的情况下,既能满足时间要求,又能满足空间要求,所以我们需要一种消耗更少的数据结构和算法时间和空间。布隆过滤器是一种解决方案。什么是布隆过滤器?BloomFilter,Bloomfilter由Bloom于1970年提出。它实际上是一个长的二值向量和一系列随机映射函数,Bloomfilters可以用来检索一个元素是否在集合中。其优点是空间效率和查询时间远超一般算法,缺点是存在一定的误识别率和删除难度。根据其特点,应用场景如下:爬虫过滤。邮箱垃圾邮件过滤。黑名单过滤。大数据去重。防止缓存穿透。Bloomfilter的原理Bloomfilter的原理是当一个元素加入到集合中时,通过K个哈希函数将该元素映射到位数组中的K个点,并将它们置为1。在检索时,我们只需要看看这些点是否都为1,我们就可以(大概)知道它是否存在于集合中。如果这些点中的任何一个为0,则所检查的元素一定不存在。如果它们都是1,则所选元素可能在那里。BloomFilter与单一哈希函数Bit-Map的区别在于,BloomFilter使用了k个哈希函数,每个字符串对应k个比特位,从而降低了碰撞概率。由于布隆过滤器只存储0和1,不存储具体值,所以在一些机密场合具有先天优势。位图的每一位都是一个位,所以通过位图有10亿个位置,位图的大小是0.12G,插入和查询的时间复杂度是O(k),k是哈希函数的个数。Bloomfilter的问题Bloomfilter之所以能够在时间和空间上取得比较高的效率,是因为它牺牲了判断的准确性和删除的便利性。如果判断错误,你要找的元素可能不在容器中,但是哈希后得到的k个位置都是1。如果Bloomfilter中存储了一个黑名单,可以通过创建来存储可能被误判的元素白名单。对于这个问题,可以通过增加位图数组的大小(位图数组越大,占用的内存越大)和减少哈希冲突来解决。但缺点是会增加占用的内存空间。另一种解决方案是增加散列函数的数量并减少散列冲突。如果同一个键值等于一个函数,通过两个或多个哈希函数得到相等结果的概率自然会降低。然而,这将导致计算效率下降,因为时间复杂度退化为O(hashtimes)。难以删除放置在容器中的元素映射到位数组的k个位置中的1。删除的时候不能简单的直接设置为0,这样可能会影响其他元素的判断。您可以使用CountingBloomFilter来解决这个问题。Java中如何使用布隆过滤器google的guava就提供了这样的API。com.google.guavaguava22.0编写测试代码importcom.google.common.base.Charsets;importcom.google.common.hash.BloomFilter;importcom.google.common.hash.Funnels;公共类GuavaBloomFilter{publicstaticvoidmain(String[]args){inttotal=1000000;//defaultfalsepositiveratefpp0.03//fpp:Bloomfilter中总会有误报率//因为hash冲突不可能100%避免。//Bloomfilter称这个误判率误报概率,简写为fppBloomFilterbf=BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),total);//将总柱数据初始化到过滤器中for(inti=0;ibfWithFpp=BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),total,0.0001);对于(inti=0;i