java - 布隆过滤器实现

Question

使用布隆过滤器，我们将获得空间优化。 cassandra框架也有布隆过滤器的实现。但具体来说，这种空间优化是如何实现的？

Answer 1

您可以使用此示例了解它如何节省空间: 假设我在 Chrome 团队的谷歌工作，我想向浏览器添加一项功能，如果他输入的 url 是恶意 URL，它会通知用户。所以我有一个包含大约 100 万个恶意 URL 的数据集，这个文件的大小约为 25MB。由于大小相当大(与浏览器本身的大小相比很大)，我将此数据存储在远程服务器上。

案例 1:我将哈希函数与哈希表一起使用。我决定使用一个高效的哈希函数，并通过哈希函数运行所有 100 万个 url 以获取哈希键。然后我制作了一个哈希表(一个数组)，其中的哈希键会为我提供放置该 URL 的索引。所以现在一旦我散列并填充了散列表，我就检查它的大小。我已将所有 100 万个 URL 连同它们的键一起存储在哈希表中。所以大小至少为 25 MB。由于其大小，此哈希表将存储在远程服务器上。当用户出现并在地址栏中输入 url 时，我需要检查它是否是恶意的。因此，我通过散列函数运行 url(浏览器本身可以执行此操作)，并获得该 URL 的散列键。我现在必须使用该哈希键向我的远程服务器发出请求，以检查我的哈希表中具有该特定键的特定 URL 是否与用户输入的内容相同。如果是，那么它是恶意的，如果不是，那么它不是恶意的。因此，每次用户输入 URL 时，都必须向远程服务器发出请求，以检查它是否是恶意 URL。这会花费很多时间，从而使我的浏览器变慢。

案例 2:我使用布隆过滤器。整个 100 万个 URL 列表使用多个哈希函数通过布隆过滤器运行，并且各自的位置标记为 1，在一个巨大的 0 数组中。假设我们想要 1% 的误报率，使用布隆过滤器计算器 (http://hur.st/bloomfilter?n=1000000&p=0.01)，我们得到所需布隆过滤器的大小仅为 1.13 MB。这个小尺寸是预期的，因为即使数组的尺寸很大，我们也只存储 1 或 0，而不是哈希表中的 URL。这个数组可以被视为一个位数组。也就是说，因为我们只有两个值 1 和 0，所以我们可以设置单个位而不是字节。这将减少 8 倍占用的空间。这个 1.13 MB 的布隆过滤器，由于体积小，可以存储在网络浏览器本身中!!因此，当用户出现并输入 URL 时，我们只需应用所需的哈希函数(在浏览器本身)，并检查布隆过滤器(存储在浏览器中)中的所有位置。任何位置的 0 值都告诉我们这个 URL 绝对不在恶意 URL 列表中，用户可以自由进行。因此我们没有调用服务器，从而节省了时间。值 1 告诉我们该 url 可能在恶意 URLS 列表中。在这些情况下，我们调用远程服务器，在那里我们可以像第一种情况一样使用一些其他哈希函数和一些哈希表来检索和检查 url 是否实际存在。由于大多数时候，一个 url 不太可能是恶意的，浏览器中的小型布隆过滤器会识别出这一点，从而通过避免调用远程服务器来节省时间。只有在某些情况下，如果布隆过滤器告诉我们该 url 可能是恶意的，只有在这些情况下我们才会调用服务器。这个“可能”是 99% 正确的。

因此，通过在浏览器中使用一个小型布隆过滤器，我们节省了大量时间，因为我们不需要为输入的每个 url 都调用服务器。