布隆过滤器

发布于 2021-04-10  621 次阅读


如果我们需要判断10亿个数据中是否存在10w个数据,我们应该怎么做?

如果这样大量的请求打到数据库上一定是灾难的,这也是缓存穿透出现的一个原因点;

那么我们如何去避免这样的情况出现呢?

1.使用HashMap去映射,固然提高了效率,但是HashMap占用的空间很大

2.布隆过滤器,它将告诉你某样东西一定不存在或者可能存在

 

布隆过滤器数据结构

布隆过滤器是一个bit向量或者说bit数组(这也是为什么它可以存放大量数据且占用空间少)

preview

布隆过滤器通过多个不同的哈希函数生成多个哈希值,并将每个生成的哈希值指向的bit位置改为1,假如现在有个“baidu”需要存进,三个不同的哈希函数分别生成了哈希值 1、4、7,则上图变为

Ok,我们现在再存一个值 “tencent”,如果哈希函数返回 3、4、8 的话,图继续变为:

由于哈希冲突的存在,4这个bit位由于“tencent”和“baidu”的哈希函数都改变此位;

如果我们要查询“yang”这个值是否存在于布隆过滤器,哈希函数返回了1,5,8三个值,由于5这个bit位上的值位0,因此我们可以断定“yang”不存在

但是,如果现在要查询“hello”这个值,哈希函数返回了1,3,4,7,我们只能说“hello”这个值可能存在,因为在"hello"之前,“tencent”和“baidu”已经改变了1,4,7,3,4,8这几个bit位

 

布隆过滤器删除

由上可知,如果使用布隆过滤器去删除可能会出现误删的情况,因此我们不应该使用它进行删除操作;

 

如何选择哈希函数的个数和布隆过滤器的长度

显然,过短的布隆过滤器的bit很快就会为1,那么查询任何值都会返回“可能存在”,起不到过滤作用,即布隆过滤器越长误报率越小;

哈希函数的个数也需要权衡,个数过多布隆过滤器消耗时间越长,效率越低,但如果太少的话,误报率会变高;

 

 

代码实现

@Controller
public class BloomController {

    int count = 0;
    BloomFilter<String> bloomFilter = BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8),10000000,0.00001);
    public void  create(){
        int total = 10000000;
        for (int i = 0; i < total; i++) {
            bloomFilter.put(i+"");
        }
        long l = System.nanoTime();
        int i = 100000;
        for (int i1 = total; i1 < total+i; i1++) {
            if(bloomFilter.mightContain(i1+"")){
                count++;
                System.out.println(i1+"误判了");
            }
        }
        long l1 = System.nanoTime();
        System.out.println("消耗时间为:"+(l1-l)+"ns");
        System.out.println("误判数为"+count);
    }

}

她喜欢所以就做咯