cfilter

cfilter: Go 实现的 Cuckoo Filter。Cuckoo filter 是一种用于近似集合成员查询的 Bloom filter 替代方案。Cuckoo filter 支持动态添加和删除项目，且性能甚至优于 Bloom filter。对于存储大量项目且目标错误阳性率较低的应用程序，Cuckoo filter 的空间开销要小于空间优化的 Bloom filter。一些依赖于近似集合成员查询的可能用例包括数据库、缓存、路由器和存储系统，这些系统用于判断给定项目是否属于（通常较大的）集合，且错误阳性率很小。此外，由于 Cuckoo filter 设计为可替代 Bloom filter，因此还可用于减少概率路由表所需的空间、加快 IP 地址的最长前缀匹配、改进网络状态管理和监控，以及在数据包中编码多播转发信息等。

Cuckoo 过滤器提供了动态添加和删除元素的灵活性。Cuckoo 过滤器基于 Cuckoo 哈希（因此称为 Cuckoo 过滤器）。本质上，它是一个 Cuckoo 哈希表，存储每个键的指纹。Cuckoo 哈希表可以高度压缩，因此 Cuckoo 过滤器可以占用比常规 Bloom 过滤器更少的空间，适用于需要低误报率（< 3%）的应用程序。有关算法和参考文献的详细信息，请参阅原始研究论文《Cuckoo Filter: Better Than Bloom》，作者为 Bin Fan、Dave Andersen 和 Michael Kaminsky（https://www.cs.cmu.edu/~dga/papers/cuckoo-conext2014.pdf）。

• Insert(item): 将项插入到过滤器中
• Lookup(item): 如果项已在过滤器中,则返回;(可能返回像 Bloom 过滤器那样的假阳性结果)
• Delete(item): 从过滤器中删除给定的项。请注意,要使用此方法,必须确保此项已在过滤器中(例如,基于外部存储的记录);否则,可能会删除一个假的项。
• Count(): 返回当前过滤器中项的总数