维基百科
布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都远远超过一般的算法，缺点是有一定的误识别率和删除困难。
理论说明
当一个元素被加入集合时，通过K个Hash函数将这个元素映射成一个位数组中的K个点，把他们置为1。检索时，只要看这些点是不是都为1（大约）知道集合中有没有它了。如果这些点有0（1个或者多个），则被检元素一定不在；如果都是1，则被检元素很可能存在。布隆过滤器的基本思想。
使用场景
- 垃圾邮件地址过滤
- 爬虫URL地址去重
- 缓存解决击穿问题
- 浏览器安全网址提醒
- Google分布式数据库Bigtable以及HBase使用布隆过滤器来查找不存在的行与列，以减少磁盘查找的IO次数
- 文档存储检索系统也可以采用布隆过滤器来检测先前存储的数据
具体实现
- Google的guava框架：com.google.common.hash.BloomFilter
- Redis 4.0 集成插件：redislabs/rebloom
- Java实现：
public interface BloomFilter<T> {
void add(T t);
boolean exists(T t);
}
public class BloomFilterUtils {
private static final int ALPHA_SIZE = 26;
private static final char[] CHARS = new char[ALPHA_SIZE];
static {
for (int i = 0; i < ALPHA_SIZE; i++) {
CHARS[i] = (char)('a' + i);
}
}
/**
* 提供指定长度的随机字符串（26小写字母）
* @param size
* @return
*/
public static String random(int size) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < size; i++) {
sb.append(CHARS[(int)(Math.random() * ALPHA_SIZE)]);
}
return sb.toString();
}
public static void main(String[] args) {
IntStream.range(0, 100).forEach(i -> System.out.println(random(64)));
}
}
public class SimpleBloomFilter implements BloomFilter<String> {
/**
* n
*/
private static final int DEFAULT_SIZE = 2 << 24;
/**
* 哈希函数 k
*/
private static final int[] SEEDS = new int[] {3, 7, 11, 13, 31, 37, 55, 59};
private BitSet bits = new BitSet(DEFAULT_SIZE);
private BloomHash[] func = new BloomHash[SEEDS.length];
public SimpleBloomFilter() {
for (int i = 0; i < SEEDS.length; i++) {
func[i] = new BloomHash(DEFAULT_SIZE, SEEDS[i]);
}
}
@Override
public void add(String value) {
for (BloomHash bh : func) {
bits.set(bh.hash(value) % DEFAULT_SIZE, true);
}
}
@Override
public boolean exists(String value) {
if (value == null) {
return false;
}
boolean ret = true;
for (BloomHash bh : func) {
ret = ret && bits.get(bh.hash(value));
}
return ret;
}
public static class BloomHash {
private int cap;
private int seed;
public BloomHash(int cap, int seed) {
this.cap = cap;
this.seed = seed;
}
public int hash(String value) {
int h = 0;
if (value != null) {
for (int i = 0; i < value.length(); i++) {
h = seed * h + value.charAt(i);
}
h = (cap - 1) & h;
}
return h;
}
}
public static void main(String[] args) {
SimpleBloomFilter bf = new SimpleBloomFilter();
String s = "abcd";
System.out.println(bf.exists(s));
bf.add(s);
System.out.println(bf.exists(s));
// train
int times = 2 << 20;
IntStream.range(0, times).forEach(i -> bf.add(BloomFilterUtils.random(64)));
// test
Long count = IntStream.range(0, times).filter(i -> bf.exists(BloomFilterUtils.random(64))).count();
System.out.println("falses : " + count + ", total : " + times);
// 通过实际数据验证假阳性的概率为万分之五
BigDecimal ratio = new BigDecimal(1.0 * count / times);
System.out.println("ratio = " + (1.0 * count / times));
System.out.println("ratio = " + ratio.toPlainString());
}
}
