文章/答案/技术大牛

发布

社区首页 >问答首页 >假阳性数布隆过滤器

问假阳性数布隆过滤器
EN

Stack Overflow用户

提问于 2019-11-23 01:36:26

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

我实现了一个带有3个哈希函数的布隆过滤器，现在我应该计算该过滤器中的误报(而不是可能性)的确切数量。有没有一种有效的方法来计算？过滤器中的项数为2亿，位数组大小为4亿

发布于 2019-12-24 17:18:57

是的，而且非常简单。

计算'on‘的位数，并除以总位数。这将给你你的填充率。

查询时，之前插入的所有元素都将命中'on‘位并返回正数。对于没有插入到过滤器中的元素，命中'on‘位的概率是您的填充率。因此，使用3个散列函数，您的错误率将为(fill_rate^3)。

虽然0.5是最大化空间与错误率的最佳填充率，但任何其他填充率都是可能的，但它要么占用太多空间，要么具有比所需更高的错误率。所以你最好使用4个散列函数，占用的空间更少。这真的取决于你的用例。你的要求是什么？你想要的错误率是多少？

票数 0

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

原文链接：

https://stackoverflow.com/questions/58999182

复制

相似问题

问假阳性数布隆过滤器EN