什么是布隆过滤器
布隆过滤器（Bloom Filter）是 1970 年由布隆提出来的。 它实际上是由一个很长的二进制数组+一系列 hash 算法映射函数，用于判断一个元素是否存在于集合中。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
场景
假设有 10 亿条手机号，然后判断某条手机号是否在列表内？
mysql 可以吗？
正常情况下，如果数据量不大，我们可以考虑使用 mysql 存储。将所有数据存储到数据库，然后每次去库里查询判断是否存在。但是如果数据量太大，超过千万，mysql 查询效率是很低的，特别消耗性能。
HashSet 可以吗
我们可以把数据放入 HashSet 中，利用 HashSet 天然的去重性，查询只需要调用 contains 方法即可，但是 hashset 是存放在内存中的，数据量过大内存直接 oom 了。
布隆过滤器特点
插入和查询效率高，占用空间少，但是返回的结果是不确定的。
一个元素如果判断为存在的时候，它不一定真的存在。但是如果判断一个元素不存在，那么它一定是不存在的。
布隆过滤器可以添加元素，但是一定不能删除元素，会导致误判率增加。
布隆过滤器原理
布隆过滤器其实就是是一个 BIT 数组，通过一系列 hash 算法映射出对应的 hash,然后将 hash 对应的数组下标位置改为 1。查询时就是对数据在进行一系列 hash 算法得到下标，从 BIT 数组里取数据如如果是 1 则说明数据有可能存在，如果是 0 说明一定不存在
为什么会有误差率
我们知道布隆过滤器其实是对数据做 hash,那么不管用什么算法，都有可能两条不同的数据生成的 hash 确是相同的，也就是我们常说的 hash 冲突。
首先插入一条数据： 好好学技术
再插入一条数据：
这是如果查询一条数据，假设他的 hash 下标已经标为 1 了，那么布隆过滤器就会认为他存在
常见使用场景
缓存穿透
java 实现布隆过滤器
package com.fandf.test.redis;
import java.util.BitSet;
/** * java布隆过滤器 * * @author fandongfeng */public class MyBloomFilter {
/** * 位数组大小 */ private static final int DEFAULT_SIZE = 2 << 24;
/** * 通过这个数组创建多个Hash函数 */ private static final int[] SEEDS = new int[]{4, 8, 16, 32, 64, 128, 256};
/** * 初始化位数组，数组中的元素只能是 0 或者 1 */ private final BitSet bits = new BitSet(DEFAULT_SIZE);
/** * Hash函数数组 */ private final MyHash[] myHashes = new MyHash[SEEDS.length];
/** * 初始化多个包含 Hash 函数的类数组，每个类中的 Hash 函数都不一样 */ public MyBloomFilter() { // 初始化多个不同的 Hash 函数 for (int i = 0; i < SEEDS.length; i++) { myHashes[i] = new MyHash(DEFAULT_SIZE, SEEDS[i]); } }
/** * 添加元素到位数组 */ public void add(Object value) { for (MyHash myHash : myHashes) { bits.set(myHash.hash(value), true); } }
/** * 判断指定元素是否存在于位数组 */ public boolean contains(Object value) { boolean result = true; for (MyHash myHash : myHashes) { result = result && bits.get(myHash.hash(value)); } return result; }
/** * 自定义 Hash 函数 */ private class MyHash { private int cap; private int seed;
MyHash(int cap, int seed) { this.cap = cap; this.seed = seed; }
/** * 计算 Hash 值 */ int hash(Object obj) { return (obj == null) ? 0 : Math.abs(seed * (cap - 1) & (obj.hashCode() ^ (obj.hashCode() >>> 16))); } }
public static void main(String[] args) { String str = "好好学技术"; MyBloomFilter myBloomFilter = new MyBloomFilter(); System.out.println("str是否存在：" + myBloomFilter.contains(str)); myBloomFilter.add(str); System.out.println("str是否存在：" + myBloomFilter.contains(str)); }
}
复制代码
Guava 实现布隆过滤器
引入依赖
<dependency> <groupId>com.google.guava</groupId> <artifactId>guava</artifactId> <version>31.1-jre</version></dependency>
复制代码
package com.fandf.test.redis;
import com.google.common.base.Charsets;import com.google.common.hash.BloomFilter;import com.google.common.hash.Funnels;
/** * @author fandongfeng */public class GuavaBloomFilter {
public static void main(String[] args) { BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),100000,0.01); bloomFilter.put("好好学技术"); System.out.println(bloomFilter.mightContain("不好好学技术")); System.out.println(bloomFilter.mightContain("好好学技术")); }}
复制代码
hutool 实现布隆过滤器
引入依赖
<dependency> <groupId>cn.hutool</groupId> <artifactId>hutool-all</artifactId> <version>5.8.3</version></dependency>
复制代码
package com.fandf.test.redis;
import cn.hutool.bloomfilter.BitMapBloomFilter;import cn.hutool.bloomfilter.BloomFilterUtil;
/** * @author fandongfeng */public class HutoolBloomFilter { public static void main(String[] args) { BitMapBloomFilter bloomFilter = BloomFilterUtil.createBitMap(1000); bloomFilter.add("好好学技术"); System.out.println(bloomFilter.contains("不好好学技术")); System.out.println(bloomFilter.contains("好好学技术")); }
}
复制代码
Redisson 实现布隆过滤器
引入依赖
<dependency> <groupId>org.redisson</groupId> <artifactId>redisson</artifactId> <version>3.20.0</version></dependency>
复制代码
package com.fandf.test.redis;
import org.redisson.Redisson;import org.redisson.api.RBloomFilter;import org.redisson.api.RedissonClient;import org.redisson.config.Config;
/** * Redisson 实现布隆过滤器 * @author fandongfeng */public class RedissonBloomFilter {
public static void main(String[] args) { Config config = new Config(); config.useSingleServer().setAddress("redis://127.0.0.1:6379"); //构造Redisson RedissonClient redisson = Redisson.create(config);
RBloomFilter<String> bloomFilter = redisson.getBloomFilter("name"); //初始化布隆过滤器：预计元素为100000000L,误差率为1% bloomFilter.tryInit(100000000L,0.01); bloomFilter.add("好好学技术");
System.out.println(bloomFilter.contains("不好好学技术")); System.out.println(bloomFilter.contains("好好学技术")); }}
复制代码
评论