数据结构与算法:数据结构 -Bloom filter(布隆过滤器)

布隆过滤器(英语:Bloom Filter)是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法,缺点是有一定的误识别率和删除困难。

可以理解为把每个string(或者其他类型数据)通过特定的hash方法(通常是用8个不同的质数种子)生成8个不同的hashCode然后存入BitSet,在判断某段string是否已存在的时候,按照相同的方法生成8个hashCode,只要这8个HashCode都存在于BitSet则string验证成功(因为hash冲突的原因,也有可能8个hashCode都验证成功但是其实string是不相等的,如果hash方法选择得当这种情况出现的概率是很小的),如果生成的8个hashCode中至少一个hashCode不存在于BitSet则string验证失败,因此为了减少hash冲突,hash算法的选择至关重要。
示例hash方法照搬参照了Java8的HashMap内部类Node的hashCode方法,而且因为BitSet只接受0和正整数所以对hash结果求绝对值。
采用BitSet数据结构是为了节省存储空间,BitSet数据结构是用bit位数的状态表示某数字是否存在(比如第124个bit状态为1则表示123这个数字存在(位数从0开始)),所以只支持0和正整数,而BitSet的length指的是当前已存储的最大数字的bit位数(即存储的最大数字+1)(logical size),BitSet的size指的是BitSet的当前占用容量的最大bit位数(默认最小容量为64位,存储数字大于等于64之后按照存储的数字区间每次容量扩大为该数字所在最小的2^n的大小,即存储数字是64的话容量扩大为128,存储数字为511的话容量就扩大为512)(number of bits of space),都无法表示当前存储数字的数量,不过可以间接使用bitSet.stream().toArray().length来实现。
因为Bloom filter不要求存储元数据,同时因为在数据量巨大的时候可能会验证错误,所以适用于验证的元数据占用存储空间比较大,并且验证正确率要求不是100%的场景。

布隆过滤器

Java实现

package com.github.liuzhuoming23.bloomfilterdemo;

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Objects;

/**
* bloom filter
*
* @author liuzhuoming
*/
public class BloomFilter {

private static final byte[] DEFAULT_SEEDS = {2, 3, 5, 7, 11, 13, 17, 19};
private static BitSet bitSet = new BitSet();
private byte[] seeds;

public BloomFilter() {
seeds = DEFAULT_SEEDS;
}

/**
* build object based on seed string
*
* @param seed seed string
*/
public BloomFilter(String seed) {
try {
this.seeds = seeds(seed);
} catch (NoSuchAlgorithmException e) {
seeds = DEFAULT_SEEDS;
}
}

/**
* parse seeds from seed string
*
* @param seed seed
*/
private byte[] seeds(String seed) throws NoSuchAlgorithmException {
MessageDigest md5Digest = MessageDigest.getInstance("md5");
byte[] digest = md5Digest.digest(seed.getBytes(StandardCharsets.UTF_8));
return Arrays.copyOfRange(digest, 4, 12);
}

/**
* add
*
* @param value value
*/
public void add(String value) {
if (value != null) {
for (int seed : seeds) {
bitSet.set(hash(value, seed), true);
}
}
}

/**
* contains
*
* @param value value
* @return t:contains f:not contains
*/
public boolean contains(String value) {
if (value == null) {
return false;
}
boolean tf = true;
for (int seed : seeds) {
tf = bitSet.get(hash(value, seed));
if (!tf) {
break;
}
}
return tf;
}

/**
* hash
*
* @param value value
* @param seed seed
* @return hash
* @see java.util.HashMap.Node#hashCode()
*/
private int hash(String value, int seed) {
return Math.abs(Objects.hashCode(value) ^ Objects.hashCode(seed));
}
}

测试类

package com.github.liuzhuoming23.bloomfilterdemo;

import org.junit.Test;

/**
* bloom filter test
*
* @author liuzhuoming
*/
public class BFTest {

@Test
public void test1() {
String value1 = "liuzhuoming23@live.com";
String value2 = "liuzhuoming23.github.io";
String value3 = "test@qq.com";

BloomFilter bloomFilter = new BloomFilter();
bloomFilter.add(value1);
bloomFilter.add(value2);

System.out.println(bloomFilter.contains(value1));
System.out.println(bloomFilter.contains(value3));
}
}

运行结果:

true
false

参考来源

  1. 布隆过滤器 - 维基百科,自由的百科全书