用 Java 实现一个可用的布隆过滤器（Bloom Filter）

布隆过滤器可以使用极少的空间来判断一个元素是否存在某一个集合中，本文不具体讨论布隆过滤器的原理，而是探讨如何实现一个可用的布隆过滤器。

本文代码提取自 Apache ORC 项目。

基本概念

这里附带一些链接，适合不了解布隆过滤器的人阅读。

• https://zhuanlan.zhihu.com/p/72378274
• https://www.cnblogs.com/liyulong1982/p/6013002.html

误算率 False Positive

使用布隆过滤器时要注意：一个元素经过计算不存在时，那它一定不存在该集合中。但是如果一个元素经过计算存在时，它并不一定存在该集合中，所以其产生了一定的误算率。

所以设计一个可用的布隆过滤器，必须要确保它的误算率低。

这里我们令布隆过滤器 hasn 函数个数为 $k$，有 $m$ 个 bits，期望插入数字个数为 $n$，误算率为 $FPP$。

最佳 hash 函数数量计算公式
$$
k=\frac{m}{n}ln2,k\geq 0
$$
$k$ 为此值能够确保误算率最低。

最佳 bits 个数计算公式
$$
m=-\frac{n \cdot ln{FPP}}{(ln2)^2}
$$

想知道上面两个公式如何推导的，可以参考：https://en.wikipedia.org/wiki/Bloom_filter#Optimal_number_of_hash_functions

这里我们假设希望误算率维持在 5%，预期会有 100 个元素插入。
$$
m=-\frac{100 \cdot ln{0.05}}{(ln2)^2} \approx 640
$$

$$
k=\frac{640}{100}ln2 \approx 4
$$

故该布隆过滤器的大小应有 640 个 bits 和 4 个 hash 函数。

Hash 函数设计

一个好的 Hash 函数就是要降低碰撞率，这里我们使用 Murmur Hash 3 作为 Hash 函数，它计算速度快，而且经过广泛的测试。

Hash 函数的实现已经附带在源码中了。

Bitset

Java 作为一门高级语言，没有直接提供传统的 bit 操作。但是我们可以参考官方的 Bitset 源码实现，自己设计一个 Bitset。之所以不使用官方的 Bitset，是因为其过为复杂，没有必要。

我们使用 long 数组来存放每一个 bit。在 Java 中，一个 long 占用 64 个 bit，这样可以一次性多存点。

序列化

我们生成的布隆过滤器肯定要支持持久化到磁盘中，这里我们使用 protobuf 来作为序列化框架。序列化的 proto 文件代码如下：

message BloomFilter {
  required uint32 numHashFunctions = 1;
  repeated fixed64 bitset = 2;
}

我们只要保存 hash 函数的个数和 bitset 即可。bitset 使用 fixed64 类型是因为 long 占用 64 个 bit，bitset 使用 repeated 修饰是因为其为一个 long 数组。

源码食用方法

首先系统安装完成 protoc，用于编译 protobuf 文件。

在源码目录执行命令 protoc --java_out=src/main/java src/main/resources/BloomFilter.proto。

测试代码如下，先生成一个布隆过滤器，填充值后序列化到磁盘中名为 bloom_filter 文件。然后读取文件，检测某个值是否添加过：

package org.inlighting;

import org.inlighting.proto.BloomFilterProtos;

import java.io.FileInputStream;
import java.io.FileOutputStream;
import java.io.IOException;
import java.nio.charset.StandardCharsets;

public class Test {

    private static final String STORE_PATH = "bloom_filter";

    public static void main(String[] args) throws IOException {

        // Serialize to bloom_filter to disk.
        {
            BloomFilter bloomFilter = new BloomFilter(10, 0.05);
            System.out.println(bloomFilter.toString());
            bloomFilter.addString("Hello World");
            bloomFilter.addLong(2L);
            bloomFilter.addLong(1);
            bloomFilter.add("ni".getBytes(StandardCharsets.UTF_8));
            BloomFilterProtos.BloomFilter.Builder builder = BloomFilterProtos.BloomFilter.newBuilder();
            BloomFilterIO.serialize(builder, bloomFilter);
            builder.build().writeTo(new FileOutputStream(STORE_PATH));
        }


        // read from bloom_filter
        {
            BloomFilterProtos.BloomFilter bloomFilterProtos =
                    BloomFilterProtos.BloomFilter.parseFrom(new FileInputStream(STORE_PATH));
            BloomFilter bloomFilter =  BloomFilterIO.deserialize(bloomFilterProtos);
            System.out.println(bloomFilter.testString("Hello World")); // true
            System.out.println(bloomFilter.testLong(2)); // true
            System.out.println(bloomFilter.testLong(2L)); // true
            System.out.println(bloomFilter.testLong(1)); // true
            System.out.println(bloomFilter.testLong(1L)); // true
            System.out.println(bloomFilter.test("ni".getBytes(StandardCharsets.UTF_8))); // true
            System.out.println(bloomFilter.test("hao".getBytes(StandardCharsets.UTF_8))); // false
            System.out.println(bloomFilter.testString("hello world")); // false
            System.out.println(bloomFilter.testLong(3)); // false
        }
    }
}

输出结果：

numBits: 64, numHashFunctions: 4
true
true
true
true
true
true
false
false
false

生成的 BloomFilter 占用空间 11B，比较理想。

后序看有没有必要把这个封装成一个 jar 包上传到 Maven 中央仓库供调用。

结尾附带一个 Bloom Filter 计算器，可以在线计算需要的 hash 函数的个数和空间：https://krisives.github.io/bloom-calculator/