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