布隆过滤器

**注意：此版本来自https://github.com/seiflotfy/rust-cuckoofilter。@seiflotfy的原始版本完全正常工作，但最新的master版本（0.4）尚未在crates.io上发布。为了发布tinysearch，我们在那里发布了我们自己的版本。TODO：一旦https://github.com/seiflotfy/rust-cuckoofilter/issues/30得到解决，就切换到上游版本。**

文档

布隆过滤器是一种用于近似集合成员查询的布隆过滤器的替代品。虽然布隆过滤器是众所周知的节省空间的数据结构，用于查询诸如“项目x是否在集合中？”等问题，但它不支持删除。实现删除的方差（如计数布隆过滤器）通常需要更多的空间。

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

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

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

示例用法

extern crate tinysearch_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为将其嵌入到除Rust以外的其他语言中提供了一个C接口。有关更多详细信息，请参阅C接口文档。

注意事项 & TODOs

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