高级数据结构之布隆过滤器

封面画师：Nengoro(ネんごろぅ)     封面ID：67041803

本文参考视频：小马哥教育(SEEMYGO) 2019年 恋上数据结构与算法（第二季）

源码仓库：mofan212/data-structure-and-algorithm (github.com)

辅助学习网址：数据结构和算法动态可视化     Data Structure Visualizations

0. 需求分析

如果需要 经常 判断 1 个元素是否存在，可以怎么做？

很容易想到使用哈希表（HashSet、HashMap），将元素作为 key 去查找。使用哈希表进行判断时，时间复杂度为 $O(n)$，但是哈希表的空间利用率不高，需要占用比较多的内存资源。

如果需要编写一个网络爬虫去爬 10 亿个网站数据，为了避免爬取到重复的网站，如何判断某个网站是否被爬取过呢？

很显然，使用哈希表并不是最佳的选择，因为会占用非常非常多的内存资源。

是否存在时间复杂度低、内存占用比较少的方案？

可以使用 布隆过滤器（Bloom Filter）。

1. 布隆过滤器

1.1 基本概念

布隆过滤器在 1970 年由布隆提出，它是一个空间效率高的 概率型 数据结构，可以用来判断一个元素 一定 不存在或者 可能 存在。

因此布隆过滤器的优缺点也很明显：

• 优点：空间效率和查询时间都远远超过一般的算法
• 缺点：有一定的误判率、删除困难

布隆过滤器实质上是一个很长的二进制向量和一系列随机映射函数（Hash 函数）。

布隆过滤器的适用场景：

• 经常 要判断某个元素是否存在
• 元素数量巨大，希望占用较少的内存空间
• 允许有一定的误判率

常见应用：网页黑名单系统、垃圾邮件过滤系统、爬虫的网址判重系统、解决缓存穿透问题等。

1.2 实现原理

假设布隆过滤器由 20 个二进制位、3 个哈希函数组成，每个元素经过哈希函数处理都能生成一个索引位置。初始时，20 个二进制位都是 0。

添加元素 时，在给定的二进制位中，将每一个哈希函数生成的索引位置都设为 1。

假设需要添加元素 A 和 B，A 经过每个哈希函数的运算后，得到的索引位置是 4、7、18，B 经过每个哈希函数的运算后，得到的索引位置是 2、7、15：

由于不同的元素在经过同一个哈希函数的运算后可能得到相同的结果，因此 查询元素是否存在 时：

• 如果 有 一个哈希函数生成的索引位置不为 1，代表 一定 不存在；
• 如果 每 一个哈希函数生成的索引位置都为 1，代表可能存在。

那怎么 删除元素 呢？

同样是因为不同的元素经过同一个哈希函数的运算后可能得到相同的结果，因此在删除元素时，不能简单地将被删除元素使用哈希函数计算出的索引位置设置为 0，其他元素计算出的索引位置有可能恰好等于被删除元素的索引位置。

在布隆过滤器中删除一个元素是比较困难的，因此许多布隆过滤器的实现都不会提供删除元素的 API。

添加、查询的时间复杂度都是 $O(k)$，$k$ 是哈希函数的个数。空间复杂度是 $O(m)$，$m$ 是二进制位的个数。

1.3 误判率

布隆过滤器的误判率 $p$ 受 3 个因素影响，二进制位的个数 $m$、哈希函数的个数 $k$ 以及数据规模 $n$：

$$p = \Bigg( 1 - e^{- \frac{k(n + 0.5)}{m - 1}} \Bigg)^k$$

由于布隆过滤器常用于数据规模 $m$ 非常大的场景，因此误判率 $p$ 可以使用如下近似计算：

$$p \approx \Bigg( 1 - e^{- \frac{kn}{m}} \Bigg)^k$$

在已知误判率 $p$ 和数据规模 $n$ 的情况下，二进制位的个数 $m$ 和哈希函数的个数 $k$ 的计算公式如下：

$$\begin{aligned} m & = - \frac{nlnp}{(ln2)^2} \\ \\ k & = \frac{m}{n}ln2 \\ \\ k & = - \frac{lnp}{ln2} = -log_2p \end{aligned}$$

2. 代码实现

2.1 构造方法与成员变量

根据【1.3 误判率】给出的公式可知，在使用布隆过滤器时应当提供允许的误判率 $p$ 和数据规模 $n$，因此应该提供如下的构造方法和成员变量：

/**
 * @author mofan
 * @date 2022/12/3 17:08
 */
public class BloomFilter<T> {

    /**
     * 二进制向量的长度（一共有多少个二进制位）
     */
    private final int bitSize;

    /**
     * <p>长整数数组，存储二进制向量</p>
     * <p>long 占 8 字节，1 字节 8 bit，因此一个 long 可以表示 64 位</p>
     */
    private final long[] bits;

    /**
     * 哈希函数的个数
     */
    private final int hashSize;

    /**
     * 布隆过滤器构造方法
     *
     * @param n 数据规模
     * @param p 允许的误判率，范围 (0, 1)
     */
    public BloomFilter(int n, double p) {
        if (n <= 0 || p <= 0 || p >= 1) {
            throw new IllegalArgumentException("wrong n or p");
        }
        double ln2 = Math.log(2);
        // 二进制向量的长度
        bitSize = (int) (-(n * Math.log(p)) / (ln2 * ln2));
        // 哈希函数的个数
        hashSize = (int) (bitSize * ln2 / n);
        // bits 数组的长度，向上取整
        bits = new long[(bitSize + Long.SIZE - 1) / Long.SIZE];
    }
}

2.2 需要提供的接口

根据【1.2 实现原理】可知，布隆过滤器通常会提供 添加元素 和 判断元素是否存在 共两个接口，即：

/**
 * 添加元素
 *
 * @param value 被添加的元素
 * @return value 的添加是否造成了二进制位的变化
 */
public boolean put(T value) {
    return false;
}

/**
 * 判断某个元素是否存在
 *
 * @param value 目标元素
 * @return 不存在 --> false，存在 --> true
 */
public boolean contains(T value) {
    return false;
}

2.3 添加元素

通过传入的误判率 $p$ 和数据规模 $n$ 可以确定二进制位的个数 $m$ 和哈希函数的个数 $k$，那么在添加元素时需要使用使用指定的哈希函数求出添加元素在二进制位中的位置。

为了简单起见，使用以下方式实现元素的添加：

/**
 * 添加元素
 *
 * @param value 被添加的元素
 * @return value 的添加是否造成了二进制位的变化
 */
public boolean put(T value) {
    nullCheck(value);

    int hash1 = value.hashCode();
    int hash2 = hash1 >>> 16;

    boolean result = false;
    for (int i = 1; i <= hashSize; i++) {
        int combinedHash = hash1 + (i * hash2);
        if (combinedHash < 0) {
            combinedHash = ~combinedHash;
        }
        // 生成索引
        int index = combinedHash % bitSize;
        // 将 index 位置的二进制位设置为 1
        if (this.set(index)) result = true;
    }
    return result;
}

private void nullCheck(T value) {
    if (value == null) {
        throw new IllegalArgumentException("value must not be null.");
    }
}

索引 index 的由来不重要，此处只是简单的模拟使用给定的哈希函数个数进行计算。

在 for 循环体的最后一行，调用了 set() 方法，该方法可以将 index 位置的二进制位设置为 1。

/**
 * 设置 index 位置的二进制位为 1
 *
 * @param index 目标索引
 * @return index 位置的二进制位是否从 0 变成了 1
 */
private boolean set(int index) {
    // 计算 index 位于 long 数组中的哪一个 long 中
    long value = bits[index / Long.SIZE];
    // 找到 index 在 long 中的哪个二进制位
    long bitValue = 1L << (index % Long.SIZE);
    // 将二进制位设置为 1 后再重新赋值
    bits[index / Long.SIZE] = value | bitValue;
    // 判断 index 位置的二进制位是否从 0 变成了 1
    return (value & bitValue) == 0;
}

由于采用 long 数组进行二进制位的存储，因此需要先计算 index 指向的二进制索引位置是在 long 数组中的哪个元素中，之后再计算是 long 值中的哪个二进制位。

要想将指定位置的二进制位设置为 1，可以使用按位或 | 运算，其运算规则是“有 1 取 1，全 0 为 0”。假设有二进制数 100000，现需要将其第三位二进制位设置为 1，使用按位或运算：

    100000
  | 000100
-------------
    100100

二进制数 000100 就是 1 << 2，1 左移 2 位。

在判断指定位置的二进制位是否发生了变化，可以使用按位与 & 运算，其运算规则是“全 1 为 1，反之为 0”。假设将二进制数 100000 的第三位二进制为设置为 1，那么会得到 100100，可以使用按位与运算描述原二进制数的第三位二进制位发生了变化：

    100000
  & 000100
-------------
    000000

假设将二进制数 100100 的第三位二进制位设置为 1，由于指定位置的二进制位本就是 1，因此这个位置的二进制位不会发生变化，用按位与描述这种情况：

    100100
  & 000100
-------------
    000100

在这种情况下，使用按位与运算得到的结果为 0 时，表示指定位置的二进制位发生了变化，如果得到的结果不是 0，表示指定位置的二进制位没有发生变化。

2.4 判断元素是否存在

在判断一个元素是否存在于布隆过滤器中时，需要使用与添加元素时相同的哈希函数计算出若干个二进制位的索引值，并判断指向的二进制位是否为 0，如果有一个不为 0，就表示指定元素在布隆过滤器中不存在。

/**
 * 判断某个元素是否存在
 *
 * @param value 目标元素
 * @return 不存在 --> false，存在 --> true
 */
public boolean contains(T value) {
    nullCheck(value);
    // 利用value生成2个整数
    int hash1 = value.hashCode();
    int hash2 = hash1 >>> 16;

    for (int i = 1; i <= hashSize; i++) {
        int combinedHash = hash1 + (i * hash2);
        if (combinedHash < 0) {
            combinedHash = ~combinedHash;
        }
        // 生成一个二进制的索引
        int index = combinedHash % bitSize;
        // 查询第index位置的二进制是否为0
        if (!this.get(index)) return false;
    }
    return true;
}

在 for 循环的最后一行调用了 get() 方法，该方法可以判断指定位置的二进制位是否为 0。

/**
 * 获取 index 位置二进制位的值
 *
 * @param index 目标索引
 * @return true --> 1，false --> 0
 */
private boolean get(int index) {
    // 计算 index 位于 long 数组中的哪一个 long 中
    long value = bits[index / Long.SIZE];
    return (value & (1L << (index % Long.SIZE))) != 0;
}

get() 方法相比于 set() 方法更加简单，可以发现在 set() 方法的基础上将重新赋值的那一行去掉后就得到了 get() 方法，因此不再赘述。

2.5 测试验证

public static void main(String[] args) {
    int n = 1_00_0000;
    BloomFilter<Integer> filter = new BloomFilter<>(n, 0.01);
    for (int i = 1; i <= n; i++) {
        filter.put(i);
    }

    for (int i = 1; i <= n; i++) {
        assert filter.contains(i);
    }
}

2.6 第三方类库

在实际开发中如果需要使用到布隆过滤器，可以考虑在工程中引入 Google 的 Guava 或国产的 Hutool。

Guava 的 pom.xml 坐标：

<!-- https://mvnrepository.com/artifact/com.google.guava/guava -->
<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>${guava-version}</version>
</dependency>

Hutool 的 pom.xml 坐标：

• 只引入 Hutool 的 bloomFilter 模块：

<!-- https://mvnrepository.com/artifact/cn.hutool/hutool-bloomFilter -->
<dependency>
    <groupId>cn.hutool</groupId>
    <artifactId>hutool-bloomFilter</artifactId>
    <version>${hutool-bloomFilter-version}</version>
</dependency>

• 引入 Hutool 的所有模块：

<!-- https://mvnrepository.com/artifact/cn.hutool/hutool-all -->
<dependency>
    <groupId>cn.hutool</groupId>
    <artifactId>hutool-all</artifactId>
    <version>${hutool-all-version}</version>
</dependency>