背景

如果有一组结构化数据（通过记录ID标识），存储在一组数据文件中，如何确定哪个文件可能包含我们所需的数据呢？如果逐个读取文件，速度会极慢（尤其是要不断从磁盘将数据移入内存）。

一种解决方案是：构建一个索引表，其中每个数据文件对应一个索引，即将每个记录ID映射到数据文件中的偏移量（索引文件根据记录ID进行排序）。要搜索指定记录ID时，使用二分查找。但是，我们能做得更好吗？

算法描述

使用Bloom过滤器快速测试元素是否为集合的成员。返回结果为：可能在集合中，或绝对不在集合中。可能误报（即搜索一个不存在的元素，返回值为“存在”）；不会出现漏报。随着过滤器中元素数量的增加，错误率也会增加。

一个空的Bloom过滤器是一个位数组，包含m位，全部设置为0。还有k个不同的哈希函数：每个函数都将集合中的元素映射到m位位置中的一个。 * 添加元素：将其输入到哈希函数中，得到k个位位置，并将这些位置的位设置为1； * 测试元素是否在集合中：将其输入到哈希函数中，得到k个位位置。 * 如果这些位置中的任何一个位是0，那么该元素肯定不在集合中； * 如果全部是1，那么该元素可能在集合中。

为什么Bloom过滤器不能删除数据？

解答：无法判断待删除元素映射到的 k 位中，哪一个应该被清除。尽管将这 k 位中的任何一个设置为零就足以删除该元素，但它也会删除碰巧映射到该位的任何其他元素。因此清除任何位都会引入漏报的可能性。

然而，不允许删除的机制会导致其中的无效元素可能会越来越多，即实际已经在磁盘删除中的元素，但在Bloom过滤器中还认为可能存在，造成越来越多的false positive。

空间和时间优势

  • 存储空间：常数（O(k)），因为其不需要存储实际数据项（适合有保密要求的场景）；
  • 插入/查询时间：常数（O(k)）， 不会随着元素增加而增加；
  • 空间复杂度为O(m)：不会随着元素增加而增加，占用空间少

缺点：

  1. 随着存入的元素数量增加，误报率随之增加；
  2. 一般情况下不能从布隆过滤器中删除元素。

误报率

  1. FN（False Negative）：集合里有某元素，查找结果是没有该元素（漏报）

    • 恒有：FN=0

  2. FP（False Positive）：集合里没有某元素，查找结果是有该元素（误报）

    其中：n为插入元素的数量；k为哈希次数；m为Bloom过滤器的长度 > 极端情况下，当布隆过滤器没有空闲空间时（满），每一次查询都会返回 true 。这也就意味着 m 的选择取决于期望预计添加元素的数量 n ，并且 m 需要远远大于 n 。

哈希函数的最佳数量

对于给定的 m 和 n，使假阳性概率最小的 k 值为：

有：

即对于给定的假阳性概率 ε，布隆过滤器 m 的长度与被过滤的元素数量n成正比，并且所需的哈希函数数量仅取决于目标假阳性概率 ε。

因此：

应用场景

去重统计

转载：https://blog.csdn.net/CrankZ/article/details/84928562

网页爬虫对 URL 去重，避免爬取相同的 URL 地址，有以下几种思路： 1. 用HashSet保存访问过的URL，只需接近O(1)的代价就可以查到一个URL是否被访问过了； * 太消耗内存。随着URL的增多，占用的内存会越来越多。就算只有1亿个URL，每个URL只算50个字符，就需要5GB内存。 2. URL经过MD5或SHA-1等单向哈希后再保存到HashSet或数据库； * 于字符串经过MD5处理后的信息摘要长度只有128Bit，SHA-1处理后也只有160Bit，因此方法3比方法2节省了好几倍的内存。 3. Bit-Map方法。建立一个BitSet，将每个URL经过一个哈希函数映射到某一位。 * 单一哈希函数发生冲突的概率太高。若要降低冲突发生的概率到1%，就要将BitSet的长度设置为URL个数的100倍。 4. 使用Bloom过滤器。

缓存穿透

缓存穿透：查询⼀个在缓存和数据库都不存在的数据，这个数据始终⽆法被缓存，导致每次请求都直接访问数据库，增加数据库的负载。典型的情况是攻击者可能通过构造不存在的 key ⼤量访问缓存，导致对数据库的频繁查询。

解决方案：利用Bloom过滤器我们可以预先把数据查询的主键，比如用户 ID 或文章 ID 缓存到过滤器中。要查询时：首先去Bloom过滤器查询该key是否存在；若存在，则进行下一步处理；若不存在，直接返回，因此不会触发后续的数据库查询。

实现：Google Guava

  • 导入Guava库 

    1
    2
    3
    4
    5
    <dependency>
       <groupId>com.google.guava</groupId>
       <artifactId>guava</artifactId>
       <version>28.0-jre</version>
    </dependency>

  • 新建一个 BloomFilterDemo 类，在 main 方法中我们通过 BloomFilter.create 方法来创建一个布隆过滤器，初始化 1 百万条数据到过滤器中；在原有的基础上增加 10000 条数据，并判断这些数据是否存在布隆过滤器中： 

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    import com.google.common.base.Charsets;
    import com.google.common.hash.BloomFilter;
    import com.google.common.hash.Funnels;

    public class BloomFilterDemo {
        public static void main(String[] args) {
            int total = 1000000; // 总数量
            BloomFilter<CharSequence> bf = 
              BloomFilter.create(Funnels.stringFunnel(Charsets.UTF_8), total);
            // 初始化 1000000 条数据到过滤器中
            for (int i = 0; i < total; i++) {
                bf.put("" + i);
            }
            // 判断值是否存在过滤器中
            int count = 0;
            for (int i = 0; i < total + 10000; i++) {
                if (bf.mightContain("" + i)) {
                    count++;
                }
            }
            System.out.println("已匹配数量 " + count);
        }
    }
    当以上代码运行后，控制台输出结果： 
    1
    已匹配数量 1000309
    误判率为：309/(1000000 + 10000) * 100 ≈ 0.030594059405940593

  • 提高匹配精度：在创建布隆过滤器的时候设置误判率 fpp： 

    1
    2
    3
    BloomFilter<CharSequence> bf = BloomFilter.create(
      Funnels.stringFunnel(Charsets.UTF_8), total, 0.0002
    );
    > 在 BloomFilter 内部，误判率 fpp 的默认值是 0.03： > 
    1
    2
    3
    4
    // com/google/common/hash/BloomFilter.class
    public static <T> BloomFilter<T> create(Funnel<? super T> funnel, long > > expectedInsertions) {
     return create(funnel, expectedInsertions, 0.03D);
    >}

误判率 fpp 的值越小，匹配的精度越高；当减少误判率 fpp 的值，需要的存储空间也越大。在实际使用过程中，需要在误判率和存储空间之间权衡。