目录
- 介绍
- 特点
- 数据结构
- 新增数据
- 查询数据
- 删除数据
- 作用
- 业务使用
- 快速开始
介绍
布隆过滤器(BloomFilter)是一种数据结构,特点是高效地插入和查询,可以用来告诉你某个key一定不存在或者可能存在,它是用多个哈希函数,将一个key映射到多个数组下标中。
特点
布隆过滤器可以告诉我们 "某样东西一定不存在或者可能存在",也就是说布隆过滤器说这个key不存在则一定不存在,布隆过滤器说这个key存在则可能不存在(会存在误判),利用这个判断是否存在的特点可以做很多有趣的事情。
数据结构
由一串很长的二进制数组向量组成,可以将其看成一个二进制数组。既然是二进制,那么里面存放的不是0,就是1,但是初始默认值都是0。
新增数据
把一个key经过多个hash函数计算出多个数组下标,把计算出的下标的位置的0变成1。
查询数据
当要查询一个key是否在布隆过滤器中,用相同的方法计算出多个1,判断根据这个key计算出的多个1的位置在布隆过滤器中是否都是1,如果都是那么代表可能存在,如果不都是代表一定不存在。
删除数据
布隆过滤器很难进行删除操作。
作用
高效判断一个数据在不在某一组数据中。
误差率: 创建布隆过滤器时,可以设置误差率,误差率越小,hash函数越多,二进制数据占用空间越大。hash函数越多,计算出的hash值多,对应计算出的二进制数组下标越多,效率越低,有一个位置在布隆过滤器中置不为1,就代表不存在,精确度越高。
业务使用
布隆过滤器就是在Redis缓存前面在加一层过滤,负责过滤无效的请求,如果请求没有通过布隆过滤器就不会到缓存和数据库。
布隆过滤器的优点 :
- 空间效率 和 查询效率都远远超过一般的算法。
- 增加和查询元素的时间复杂为O(N)(N为哈希函数的个数,通常情况比较小)。
- 占用空间小,如果允许存在一定的误判,布隆过滤器是非常节省空间。
- 保密性强,布隆过滤器不存储数据本身。
布隆过滤器的缺点: 有点一定的误判率,但是可以通过调整参数来降低。
- 无法获取元素本身。
- 很难删除元素。
快速开始
导入依赖:
<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>28.0-jre</version> </dependency>
配置类:
把布隆过滤器对象注入进IOC容器。
import com.google.common.hash.BloomFilter; import com.google.common.hash.Funnels; import org.springframework.context.annotation.Bean; import org.springframework.context.annotation.Configuration; import java.nio.charset.Charset; @Configuration public class BloomFilterConfig { /** * expectedInsertions:期望添加的数据个数 * fpp:期望的误判率,期望的误判率越低,布隆过滤器计算时间越长 * @return */ @Bean public BloomFilter<String> goodsIDBloom(){ BloomFilter<String> filter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 1000,0.00001); return filter; } @Bean public BloomFilter<String> orderBloom(){ BloomFilter<String> filter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("utf-8")), 1000,0.00001); return filter; } }
启动项目时把所有key插入布隆过滤器:
import com.baomidou.mybatisplus.core.conditions.query.QueryWrapper; import com.google.common.hash.BloomFilter; import com.liu.seckill.entity.SeckillGood; import com.liu.seckill.service.SeckillGoodService; import com.liu.seckill.service.UserService; import lombok.extern.slf4j.Slf4j; import org.springframework.beans.factory.InitializingBean; import org.springframework.beans.factory.annotation.Autowired; import org.springframework.beans.factory.annotation.Qualifier; import org.springframework.context.annotation.Configuration; import org.springframework.data.redis.core.RedisTemplate; import org.springframework.scheduling.annotation.Scheduled; import java.time.Duration; import java.time.LocalDateTime; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.concurrent.TimeUnit; @Slf4j @Configuration public class InitConfig implements InitializingBean { @Autowired UserService userService; @Autowired SeckillGoodService seckillGoodService; @Autowired RedisTemplate redisTemplate; @Autowired RedisConfig redisConfig; @Autowired @Qualifier("goodsIDBloom") BloomFilter<String> goodsIDBloom; /** * 把商品库存加载到 Redis中 * 每天更新 * @throws Exception */ @Override @Scheduled(fixedRate = 1000*60*60*24) public void afterPropertiesSet() throws Exception { //只缓存秒杀还没结束或秒杀还没开始的商品 List<SeckillGood> seckillGoods = seckillGoodService.list(new QueryWrapper<SeckillGood>().ge("end_time", LocalDateTime.now())); if (seckillGoods == null) { log.info("暂无秒杀商品"); return; } //将秒杀商品ID和库存分别存入redis中 List<Long> seckillGoodIDList = new ArrayList<>(); for (SeckillGood seckillGood : seckillGoods) { seckillGoodIDList.add(seckillGood.getSgId()); //设置过期时间 long millis = Duration.between(LocalDateTime.now(), seckillGood.getEndTime()).toMillis(); redisTemplate.opsForValue().set("seckillGoodID:" + seckillGood.getSgId(), seckillGood.getSgStock(), millis, TimeUnit.MILLISECONDS); //存储值到布隆过滤器中 goodsIDBloom.put(seckillGood.getSgId()+""); } redisTemplate.opsForValue().set("seckillGoodIDList:", seckillGoodIDList,1,TimeUnit.DAYS); } }
使用布隆过滤器:
查询redis之前先走布隆过滤器,如果布隆过滤器判断没有则一定没有。
@RestController @RequestMapping("/seckillOrder") public class SeckillOrderController { //如果有多个布隆过滤器,就同时使用@Qualifier和@Autowired @Autowired @Qualifier("goodsIDBloom") BloomFilter<String> goodsIDBloom; @Autowired @Qualifier("orderBloom") BloomFilter<String> orderBloom; @GetMapping("/seckillGoods/{goodId}") public Result seckillGoods(@PathVariable("goodId") Long goodId) { ValueOperations valueOperations = redisTemplate.opsForValue(); //判断秒杀商品是否存在 //如果商品id在布隆过滤器中存在,那么就要再去判断在不在redis中,在,才能证明真的在 if (goodsIDBloom.mightContain(goodId+"")){ ArrayList<Long> seckillGoodIDList = (ArrayList<Long>) valueOperations.get("seckillGoodIDList:"); Assert.isTrue(seckillGoodIDList.contains(goodId),"未找到该商品,商品ID有误或此商品不参与秒杀或此商品秒杀已结束"); }else { Assert.isTrue(false,"未找到该商品,商品ID有误或此商品不参与秒杀或此商品秒杀已结束"); } } }
到此这篇关于Java SpringBoot使用guava的布隆过滤器的文章就介绍到这了,更多相关SpringBoot使用guava 内容请搜索自由互联以前的文章或继续浏览下面的相关文章希望大家以后多多支持自由互联!