google-chrome - 谷歌浏览器使用布隆过滤器

Question

我正在阅读一篇关于 Bloom Filters 用法的维基百科文章。文章中提到，谷歌浏览器使用 Bloom 过滤器来检测输入的 URL 是否是恶意的。因为存在误报

Google Chrome web browser uses a Bloom filter to identify malicious URLs. Any URL is first checked against a local Bloom filter and only upon a hit ,a full check of the URL is performed

我猜全面检查意味着 Google 存储了恶意 URL 列表的严苛表，并且该 URL 被散列以检查它是否存在于表中。如果是这种情况，是不是最好只使用哈希表而不是哈希表 + 布隆过滤器？？

请赐教，我的完整检查版本是否正确？？？

Answer 1

布隆过滤器是一种概率数据结构，它告诉我们元素要么肯定不在集合中，要么可能在集合中。与 Hashmap 相比，Bloom filter 占用的空间更少(取决于配置的哈希函数和错误率)。 Hashmap 可以判断一个元素是否存在，而bloomfilter 只能确定性地检查一个元素是否不存在。

让我们看一下 Google Chrome 用例。当用户输入一个 URL 时，它应该验证该 URL 是否安全。为了验证 URL，chrome 可以调用 google 服务(内部 google 可以维护任何数据结构来找出这一点)。然而，这种方法的挑战是多方面的。对于在 chrome 上提供的每个 URL 请求，URL 验证都是通过谷歌服务器进行的，这增加了对谷歌服务器的额外依赖、网络往返时间以及保持高可用性以验证所有 URL 的要求从世界各地的 chrome 浏览器触发的 URL。

由于这些数据不会经常更改(可能会在一小时左右更新)，chrome 可能已经考虑将所有恶意站点数据捆绑为布隆过滤器，并且 google 可能会定期与客户端同步这些数据(恶意站点是与成熟的网站相比要少。)。当用户在 chrome 中打开一个 url 时，如果该 URL 不存在，它会检查布隆过滤器，它是安全的。如果存在，则布隆过滤器不确定，因此流量会转到 google 服务器进行验证(与路由所有流量相比，此流量会少得多)。