当前位置 : 主页 > 编程语言 > java >

图解布隆过滤器,十分钟带你理解什么是布隆过滤器

来源:互联网 收集:自由互联 发布时间:2023-03-22
之前我们介绍Redis入门系列课程的时候,讲了Redis的缓存雪崩、穿透、击穿。在文章里我们说了解决缓存穿透的办法之一,就是使用布隆过滤器,但是由于并没有详细介绍什么是布隆过滤

之前我们介绍Redis入门系列课程的时候,讲了Redis的缓存雪崩、穿透、击穿。在文章里我们说了解决缓存穿透的办法之一,就是使用布隆过滤器,但是由于并没有详细介绍什么是布隆过滤器,所以就有很多小伙伴问我——到底什么是布隆过滤器?

那么接下来就来给大家介绍什么是布隆过滤器以及他的实现原理。

一、什么是布隆过滤器?

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

其实说白了,布隆过滤器就是一种节省空间的概率数据结构,通过使用很数组和一些列随机映射函数。用于判断一个元素是否在一个集合中,0代表不存在某个数据,1代表存在某个数据。

图解布隆过滤器,十分钟带你理解什么是布隆过滤器_实现原理

二、布隆过滤器的优缺点

2.1优点

相比于其它的数据结构,布隆过滤器在空间和时间方面都有巨大的优势。

  • 布隆过滤器存储空间和插入/查询时间都是常数(即hash函数的个数);
  • Hash 函数相互之间没有关系,方便由硬件并行实现;
  • 布隆过滤器不需要存储元素本身,在某些对保密要求非常严格的场合有优势;
  • 布隆过滤器可以表示全集,其它任何数据结构都不能;

2.2缺点

布隆过滤器的缺点和优点一样明显:

  • 误算率(False Positive)是其中之一。随着存入的元素数量增加,误算率随之增加(误判补救方法是:再建立一个小的白名单,存储那些可能被误判的信息)。但是如果元素数量太少,则使用散列表足矣。
  • 一般情况下不能从布隆过滤器中删除元素。我们很容易想到把位列阵变成整数数组,每插入一个元素相应的计数器加 1, 这样删除元素时将计数器减掉就可以了。然而要保证安全的删除元素并非如此简单。首先我们必须保证删除的元素的确在布隆过滤器里面. 这一点单凭这个过滤器是无法保证的。另外计数器回绕也会造成问题。

三、布隆过滤器的使用场景

利用布隆过滤器减少磁盘 IO 或者网络请求,因为一旦一个值必定不存在的话,就可以直接结束查询,比如以下场景:

  • 大数据去重,比如判断一个数字是否存在于包含大量数字的数字集中(数字集很大,5 亿以上!);
  • 网页爬虫对 URL 的去重,避免爬取相同的 URL 地址;
  • 反垃圾邮件,从数十亿个垃圾邮件列表中判断某邮箱是否垃圾邮箱;
  • 缓存击穿,将已存在的缓存放到布隆过滤器中,当黑客频繁访问不存在的缓存时迅速返回避免缓存及数据库挂掉;

图解布隆过滤器,十分钟带你理解什么是布隆过滤器_数组_02

四、布隆过滤器实现原理

4.1数据结构

布隆过滤器是一个基于数组和哈希函数散列元素的结构,很像HashMap的哈希桶。它可以用于检测一个元素是否在集合中。它的优点是空间效率和查询时间比一般算法要好很多,缺点是有一定概率的误判性,如HashMap出现哈希碰撞。

图解布隆过滤器,十分钟带你理解什么是布隆过滤器_数组_03

4.2实现原理

(1)存入过程

布隆过滤器的核心就是一个二进制数据的集合和hash计算函数。当一个元素加入布隆过滤器中的时会进行如下操作:

1.使用布隆过滤器中的哈希函数对元素值进行计算,返回对应的哈希值(一般有几个哈希函数得到几个哈希值);

2.根据返回的hash值映射到对应的二进制集合的下标;

3.将下标对应的二进制数据改成1;

图解布隆过滤器,十分钟带你理解什么是布隆过滤器_数组_04

如上图所示,三个Hash函数计算key值“test”的hash值分别为2、5、9;那么就会把集合中2、5、9下标对应的数据改成1。

(2)判断是否存在

当我们需要判断一个元素是否存在于布隆过滤器的时候,会进行如下操作:

1.对给定元素再次进行相同的哈希计算;

2.根据返回的hash值判断位数组中对应的元素是否都为 1,如果值都为 1,那么说明这个值在布隆过滤器中,如果存在一个值不为 1,则说明该元素不在布隆过滤器中。

图解布隆过滤器,十分钟带你理解什么是布隆过滤器_布隆过滤器_05

从上图可以看到,元素“test”通过哈希函数计算,得到下标为 2、5、9 这 3个数据。虽然前两个点都为 1,但是很明显第 3 个点得到的数据为0,说明元素不在集合中。

五、布隆过滤器实现

目前市面上有很多实现布隆过滤器的方式,比如Google的GUAVA实现,还有Redis的插件RedisBloom等。接下来,我们简单实现一个布隆过滤器算法。需要注意的是,我这里的示例是为了演示布隆过滤器的实现原理的简单实现,实际上完善的布隆过滤器的算法还是比较复杂的,包括误判率,哈希计算方式等。

1. 构建集合

根据之前介绍的布隆过滤器的实现原理,布隆过滤器的实现主要包括可以存放二进制元素的 BitSet 以及多样性的哈希计算函数。下面通过示例演示布隆过滤器的实现。

public class MyBloomFilter { /** * 位数组的大小 */ private static final int DEFAULT_SIZE = 2 << 24; /** * 位数组。数组中的元素只能是 0 或者 1 */ private BitSet bits = new BitSet(DEFAULT_SIZE); /** * 通过这个数组可以创建 3 个不同的哈希函数 */ private static final int[] SEEDS = new int[]{3, 13, 46}; /** * 存放包含 hash 函数的类的数组 */ private SimpleHash[] func = new SimpleHash[SEEDS.length]; /** * 初始化多个包含 hash 函数的类的数组,每个类中的 hash 函数都不一样 */ public MyBloomFilter() { // 初始化多个不同的 Hash 函数 for (int i = 0; i < SEEDS.length; i++) { func[i] = new SimpleHash(DEFAULT_SIZE, SEEDS[i]); } }}

所有的元素存放都经过多样的哈希计算存放到 BitSet 中,这样可以尽可能的分散元素,减少误判性。

2. 哈希函数

这里只是提供了一种哈希计算的方式,实际可以实现多种不同的hash计算方式,每一个哈希计算都是一次扰动处理。一个元素的存放可以经过多次哈希,尽量让元素值做到散列,从而避免hash碰撞。

/** * 静态内部类。用于 hash 操作! */ public static class SimpleHash { private int cap; private int seed; public SimpleHash(int cap, int seed) { this.cap = cap; this.seed = seed; } /** * 计算 hash 值 */ public int hash(Object value) { int h; return (value == null) ? 0 : Math.abs(seed * (cap - 1) & ((h = value.hashCode()) ^ (h >>> 16))); } }

3. 添加元素

添加元素就是当某个元素不在集合中时,我们使用布隆过滤器中的哈希函数对元素值进行计算得到哈希值,然后根据返回的哈希值,将集合数组中把对应下标的值置为 1。具体代码如下:

/** * 添加元素到位数组 */ public void add(Object value) { for (SimpleHash f : func) { bits.set(f.hash(value), true); } }

4. 比对元素

比对元素就是判断某个元素是否存在。我们对该元素进行哈希计算,然后通过哈希值获取集合中的数据,最后把这些哈希值 进行&& 计算,从而确定该元素是否存在。具体代码如下:

/** * 判断指定元素是否存在于位数组 */ public boolean contains(Object value) { boolean ret = true; for (SimpleHash f : func) { ret = ret && bits.get(f.hash(value)); } return ret; }

这里使用多个集合中的bit位置记录同一个元素的状态,确保结果更加准确,避免hash碰撞。

5. 验证测试

接下来我们创建一个测试类,验证布隆过滤器是否生效。示例代码如下:

public class MyBloomFilterTest { public static void main(String[] args) { String value1 = "com:weiz:user:logininfo"; String value2 = "https://www.cnblogs.com/zhangweizhong"; String value3 = "200110221"; MyBloomFilter filter = new MyBloomFilter(); filter.add(value1); filter.add(value2); System.out.println("key:" + value1 +"是否存在:"+ filter.contains(value1)); System.out.println("key:" + value2 +"是否存在:"+ filter.contains(value2)); System.out.println("key:" + value3 +"是否存在:"+ filter.contains(value3)); }}

运行上面的测试代码,验证布隆过滤器算法是否正常,具体结果如下图所示:

图解布隆过滤器,十分钟带你理解什么是布隆过滤器_布隆过滤器_06

通过上面的输出结果可以看到,value1和value2已经添加到布隆过滤器,返回结果为true,而value3未加入到布隆过滤器,所以返回false。说明布隆过滤器起到了数据过滤的作用。

五、常见面试题

1.布隆过滤器的使用场景?

(1)解决Redis缓存穿透

(2)在爬虫时,对爬虫网址进行过滤,已经存在布隆中的网址,不在爬取。

(3)垃圾邮件过滤,对每一个发送邮件的地址进行判断是否在布隆的黑名单中,如果在就判断为垃圾邮件。

2.布隆过滤器的实现原理和方式?

参照上面讲的布隆过滤器原理。

3.如何提高布隆过滤器的准确性?

使用更大的集合和同时用多个不同的hash函数计算方式。

4.你了解哪些类型的布隆过滤器实现?

(1)Google 开源的 Guava 中自带的布隆过滤器;

(2)Redis 中的布隆过滤器插件RedisBloom;

最后

以上,我们就把布隆过滤器的原理介绍完了,布隆过滤器的原理还是比较简单的,但是要实现真正的布隆过滤器算法,还需要考虑很多其他的问题:如误判率等。感兴趣的朋友可以深入研究。

网友评论