可扩展布隆过滤器

CRATES.IO | 文档

概述

Scalable Bloom Filters的实现，同时提供serde序列化和反序列化。

布隆过滤器允许你使用insert插入项，然后使用contains测试关联。它空间和时间效率高，但以假阳性为代价。特别是，如果contains返回true，它可能在过滤器中。但如果contains返回false，它肯定不在布隆过滤器中。

你可以通过适当地设置desired_error_prob和est_insertions来控制失败率。

use growable_bloom_filter::GrowableBloom;

// Create and insert into the bloom filter
let mut gbloom = GrowableBloom::new(0.05, 1000);
gbloom.insert(&0);
assert!(gbloom.contains(&0));

// Serialize and Deserialize the bloom filter
use serde_json;

let s = serde_json::to_string(&gbloom).unwrap();
let des_gbloom: GrowableBloom = serde_json::from_str(&s).unwrap();
assert!(des_gbloom.contains(&0));

// Builder API
use growable_bloom_filter::GrowableBloomBuilder;
let mut gbloom = GrowableBloomBuilder::new()
    .estimated_insertions(100)
    .desired_error_ratio(0.05)
    .build();
gbloom.insert(&0);
assert!(gbloom.contains(&0));

应用

布隆过滤器通常用作预缓存以避免昂贵的操作。例如，如果你需要询问一万个服务器是否有数据XYZ，你可以使用GrowableBloom来确定哪些服务器没有XYZ。

稳定性

序列化和反序列化的布隆过滤器可以在不同的平台上传输和使用，不受端序、架构或字大小的限制。

请注意，稳定性仅保证在同一主要版本内。

从1.x升级到2.x

• 任何1.x序列化的布隆过滤器将无法在2.x中加载。
• 其他API更改不大。