.NET 中用 C# 构建布隆过滤器（Bloom Filter）实战教程

.NET 2025年09月08日12:31

布隆过滤器是一种空间高效的概率型数据结构，常用于快速判断某元素绝对不存在，从而优化缓存、防止缓存穿透或数据库重复查询场景。尤其在 .NET 系统中，它能显著减少数据库或其他后端服务的压力。

.NET 上常用的布隆过滤器库

在 .NET 社区，你可以使用成熟的 NuGet 包来简化开发，例如 BloomFilter.NetCore。该库支持配置位数组大小、哈希函数数量，并能根据目标误判率与预计元素数量自动计算配置，同时提供多种哈希函数选择，还支持 Redis 后端并发使用，适合内存与分布式场景。

基本用法示例（内存版）：

IBloomFilter bf = FilterBuilder.Build(10_000_000, 0.01);
bf.Add("Value");
Console.WriteLine(bf.Contains("Value"));

若需跨服务共享过滤器，也可使用 Redis 后端版本：

IBloomFilter bf = FilterRedisBuilder.Build("localhost", "InstanceName", 5_000_000, 0.001);
bf.Add("Value");
Console.WriteLine(bf.Contains("Value"));

这种方式极大简化了布隆过滤器的集成过程，并具备高并发适用性。

自定义 C# 实现：从零搭建布隆过滤器

若你希望深入理解实现细节或进行定制，以下是简单实战步骤：

BitArray 存储位图

使用 BitArray 维护位状态，通过位数组标记元素映射位置。

多哈希函数处理

可通过不同种子值依次调用 GetHashCode() 来模拟多个哈希函数。

Add 与 Contains 方法

Add(item)：依次通过 k 个哈希函数映射，设置对应位为 1。

Contains(item)：检查对应位是否全为 1，若有 0 则“绝对不存在”；若都是 1，则“可能存在”。

以下是简明的 C# 示例伪代码，相当适合入门：

public class BloomFilter
{
    private BitArray bits;
    private int size;
    private int hashCount;

    public BloomFilter(int size, int hashCount)
    {
        this.size = size;
        this.hashCount = hashCount;
        bits = new BitArray(size);
    }

    private int Hash(string item, int seed)
    {
        int hash = item.GetHashCode() ^ seed;
        return Math.Abs(hash) % size;
    }

    public void Add(string item)
    {
        for (int i = 0; i < hashCount; i++)
        {
            bits.Set(Hash(item, i), true);
        }
    }

    public bool Contains(string item)
    {
        for (int i = 0; i < hashCount; i++)
        {
            if (!bits.Get(Hash(item, i)))
                return false;
        }
        return true;
    }
}

这是一个精炼且可运行的示范版本，适合于原理教学或小规模场景开发。