当前位置:首页 > 数码 > 深入解析布隆过滤器-概念-实现与应用 (布隆cg)

深入解析布隆过滤器-概念-实现与应用 (布隆cg)

admin8个月前 (04-19)数码24

布隆过滤器(Bloom Filter)是一种空间效率极高的概率型数据结构,用于判断一个元素是否在一个集合中。它基于位数组和多个哈希函数的原理,可以高效地进行元素的查询,而且占用的空间相对较小。

布隆过滤器的执行过程

  1. 将要插入的元素使用多个哈希函数计算出多个哈希值。
  2. 将计算出的多个哈希值映射到一个固定大小的位数组中,并将其对应位置的值设置为 1。
  3. 查询时,对要查找的元素进行相同的哈希计算,并查询哈希值对应的位是否全部为 1。
  4. 如果全部为 1,则说明该元素可能存在于集合中,但不能确定;如果有一个为 0,则说明该元素一定不在集合中。

布隆过滤器的使用场景

布隆过滤器的主要使用场景有以下几个:
  • 集合成员资格测试:快速判断一个元素是否属于一个集合。
  • 去重:在海量数据中快速去重。
  • 缓存预热:预先将可能被查询的数据加载到缓存中。
  • 废品邮件过滤:判断一封邮件是否为废品邮件。

Java 中的使用

在 Java 开发中,可以使用 Guava 中提供的 BloomFilter 类来实现布隆过滤器。

实现方法

以下代码展示了如何使用 Guava 实现布隆过滤器: java import com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels; public class BloomFilterExample { public static void main(String[] args) { // 估计要插入元素的数量 int expectedInsertions = 10000; // 误差率,取值为 0 到 1 之间 double fpp = 0.01; // 创建布隆过滤器 BloomFilter bloomFilter = BloomFilter.create( Funnels.stringFunnel(), expectedInsertions, fpp); // 添加元素到布隆过滤器 bloomFilter.put("element1"); bloomFilter.put("element2"); // 检查元素是否存在 boolean isPresent = bloomFilter.mightContain("element1"); System.out.println(isPresent); // true isPresent = bloomFilter.mightContain("element3"); System.out.println(isPresent); // false } }

使用注意事项

使用布隆过滤器时需要注意以下几点:
  • 误差率不可避免:布隆过滤器是一种概率型数据结构,因此存在误差率。误差率大小取决于插入元素的数量和布隆过滤器的大小。
  • 不可删除元素:一旦将元素添加到布隆过滤器中,就无法将其删除。
  • 空间占用:布隆过滤器需要占用一定的内存空间。空间占用大小取决于插入元素的数量和误差率。

总结

布隆过滤器是一种高效的空间优化数据结构,可以用于快速判断元素是否属于一个集合。在 Java 开发中,可以使用 Guava 中的 BloomFilter 类来实现布隆过滤器。在使用时需要注意误差率不可避免、不可删除元素和空间占用等注意事项。

布隆过滤器

如果使用哈希表,内存空间需要100亿*64字节=640G(10亿字节(byte)是1G),空间就爆掉了。此时就轮到布隆过滤器登场了。

布隆过滤器应用场景:黑名单 爬虫去重 布隆过滤器优势:节省内存(30G以内),查询速度快 布隆过滤器劣势:存在一定失误率

但布隆过滤器的失误率是可以容忍的,一是可以通过设计人为的把失误率控制的很低;二是就算失误了不会误报已经在黑名单里的URL。布隆过滤器只会把正常的URL当成黑名单系统里的,但不会误报已经在黑名单里的URL。形象点说就是“宁可错杀三千不会放过一个”

在讲解布隆过滤器原理之前先讲位图。 位图是bit类型的数组。 int类型4字节即32bit,所以长度100的int类型数组可以看出长度3200的bit数组。假如要找1782位比特,那么在int数组里下标是1782/32,在下标里存的int数字里第几个比特位?即1782%32的计算结果,从而把整型数组操作转换成比特类型数组操作。

布隆过滤器即大位图,假设是长度为m的bit数组,那么占用m/8位字节(Byte), URL加黑名单过程:开始时m位比特都是0(白)的状态,该URL通过哈希函数f1得到一个哈希值,然后%m,得到0~m-1上某个位置,将该位置描黑(变成1),再用哈希函数f2得到一个哈希值,再描黑,再用哈希函数f3同样处理(f1、f2、f3是独立的哈希函数),假设一共用了k个哈希函数,那么描黑了k个位置(某个位置重复了就重复了,但一旦描黑就没有描白的时候)完成后可以说该URL加入了位图里。对下一个URL同样处理,用k个哈希函数描黑k个位置……一直做100亿个,位图中有相当多位置被描黑了。 如何查某个URL在不在黑名单里?把待查的URL用K个哈希函数算出对应的哈希值,再把该哈希值%m,把K个位置的状态都拿出来,如果全黑,就说这个URL属于黑名单系统,如果有一个是白,就不属于黑名单系统。如果m很小,100亿个URL之后所有位图都是黑的,那么不论查谁都在黑名单里;如果m取的大一些,失误率就会降低。 但布隆过滤器需要准备多少个bit位和单样本的大小无关。一个URL经过K个哈希函数得到K个哈希值,对m取模后去相应的大比特map中描黑,只要保证哈希函数能接收单样本这种类型的参数就可以了,与样本是64字节还是128字节无关。所以影响失误率的重要参数就是样本量N和位图比特数组长度m。 布隆过滤器三公式: 出处 1.确定m:对于输入的数据量n(这里是100亿)和失误率p(这里是万分之一),布隆过滤器的大小m:m = - (n lnp) / (ln2 ln2) 2.确定K:K假如很少,例如只有一个哈希函数,相当于每个数据只采集了一个特征点,只把一个位置描黑,查的时候也只用一个哈希函数,特征点不够,失误率虽然不至于很高但有一定的量,如果K很大,例如用10万个哈希函数去把10万个位置描黑,m的空间会接近耗尽,查什么URL都是黑的,失误率非常高。需要的哈希函数的个数k:k = ln2 * m/n = 0.7 * m/n 3.因为前两步中公式1公式2都会进行向上取整,所以公式3算出的实际的失误率与比预期失误率要低

布隆过滤器在Hadoop中的应用:Hadoop中的分布式文件系统,是由许多小文件组成的,如何查询一个数据在哪个文件里?首先不可能记录每个小文件的索引,这样做占用空间太大了。所以每个小文件里都搞一个布隆过滤器,当Hadoop想知道某个key在哪个文件里,就查每一个布隆过滤器,文件a的布隆过滤器会说明你这个key在我这个文件里,但可能会有误报;文件c的布隆过滤器会说明你这个key在我这个文件里,但可能会有误报……如果失误率很低,哪怕有几万个分布式文件,最终可能算出来只有3个文件里可能含有这个key。那么就只用把这3个小文件遍历一遍,就知道key在哪个小文件里了。通俗点讲,如果一个文件真的含有key,那么它的布隆过滤器会说这个key属于我;但因为有失误率,可能会发生一个文件不含有这个key,它还是会说这个key属于我;可是这也没关系,多查一遍就可以,反正失误率很低,需要遍历的文件很少。

布隆cg

布隆过滤器(Bloom Filter)与比特币

布隆过滤器(Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合。它的优点是空间效率和查询时间都比一般的算法要好得多,缺点是有一定的误识别率和删除困难。

如果想要判断一个元素是否在一个集合里,一般想到的是将所有元素保存起来,然后通过比较确定。数组、链表、树等数据结构都是这种思路,它们的时间复杂度为(O(n)、O(logn))。散列表是一个能够提供更快查询速度的数据结构(时间复杂度为O(1))。但是随着集合中元素的增加,我们需要的存储空间越来越大,特别是随着大数据的发展,我们越来越不可能将所有的数据都先加载到内存中再进行查找。 这时,我们就可以借助一种新的数据结构,也就是本文的主题:布隆过滤器(Bloom Filter)。 我们使用一段长度为m的二进制位数组,再使用k个哈希函数,将一个值进行k次哈希,得到k个索引,并将对应的位置设置为1。

布隆过滤器主要提供两种方法:Add和Test。 Add:通过哈希函数计算,得到k个索引,并将其对应的二进制位设置为1。 Test:通过哈希函数计算,得到k个索引,判断如果任意位置上的二进制都为0,则表示该值一定不在集合中;但是如果所有位置上的二进制都为1,却并不能表示该值一定在集合中,这被称为假阳性,或是判断错误。 可以通过增大数组的长度m,以及增加哈希函数的数量k来降低假阳性的概率。

时间复杂度 由于需要计算k次的哈希,需要的时间复杂度为O(k),而计算出对应的索引后,可以进行直接地址访问,需要的时间复杂度为O(1),所以总的时间复杂度为O(k)。

空间复杂度 由于需要长度为m的二进制数据,所以空间复杂度为O(m),但是由于数据的基本单位是位,假设为了处理100万条数据,为了降低假阳性的概率,我们使用长度为1000万的二进制数组,所需的内存空间为10,000,000/8/1024/1024=1.2M内存空间。

优点

缺点

免责声明:本文转载或采集自网络,版权归原作者所有。本网站刊发此文旨在传递更多信息,并不代表本网赞同其观点和对其真实性负责。如涉及版权、内容等问题,请联系本网,我们将在第一时间删除。同时,本网站不对所刊发内容的准确性、真实性、完整性、及时性、原创性等进行保证,请读者仅作参考,并请自行核实相关内容。对于因使用或依赖本文内容所产生的任何直接或间接损失,本网站不承担任何责任。

标签: 布隆过滤器