And*_*ndy 1 xor bloom-filter data-structures
不久前有一篇关于 XOR 过滤器的精彩文章：什么是 XOR 过滤器？
有人可以解释一下二元保险丝滤波器吗？它在结构上有何不同？做出这样选择的理由是什么？我试图阅读这篇论文，但迷失在二进制熔丝的具体细节中。它与异或相比如何？为什么它更小更快？
直观上，二元熔丝滤波器遵循与常规 XOR 滤波器相同的策略，但放置项目的策略略有不同，因此，如果您还没有\xe2\x80\x99t 了解XOR 滤波器的工作原理，那么它\xe2\x80\x99s最好从那里开始。
\n与 XOR 过滤器一样，二进制熔丝过滤器（以及其他几个相关结构，例如 Ribbon 过滤器）的工作原理是计算每个项目 x 的指纹 f(x)，以及计算一些哈希值 h1(x)、h2(x)、和 h3(x) 给出数组中的位置。然后填充该数组，以便过滤器中所有元素的值 h1(x) xor h2(x) xor h3(x) = f(x)。
\nXOR 滤波器和二进制熔丝滤波器之间的区别在于该表的填充方式。这两种数据结构都使用一种称为剥离的方法来填充表。那\xe2\x80\x99s是另一篇文章中概述的策略：找到一个只有一个散列项的槽，将其删除，递归地放置其他元素，然后在该槽中设置值，以便删除的元素\xe2 \x80\x99s 哈希值计算正确。
\n在 XOR 滤波器中，时隙数组的大小需要大约为 1.23n，此过程才有很高的成功机会。其原因在数学上令人惊讶：如果散列在表中均匀分布，那么在槽数少于 1.23n 的情况下，剥离策略起作用的概率会很快下降到 0，而在槽数超过 1.23n 的情况下，剥离策略起作用的概率会非常快地下降到 0。剥离策略的工作速度非常快，趋势为 1。因此，您可以将 1.23n 视为使用 XOR 过滤器的表大小的严格理论限制。
\n熔丝过滤器背后的想法是改变散列在表上的分配方式。我们使用另一种方法，而不是选择散列以使它们\xe2\x80\x99在表中均匀随机。选择窗口大小w。然后，对于每个元素 x，按以下方式选择 h1(x)、h2(x) 和 h3(x)：
\n（二元熔丝滤波器的实际逻辑与此略有不同，因为它要求 h1(x)、h2(x) 和 h3(x) 间隔一点，但让\xe2\x80\x99s 忽略这一点目前。）
\n一旦我们\xe2\x80\x99以这种方式分配了哈希值，我们就使用与之前相同的剥离策略来填充数组：我们找到一个只有一个项目哈希的槽，删除该项目，放置所有其他项目，然后将项目返回。
\n这里\xe2\x80\x99 的美妙之处在于剥离过程的进行。直观上，由于我们分配哈希值的方式，最接近数组两端的槽最有可能只有一项哈希值。为什么？因为在末端附近发生碰撞的唯一方法是，如果您有两个项目，其窗口都非常靠近末端，并且恰好选择了远离窗口两侧的窗口内的插槽。\xe2\x80\x99 的可能性很小，因此最左边和最右边的项目可能会被剥离。
\n但是，一旦这些项目被剥离，按照相同的逻辑，现在位于最左侧或最右侧的项目很可能是可剥离的。这就是 \xe2\x80\x9cfuse\xe2\x80\x9d 这个名字的由来 - 它 \xe2\x80\x99 就像在两端点燃一根保险丝，然后看着它向中心燃烧。
\n事实上，这里有一些关于项目可剥离位置的可预测性，这意味着与在表中随机分配哈希值相比，我们需要更少的表槽。该论文引用了大约需要 1.13n 个表槽的空间使用量，比 XOR 过滤器所需的 1.23n 个表槽有了很大的改进，并且它\xe2\x80\x99 纯粹是通过更改分配哈希值的策略来完成的。很简约！
\n