如何测量布隆过滤器的误报率

Question

你有一个布隆过滤器，你想实际地(而不是理论上)测量误报率。

你是怎么做的?

你是否插入N个元素并计算哈希冲突的次数，然后除以N，就这样?

还是插入N个元素，然后对所有未插入的其他元素进行隶属度测试(通常是无限的)?

还是别的什么?

Answer 1

假设你的计算表明，当布隆过滤器中有N个项目时，你将有X的假阳性率。

生成2N个唯一的随机密钥。将其中一半放入布隆滤镜中。现在用另一半测试。你知道键是唯一的，所以任何"正的"点击你得到的将是假阳性。

将你的实验结果与计算结果进行比较。