布隆过滤器

2020-05-22 本文已影响0人水煮鱼又失败了

1 简介

布隆过滤器是一种概率型算法，底层通过二进制向量实现，可以计算出请求的数据绝对不存在或者可能存在。
因为判定为数据存在时，一定概率判断失误，故为概率型算法，通过此算法计算出的结果。
误判指的是有一定概率，将不存在的数据判定为存在，误判概率可在算法中指定。
布隆过滤器计算后的结果，可以再进行精准判断，已保证结果的真实有效性，来修复误判的情况。
因此算法极快的插入速度和查询速度，空间占用小，可以绝对判断出绝大部分不存的数据。可以用来缓解请求不存在数据情况的压力。
可用来应对redis的缓存击穿问题。

2 产生的场景

通过解决方案：

Java中如将数据存储在内存中，最简单的算法结构是HashMap。通过HashMap判断key是否存在，来判断数据是否存在。通过hash算法查找元素，时间复杂度基本是O(1)（可能存在hash冲突后转换成链表或红黑树的情况，时间复杂度的影响可以忽略）。

使用HashMap速度很快，存储简单，绝大部分场景可以使用。但是HashMap占用的空间比较大：

HashMap存储的数据类型如String、Integer等，占用固定的字节数。如Integer固定大小 4字节，同占用4*8=32位。
HashMap内部实现机制中的阈值，默认情况下在HashMap数据占用空间达到75%的时候，将进行扩容，且扩容是原有大小两倍的扩容，HashMap的占用的内存空间无法完全使用。

为什么出现布隆过滤器：

布隆过滤器底层使用byte数组实现，空间占用小，可以用极少的空间存储较多的数据
布隆过滤器使用hash算法进行存储和计算，速度较快

举例：

如1000万个Integer存储在内存中，占用空间为：4x32x10000000位，即1220兆。如布隆过滤器通过4字节存储（布隆过滤器通过多次hash对数据计算后-->几次hash根据数据量指定，得到多个数据，占用多个位），则占用空间为610M。比原有空间少一半。

个人觉得，此比较在字符等的比较中尤为有效。
一个字符串多个字符，根据编码方式，一个字符两个或三个字节，如10个字符，字符串存储占用20个字节，还有相关字符串相关的类信息的内存占用。
位存储，根据数据量的大小，hash的位数，灵活计算。如4个字节，则是原hashMap占用空间的五分之一。

3 原理

3.1 算法过程

3.1.1 写入数据

（1）定义字节向量

先定义一个指定长度的字节数组（字节数组，数组内每个元素的值）。

如长度为8（一个字节大小），默认所有元素值均为0，如下：

索引	0	1	2	3	4	5	6	7
元素	0	0	0	0	0	0	0	0

（2）计算哈希值

将要写入过滤器的数据，根据一定数量的哈希函数，得到多个哈希值，再依次判断每个哈希值对应的索引。

如使用3个哈希函数，计算得到3个哈希值，判定哈希值对应的字节向量为为1，3，7。

（3）更新字节向量

将计算出的字节向量的索引，对应的字节向量中的元素值更高为1（无论之前为0或者为1，均更改为1）。如下：

索引	0	1	2	3	4	5	6	7
元素	0	`1`	0	`1`	0	0	0	`1`

3.1.2 查询数据

（1）计算哈希值

将要判断过滤器中是否存在的数据，根据一定数量的哈希函数，得到多个哈希值，再依次判断每个哈希值对应的索引。

如使用3个哈希函数，计算得到3个哈希值，判定哈希值对应的字节向量为为1，3，7。

注意：哈希函数的判断方式和计算索引的方式，需和写入数据时完全一致。

（2）判断是否存在

如原字节数组中，对应1，3，7中存在的元素的值都为1。则判定为此元素可能存在，但凡有一个元素的值不为1，则判定此元素一定不存在。

为什么满足全为1的情况下，只能判定此元素为可能存在？

因为：

当元素大量写入过滤器后，可能存在一些索引下的元素被不同值重复写入的情况（如有的值写入了1、3、5，有的值写入了2、4、7，也存在1、3、5元素全为1的情况）。

3.2 注意事项

3.2.1 计算参数

布隆过滤器，主要需实现的目标是，在指定的数据个数范围内，满足误判率在设定的范围内，误判率太高的话，无法起到过滤数据的情况，误判率不能为0。

因此需要计算两个数据来满足存储数据的个数和误判率：

字节数组的长度
哈希计算位置的个数

3.2.2 哈希选择

使用布隆过滤器的决定性因素之一，就是此算法插入数据和查询数据的速度必须非常快。因此在对数据进行哈希运算的时候，需选择计算快的哈希算法。

而且，写入数据以及查询数据的哈希算法，顺序和算法都需完全一致。

4 公式

待完善。。。。。

5 应用

5.1 内存实现

可以通过google的guava，在内存中轻松实现布隆过滤器。

无需手动计算满足字节数组的长度和哈希个数，只需要输入拟输入数据的个数和期望误判率即可。

不输入期望误判率的情况下，误判率为0.03，即100个非范围内的数据进行校验时，约三个数据会判定为存在。

5.1.1 pom依赖

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>28.2-jre</version>
</dependency>

5.1.2 代码实现

/**
 * 布隆过滤器
 */
public class BloomFilterTest {
    /**
     * 预计要插入的数据
     */
    private static Long expectedInsertions=1000000L;
    
    /**
     * 期望误判率
     */
    private static Double fpp=0.01D;
    
    /**
     * 布隆过滤器（指定过滤数据的类型为Long）
     */
    public static BloomFilter<Long> bloomFilter=BloomFilter.create(Funnels.longFunnel(),expectedInsertions,fpp);
    
    public static void main(String[] args) {
        System.out.println("-------写入数据---开始");
        for(long i=1;i<=1000000L;i++){
            bloomFilter.put(i);
        }
        System.out.println("-------写入数据---结束");
    
        long okCount=0L;
        for(long i=1;i<=1000000L;i++){
            if(bloomFilter.mightContain(i)){
                okCount++;
            }
        }
        System.out.println("全部范围内存在的数量："+okCount);
        
        long contaisCount=0;
        for(long i=1000000L;i<=2000000L;i++){
            if(bloomFilter.mightContain(i)){
                contaisCount++;
            }
        }
        System.out.println("范围外判断可能存在的结果："+contaisCount);
    }
}

5.1.3 执行结果

-------写入数据---开始
-------写入数据---结束
全部范围内存在的数量：1000000
范围外判断可能存在的结果：9947

多次执行，结果一致，根据结果判定：

如数据在存在，则一定会判定为存在
如数据不存，则会在一定几率（期望误判率）的下判定为存在
布隆过滤器执行结果是幂等的，即多次执行，结果一致（计算方式一样，一样的哈希算法）

5.2 redis实现

内存的存储存在局限性，可以使用redis中的bitMap来实现字节数组的存储。

使用redis实现布隆过滤器。需要根据公式，手动计算字节数组的长度和哈希的个数。

实现过程，待完善。。。。。。