布谷鸟过滤器：为什么正好有 7 个计数？(与实体插入"limited count"一样。

Question

在过去的几天里，我一直试图用杜鹃滤镜来掩饰自己。我知道它们在很多方面都比bloom过滤器有优势，通常情况下，它们的使用是更可取的(如果你能使用它们的话)。

不过，我需要计算一下我正在寻找的申请。我在任何地方都找不到关于杜鹃过滤器中为什么存在"有限计数"的确切信息。(尽管我听说限额是7。)

这是理论上的极限吗？

Answer 1

布谷鸟过滤器可以保存单个密钥的多个副本。所有项目都具有相同的哈希值，因此它们都被插入到两个可能的bucket之一的一个slot中。当存储桶的大小为4时，即总共8个插槽。

一般来说，在可能的插槽已满时尝试添加密钥不是问题——插槽中的一个密钥只会被踢出。然而，当所有密钥都相同时，就不会出现溢出或备份位置。