什么是布隆过滤器
布隆过滤器（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("好好学技术")); }}