Google Chrome 使用布隆过滤器

Question

我正在阅读一篇关于 Bloom Filters 用法的维基百科文章。文章中提到，Google Chrome 使用 Bloom 过滤器来检测输入的 URL 是否是恶意的。由于假阳性的存在

Google Chrome 网络浏览器使用布隆过滤器来识别恶意 URL。任何 URL 首先都会根据本地 Bloom 过滤器进行检查，并且只有在命中时才会执行 URL 的完整检查

我猜测完整检查意味着 Google 存储了恶意 URL 列表的严格表格，并对 URL 进行哈希处理以检查它是否存在于表中。如果是这种情况，那么只使用哈希表而不是哈希表+布隆过滤器是不是更好？

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

Answer 1

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

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

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