问布谷鸟过滤器必须使用2的下一个幂作为容量吗？
EN

Stack Overflow用户

提问于 2021-03-11 23:34:47

回答 1查看 54关注 0票数 0

我发现大多数布谷鸟过滤器的实现都将调用者给出的容量增加到2的下一个幂。我在论文中没有看到提到"m“必须是2的幂的地方。这样做会导致较小的平均负载率。

发布于 2021-07-26 12:34:04

是。布谷鸟过滤器必须使用2的下一个幂(PO2)作为容量。

原因是计算指纹的替代位置时使用了XOR运算符。因为过滤器有分配给它的内存，所以任何数量的非PO2的存储桶都可能落在分配的边界之外的内存地址上。

票数 0

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/66585651

复制

相似问题

问布谷鸟过滤器必须使用2的下一个幂作为容量吗？EN