共计 5132 个字符，预计需要花费 13 分钟才能阅读完成。
后面咱们曾经讲过布隆过滤器的原理【实战问题】– 缓存穿透之布隆过滤器（1），都了解是这么运行的，那么个别咱们应用布隆过滤器，是怎么去应用呢？如果本人去实现，又是怎么实现呢？
[TOC]
布隆过滤器
再念一次定义：
布隆过滤器（Bloom Filter）是由布隆（Burton Howard Bloom）在 1970 年提出的，它实际上是由一个很长的二进制向量和一系列随机 hash 映射函数组成（说白了，就是用二进制数组存储数据的特色）。
譬如上面例子：有三个 hash 函数，那么“陈六”就会被三个 hash 函数别离hash，并且对位数组的长度，进行取余，别离 hash 到三个地位。
如果对原理还有不了解的中央，能够查看我的上一篇文章。
手写布隆过滤器
那么咱们手写布隆过滤器的时候，首先须要一个位数组，在 Java 外面有一个封装好的位数组，BitSet。
简略介绍一下BitSet，也就是位图，外面实现了应用紧凑的存储空间来示意大空间的位数据。应用的时候，咱们能够间接指定大小，也就是相当于创立出指定大小的位数组。
BitSet bits = new BitSet(size);同时，BitSet提供了大量的API，根本的操作次要包含：
- 清空位数组的数据
- 翻转某一位的数据
- 设置某一位的数据
- 获取某一位的数据
- 获取以后的
bitSet的位数
上面就讲一下，写一个简略的布隆过滤器须要思考的点：
- 位数组的大小空间，须要指定，其余雷同的时候，位数组的大小越大，
hash抵触的可能性越小。 - 多个
hash函数，咱们须要应用hash数组来存，hash函数须要如何设置呢？为了防止抵触，咱们应该应用多个不同的质数来当种子。 - 办法：次要实现两个办法，一个往布隆过滤器外面增加元素，另一个是判断布隆过滤器是否蕴含某个元素。
上面是具体的实现, 只是简略的模仿，不可用于生产环境，hash函数较为简单，次要是应用 hash 值得高下位进行异或，而后乘以种子，再对位数组大小进行取余数：
import java.util.BitSet;
public class MyBloomFilter {
// 默认大小
private static final int DEFAULT_SIZE = Integer.MAX_VALUE;
// 最小的大小
private static final int MIN_SIZE = 1000;
// 大小为默认大小
private int SIZE = DEFAULT_SIZE;
// hash 函数的种子因子
private static final int[] HASH_SEEDS = new int[]{3, 5, 7, 11, 13, 17, 19, 23, 29, 31};
// 位数组，0/1, 示意特色
private BitSet bitSet = null;
// hash 函数
private HashFunction[] hashFunctions = new HashFunction[HASH_SEEDS.length];
// 无参数初始化
public MyBloomFilter() {
// 依照默认大小
init();}
// 带参数初始化
public MyBloomFilter(int size) {
// 大小初始化小于最小的大小
if (size >= MIN_SIZE) {SIZE = size;}
init();}
private void init() {
// 初始化位大小
bitSet = new BitSet(SIZE);
// 初始化 hash 函数
for (int i = 0; i < HASH_SEEDS.length; i++) {hashFunctions[i] = new HashFunction(SIZE, HASH_SEEDS[i]);
}
}
// 增加元素，相当于把元素的特色增加到位数组
public void add(Object value) {for (HashFunction f : hashFunctions) {
// 将 hash 计算出来的地位为 true
bitSet.set(f.hash(value), true);
}
}
// 判断元素的特色是否存在于位数组
public boolean contains(Object value) {
boolean result = true;
for (HashFunction f : hashFunctions) {result = result && bitSet.get(f.hash(value));
// hash 函数只有有一个计算出为 false，则间接返回
if (!result) {return result;}
}
return result;
}
// hash 函数
public static class HashFunction {
// 位数组大小
private int size;
// hash 种子
private int seed;
public HashFunction(int size, int seed) {
this.size = size;
this.seed = seed;
}
// hash 函数
public int hash(Object value) {if (value == null) {return 0;} else {
// hash 值
int hash1 = value.hashCode();
// 高位的 hash 值
int hash2 = hash1 >>> 16;
// 合并 hash 值(相当于把高下位的特色联合)
int combine = hash1 ^ hash1;
// 相乘再取余
return Math.abs(combine * seed) % size;
}
}
}
public static void main(String[] args) {Integer num1 = new Integer(12321);
Integer num2 = new Integer(12345);
MyBloomFilter myBloomFilter =new MyBloomFilter();
System.out.println(myBloomFilter.contains(num1));
System.out.println(myBloomFilter.contains(num2));
myBloomFilter.add(num1);
myBloomFilter.add(num2);
System.out.println(myBloomFilter.contains(num1));
System.out.println(myBloomFilter.contains(num2));
}
}运行后果, 合乎预期：
false
false
true
true然而下面的这种做法是不反对预期的误判率的，只是能够指定位数组的大小。
当然咱们也能够提供数据量，以及期待的大抵的误判率来初始化，大抵的初始化代码如下：
// 带参数初始化
public BloomFilter(int num,double rate) {
// 计算位数组的大小
this.size = (int) (-num * Math.log(rate) / Math.pow(Math.log(2), 2));
// hsah 函数个数
this.hashSize = (int) (this.size * Math.log(2) / num);
// 初始化位数组
this.bitSet = new BitSet(size);
}Redis 实现
平时咱们能够抉择应用 Redis 的个性于布隆过滤器，为什么呢？因为 Redis 外面有相似于 BitSet 的指令，比方设置位数组的值：
setbit key offset value下面的 key 是键，offset是偏移量，value就是 1 或者0。比方上面的就是将 key1 的第 7 地位为 1。
而获取某一位的数值能够应用上面这个命令：
gitbit key offset借助 redis 这个性能咱们能够实现优良的布隆过滤器，然而实际上咱们不须要本人去写了，Redisson这个客户端曾经有较好的实现。
上面就是用法：
应用 maven 构建我的项目，首先须要导包到pom.xml：
<dependencies>
<dependency>
<groupId>org.redisson</groupId>
<artifactId>redisson</artifactId>
<version>3.11.2</version>
</dependency>
</dependencies>代码如下，我应用的docker，启动的时候记得设置明码，运行的时候批改明码不起成果：
docker run -d --name redis -p 6379:6379 redis --requirepass "password"实现的代码如下，首先须要连贯上 redis，而后创立redission，应用redission 创立布隆过滤器，间接应用即可。（能够指定预计的数量以及期待的误判率）
import org.redisson.Redisson;
import org.redisson.api.RBloomFilter;
import org.redisson.api.RedissonClient;
import org.redisson.config.Config;
public class BloomFilterTest {public static void main(String[] args) {Config config = new Config();
config.useSingleServer().setAddress("redis://localhost:6379");
config.useSingleServer().setPassword("password");
// 相当于创立了 redis 的连贯
RedissonClient redisson = Redisson.create(config);
RBloomFilter<String> bloomFilter = redisson.getBloomFilter("myBloomFilter");
// 初始化, 预计元素数量为 100000000, 期待的误差率为 4%
bloomFilter.tryInit(100000000,0.04);
// 将号码 10086 插入到布隆过滤器中
bloomFilter.add("12345");
System.out.println(bloomFilter.contains("123456"));//false
System.out.println(bloomFilter.contains("12345"));//true
}
}运行后果如下：值得注意的是，这是单台 redis 的状况，如果是 redis 集群的做法略有不同。
Google GUAVA 实现
Google提供的 guava 包外面也提供了布隆过滤器, 引入 pom 文件：
<dependency>
<groupId>com.google.guava</groupId>
<artifactId>guava</artifactId>
<version>18.0</version>
</dependency>具体的实现调用的代码如下, 同样能够指定具体的存储数量以及预计的误判率：
import com.google.common.base.Charsets;
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
public class GuavaBloomFilter {public static void main(String[] args) {
BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),1000000,0.04);
bloomFilter.put("Sam");
System.out.println(bloomFilter.mightContain("Jane"));
System.out.println(bloomFilter.mightContain("Sam"));
}
}执行的后果如下, 合乎预期
下面三种别离是手写，redis，guava实际了布隆过滤器，只是简略的用法，其实 redis 和guava外面的实现也能够看看，有趣味能够理解一下，我先立一个Flag。
对于作者
秦怀，公众号【秦怀杂货店】作者，技术之路不在一时，山高水长，纵使迟缓，驰而不息。集体写作方向：Java 源码解析，JDBC，Mybatis，Spring，redis，分布式，剑指 Offer，LeetCode 等，认真写好每一篇文章，不喜爱题目党，不喜爱花里胡哨，大多写系列文章，不能保障我写的都完全正确，然而我保障所写的均通过实际或者查找材料。脱漏或者谬误之处，还望斧正。
2020 年我写了什么？
开源编程笔记
