什么是缓存穿透
我们在项目中使用缓存通常都是先检查缓存中是否存在，如果存在直接返回缓存内容，如果不存在就直接查询数据库然后再缓存查询结果返回。这个时候如果我们查询的某一个数据在缓存中一直不存在，就会造成每一次请求都查询DB，这样缓存就失去了意义，在流量大时，可能DB就挂掉了。
什么是布隆过滤器
布隆过滤器就是引入了k(k>1)个相互独立的哈希函数，保证在给定的空间、误判率下，完成元素判重的过程。下图中是k=3时的布隆过滤器。
x,y,z经由哈希函数映射将各自在Bitmap中的3个位置置为1，当w出现时，仅当3个标志位都为1时，才表示w在集合中。图中所示的情况，布隆过滤器将判定w不在集合中,也会出现一种情况是随着元素的增加会出现误算率，这种情况不可能完全避免只可能降低，那就是提升k的值增加散列函数。
谷歌封装的过滤器代码
import com.google.common.hash.BloomFilter;
import com.google.common.hash.Funnels;
...
BloomFilter<String> filter = BloomFilter.create(Funnels.stringFunnel(Charset.forName("UTF-8")), Integer.MAX_VALUE);
...
自定义实现的过滤器代码
import java.util.BitSet;
/**
* 布隆过滤器-防止缓存穿透问题
* Created by zhangluncong on 2018/5/23.
*/
public class SimpleBloomFilter {
//布隆过滤器能存放的最大数据,2的二进制00000010左移29位，左移一位相当于乘与2
//private static final int DEFAULT_SIZE = 2 << 29;
//布隆过滤器能存放的最大数据,大概20多亿位
private static final int DEFAULT_SIZE = Integer.MAX_VALUE;
//产生随机数的种子，可产生多个不同的随机数产生器,这里要选取质数，能很好的降低错误
private static final int[] seeds = new int[]{3, 5, 7, 11, 13, 31, 37, 61};
//Java中的按位存储的思想，其算法的具体实现
private BitSet bits = new BitSet(DEFAULT_SIZE);
//根据随机数的种子，创建多个哈希函数
private SimpleHash[] func = new SimpleHash[seeds.length];
/**
* 设置布隆过滤器所对应k个哈希函数
*/
public SimpleBloomFilter() {
for (int i = 0; i < seeds.length; i++) {
func[i] = new SimpleHash(DEFAULT_SIZE, seeds[i]);
}
}
/**
* 内部类SimpleHash函数
*/
public static class SimpleHash {
private int cap;
private int seed;
/**
* 默认构造器，哈希表长默认为DEFAULT_SIZE大小，此哈希函数的种子为seed
*/
public SimpleHash(int cap, int seed) {
this.cap = cap;
this.seed = seed;
}
public int hash(String value) {
int result = 0;
int len = value.length();
for (int i = 0; i < len; i++) {
//将此URL用哈希函数产生一个值（使用到了集合中的每一个元素）
result = seed * result + value.charAt(i);
}
//产生单个信息指纹
return (cap - 1) & result;
}
}
/**
* bloom filter 添加值
*
* @param value
*/
public void add(String value) {
for (SimpleHash f : func) {
bits.set(f.hash(value), true);
}
}
/**
* 是否存在
*/
public boolean contains(String value) {
if (value == null) {
return false;
}
boolean ret = true;
//根据此URL得到在布隆过滤器中的对应位，并判断其标志位（k个不同的哈希函数产生k种不同的映射）
for (SimpleHash f : func) {
ret = ret && bits.get(f.hash(value));
}
return ret;
}
public static void main(String[] args) {
String value = "haha";
long start = System.currentTimeMillis();
SimpleBloomFilter filter = new SimpleBloomFilter();
for (int i = 0; i < 100000000; i++) {
filter.add(value + i);
}
System.out.println(filter.contains(value + "4"));
System.out.println(filter.contains(value + "ads"));
long end = System.currentTimeMillis();
System.out.println("sub=" + (end - start));
}
}
