| java实现布隆过滤器 | 您所在的位置：网站首页 › java集合使用场景 › java实现布隆过滤器 |
java实现布隆过滤器
|
什么是布隆过滤器
布隆过滤器（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 >> 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实现布隆过滤器引入依赖 com.google.guava guava 31.1-jre 复制代码 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 bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),100000,0.01); bloomFilter.put("好好学技术"); System.out.println(bloomFilter.mightContain("不好好学技术")); System.out.println(bloomFilter.mightContain("好好学技术")); } } 复制代码 hutool实现布隆过滤器引入依赖 cn.hutool hutool-all 5.8.3 复制代码 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实现布隆过滤器引入依赖 org.redisson redisson 3.20.0 复制代码 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 bloomFilter = redisson.getBloomFilter("name"); //初始化布隆过滤器：预计元素为100000000L,误差率为1% bloomFilter.tryInit(100000000L,0.01); bloomFilter.add("好好学技术"); System.out.println(bloomFilter.contains("不好好学技术")); System.out.println(bloomFilter.contains("好好学技术")); } } 复制代码 |
【本文地址】
公司简介
联系我们