Cuckoo Filter

文档

Cuckoo filter 是一种用于近似集合成员查询的 Bloom filter 的替代品。虽然 Bloom filter 是众所周知的空间高效数据结构，用于查询诸如“项目 x 是否在集合中？”等问题，但它不支持删除。允许删除的变体（如计数 Bloom filter）通常需要更多的空间。

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

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

"Cuckoo Filter: Better Than Bloom" by Bin Fan, Dave Andersen and Michael Kaminsky

示例用法

extern crate 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

C接口

此crate提供C接口，以便将其嵌入到除Rust之外的其他语言中。有关详细信息，请参阅C接口文档。

注意事项 & TODOs

• 此实现根据我对上述论文中提到的最佳桶/指纹/大小比率的理解，使用静态桶大小为4个指纹和指纹大小为1字节。
• 当过滤器返回 NotEnoughSpace 时，给定的元素实际上被添加到过滤器中，但随机删除了另一个元素。可以通过实现用于该删除元素的单一项目驱逐缓存来改进这一点。
• 没有为C语言以外的其他语言提供高级绑定。例如，可以使用milksnake为Python添加这些绑定。