1.简介
布隆过滤器（Bloom
Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。
2.基本思想
如果想要判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路.
但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢(O(n),O(logn))。不过世界上还有一种叫作散列表（又叫哈希表，Hash
table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit
array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。
3.特性
- 如果根据同一个哈希函数得到的哈希值不同，那么这两个哈希值的原始输入值肯定不同。
- 如果根据同一个哈希函数得到的两个哈希值相等，两个哈希值的原始输入值有可能相等，有可能不相等。
这就类似于 Java 中两个对象的 HashCode
相等，但是对象本身不一定相等的道理。说白了，通过散列函数计算后得到位数组上映射点的值全都是1，不一定是要查询的这个变量之前存进来时设置的，也有可能是其他元素映射的点。这也就引出了布隆过滤器的一个特性：
存在一定的误判 。
4.总结
优点：
在空间和时间方面，都有着巨大的优势。因为不是存完整的数据，是一个二进制向量，能节省大量的内存空间，时间复杂度方面，由于计算时是根据散列函数计算查询的，那么假设有N个散例函数，那么时间复杂度就是O(N)；同时在存储元素时存储的不是元素本身，而是二进制向量，所以在一些对保密性要求严格的场景有一定优势。
缺点：
存在一定的误判（存进布隆过滤器里的元素越多，误判率越高）；不能删除布隆过滤器里的元素，随着使用的时间越来越长，因为不能删除，存进里面的元素越来越多，导致占用内存越来越多，误判率越来越高，最后不得不重置。
5.应用
- 网页爬虫对URL的去重 ，避免爬去相同的URL地址。
- 垃圾邮件过滤 ，从数十亿个垃圾邮件列表中判断某邮箱是否是杀垃圾邮箱。
- 解决数据库缓存击穿 ，黑客攻击服务器时，会构建大量不存在于缓存中的key向服务器发起请求，在数据量足够大的时候，频繁的数据库查询会导致挂机。
- 秒杀系统 ，查看用户是否重复购买。
6.代码实现
import java.util.BitSet;
public class MyBloomFilter {
/**
* 一个长度为10亿的比特位
*/
private static final int DEFAULT_SIZE = 256 << 22;
private static final int[] seeds = {
3, 5, 7, 11, 13, 31, 37, 61};
private static HashFunction[] functions = new HashFunction[seeds.length];
private static BitSet bitset = new BitSet(DEFAULT_SIZE);
static {
for (int i = 0; i < functions.length; i++) {
functions[i]=new HashFunction(DEFAULT_SIZE,seeds[i]);
}
}
public static void add(String value) {
if (value != null) {
for (HashFunction f : functions) {
//计算 hash 值并修改 bitmap 中相应位置为 true
bitset.set(f.hash(value), true);
}
}
}
public static boolean contains(String value){
if(value==null){
return false;
}
boolean ret=true;
for (HashFunction f : functions) {
ret=bitset.get(f.hash(value));
if(!ret){
break;
}
}
return ret;
}
/**
* 测试
* @param args
*/
public static void main(String[] args) {
for (int i = 0; i < 100000000; i++){
add(i+"");
}
String id1=1234567+"";
String id2=123456789+"";
System.out.println(id1+" "+contains(id1));
System.out.println(id2+" "+contains(id2));
}
static class HashFunction{
private int size;
private int seed;
public HashFunction(int size, int seed) {
this.size = size;
this.seed = seed;
}
public int hash(String value){
int result=0;
int len=value.length();
for (int i = 0; i < len; i++) {
result=seed*result+value.charAt(i);
}
return (size-1)&result;
}
}
}
