用 Java 实现一个可用的布隆过滤器(Bloom Filter)

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

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

基本概念

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

误算率 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/

原创文章,作者:Smith,如若转载,请注明出处:https://www.inlighting.org/archives/java-implement-bloom-filter

打赏 微信扫一扫 微信扫一扫
SmithSmith
上一篇 2021年1月1日 下午1:33
下一篇 2019年8月3日 上午12:18

相关推荐

  • Spring Boot 2 + Spring Security 5 + JWT 的单页应用

    此前我已经写过一篇类似的教程,但那时候使用了投机的方法,没有尊重 Spring Security 的官方设计,自己并不感到满意。这段时间比较空,故重新研究了一遍。 老版本:http…

    2019年8月3日
    1.7K0
  • Spring Boot2 + Spring Security + Thymeleaf 简单教程

    因为有一个项目需采用MVC构架,所以学习了Spring Security并记录下来,希望大家一起学习提供意见 如果有疑问,请在 GitHub 中发布 issue,我有空会为大家解答…

    2019年8月2日
    1.5K0
  • JDK 动态代理踩坑

    最近阅读 Hadoop 的源码,看到各种动态代理,打算学习下。虽然以前也学过,但是感觉就是死记硬背的代码,有些地方根本不懂。温习了一遍网上 JDK 动态代理的教程后,自己尝试再一次…

    2021年1月1日
    1.1K0

发表回复

您的邮箱地址不会被公开。 必填项已用 * 标注