Cuckoo 过滤器是近似集合成员查询的布隆过滤器替代品。虽然 Bloom 过滤器是众所周知的节省空间的数据结构,可以服务于“如果项目 x 在一个集合中?”之类的查询,但它们不支持删除。它们启用删除的差异(如计算 Bloom 过滤器)通常需要更多空间。
Cuckoo 过滤器提供了动态添加和删除项目的灵活性。布谷鸟过滤器基于布谷鸟散列(因此称为布谷鸟过滤器)。它本质上是一个存储每个密钥指纹的布谷鸟哈希表。Cuckoo 哈希表可以非常紧凑,因此对于需要低误报率 (< 3%) 的应用程序,cuckoo 过滤器可以比传统的 Bloom 过滤器使用更少的空间。
更多详情、使用方法,请下载后阅读README.md文件
2022-07-13 09:06:55
10KB
go语言