如何测试Bloom过滤器？

Question

我目前正在开发一个Bloom过滤器实现。我想知道如何测试这样的数据结构，因为Bloom过滤器在本质上是概率的，我猜。我想要单元测试，也测试假阳性。特别是，我如何对过滤器方法(添加/包含)进行单元测试，以及如何验证误报是否低于一定百分比？

Answer 1

假阳性是有可能的，在一个花过滤器。所以拥有一个并不是个失败。你可以测试很多其他的东西，但这是在问不可能的事情。

您可以设置一个阈值，您希望错误的阳性低于，但这需要足够的试验，以停止测试是快速的。