网站建设的经济效益,石家庄个人做网站,广州网站设计建设公司,淮北论坛招聘最新消息什么是布隆过滤器 布隆过滤器#xff08;Bloom Filter#xff09;是1970年由布隆提出来的。 它实际上是由一个很长的二进制数组一系列hash算法映射函数#xff0c;用于判断一个元素是否存在于集合中。 布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和…什么是布隆过滤器 布隆过滤器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实现布隆过滤器
引入依赖
dependencygroupIdcom.google.guava/groupIdartifactIdguava/artifactIdversion31.1-jre/version
/dependencypackage 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) {BloomFilterString bloomFilter BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),100000,0.01);bloomFilter.put(好好学技术);System.out.println(bloomFilter.mightContain(不好好学技术));System.out.println(bloomFilter.mightContain(好好学技术));}
}hutool实现布隆过滤器
引入依赖
dependencygroupIdcn.hutool/groupIdartifactIdhutool-all/artifactIdversion5.8.3/version
/dependencypackage 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实现布隆过滤器
引入依赖
dependencygroupIdorg.redisson/groupIdartifactIdredisson/artifactIdversion3.20.0/version
/dependencypackage 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);//构造RedissonRedissonClient redisson Redisson.create(config);RBloomFilterString bloomFilter redisson.getBloomFilter(name);//初始化布隆过滤器预计元素为100000000L,误差率为1%bloomFilter.tryInit(100000000L,0.01);bloomFilter.add(好好学技术);System.out.println(bloomFilter.contains(不好好学技术));System.out.println(bloomFilter.contains(好好学技术));}
}
