大话布隆过滤器及其应用场景

Dear 丶 2023-07-20 05:56 112阅读 0赞

## 1.前言 ##

今天看博客，有这么一篇文章，他以一道面试题引出了布隆过滤器的概念。这道题大致意思是这样的：假设现在有1000瓶水，其中有一瓶有毒，只要喝一滴，过30天就会毒发身亡。问最少需要多少只小白鼠可以找到有毒的那瓶水，当然是要求30天找到。不然我可以用一只小白鼠实验30\*1000=30000天(大约82年)\[想想好多人连30000天都活不了，不谈这个伤心的话题了\]。那么这个问题怎么解决呢？这里就用到了布隆过滤器。为了便于说明问题，我们假定有10瓶水。我们大致说一下解决思路:

1.先对10瓶水进行编号，并且转换为2进制。所以就有了10串二进制的数。

2.让一号小白鼠和最右边一列为1的水，分别为1、3、5、7、9(只要一滴，撑不死的)

3.让二号、三号、四号小白鼠分别喝相对应列中为1的水。

4.30天后统计被毒死的小白鼠。可以算出那一瓶有毒。（如下图）

![20200331183241851.png][]

分析：

假如我们发现第一只小白鼠和第三只小白鼠被毒死了。二号和四号无恙。我们首先找B列和D列为1的，A列和C列为0的。所以我们找到为0101,即5号瓶子有毒。

那么我们回到上诉问题，如果有1000瓶水呢？我们可以将1000转换为2进制，应该是10位。所以需要10只小白鼠。

11 1110 1000

## 2.概述 ##

通过上面的实例相信大家对布隆过滤器有了初步的了解。那么什么是布隆过滤器呢？布隆过滤器（Bloom Filter）是1970年由布隆提出的。它实际上是一个很长的二进制向量和一系列随机映射函数。布隆过滤器可以用于检索一个元素是否在一个集合中。它的优点是空间效率和查询时间都比一般的算法要好的多，缺点是有一定的误识别率和删除困难。布隆其实有布尔的谐音，也不知道是不是巧合。我们不去关注这个问题。

如果想要判断一个元素是不是在一个集合里，一般想到的是将所有元素保存起来，然后通过比较确定。链表，树等等数据结构都是这种思路. 但是随着集合中元素的增加，我们需要的存储空间越来越大，检索速度也越来越慢(O(n),O(logn))。不过世界上还有一种叫作散列表（又叫哈希表，Hash table）的数据结构。它可以通过一个Hash函数将一个元素映射成一个位阵列（Bit array）中的一个点。这样一来，我们只要看看这个点是不是1就可以知道集合中有没有它了。这就是布隆过滤器的基本思想。  
Hash面临的问题就是冲突。假设Hash函数是良好的，如果我们的位阵列长度为m个点，那么如果我们想将冲突率降低到例如 1%, 这个散列表就只能容纳m / 100个元素。显然这就不叫空间效率了（Space-efficient）了。解决方法也简单，就是使用多个Hash，如果它们有一个说元素不在集合中，那肯定就不在。如果它们都说在，虽然也有一定可能性它们在说谎，不过直觉上判断这种事情的概率是比较低的。

但是布隆过滤器也有缺点。误算率是其中之一。随着存入的元素数量增加，误算率随之增加。常见的补救办法是建立一个小的白名单，存储那些可能被误判的元素。但是如果元素数量太少，则使用散列表足矣。

## 3.应用案例 ##

其实在读了那篇文章好，我突然想起之前写的一段自我感觉很牛的代码是不是可以通过布隆过滤器优化一下呢？这个业务逻辑是这样的，假设现在有10个按钮，分别为btn1、btn2、btn3...btn10。我们怎么快速判断那一个按钮可以点击，哪一个不可以点击。如果按照正常情况我们会分成2的10次方进行分别讨论，那代码量可想而知。那么我们现在有没有一个通用的方法通过给定一个模数，然后返回需要打开可编辑的按钮呢？

### 3.1我最原始的代码 ###

@Test
    public void test1() {
    	//构造符合要求的按钮集合
        List < FunBtn > btns = new ArrayList < > ();
        for (int i = 9; i >= 0; i--) {
        	//这里用到左移，也就是2的N次方
            btns.add(new FunBtn("btn" + i, 1 << i));
        }
    
        changeEnableFun1(btns, 50);
    
    }
    public void changeEnableFun1(List < FunBtn > funBtns, int funMode) {
        for (FunBtn funBtn: funBtns) {
            funMode = checkFun(funMode, funBtn);
        }
    }
    
    private int checkFun(int funMode, FunBtn funBtn) {
    	//从后往前查找，如果模数大于最大按钮的权重，说明此按钮包含在模数中，最终减去此按钮的权重
    	//否则不包含
    	//
        int weigth = funBtn.getWeight();
        if (funMode >= weigth) {
            System.out.println(funBtn.name);
            funMode -= weigth;
        }
        return funMode;
    }
    
    /**
     * 按钮对象
     * name:假定按钮对象
     * weight:权重，这里的权重按照2的n次方
     */
    public static class FunBtn {
        private String name;
        private Integer weight;
    
        public FunBtn(String name, Integer weight) {
            this.name = name;
            this.weight = weight;
        }
    
        public String getName() {
            return name;
        }
    
        public void setName(String name) {
            this.name = name;
        }
    
        public Integer getWeight() {
            return weight;
        }
    
        public void setWeight(Integer weight) {
            this.weight = weight;
        }
    }

我们可以事先算好一种业务模式。比如业务场景一，我们需要将按钮btn0、btn1、btn3可编辑，那么我们可以传入的数为2^0+2^1+2^3 = 11。所以，我们将funModel传入11的时候，按钮btn0、btn1、btn3可编辑。大家可以尝试一下。

### 3.2 通过布隆过滤器改造的代码 ###

@Test
    public void test2() {
        List < String > btns = new ArrayList < > ();
        for (int i = 0; i < 10; i++) {
            btns.add("btn" + i);
        }
    
        changeEanbleFun2(btns, 50);
    }
    public void changeEanbleFun2(List < String > btns, int funMode) {
        Integer result = Integer.valueOf(Integer.toBinaryString(funMode));
        String s = String.format("%010d", result);
        for (int i = 0; i < 10; i++) {
            if (s.charAt(i) == 49) {
                System.out.println(btns.get(9 - i));
            }
        }
    }

首先我们不需要定义那个FunBtn对象了，changeEanbleFun2在处理逻辑上也精简了不少。处理逻辑如下:

1.首先先将funMode转换为2进制数。如果不够10位的左侧补0.

2.接着我们对这个二进制的字符串逐个检查，如果等于1，即符合条件的输出结果，否则不变。此时需要注意的是我们通过按钮集合btns的索引位置确定按钮的权重。

我们可以和上面小白鼠对照一下。10个按钮->10只小白鼠，funMode->有毒的水瓶编号，可编辑的按钮->被毒死的小白鼠。好像这里求的过程和上面的不一样。上面例题中是通过毒死的小白鼠求有毒的水瓶编号，而这里编程通过有毒水瓶的编号求被毒死的小白鼠。不管怎么样，最终还是可以求出结果的。

### 3.3 两种思路的耗时比较 ###

private static final Integer LOOP = 100000;
    
    @Test
    public void test1() {
        List < FunBtn > btns = new ArrayList < > ();
        for (int i = 9; i >= 0; i--) {
            btns.add(new FunBtn("btn" + i, 1 << i));
        }
        for (int i = 0; i < LOOP; i++) {
            changeEnableFun1(btns, 50);
        }
    }
    
    @Test
    public void test2() {
        List < String > btns = new ArrayList < > ();
        for (int i = 0; i < 10; i++) {
            btns.add("btn" + i);
        }
        for (int i = 0; i < LOOP; i++) {
            changeEanbleFun2(btns, 50);
        }
    }

为了区别明显，我们让其循环10000次，test1是我最开始写的代码，test2是通过布隆过滤器调用的方法。

![20200331191216399.png][]

是不是有点惊讶，我们费了半天写的代码竟然没有之前执行的效率高。打击可不是一般的小啊。不过我们还是要分析一下原因。讲过对比，其实问题还是出现在Integer result = Integer.valueOf(Integer.toBinaryString(funMode));。在Integer.toBinaryString(funMode)中，JDK对于数字转换也是通过遍历的方式。

static int formatUnsignedInt(int val, int shift, char[] buf, int offset, int len) {
        int charPos = len;
        int radix = 1 << shift;
        int mask = radix - 1;
        do {
            buf[offset + --charPos] = Integer.digits[val & mask];
            val >>>= shift;
        } while (val != 0 && charPos > 0);
    
        return charPos;
    }

其实核心代码还是代码6、7行。这个在下面会有分析。说白了，我们在test2中，其实是执行了两次循环。这样一来，时间就有差距了。

既然test2进行了两次循环，我们能不能在一次循环中解决问题，换句话说在生成二进制的期间就把问题解决了？顺着这个思路，我们有了以下的改进。

### 3.4 代码改进 ###

**3.4.1 思路**

学过计算机的都应该了解一个十进制转换二进制的方法。我们在这里使用其中一种思路:

1)对十进制与2取模，写到第一位；

2)对十进制的数除以2，得到新的数，然后在对2取模。

3)依次类推。。。

**3.4.2 代码样例**

private void changeEanbleFun3(List < String > btns, int funMode) {
        int position = 0;
        while (funMode != 0) {
            if (funMode % 2 == 1) {
                System.out.println(btns.get(position));
            }
            funMode = funMode / 2;
            position++;
        }
    }

看起来代码更简洁了。那么我们看一下执行效率。

![20200331211359500.png][]

这次终于有些成就感了。不知道你们是否还记得上面提到JDK实现十进制转换二进制的方式？他主要是通过位运算实现的。那么我们是否可以借鉴一下想法。

### 3.5 终极解决 ###

**3.5.1 JDK转换二进制源码分析**

我们主要分析一下代码6行和代码7行。

1）代码6行中主要实现为val & mask。这里再次用到了掩码的思想。mask的英文就是掩码的意思，掩码一般和&一起使用。这里mask为1，通过运算，也就是对val对2取模。

2）代码7行中val >>>= shift;中，是无符号右移1位，说白了就是执行了val/2的运算。其实思路和上面一样，先取模，在除以2，只不过这里使用位运算。感觉效率会比四则运算高。

**3.5.2 代码展示**

private void changeEanbleFun4(List < String > btns, int funMode) {
        int position = 0;
        do {
            if ((funMode & 1) == 1) {
                System.out.println(btns.get(position));
            }
            funMode >>>= 1;
            position++;
    
        } while (funMode != 0);
    }

这里就不做解释了，相信大家能看懂。我们看一下耗时吧。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29ZaW5IZVpoaUd1YW5n_size_16_color_FFFFFF_t_70][]

test3和test4基本差不多。不过实现起来还是显得高大上了写。

## 4.总结 ##

在实际工作中，我们对于同一个问题往往有多种不同的解决思路。只要我们肯去思考，就一定能找出一条最优的方案。

[20200331183241851.png]: /images/20230528/6748806ec4f24c63845974948907143d.png
[20200331191216399.png]: /images/20230528/1df95538683b4f94b579370ef8931e29.png
[20200331211359500.png]: /images/20230528/1b6c362ec44a4f16895734820be781f1.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L29ZaW5IZVpoaUd1YW5n_size_16_color_FFFFFF_t_70]: /images/20230528/e367e88a24d441cdb61c35f6d99a6e42.png