Page 1 of 1

【通用】布隆过滤器的原理和使用

Posted: 2022年 Dec 16日 18:03
by xuyuan

场景

如果有场景需要判断一个集合中某个值是否存在时,你第一时间想到的是怎么实现?

比较直接能想到的是使用hash表,即在判断之前对每个值进行哈希处理,将值存放到列表中对应的索引位置,查找时就能通过对目标值的哈希处理就能快速定位是否存在。

但是这个方法有个弊端,内存消耗随数据量和每条数据大小呈现线性增长
假设共有1亿条长度为10的字符串数据,每条数据20字节,考虑哈希冲突,哈希表存储效率通常小于50%,因此消耗的内存:20 * 2 * 1亿 字节 = 4G 内存

这个时候就需要布隆过滤器
由1970年巴顿.布隆提出的数据结构。用于检索一个元素是否在一个集合中,判是存在一定误差。但它的空间效率比哈希表要高出很多。

原理

简单来说,它包含一个很长的二进制向量和一系列随机映射函数。(本篇只介绍简单版本的布隆过滤器)

一个空的布隆过滤器有长度为M比特的bit数组构成,且所有位都初始化0。同时有K个不同的hash函数,每一个都可以将元素映射到bit数组的某一位上,形成一个总体的随机分布。K必须远小于M,且K和M的大小由错误率(false positive rate)决定。
每添加一个元素,由这K个hash函数映射到K个位置,设置这些位为1。
查找一个元素是否在集合中,也是由这K个hash函数映射到K个位置,只要有一个位不为1,则元素一定不存在;但是,全部位都为1,不能代表元素一定存在,可能是其他元素的插入导致,布隆过滤器的误差就来源于此。
那移除元素呢?很显然,既然我们都无法确定一个元素一定存在,也就无法移除元素。

下图示是一个m=18,k=3的布隆过滤器。

布隆过滤器示例.png

为什么说它空间利用率高?
不保存元素值。一个误差率1%且K是最佳数量的布隆过滤器,每多一个元素大约只需要多9.6 bit,且无视元素大小。1亿条数据也只需要1G不到的内存,对比hash表方式,节省不少空间。

如何确定hash函数的数量和二进制数组的长度?
数学推导结果误差率ε:

误差率计算公式.png
  • n 是已经添加元素的数量;

  • k 哈希的次数;

  • m 布隆过滤器的长度(如比特数组的大小)

为了得到尽量小的误差率

误差率最小.png

那么,布隆过滤器的长度 m 可以根据给定的误判率ε 和期望添加的元素个数 n 的通过如下公式计算:

布隆过滤器长度公式.png

即k和ε的关系(忽略整数要求)

关系.png

实际使用中,给定一个期望的误判率ε,可以算出相应的最佳hash函数数量K;而布隆过滤器的长度则还与期望插入的元素数量正正比。

使用场景
现在如果有需求是只需要判断一个值在一个大集合里存不存在,且不需要100%的精确度时(比如有兜底确认),我们就可以考虑使用布隆过滤器来实现。

比如以下场景:

  • 缓解缓存穿透

  • 网页 URL 去重

  • 垃圾邮件识别

  • 大集合中重复元素的判断

项目实际运用

基于内存
布隆过滤器有很多实现和优化,由 Google 开发著名的 Guava 库就提供了布隆过滤器(Bloom Filter)的实现。

引入

Code: Select all

<dependency>
   <groupId>com.google.guava</groupId>
   <artifactId>guava</artifactId>
   <version>{guava.version}</version>
</dependency>

com.google.common.hash.BloomFilter

初始化参数
1、将目标对象转化为数组的函数对象
com.google.common.hash.Funnels 内有常用的实现
2、期望插入数量
和误判率一起用来计算最佳的二进制数组长度

Code: Select all

 (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2))) 

3、期望误判率,默认是3%
用于计算最佳hash函数数量

Code: Select all

Math.max(1, (int) Math.round((double) m / n * Math.log(2)))

插入元素方法:put(T Object)

判断元素是否存在方法:mightContain(T Object)

缺点:每次应用重启后都需要重新构建

基于Redis

最终需要存储的无非是一个bit数组,那就可以用redis的bitmap来存储,模仿guava来实现。

参考资料:
维基百科
https://en.wikipedia.org/wiki/Bloom_fil ... %20details

掘金
https://juejin.cn/post/6844904007790673933


Re: 布隆过滤器的原理和使用

Posted: 2022年 Dec 16日 18:17
by G.T

NewBee