商滤波器

商滤波器是一种空间效率高的概率性数据结构，用于集合成员查询。它通过将集合中项目的哈希值根据其除以过滤器大小的商划分为“桶”。这使得过滤器能够使用相对较少的内存存储大量项目，同时仍然提供一种快速检查给定项目是否在集合中的方法。商滤波器通常用于内存是限制因素的场合，如内存数据库和实时流系统。

该实现基于名为 大规模数据集的算法与数据结构 的书籍。

用法

要使用此包，只需将以下字符串添加到您的 Cargo.toml

quotient-filter = "0.2.3"

    // there is QuotientFilter32 and QuotientFilter16 as well
    // let mut filter = QuotientFilter16::new(5).unwrap();
    // let mut filter = QuotientFilter32::new(5).unwrap();
    // The input (here 5) means the table size will be 2^5 and 5 bits will be used for indexing.
    let mut filter = QuotientFilter::new(5).unwrap();
    // if method names end with 'value', it uses fnv1a as default
    let idx = filter.insert_value(&1_u8.to_be_bytes()).unwrap(); // returns Result<location of insert>
    // if you want to use something else than fnv1a
    let your_hash_result = your_hash_function(&1_u8.to_be_bytes());
    let idx2 = filter.insert(your_hash_result);

支持插入、删除、查找、合并和调整大小。

实现

在额外模块下，存在 u32 和 u16 版本，使用时可能是更好的选择。商滤波器本质上是一个围绕余数（u64、u32 或 u16）数组的包装，以及元数据（u8）。在初始化时我们提供大小。然而，它能够调整其大小并与其他合并。它通过窃取位来实现调整大小和合并。我们从余数中窃取一个位，因此商的大小变为 5 位，余数的大小变为 27 位，表的大小为 2^5，是之前的两倍。

底层发生了大量的位操作。例如，您使用商大小为 4 的 QuotientFilter32 初始化。它使用最左边的 4 位进行索引（不保存任何地方），其余 28 位与元数据一起保存到表中。使用元数据，您可以执行其他操作，甚至可以恢复原始的 u32 指纹，尽管没有保存 4 位。调整大小和合并通过位窃取来实现。我们从余数中窃取一个位，因此商的大小变为 5 位，余数的大小为 27 位，表的大小为 2^5，是之前的两倍。