布谷鸟过滤器:为什么只有7个？(如实体插入的“有限计数”。)

Question

在过去的几天里，我一直在试着用布谷鸟过滤器包裹我的大脑。我知道它们在很多方面都比bloom filters有优势，而且通常它们的使用更可取(如果你能使用它们的话)。

不过，我需要计算我正在寻找的应用程序的数量。我在任何地方都找不到关于为什么布谷鸟过滤器有“有限计数”的确切原因的信息。(虽然我听说限制是7。)

这是理论上的限制吗？

Answer 1

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

通常，当密钥的可能插槽已满时，尝试添加密钥并不是问题-其插槽中的一个密钥将被踢出。但是，当所有密钥都相同时，它们不会有溢出或备份位置可去。