xorf

• 文档
• Crates.io 注册

此仓库托管一个Rust库，实现了xor过滤器及其衍生品

• 二进制Fuse过滤器（最推荐）
  • BinaryFuse8，BinaryFuse16，BinaryFuse32
• Xor过滤器
  • Xor8，Xor16，Xor32
• Fuse过滤器（已弃用，请使用二进制Fuse过滤器代替）
  • Fuse8，Fuse16，Fuse32

Xor过滤器是一种使用少量内存快速近似集合成员的数据结构。类似于xor过滤器的概率过滤器，在允许偶尔出现假正例的情况下非常有用，但重要的是要节省空间和时间。换句话说，它们与通用哈希集合相比，以效率为代价换取准确性。类似于xor过滤器的过滤器通常与更大的基于哈希的数据结构一起使用，过滤器执行“第一轮”工作以避免不必要地使用更昂贵的资源。例如，xor过滤器等过滤器可以用于减少缓存中的磁盘写入，或者在浏览器中识别恶意URL。

异或过滤器比布隆过滤器（Bloom filter）和布谷鸟过滤器（Cuckoo filter）更快、更小。在构建过程中，异或过滤器会承受相对的时间惩罚，但在查找时非常快；预期在多次查询之后，过滤器的构建是摊销的。Daniel Lemire的go实现提供了异或过滤器优点的有用总结以及其他异或过滤器库的列表。

此库是no_std并且needs_allocator。

xorf还提供了一个HashProxy，用于使用任意键类型的Xor过滤器。

安装

在Cargo.toml中添加对xorf的依赖

[dependencies]
xorf = "M.m.p" # use a desired version

版本列表可在crates和存储库的发布中找到。

用法

请参阅库文档以获取用法信息。

功能

自定义分配器

要使用自定义全局分配器，您必须使用rustc的夜间版本，并已为xorf启用了nightly功能。

[dependencies]
xorf = { version = "M.m.p", features = ["nightly"] }

这将标记该软件包为needs_allocator，然后您将需要提供它。在此期间，全局使用自定义分配器。

序列化/反序列化

可以使用serde功能启用与serde的序列化和反序列化。

[dependencies]
xorf = { version = "M.m.p", features = ["serde"] }

默认功能

均匀随机

默认情况下，xorf使用uniform-random功能，它使用随机值而不是初始化为零来填充未使用的指纹条目。这提供了略低的误报率，但初始化成本更高。查找成本不受影响。

以下可视化了具有和不具有uniform-random功能的1,000,000个元素的BinaryFuse8过滤器中零值指纹的分布。注意y轴的刻度不同。

BinaryFuse8未使用uniform-random	BinaryFuse8使用uniform-random

要禁用uniform-random功能，指定应禁用默认功能

[dependencies]
xorf = { version = "M.m.p", default-features = false }

二进制融合

默认情况下，xorf使用binary-fuse功能，该功能添加了对二进制融合过滤器实现的支持并公开了它们。此功能引入了libm的依赖项，但没有运行时成本。此功能强烈推荐，因为二进制融合过滤器是Xor过滤器家族中最强大的。

开发

xorf的开发针对此存储库的master分支。

可以通过运行check脚本来测试更改。

scripts/check lf     # validates lint and format
scripts/check test   # tests source code

贡献

欢迎贡献。任何贡献都不算太小，所有贡献都将受到赞赏。

许可

MIT