b100m-filter

此项目已迁移至 https://crates.io/crates/fastbloom

在Rust中最快的布隆过滤器。不牺牲精度。使用任何散列函数。

用法

# Cargo.toml
[dependencies]
b100m-filter = "0.4.0"

use b100m_filter::BloomFilter;

let num_blocks = 4; // by default, each block is 512 bits
let values = vec!["42", "🦀"];

let filter = BloomFilter::builder(num_blocks).items(values.iter());
assert!(filter.contains("42"));
assert!(filter.contains("🦀"));

use b100m_filter::BloomFilter;
use ahash::RandomState;

let num_blocks = 4; // by default, each block is 512 bits

let filter = BloomFilter::builder(num_blocks)
    .hasher(RandomState::default())
    .items(["42", "🦀"].iter());

背景

布隆过滤器是一种节省空间的近似成员集数据结构。存在从contains返回假阳性的可能性，但不存在假阴性，即对于集合中的所有项的contains保证返回true，而对于集合中所有项的contains可能返回false。

通过底层位向量支持的阻塞布隆过滤器，被分成512、256、128或64位的“块”，以跟踪项成员资格。要插入，根据项的哈希值设置底层位向量中的若干位。要检查成员资格，根据项的哈希值检查底层位向量中的若干位。

一旦构建，布隆过滤器的底层内存使用量和每项位数都不会改变。

实现

b100m-filter非常快，因为它使用L1缓存友好的块，并且从每个值的一个哈希值中有效地推导出许多索引位。与传统的实现相比，b100m-filter对于小项集的速度快2-5倍，对于大项集的速度快几百倍。在所有情况下，b100m-filter都保持了有竞争力的假阳性率。

运行时性能

与其他布隆过滤器crate的运行时比较

• 布隆内存大小 = 16Kb
• 1000个包含的项
• 每个项364个哈希

*fastbloom-rs使用XXHash，比SipHash快。

假阳性性能

b100m-filter不会牺牲精度。以下是与其他布隆过滤器crate的假阳性率比较

可扩展性

b100m-filter的可扩展性非常好。

随着位数和集合大小的增加，传统的布隆过滤器需要为每个项执行更多的哈希操作以优化假阳性率。然而，b100m-filter的最佳哈希数是有限的，即使在许多项的情况下也能保持接近零的率

布隆过滤器的速度与哈希数成正比。

参考文献

• 布隆过滤器
• 更少的哈希，相同的性能：构建更好的布隆过滤器
• 快速替代模数减少

许可证

根据以下之一许可

• Apache License，版本2.0 (LICENSE-APACHE 或 https://apache.ac.cn/licenses/LICENSE-2.0)
• 麻省理工学院许可证（LICENSE-MIT 或 http://opensource.org/licenses/MIT）

根据您的选择。

贡献

除非您明确声明，否则您有意提交以供包含在本作品中的任何贡献，根据Apache-2.0许可证的定义，应双重许可如上所述，无任何额外条款或条件。