一、什么是布隆过滤器？
布隆过滤器（Bloom Filter）是 Bloom 于1970年提出的。可以把它看作由二进制向量（或者说位数组）和一系列随机映射函数（哈希函数）两部分组成的数据结构。 相比于我们平时常用的的 List、Map 、Set 等数据结构，它占用空间更少并且效率更高，但是缺点是其返回的结果可能产生哈希冲突，从而导致误判。理论情况下添加到集合中的元素越多，误报的可能性就越大。并且，存放在布隆过滤器的数据不容易删除。 布隆过滤器典型的特点是宁可错杀，不可放过。即被布隆过滤器检测为存在的可能事实上不存在，但检测为不存在的一定存在。 位数组中的每个元素都只占用 1 bit ，并且每个元素只能是 0 或者 1。 假设申请一个 100w 个元素的位数组只占用 1000000Bit / 8 = 125000 Byte = 125000/1024 kb ≈ 122kb 的空间。
二、布隆过滤器的原理
1、当一个元素加入布隆过滤器中
（1）使用布隆过滤器中的多个哈希函数对元素值进行计算，得到多个哈希值 （2）根据得到的哈希值，在位数组中把对应下标的值置为 1。
2、当需要判断一个元素是否存在于布隆过滤器
（1）对给定元素使用相同的多个哈希函数进行哈希计算，得到多个哈希值 （2）得到值之后判断位数组中的每个元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中。 如图所示，当字符串存储要加入到布隆过滤器中时，该字符串首先由多个哈希函数生成不同的哈希值，然后在对应的位数组的下表的元素设置为 1（当位数组初始化时 ，所有位置均为0）。当第二次存储相同字符串时，因为先前的对应位置已设置为1，所以很容易知道此值已经存在（去重的应用）。
如果我们需要判断某个字符串是否在布隆过滤器中时，只需要对给定字符串再次进行相同的哈希计算，得到值之后判断位数组中的每个元素是否都为 1，如果值都为 1，那么说明这个值在布隆过滤器中，如果存在一个值不为 1，说明该元素不在布隆过滤器中。
不同的字符串可能哈希出来的位置相同造成误判，如果误判率高，可以适当增加位数组大小或者调整哈希函数。
三、布隆过滤器使用场景
1、判断给定数据是否存在： 判断一个数字是否在于包含大量数字的数字集中（数字集很大） 如以下场景：
防止缓存穿透：判断请求的数据是否有效避免直接穿透缓存而请求数据库邮箱的垃圾邮件过滤黑名单功能
2、去重：比如爬给定网址的时候对已经爬取过的 URL 去重。
四、Java 布隆过滤器的参考实现
import java
.util
.BitSet
;
public class MyBloomFilter {
private static final int DEFAULT_SIZE
= 2 << 24;
private static final int[] SEEDS
= new int[]{3, 13, 46, 71, 91, 134};
private BitSet bits
= new BitSet(DEFAULT_SIZE
);
private SimpleHash
[] func
= new SimpleHash[SEEDS
.length
];
public MyBloomFilter() {
for (int i
= 0; i
< SEEDS
.length
; i
++) {
func
[i
] = new SimpleHash(DEFAULT_SIZE
, SEEDS
[i
]);
}
}
public void add(Object value
) {
for (SimpleHash f
: func
) {
bits
.set(f
.hash(value
), true);
}
}
public boolean contains(Object value
) {
boolean ret
= true;
for (SimpleHash f
: func
) {
ret
= ret
&& bits
.get(f
.hash(value
));
}
return ret
;
}
public static class SimpleHash {
private int cap
;
private int seed
;
public SimpleHash(int cap
, int seed
) {
this.cap
= cap
;
this.seed
= seed
;
}
public int hash(Object value
) {
int h
;
return (value
== null
) ? 0 : Math
.abs(seed
* (cap
- 1) & ((h
= value
.hashCode()) ^ (h
>>> 16)));
}
}
}
