1.什么是布隆过滤器
布隆过滤器：一种数据结构，是由一串很长的二进制向量组成，可以将其看成一个二进制数组。既然是二进制，那么里面存放的不是0，就是1，但是初始默认值都是0。当布隆过滤器说，某种东西存在时，这种东西可能不存在；当布隆过滤器说，某种东西不存在时，那么这种东西一定不存在。
布隆过滤器.png
添加数据
当要向布隆过滤器中添加一个元素key时，我们通过多个hash函数，算出一个值，然后将这个值所在的方格置为1。
比如，下图hash1(key)=1，那么在第2个格子将0变为1（数组是从0开始计数的），hash2(key)=5，那么将第6个格子置位1，依次类推。
bitmap.png
判断数据是否存在？
知道了如何向布隆过滤器中添加一个数据，那么新来一个数据，我们如何判断其是否存在于这个布隆过滤器中呢？
很简单，我们只需要将这个新的数据通过上面自定义的几个哈希函数，分别算出各个值，然后看其对应的地方是否都是1，如果存在一个不是1的情况，那么我们可以说，该新数据一定不存在于这个布隆过滤器中。
反过来说，如果通过哈希函数算出来的值，对应的地方都是1，那么我们能够肯定的得出：这个数据一定存在于这个布隆过滤器中吗？
答案是否定的，因为多个不同的数据通过hash函数算出来的结果是会有重复的，所以会存在某个位置是别的数据通过hash函数置为的1。
我们可以得到一个结论：布隆过滤器可以判断某个数据一定不存在，但是无法判断一定存在。
2.redis中使用布隆过滤器
1.设置值
setbit key offset value
设置值
2.获取值
getbit key offset
获取值
3.布隆过滤器使用场景
比如有如下几个需求：
1.系统原本有10亿条数据，现在又来了10万条，要快速准确判断这10万条数据是否在10亿条数据中。
解决办法一：将10亿条数据存入数据库中，进行数据库查询，准确性有了，但是速度会比较慢。
解决办法二：将10亿条数据放入内存中，比如Redis缓存中，这里我们算一下占用内存大小：10亿*8字节=8GB，通过内存查询，准确性和速度都有了，但是大约8gb的内存空间，挺浪费内存空间的。
2.缓存宕机、缓存击穿场景，一般判断用户是否在缓存中，如果在则直接返回结果，不在则查询db，如果来一波冷数据，会导致缓存大量击穿，造成雪崩效应，这时候可以用布隆过滤器当缓存的索引，只有在布隆过滤器中，才去查询缓存，如果没查询到，则穿透到db。如果不在布隆器中，则直接返回。
3.WEB拦截器，如果相同请求则拦截，防止重复被攻击。用户第一次请求，将请求参数放入布隆过滤器中，当第二次请求时，先判断请求参数是否被布隆过滤器命中。可以提高缓存命中率。
那么对于类似这种，大数据量集合，如何准确快速的判断某个数据是否在大数据量集合中，并且不占用内存，布隆过滤器应运而生了。
java中使用布隆过滤器
pom.xml
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson</artifactId>
<version>3.11.4</version>
</dependency>
java代码
public class RedisBloomDemo {
public static void main(String[] args) {
// redisson配置
Config config = new Config();
// redis地址
config.useSingleServer().setAddress("redis://127.0.0.1:6379");
// redis默认没有密码
// 构造Redisson
RedissonClient redisson = Redisson.create(config);
RBloomFilter<String> bloomFilter = redisson.getBloomFilter("phones");
// 初始化布隆过滤器：预计元素为100000000L,误差率为3%
bloomFilter.tryInit(100000000L,0.03);
// 将号码10086插入到布隆过滤器中
bloomFilter.add("10086");
// 判断下面号码是否在布隆过滤器中
System.out.println("存在123456 ？" + bloomFilter.contains("123456"));// false
System.out.println("存在10086 ？" + bloomFilter.contains("10086"));// true
// 关闭redisson
redisson.shutdown();
}
}
网友评论