cuckoofilter

Cuckoo 过滤器 Cuckoo 过滤器是一种用于近似集合成员查询的 Bloom 过滤器替代方案。虽然 Bloom 过滤器是一种著名的空间效率高的数据结构，可用于处理诸如"如果项 x 位于集合中?"这样的查询，但它们不支持删除。为了支持删除（例如计数 Bloom 过滤器），通常需要更多的空间。

Cuckoo 过滤器提供了动态添加和删除项目的灵活性。Cuckoo 过滤器基于 Cuckoo 哈希（因此称为 Cuckoo 过滤器）。本质上，它是一个 Cuckoo 哈希表，存储每个键的指纹。Cuckoo 哈希表可以高度压缩，因此 Cuckoo 过滤器可以占用比传统的 Bloom 过滤器更少的空间，适用于需要低误报率的应用程序（= log2(2b/r) 位）。

"Cuckoo Filter on GoDoc"