布隆过滤器的一些概念

主要包括：

• 简介
• 算法
• 参数
• 优势和劣势

布隆过滤器简介

布隆过滤器是「一种空间高效概率性的数据结构」（百科中原文是a space-efficient probabilistic data structure），该数据结构于1970年由Burton Howard Bloom提出，「作用是测试一个元素是否某个集合的一个成员」。布隆过滤器是可能出现false positive（这个是专有名词"假阳性"，可以理解为误判的情况，下文如果用到这个名词会保留英文单词使用）匹配的，换言之，布隆过滤器在使用的时候有可能返回结果"可能存在于集合中"或者"必定不存在于集合中"。

布隆过滤器算法描述

在场景复杂的网络爬虫中，爬取到的网页URL依赖有可能成环，例如在URL-1页面中展示了URL-2，然后又在URL-2中的页面展示了URL-1，这个时候需要一种方案记录和判断历史访问过的URL。这个时候可能会想到下面的方案：

• 方案一：使用数据库存储已经访问过的URL，例如MySQL表中基于URL建立唯一索引或者使用Redis的SET数据类型
• 方案二：使用HashSet（其实这里不局限于HashSet，链表、树和散列表等数据结构都能满足）存储已经访问过的URL
• 方案三：基于方案一和方案二进行优化，存储URL的摘要，使用摘要算法如MD5、SHA-n算法针对URL字符串生成摘要
• 方案四：使用Hash函数处理对应的URL生成一个哈希码，再把哈希码通过一个映射函数映射到一个固定容量的BitSet中的某一个比特

对于方案一、方案二和方案三，在历史访问URL数据量极大的情况下，会消耗巨大的存储空间（磁盘或者内存），对于方案四，如果URL有100亿个，那么要把冲突几率降低到1%，那么BitSet的容量需要设置为10000亿。

冷饭新炒：理解布隆过滤器算法的实现原理

所以上面的四种方案都有明显的不足之处，而布隆过滤器算法的基本思路跟方案四差不多，最大的不同点就是方案四中只提到使用了一个散列函数，而布隆过滤器中使用了k（k >= 1）个相互独立的高效低冲突的散列函数。

一个初始化的布隆过滤器是一个所有比特都设置为0的长度为m的比特数组，也就是认知中的Bit Array、Bit Set或者Redis中的Bit Map概念。然后需要引入k个不同的散列函数，某个新增元素通过这k个散列函数处理之后，映射到比特数组m个比特中的k个，并且把这些命中映射的k个比特位设置为1，产生一个均匀的随机分布。通常情况下，k的一个较小的常数，取决于所需的误判率，而布隆过滤器容量m与散列函数个数k和需要添加元素数量呈正相关。

冷饭新炒：理解布隆过滤器算法的实现原理

当需要新增的所有元素都添加到布隆过滤器之后，那么比特数组中的很多比特都被设置为1。这个时候如果需要判断一个元素是否存在于布隆过滤器中，只需要通过k个散列函数处理得到比特数组的k个下标，然后判断比特数组对应的下标所在比特是否为
1。如果这k个下标所在比特中「至少存在一个0，那么这个需要判断的元素必定不在布隆过滤器代表的集合中」；如果这k个下标所在比特全部都为1，那么那么这个需要判断的元素「可能存在于」布隆过滤器代表的集合中或者刚好是一个False Positive，至于误差率分析见下文的「布隆过滤器的相关参数」一节。False Positive出现的情况可以见下图：

冷饭新炒：理解布隆过滤器算法的实现原理

当添加到布隆过滤器的元素数量比较大，并且布隆过滤器的容量设置不合理（过小），容易出现多个元素通过k个散列函数，映射到相同的k个位（如上图的下标1、3、9所在的位），这个时候就无法准确判断这k个位由具体那个元素映射而来。其实可以极端一点思考：假设布隆过滤器容量为24，散列函数只有一个，那么添加最多25个不同元素，必定有两个不同的元素的映射结果落在同一个位。

布隆过滤器的相关参数

在算法描述一节已经提到过，布隆过滤器主要有下面的参数：

• 初始化比特数组容量m
• 散列函数个数k
• 误判率ε（数学符号Epsilon，代表False Positive Rate）
• 需要添加到布隆过滤器的元素数量n

考虑到篇幅原因，这里不做这几个值的关系推导，直接整理出结果和关系式。

• 误判率ε的估算值为：[1 - e^(-kn/m)]k
• 最优散列函数数量k的推算值：对于给定的m和n，当k = m/n * ln2的时候，误判率ε最低
• 推算初始化比特容量m的值，当k = m/n * ln2的时候，m >= n * log2(e) * log2(1/ε)
  这里贴一个参考资料中m/n、k和False Positive Rate之间的关系图：

冷饭新炒：理解布隆过滤器算法的实现原理

image.png

冷饭新炒：理解布隆过滤器算法的实现原理

这里可以推算一下表格中最大参数所需要的空间极限，假设n为10亿，m/n = 32，那么m为320亿，而k为24，此时的误判率为2.17e-07(0.000000217)，需要空间3814.69727m。一般规律是：

• 当k固定的时候，m/n越大，误判率越小
• 当m/n固定的时候，k越大，误判率越大

通常情况下，k需要固定，而n是无法确定准确值，最好要评估增长趋势预先计算一个比较大的m值去降低误判率，当然也要权衡m值过大导致空间消耗过大的问题。

既然参数的关系式都已经有推导结果，可以基于关系式写一个参数生成器：

import java.math.BigDecimal;
import java.math.RoundingMode;

public class BloomFilterParamGenerator {

    public BigDecimal falsePositiveRate(int m, int n, int k) {
        double temp = Math.pow(1 - Math.exp(Math.floorDiv(-k * n, m)), k);
        return BigDecimal.valueOf(temp).setScale(10, RoundingMode.FLOOR);
    }

    public BigDecimal kForMinFalsePositiveRate(int m, int n) {
        BigDecimal k = BigDecimal.valueOf(Math.floorDiv(m, n) * Math.log(2));
        return k.setScale(10, RoundingMode.FLOOR);
    }

    public BigDecimal bestM(int n, double falsePositiveRate) {
        double temp = log2(Math.exp(1) + Math.floor(1 / falsePositiveRate));
        return BigDecimal.valueOf(n).multiply(BigDecimal.valueOf(temp)).setScale(10, RoundingMode.FLOOR);
    }

    public double log2(double x) {
        return Math.log(x) / Math.log(2);
    }

    public static void main(String[] args) {
        BloomFilterParamGenerator generator = new BloomFilterParamGenerator();
        System.out.println(generator.falsePositiveRate(2, 1, 2));  // 0.3995764008
        System.out.println(generator.kForMinFalsePositiveRate(32, 1)); // 22.1807097779
        System.out.println(generator.bestM(1, 0.3995764009)); // 2.2382615950
    }
}

这里的计算没有考虑严格的进位和截断，所以和实际的结果可能有偏差，只提供一个参考的例子。