赞
踩
目录
布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的,是一种数据结构。它实际上是一个很长的二进制向量和一系列随机映射函数。
布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是高效的插入和查询,而且非常节省空间,缺点是hash 碰撞造成的误识别率和删除困难。
一般使用较多的场景就是避免缓存穿透,具体场景就是在使用 Reids 做数据缓存的时候,很有可能会遇到一个问题:用户想要查询一个数据,发现 redis 缓存没有命中,于是向数据库查询。发现也没有,于是本次查询失败。当用户很多的时候,缓存都没有命中,于是都去请求数据库。这会给数据库造成很大的压力,这时候就相当于出现了缓存穿透。缓存穿透也是实际开发中必须要避免和提前预防的内容之一。
避免缓存穿透,有以下几种解决方案:
1、缓存空值。为了解决这个问题呢,通常我们可以向分布式缓存中写入一个过期时间较短的空值占位,但这样会占用较多的存储空间,性价比不足。
2、使用 HashMap。将需要查询的 key 提前加载到 HashMap 中,因为 HashMap 查找的时间复杂度为 O(1) ,因此通过映射可以快速查找到相应的 Key 来判定 Key 是否存在 ,如果查不出来就没必要继续查找缓存了。但是这样做的话极其消耗宝贵的内存,数据量大的情况下成本也会上升。此种做法会对内容造成不可测的负担,不推荐使用。
3、使用 Bloom Filter。原理上和使用 HashMap 一样,但更省空间。此种做法为主流做法,推荐使用布隆过滤器。
布隆过滤器的原理:当一个元素被加入集合时,通过 K 个散列函数将这个元素映射成一个位数组中的 K 个点,把它们置为 1。检索时,我们只要看看这些点是不是都是 1 就(大约)知道集合中有没有它了:如果这些点有任何一个 0,则被检元素一定不在;如果都是 1,则被检元素很可能在。
简单来说就是准备一个长度为 m 的位数组并初始化所有元素为 0,用 k 个散列函数对元素进行 k 次散列运算跟 len (m) 取余得到 k 个位置并将 m 中对应位置设置为 1。
如上图,位数组的长度是8,散列函数个数是 3,先后存入两个元素x,y。这两个元素都经过三次哈希函数生成三个哈希值,并映射到位数组的不同的位置,并置为1。元素 x 映射到位数组的第0位,第4位,第7位,元素y映射到数组的位数组的第1位,第4位,第6位。
保存元素 x 后,位数组的第4位被设置为1之后,在处理元素 y 时第4位会被覆盖,同样也会设置为 1。
当布隆过滤器保存的元素越多,被置为 1 的 bit 位也会越来越多,元素 x 即便没有存储过,假设哈希函数映射到位数组的三个位都被其他值设置为 1 了,对于布隆过滤器的机制来讲,元素 x 这个值也是存在的,也就是说布隆过滤器存在一定的误判率。
若位数组长度太小则会导致所有 bit 位很快都会被置为 1 ,那么检索任意值都会返回”可能存在“ , 起不到过滤的效果。位数组长度越大,则误判率越小。
同时,哈希函数的个数也需要考量,哈希函数的个数越大,检索的速度会越慢,误判率也越小,反之,则误判率越高。相同位数组长度的情况下,随着哈希函数的个人的增长,误判率显著的下降。
布隆过滤器支持删除吗
布隆过滤器其实并不支持删除元素,因为多个元素可能哈希到一个布隆过滤器的同一个位置,如果直接删除该位置的元素,则会影响其他元素的判断。但我们可以通过计数布隆过滤器(不推荐)和定时重新构建布隆过滤器两种方案实现删除元素的效果。
添加Maven依赖
- <dependency>
- <groupId>com.google.guava</groupId>
- <artifactId>guava</artifactId>
- <version>22.0</version>
- </dependency>
- package com.cjian.boomfilter;
-
- import com.google.common.hash.BloomFilter;
- import com.google.common.hash.Funnels;
-
- import java.nio.charset.StandardCharsets;
-
- /**
- * @Author: cjian
- * @Date: 2023/4/20 11:53
- * @Des:
- */
- public class Demo {
- static BloomFilter<String> filter;
-
- static {
- filter = BloomFilter.create(
- //Funnel 是一个接口,用于将任意类型的对象转换为字节流,
- //以便用于布隆过滤器的哈希计算。
- Funnels.stringFunnel(StandardCharsets.ISO_8859_1),
- 10000, // 插入数据条目数量
- 0.001 // 误判率
- );
- addDate();
- }
-
- public static void main(String[] args) {
- System.out.println(mayContain("aaa"));
- System.out.println(mayContain("bbb"));
- }
-
- private static void addDate() {
- System.out.println("初始化布隆过滤器数据开始");
- //插入2个元素
- filter.put("aaa");
- filter.put("bbb");
- System.out.println("初始化布隆过滤器数据结束");
- }
-
- public static boolean mayContain(String id) {
- return filter.mightContain(id);
- }
- }
添加Maven依赖
- <dependency>
- <groupId>org.redisson</groupId>
- <artifactId>redisson</artifactId>
- <version>3.16.1</version>
- </dependency>
- package com.cjian.boomfilter;
-
- import org.redisson.Redisson;
- import org.redisson.api.RBloomFilter;
- import org.redisson.api.RedissonClient;
- import org.redisson.config.Config;
-
- /**
- * @Author: cjian
- * @Date: 2023/4/20 13:54
- * @Des:
- */
- public class RedissonDemo {
- static RBloomFilter<String> bloomFilter;
-
- static {
- Config config = new Config();
- config.useSingleServer().setAddress("redis://localhost:6379");
- bloomFilter = Redisson.create(config).getBloomFilter("myBloomFilter");
- }
-
- public static void main(String[] args) {
- init();
- System.out.println(mightContain("aaaa"));
- System.out.println(mightContain("bbbb"));
- }
-
- private static void init() {
- //10000表示插入元素的个数,0.001表示误判率
- bloomFilter.tryInit(10000, 0.001);
- //插入2个元素
- bloomFilter.add("aaaa");
- bloomFilter.add("bbbb");
- }
-
- private static boolean mightContain(String id) {
- return bloomFilter.contains(id);
- }
- }
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。