布隆过滤器的学习与JAVA实现
扩展：一种可扩容布隆过滤器设计
什么是布隆过滤器
这个问题网上一搜一大把，随便复制一段[维基百科](布隆过滤器 - 维基百科，自由的百科全书 (wikipedia.org))的解释：布隆过滤器（英语：Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
在看了一段没什么意思的介绍后，来看看为什么它最大的特点：
布隆过滤器说这个对象不存在则一定不存在
布隆过滤器说这个对象不存在则一定不存在
布隆过滤器说这个对象不存在则一定不存在
布隆过滤器为什么能行
如图，我们将全集（“张三”、“李四”）输入布隆过滤器。布隆过滤器对每个元素计算多次哈希（图中为3次）。建立一个BitSet记录每个哈希函数的结果：将结果对应的位设置为真（1）。
在验证阶段，与输入阶段一样，对每个待验证的元素计算多次哈希：
- 当任意一个哈希结果对应的位为假（0），则证明该元素没有出现过，不会误判。（图中“王五”）
- 当所有哈希结果对应的位均为真时，则认为是曾经被输入过。但是随着元素的增多，BitSet内真值密度增加，可能存在误判。（图中“赵六”）
布隆过滤器的参数选取
在使用布隆过滤器之前，我们需要评估打算放入过滤器的元素数目n以及可以接受的误判率p。
需要的BitSet长度m和哈希函数个数k可以按照一下公式计算出来。
$$
m=\frac{-n*ln(p) }{ (ln(2)^2)}
$$
$$
k=ln2*\frac{m}{n}
$$
具体推导请看参考文献1和2。
如果想要在线计算的话，可以试试Bloom Filter Calculator (krisives.github.io)
简单的JAVA实现
代码里有注释，大概可以明白？有不明白的请在评论留言，我看到后会立刻补上解释
主体
package com.loststar.bloomfilter;
import com.loststar.bloomfilter.hash.HashFunction;
import com.loststar.bloomfilter.hash.MultiplyPrimeHash;
import java.util.BitSet;
public class BloomFilter<T> {
static final int DEFAULT_INITIAL_CAPACITY = 1000;
static final double DEFAULT_INITIAL_MISJUDGMENT_RATE = 0.01f;
BitSet bitSet = null;
int bitSetLength = 0;
HashFunction hashFunctions = null;
int numHashFunctions = 0;
/**
* 使用默认的元素个数(1000)和默认误判率(0.01)构建一个布隆过滤器
*
* @author: loststar
* @time: 2022/2/1 10:53
*/
public BloomFilter() {
this(DEFAULT_INITIAL_CAPACITY, DEFAULT_INITIAL_MISJUDGMENT_RATE);
}
/**
* 使用指定的元素个数和默认误判率(0.01)构建一个布隆过滤器
*
* @param capacity
* @author: loststar
* @time: 2022/2/1 10:52
*/
public BloomFilter(int capacity) {
this(capacity, DEFAULT_INITIAL_MISJUDGMENT_RATE);
}
/**
* 使用指定的元素个数和误判率构建一个布隆过滤器
*
* @param capacity 过滤器内元素的个数
* @param misjudgmentRate 误判率
* @author: loststar
* @time: 2022/2/1 10:45
*/
public BloomFilter(int capacity, double misjudgmentRate) {
calculateLengthOfBitSet(capacity, misjudgmentRate);
calculateNumHashFunctions(capacity);
bitSet = new BitSet(bitSetLength);
hashFunctions = new MultiplyPrimeHash(numHashFunctions);
}
/**
* 向布隆过滤器添加一个元素
*
* @param value 要添加的元素
* @author: loststar
* @time: 2022/2/1 11:09
*/
public void add(T value) {
int[] hashArray = hashFunctions.hash(value);
for (int hash : hashArray) {
bitSet.set(hash % bitSetLength);
}
}
/**
* 向布隆过滤器批量添加一组元素
*
* @param values 包含要添加的元素的数组
* @author: loststar
* @time: 2022/2/1 16:17
*/
public void addAll(T[] values) {
for (T value : values) {
add(value);
}
}
/**
* 判断元素是否在布隆过滤器内
*
* @param value 被判断的元素
* @return: boolean 元素是否在布隆过滤器内
* @author: loststar
* @time: 2022/2/1 11:15
*/
public boolean contains(T value) {
int[] hashArray = hashFunctions.hash(value);
for (int hash : hashArray) {
if (!bitSet.get(hash % bitSetLength)) {
return false;
}
}
return true;
}
/**
* 计算位数组的长度，m=-n*ln(p)/(ln2)^2
*
* @param capacity 过滤器内元素的个数
* @param misjudgmentRate 误判率
*/
public void calculateLengthOfBitSet(int capacity, double misjudgmentRate) {
this.bitSetLength = (int) Math.ceil(-capacity * Math.log(misjudgmentRate) / Math.pow(Math.log(2), 2));
}
/**
* 计算位需要的函数个数，k=ln2*m/n
*
* @param capacity 过滤器内元素的个数
* @author: loststar
* @time: 2022/2/1 10:56
*/
public void calculateNumHashFunctions(int capacity) {
this.numHashFunctions = (int) Math.ceil(Math.log(2) * this.bitSetLength / capacity);
}
/**
* 计算bitset内1的占比
*
* @return: double 1的比例
* @author: loststar
* @time: 2022/2/1 13:12
*/
public double calculateTrueBitProportion() {
return bitSet.cardinality() * 1.0 / bitSetLength;
}
public int getBitSetLength() {
return bitSetLength;
}
public int getNumberOfHashAlgorithm() {
return numHashFunctions;
}
public int getCardinality() {
return bitSet.cardinality();
}
}
哈希函数
所有的哈希函数集合都会实现hash方法，用于计算key的numHashFunctions个哈希值，并返回。
package com.loststar.bloomfilter.hash;
public abstract class HashFunction {
int[] hashResult;
int numHashFunctions;
public HashFunction(int numHashFunctions) {
this.numHashFunctions = numHashFunctions;
hashResult = new int[numHashFunctions];
}
public abstract int[] hash(Object key);
}
这里使用的哈希函数思路来源于秦怀杂货店 - 掘金 (juejin.cn)和HahMap的哈希函数
package com.loststar.bloomfilter.hash;
public class MultiplyPrimeHash extends HashFunction {
static final int[] PRIME_SEED = new int[]{2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113};
public MultiplyPrimeHash(int numHashFunctions) {
super(numHashFunctions);
}
public int[] hash(Object key) {
// 类似HashMap的实现，结果乘以seed
int h;
int res = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
for (int i = 0; i < numHashFunctions; i++) {
int curHash = res * PRIME_SEED[i];
// 取绝对值
hashResult[i] = (curHash ^ (curHash >> 31)) - (curHash >> 31);
}
return hashResult;
}
}
现实中更广泛使用的还有MurmurHash等，感兴趣的可以看MurmurHash - Wikipedia。
测试
测试指标
这也算是个二分类问题，于是使用混淆矩阵作为评价。在参考文献6中可以找到相关的介绍。
测试过程
先往布隆过滤器中添加0-9000，随后测试1000-6000（出现过）以及10000-13000（之前未输入）的预测情况。代码内truePositive、falsePositive、falseNegative、trueNegative的意义同样参见参考文献6。
public static void main(String[] args) {
BloomFilter<Integer> bloomFilter = new BloomFilter<>(15000, 0.001);
int truePositive = 0, falsePositive = 0, falseNegative = 0, trueNegative = 0;
for (int i = 0; i < 9000; i++) {
bloomFilter.add(i);
}
for (int i = 1000; i < 6000; i++) {
if (bloomFilter.contains(i)) {
truePositive++;
} else {
falseNegative++;
}
}
for (int i = 10000; i < 13000; i++) {
if (!bloomFilter.contains(i)) {
trueNegative++;
} else {
falsePositive++;
}
}
formattedOutput(bloomFilter, truePositive, falsePositive, falseNegative, trueNegative);
}格式化打印结果
public static void formattedOutput(BloomFilter bloomFilter, int truePositive, int falsePositive, int falseNegative, int trueNegative) {
System.out.println("---------------------Bloom Filter----------------------");
System.out.println("*********布隆过滤器参数*********");
System.out.println("数组长度：" + bloomFilter.getBitSetLength());
System.out.println("函数个数：" + bloomFilter.getNumberOfHashAlgorithm());
System.out.println("1的占比：" + bloomFilter.calculateTrueBitProportion());
System.out.println("***********预测情况***********");
System.out.println(truePositive + "(TP) " + falsePositive + "(FP) " + falseNegative + "(FN) " + trueNegative + "(TN)");
System.out.println("精确度：" + truePositive * 1.0 / (truePositive + falsePositive));
System.out.println("正拒率/召回率：" + truePositive * 1.0 / (truePositive + falseNegative));
System.out.println("误拒率：" + falsePositive * 1.0 / (falsePositive + trueNegative));
}测试结果
可以看到，当布隆过滤器认定元素未被输入时，结果一定可信（FN）。当布隆过滤器认定为曾经输入过时，有一定几率误判（FP），总体上符合预期。
---------------------Bloom Filter----------------------
*********布隆过滤器参数*********
数组长度：215664
函数个数：10
1的占比：0.30474719934713257
***********预测情况***********
5000(TP) 26(FP) 0(FN) 2974(TN)
精确度：0.9948269001193792
正拒率/召回率：1.0
误拒率：0.008666666666666666
进程已结束,退出代码0参考文献
布隆过滤器的学习与JAVA实现
https://blog.loststar.tech/posts/de1ff129/