python - 假正数布隆过滤器

Question

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

标签： pythondataframehashbloom-filter

Answer 1

是的，而且非常简单。

计算“打开”的位数并将其除以总位数。这将为您提供填充率。

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

尽管 0.5 是最大化空间与错误率的最佳填充率，但任何其他填充率都是可能的，但它要么占用太多空间，要么具有比所需更高的错误率。因此，您最好使用 4 个空间较小的散列函数。这实际上取决于您的用例。你的要求是什么？您在寻找什么错误率？