没有键的压缩映射，基于磨损的丝带级联

这个研究级库旨在实现空间高效的静态函数，性能适合CRLite的演变。当然，它可能也适用于其他领域。

由Mike Hamburg编写。© 2020-2022 Rambus Inc, MIT许可。这个attic_c代码包含了Jean-Philippe Aumasson和Daniel J. Bernstein的公有领域SipHash代码；以及基于公有领域Murmur3代码的Peter Scott的代码。

这个实现仍然是研究级的。不要在生产环境中部署它。特别是，它依赖于bincode版本2.0.0-RC.1，该版本在发布前可能会有重大变化。

C FFI目前不完整，我可能需要将类型名称更改为命名空间化的，或者更不荒谬的名称。如果需要在C FFI中添加或更改某些内容，请通知我（通过问题）。目前，它不公开Rust侧的全部功能，尤其是在构建选项方面。

静态函数，即CompressedMap

静态函数问题是要压缩类型为K -> V的映射M。压缩可以丢弃键。使用压缩映射，应该可以确定M[k]对于M的所有键k。然而，可能无法列出所有映射键，也无法确定某个键是否在映射中。如果你查询了k不在M中的某个键，那么将返回任意结果。

本库提供了CompressedMap，这是一个从可哈希类型K到值V的静态函数。值存储在结构体中，因此它们应该可克隆，以便在程序中使用，或者如果需要序列化，则可序列化。CompressedMap格式针对值数量少且小的场景进行了优化，例如布尔值、小整数、短字符串等。最佳用例是正好两个值（例如true、false）和数百万或更多键。它不会尝试压缩值，因此不要使用此结构体存储大字符串。

CompressedMap将收集值的分布统计信息，并使用这些信息来最小化存储大小。它使用的存储空间略多于值的香农熵：在0.1%到11%之间。这通常比CRLite少约40%的空间。

压缩随机映射

本库还提供了CompressedRandomMap。它将可哈希类型K映射到最多64位的整数类型V。与CompressedMap不同，CompressedRandomMap不存储其值，也不使用统计信息来尝试减小存储大小：它更适合值是均匀随机值的情况。

近似集

与近似集问题密切相关的是压缩对象集S。您可以查询元素x以确定它是否在S中。如果它确实在S中，则查询将始终返回true。如果不是，则通常会返回false，但可能会有误报，它将返回true。

本库提供了ApproxSet，这是一个可哈希键的近似集。与布隆过滤器相比，ApproxSet构建需要更长的时间（和多倍的内存），但查询速度更快；占据约30%的空间。

其他细节

有关这些结构的构建、序列化、注意事项等，请参阅Rust文档。

内部结构

该库使用所谓的“破烂的丝带过滤器”，因为它们类似于丝带过滤器。这些过滤器在构建时的渐近时间为Õ(n^(3/2))时间和Õ(n)内存。在实际应用中，由于内存消耗，它们在通用硬件上的行数上限约为几亿到十亿行，除非有人能够提出更轻的构建算法。

对于CompressedMap，并非每个键在每个级别都被使用。粗略地说，如果有单个“主导”值出现的频率远高于其他值，则内存消耗取决于非主导值出现频率的某个倍数（2-3倍）。