performance - 布隆过滤器中正匹配的后果

Question

假设:

• 注册用户的用户名存储在一个集合中
• 我想使用布隆过滤器来加快查找速度。
• 布隆过滤器存在一定的误报概率 (0.1%)

当新用户想要注册时，在大多数情况下，我的用户界面会告诉他们“该名称未被使用，您可以开始”。

但是如果找到正匹配，后端需要做什么？

结果可能是误报。找出真正的答案不会增加时间复杂度，从而在许多情况下使布隆过滤器效率低下吗？

告诉用户“命名已在使用中，选择不同的 oe”可能没那么糟糕，但对于其他你不会出错的用例呢？

Answer 1

使用布隆过滤器的一般模型如下:

1. 查询过滤器以查看答案是否可能为是。
2. 如果布隆过滤器说不，答案肯定是否定的。
3. 如果布隆过滤器回答"is"，则答案可能是"is"，因此请查询更准确的数据结构以获得最终确定。

当步骤 (3) 的形式为“查询某个服务器以搜索庞大的数据库以查看是否有相关项目”时，布隆过滤器确实会发挥作用。在这种情况下，减少服务器做出决定所需的 ping 次数可以为客户端带来巨大的性能提升并减少服务器的负载。

另一方面，如果您在计算机上本地存储一个小数据集，那么布隆过滤器不太可能做那么多事情，因为直接查询该数据集可能对于所有数据集来说都足够快您的需求。