flit

BloomFilter 是一种概率性数据结构，可以快速且确定地断定它不包含一个项。另一方面，它只能断定它 可能 包含一个项，即数据结构具有大于 0% 的固有误报率。

可以往 Bloom 过滤器中添加项，但不能删除 - 这会引入误报情况。如果需要，可能需要使用计数 Bloom 过滤器（本软件包中尚未实现）作为替代。

此实现基于 Rust 对 xxHash 哈希算法 的实现，twox-hash。

参考资料

• Less Hashing, Same Performance: Building a Better Bloom Filter
• 维基百科文章
• Bloom 过滤器示例
• Bloom 过滤器计算器

示例

use flit::BloomFilter;

let mut filter = BloomFilter::new(0.01, 10000);
filter.add(&"Hello, world!");

assert_eq!(filter.might_contain(&"Hello, world!"), true); // probably true
assert_eq!(filter.might_contain(&"Dogs are cool!"), false); // definitely false!

基准测试

基准测试使用 criterion 进行。

提供了添加 100、1000 和 10000 个 u32 到 BloomFilter 中的简单基准测试。要运行基准测试，请运行

cargo bench

add 100                 time:   [22.454 us 22.477 us 22.507 us]
add 1000                time:   [224.44 us 224.65 us 224.90 us]
add 10000               time:   [2.2424 ms 2.2443 ms 2.2463 ms]