Java技术栈

www.javastack.cn

打开网站看更多优质文章

作者：CodeBear的园子

www.cnblogs.com/CodeBear/p/10911177.html

本文是站在小白的角度去讨论布隆过滤器，如果你是科班出身，或者比较聪明，又或者真正想完全搞懂布隆过滤器的可以移步。

不知道从什么时候开始，本来默默无闻的布隆过滤器一下子名声大燥，仿佛身在互联网，做着开发的，无人不知，无人不晓，哪怕对技术不是很关心的小伙伴也听过它的名号。

我也花了不少时间去研究布隆过滤器，看了不少博客，无奈不是科班出身，又没有那么聪明的头脑，又比较懒...经过“放弃，拿起，放弃，拿起”的无限轮回，应该算是了解了布隆过滤器的核心思想，所以想给大家分享下。

布隆过滤器的应用

我们先来看下布隆过滤器的应用场景，让大家知道神奇的布隆过滤器到底能做什么。

缓存穿透

大量数据，判断给定的是否在其中

现在有大量的数据，而这些数据的大小已经远远超出了服务器的内存，现在再给你一个数据，如何判断给你的数据在不在其中。

如果服务器的内存足够大，那么用是一个不错的解决方案，理论上的时间复杂度可以达到O(1)，但是现在数据的大小已经远远超出了服务器的内存，所以无法使用HashMap，这个时候就可以使用“布隆过滤器”来解决这个问题。但是还是同样的，会有一定的“误判率”。

什么是布隆过滤器

布隆过滤器是一个叫“布隆”的人提出的，它本身是一个很长的二进制向量，既然是二进制的向量，那么显而易见的，存放的不是0，就是1。

现在我们新建一个长度为16的布隆过滤器，默认值都是0，就像下面这样：

现在需要添加一个数据：

我们通过某种计算方式，比如Hash1，计算出了Hash1(数据)=5，我们就把下标为5的格子改成1，就像下面这样：

我们又通过某种计算方式，比如Hash2，计算出了Hash2(数据)=9，我们就把下标为9的格子改成1，就像下面这样：

还是通过某种计算方式，比如Hash3，计算出了Hash3(数据)=2，我们就把下标为2的格子改成1，就像下面这样：

这样，刚才添加的数据就占据了布隆过滤器“5”，“9”，“2”三个格子。

可以看出，仅仅从布隆过滤器本身而言，根本没有存放完整的数据，只是运用一系列随机映射函数计算出位置，然后填充二进制向量。

这有什么用呢？比如现在再给你一个数据，你要判断这个数据是否重复，你怎么做？

你只需利用上面的三种固定的计算方式，计算出这个数据占据哪些格子，然后看看这些格子里面放置的是否都是1，如果有一个格子不为1，那么就代表这个数字不在其中。

这很好理解吧，比如现在又给你了刚才你添加进去的数据，你通过三种固定的计算方式，算出的结果肯定和上面的是一模一样的，也是占据了布隆过滤器“5”，“9”，“2”三个格子。

但是有一个问题需要注意，如果这些格子里面放置的都是1，不一定代表给定的数据一定重复，也许其他数据经过三种固定的计算方式算出来的结果也是相同的。这也很好理解吧，比如我们需要判断对象是否相等，是不可以仅仅判断他们的哈希值是否相等的。

也就是说布隆过滤器只能判断数据是否一定不存在，而无法判断数据是否一定存在。

按理来说，介绍完了新增、查询的流程，就要介绍删除的流程了，但是很遗憾的是布隆过滤器是很难做到删除数据的，为什么？你想想，比如你要删除刚才给你的数据，你把“5”，“9”，“2”三个格子都改成了0，但是可能其他的数据也映射到了“5”，“9”，“2”三个格子啊，这不就乱套了吗？

相信经过我这么一介绍，大家对布隆过滤器应该有一个浅显的认识了，至少你应该清楚布隆过滤器的优缺点了：

• 优点：由于存放的不是完整的数据，所以占用的内存很少，而且新增，查询速度够快；

• 缺点：随着数据的增加，误判率随之增加；无法做到删除数据；只能判断数据是否一定不存在，而无法判断数据是否一定存在。

可以看到，布隆过滤器的优点和缺点一样明显。

在上文中，我举的例子二进制向量长度为16，由三个随机映射函数计算位置，在实际开发中，如果你要添加大量的数据，仅仅16位是远远不够的，为了让误判率降低，我们还可以用更多的随机映射函数、更长的二进制向量去计算位置。

guava实现布隆过滤器

现在相信你对布隆过滤器应该有一个比较感性的认识了，布隆过滤器核心思想其实并不难，难的在于如何设计随机映射函数，到底映射几次，二进制向量的长度设置为多少比较好，这可能就不是一般的开发可以驾驭的了。

好在大佬给我们提供了开箱即用的组件，来帮助我们实现布隆过滤器，现在就让我们看看怎么大佬送给我们的“礼物”吧。

首先在pom引入“礼物”：

    
       
     
      com.google.guava
       
     
      guava
       
     
      19.0
     
    

然后就可以测试啦：

private static int size = 1000000;//预计要插入多少数据private static double fpp = 0.01;//期望的误判率private static BloomFilter
    
      bloomFilter = BloomFilter.create(Funnels.integerFunnel(), size, fpp);public static void main(String[] args) {  //插入数据  for (int i = 0; i < 1000000; i++) {    bloomFilter.put(i);  }  int count = 0;  for (int i = 1000000; i < 2000000; i++) {    if (bloomFilter.mightContain(i)) {      count++;      System.out.println(i + "误判了");    }  }  System.out.println("总共的误判数:" + count);}
    

代码简单分析：

我们定义了一个布隆过滤器，有两个重要的参数，分别是 我们预计要插入多少数据，我们所期望的误判率，误判率不能为0。

我向布隆过滤器插入了0-1000000，然后用1000000-2000000来测试误判率。

运行结果：

1999501误判了1999567误判了1999640误判了1999697误判了1999827误判了1999942误判了总共的误判数:10314

现在总共有100万数据是不存在的，误判了10314次，我们计算下误判率：

和我们定义的期望误判率0.01相差无几。

redis实现布隆过滤器

可能有小伙伴会说，纳尼，布隆过滤器还没介绍完，怎么又出来一个bitmap，没事，你可以把bitmap就理解为一个二进制向量。

要用redis来实现布隆过滤器，我们需要自己设计映射函数，自己度量二进制向量的长度，这对我来说，无疑是一个不可能完成的任务，只能借助搜索引擎，下面直接放出代码把。

public class RedisMain {    static final int expectedInsertions = 100;//要插入多少数据    static final double fpp = 0.01;//期望的误判率    //bit数组长度    private static long numBits;    //hash函数数量    private static int numHashFunctions;    static {        numBits = optimalNumOfBits(expectedInsertions, fpp);        numHashFunctions = optimalNumOfHashFunctions(expectedInsertions, numBits);    }    public static void main(String[] args) {        Jedis jedis = new Jedis("192.168.0.109", 6379);        for (int i = 0; i < 100; i++) {            long[] indexs = getIndexs(String.valueOf(i));            for (long index : indexs) {                jedis.setbit("codebear:bloom", index, true);            }        }        for (int i = 0; i < 100; i++) {            long[] indexs = getIndexs(String.valueOf(i));            for (long index : indexs) {                Boolean isContain = jedis.getbit("codebear:bloom", index);                if (!isContain) {                    System.out.println(i + "肯定没有重复");                }            }            System.out.println(i + "可能重复");        }    }    /**     * 根据key获取bitmap下标     */    private static long[] getIndexs(String key) {        long hash1 = hash(key);        long hash2 = hash1 >>> 16;        long[] result = new long[numHashFunctions];        for (int i = 0; i < numHashFunctions; i++) {            long combinedHash = hash1 + i * hash2;            if (combinedHash < 0) {                combinedHash = ~combinedHash;            }            result[i] = combinedHash % numBits;        }        return result;    }    private static long hash(String key) {        Charset charset = Charset.forName("UTF-8");        return Hashing.murmur3_128().hashObject(key, Funnels.stringFunnel(charset)).asLong();    }    //计算hash函数个数    private static int optimalNumOfHashFunctions(long n, long m) {        return Math.max(1, (int) Math.round((double) m / n * Math.log(2)));    }    //计算bit数组长度    private static long optimalNumOfBits(long n, double p) {        if (p == 0) {            p = Double.MIN_VALUE;        }        return (long) (-n * Math.log(p) / (Math.log(2) * Math.log(2)));    }}

运行结果：

88可能重复89可能重复90可能重复91可能重复92可能重复93可能重复94可能重复95可能重复96可能重复97可能重复98可能重复99可能重复

本篇博客到这里就结束了，谢谢大家。写作不易，坚持更难，如大家喜欢就帮忙推送给其他人！

最近热文：

1、

2、

3、

4、

5、

6、

7、

8、

9、

10、

扫码关注Java技术栈公众号阅读更多干货。

点击「」获取面试题大全～