什么是布隆过滤器布隆过滤器（BloomFilter）是布卢姆在1970年提出的，它实际上是由一个很长的二进制数组+一系列的哈希算法映射函数组成，用来判断一个元素是否存在于集合中.布隆过滤器可用于检索元素是否在集合中。它的优点是空间效率和查询时间都比一般算法好很多，缺点是存在一定的误识别率和删除难度。场景假设有10亿个手机号码，然后判断某个手机号码是否在列表中？mysql可以吗？一般情况下，如果数据量不大，我们可以考虑使用mysql存储。把所有的数据存到数据库里，然后每次去图书馆查查是否存在。但是如果数据量太大，超过几千万，mysql的查询效率很低，性能消耗很大。HashSet可以吗？我们可以把数据放到HashSet中，利用HashSet天然的去重。查询只需要调用contains方法，hashset是保存在内存中的。如果数据量太大，内存会直接OOD。布隆过滤器插入查询效率高，占用空间小，但返回结果不确定。当一个元素被判断存在时，它不一定存在。但是如果判断一个元素不存在，那么它一定不存在。布隆过滤器可以添加元素，但绝对不能删除元素，这样会增加误报率。Bloomfilter原理Bloomfilter其实就是一个BIT数组，通过一系列的hash算法映射出对应的hash，然后将hash对应的数组下标位置改为1。查询的时候，进行一系列的hash算法在数据上获取下标。如果数据取自BIT数组，如果为1，说明数据可能存在。如果为0，则表示它一定不存在。为什么会有错误率？我们知道布隆过滤器其实就是对数据进行哈希处理，所以不管用什么算法，都有可能两个不同的数据产生的哈希值确实相同，也就是我们常说的哈希冲突。先插入一条数据：学好技术再插入一条数据：如果查询一条数据，假设它的hash下标已经标记为1，那么Bloomfilter会认为它有一个通用的用法场景缓存穿透java实现Bloomfilter包com.fandf.test.redis;importjava.util.BitSet;/***javaBloomfilter**@authorfandongfeng*/publicclassMyBloomFilter{/***bit数组大小*/privatestaticfinalintDEFAULT_SIZE=2<<24;/***通过这个数组创建多个哈希函数*/privatestaticfinalint[]SEEDS=newint[]{4,8,16,32,64,128,256};/***初始化位数组，数组中的元素只能为0或1*/privatefinalBitSetbits=newBitSet(DEFAULT_SIZE);/***哈希函数数组*/privatefinalMyHash[]myHashes=newMyHash[SEEDS.length];/***初始化多个包含Hash函数的类数组，每个类中的Hash函数不同*/publicMyBloomFilter(){//初始化多个不同的Hash函数for(inti=0;i>>16)));}}publicstaticvoidmain(String[]args){Stringstr="从技术上学习";MyBloomFiltermyBloomFilter=newMyBloomFilter();System.out.println("str是否存在："+myBloomFilter.contains(str));myBloomFilter.add(str);System.out.println("str是否存在："+myBloomFilter.contains(str));}}Guava实现布隆过滤器，引入依赖com.google.guavaguava31.1-jrepackagecom.fandf.test.redis；导入com.google.common.base.Charsets；导入com.google.common.hash。BloomFilter;importcom.google.common.hash.Funnels;/***@authorfandongfeng*/publicclassGuavaBloomFilter{publicstaticvoidmain(String[]args){BloomFilterbloomFilter=BloomFilter.create(Funnels.stringFunnel(字符集.UTF_8),100000,0.01);bloomFilter.put("学好技术");System.out.println(bloomFilter.mightContain("技术没学好"));System.out.println(bloomFilter.mightContain("学好技术"));}}hutool实现Bloomfilter并引入依赖cn.hutoolhutool-all5.8.3packagecom.fandf.test.redis;导入cn.hutool.bloomfilter.BitMapBloomFilter;导入cn.hutool.bloomfilter.BloomFilterUtil;/***@authorfandongfeng*/publicclassHutoolBloomFilter{publicstaticvoidmain(String[]args){BitMapBloomFilterbloomFilter=BloomFilterUtil.createBitMap(1000);bloomFilter.add("学好技术");System.out.println(bloomFilter.contains("没有学好技术"));System.out.println(bloomFilter.contains("学好技术"));}}Redisson实现布隆过滤器，引入依赖org.redissonredisson3.20.0packagecom.fandf.test.redis；导入org.redisson.Redisson；导入org.redisson.api.RBloomFilter；导入org.redisson。api.RedissonClient;importorg.redisson.config.Config;/***Redisson实现Bloomfilter*@authorfandongfeng*/publicclassRedissonBloomFilter{publicstaticvoidmain(String[]args){Configconfig=newConfig();config.useSingleServer().setAddress("redis://127.0.0.1:6379");//构建RedissonRedissonClientredisson=Redisson.create(config);RBloomFilterbloomFilter=redisson.getBloomFilter("name");//初始化布隆过滤器：预期元素为100000000L，错误率为1%bloomFilter.tryInit(100000000L,0.01);bloomFilter.add("学好技术");System.out.println(bloomFilter.contains("学好技术"));System.out.println(bloomFilter.contains("学好技术"));}}
