fastbloom

Rust中最快的布隆过滤器。无精度妥协。完全支持并发，兼容任何哈希函数。

概述

fastbloom是一个用Rust实现的快速、灵活且精准的布隆过滤器。fastbloom的默认哈希函数是使用随机密钥的SipHash-1-3，但可以通过种子或配置使用任何哈希函数。fastbloom比现有布隆过滤器实现快2到20倍，且精度高出数个数量级。fastbloom的AtomicBloomFilter是一个避免锁争用的并发布隆过滤器。

用法

由于0.17.x版本采用了不同（改进的！）算法，布隆过滤器的序列化/反序列化与之前版本不兼容。

# Cargo.toml
[dependencies]
fastbloom = "0.17.0"

基本用法：

use fastbloom::BloomFilter;let mut filter = BloomFilter::with_num_bits(1024).expected_items(2);
filter.insert("42");
filter.insert("🦀");

以目标误报率实例化：

use fastbloom::BloomFilter;let filter = BloomFilter::with_false_pos(0.001).items(["42", "🦀"].iter());
assert!(filter.contains("42"));
assert!(filter.contains("🦀"));

使用任何哈希器：

use fastbloom::BloomFilter;
use foldhash::fast::RandomState;let filter = BloomFilter::with_num_bits(1024)
    .hasher(RandomState::default())
    .items(["42", "🦀"].iter());

完全支持并发。AtomicBloomFilter 是 RwLock 的直接替代品，因为所有方法都接收 &self：

use fastbloom::AtomicBloomFilter;let filter = AtomicBloomFilter::with_num_bits(1024).expected_items(2);
filter.insert("42");
filter.insert("🦀");

背景

布隆过滤器是一种空间高效的近似成员集合数据结构，由底层的位数组支持，用于跟踪项目成员资格。插入/检查成员时，会根据项目的哈希值设置/检查多个位的位置。成员检查可能出现误报，但不会出现漏报。构建完成后，布隆过滤器的底层内存使用量和每个项目的位数都不会改变。查看更多。

hash(4) ──────┬─────┬───────────────┐
              ↓     ↓               ↓
0 0 0 0 0 0 0 1 0 0 1 0 0 0 0 0 0 0 1 0
  ↑           ↑           ↑
  └───────────┴───────────┴──── hash(3) (not in the set)

实现

fastbloom 之所以极其快速，是因为它通过每个元素仅使用一次真实哈希高效地派生出多个索引位，并利用了关于布隆过滤器的其他研究成果。fastbloom 对原始 64 位哈希的两个 32 位半部分采用“哈希组合”技术。每个后续哈希通过将原始哈希值与不同常数结合，使用模运算和按位操作导出。这样得到的一组哈希函数实际上是独立且均匀分布的，尽管它们是从相同的原始哈希函数派生的。计算两个原始哈希的组合比分别使用不同种子重新计算哈希要快。这一技术在这篇论文中有详细解释。

速度

AMD Ryzen 9 5900X 12核处理器 (3.70 GHz)
64 位操作系统，基于 x64 的处理器

使用的哈希器：

- xxhash: sbbf

- Sip1-3: bloom, bloomfilter, probabilistic-collections

- foldhash: fastbloom

基准测试来源

准确度

fastbloom 并不牺牲准确度。以下是与其他布隆过滤器库的误报率对比：

基准测试来源

可用特性

rand - 默认启用，该特性使 DefaultHasher 使用 thread_rng() 作为随机状态源，而非硬件源。从用户空间获取熵明显更快，但需要额外依赖。禁用此特性（使用 default-features = false）则使 DefaultHasher 使用 foldhash 获取熵，代码更简洁但速度较慢。
serde - 当可能时，BloomFilter 实现了 Serialize 和 Deserialize。
loom - AtomicBloomFilter 使用 loom 的原子操作，支持 loom 测试。

参考资料

许可证

可选择以下任一许可证

Apache 许可证，版本 2.0

(LICENSE-APACHE 或 http://www.apache.org/licenses/LICENSE-2.0)

MIT 许可证

(LICENSE-MIT 或 http://opensource.org/licenses/MIT)

由您选择。

贡献

除非您明确说明，否则任何您有意提交用于包含在本作品中的贡献，根据 Apache-2.0 许可证定义，应按上述双重许可授权，且无任何额外条款或条件。

--- Tranlated By Open Ai Tx | Last indexed: 2026-05-15 ---