bugu

在 Rust 中实现的铜鸟过滤器。

铜鸟过滤器是近似集合成员查询的 Bloom 过滤器的替代品。虽然 Bloom 过滤器是众所周知的用于查询“项目 x 是否在集合中？”的空间高效数据结构，但它们不支持删除。通常需要更多的空间来启用删除（如计数 Bloom 过滤器）。

铜鸟过滤器提供了动态添加和删除项目的灵活性。铜鸟过滤器基于铜鸟哈希（因此命名为铜鸟过滤器）。它基本上是一个存储每个键的指纹的铜鸟哈希表。铜鸟哈希表可以非常紧凑，因此铜鸟过滤器可能比传统的 Bloom 过滤器使用更少的空间，适用于需要低误报率（< 3%）的应用。

有关算法和引用的详细信息，请现在使用此文章

"铜鸟过滤器：优于 Bloom" by Bin Fan, Dave Andersen and Michael Kaminsky

示例用法

use bugu::CuckooFilter;

let value: &str = "hello world";

// Create cuckoo filter with default max capacity of 1000000 items
let mut cf = CuckooFilter::new();

// Add data to the filter
let success = cf.add(value).unwrap();
// success ==> Ok(())

// Lookup if data is in the filter
let success = cf.contains(value);
// success ==> true

// Test and add to the filter (if data does not exists then add)
let success = cf.test_and_add(value).unwrap();
// success ==> Ok(false)

// Remove data from the filter.
let success = cf.delete(value);
// success ==> true

注释 & TODOs

• 此实现根据我对上述论文中提到的最佳桶/指纹/大小比例的理解，使用4个指纹的静态桶大小和1字节的指纹大小。
• 当过滤器返回 NotEnoughSpace 时，给定的元素实际上被添加到过滤器中，但随机移除了一些其他元素。可以通过实现针对该移除元素的单个项驱逐缓存来改进这一点。