Qfilter

类似于高效Bloom过滤器的数据结构，基于Rank Select Quotient Filter (RSQF)。

这是一个小型且灵活的通用 AMQ-Filter。它不仅支持类似于Bloom过滤器的近似成员测试，还支持删除、合并、调整大小和 serde 序列化。

• 高性能
• 支持删除操作
• 极为紧凑，比类似的过滤器更加紧凑
• 可以以初始较小的容量创建，并根据需要增长
• (De)Serializable with serde
• 可移植的Rust实现
• 仅使用可验证的不安全操作

此数据结构类似于一个存储指纹的非常紧凑的哈希表。指纹类似于哈希值，但可能是截断的。假阳性的原因是多个项目可以映射到相同的指纹。更多信息请参阅quotient filter Wikipedia页面，其中描述了类似但不太优化的数据结构版本。实际实现基于Rank Select Quotient Filter (RSQF)。

公共API还公开了指纹API，可用于简洁地存储u64哈希值。

示例

let mut f = qfilter::Filter::new(1000000, 0.01);
for i in 0..1000 {
    f.insert(i).unwrap();
}
for i in 0..1000 {
    assert!(f.contains(i));
}

哈希器

使用的哈希算法是xxhash3，它提供高性能和跨平台的稳定性。

过滤器大小

对于给定的容量和错误概率，RSQF可能比等效的Bloom过滤器或其他AMQ-Filters需要的空间要少得多。

版本0.1和0.2之间的兼容性

版本0.2更改了公共API（例如故障构造函数），这需要版本号的重大增加。

序列化在版本0.1和0.2之间双向兼容。

未实现

• 附加指纹值
• 使用指纹值进行计数，而不是指纹重复
• 更高级的增长策略（InfiniFilter）。

旧版 x86_64 CPU 支持

实现假定在为 x86_64 目标编译时，存在 popcnt 指令（等同于 integer.count_ones()）。理论上这不能保证，因为该指令仅在 2007/2008 年之后发布的 AMD/Intel CPU 上可用。如果不符合这种情况，Filter 构造函数将引发恐慌。

可以通过启用 legacy_x86_64_support 选项来支持此类旧版 x86_64 CPU，这会带来约 10% 的性能损失。

许可证

本项目采用 MIT 许可证。