问什么是二进制熔断器滤波器？

EN

从直觉上看，二进制fuse过滤器遵循与常规XOR筛选器相同的策略，但是对于放置条目的策略略有不同，所以如果您还没有阅读过how XOR filters work，最好从这里开始。

与异或滤波器一样，二进制融合滤波器(以及其他几个相关结构，如丝带滤波器)通过计算每个项目x的指纹f(x)，以及计算一些哈希h1(x)、h2(x)和h3(x)来工作，从而将位置分配到数组中。然后填充数组，以便筛选器中所有元素的值h1(x) xor h2(x) xor h3(x) = f(x)。

XOR过滤器和二进制fuse过滤器之间的区别在于如何填充该表。这两种数据结构都使用一种名为剥离的方法来填充表。这是另一篇文章中概述的策略:找到一个只有一项散列的槽，删除它，递归地放置其他元素，然后在该槽中设置值，以便删除元素的散列正确计算。

在XOR过滤器中，插槽数组需要大小约为1.23n才能使此进程获得很高的成功机会。其原因在数学上是令人惊讶的:如果散列均匀分布在整个表中，那么在少于1.23n槽的情况下，剥离策略工作的概率迅速下降到0，而在超过1.23n槽的情况下，脱皮策略非常迅速地工作的概率会迅速上升到1。因此，可以使用异或过滤器将1.23n看作是对表大小的严格理论限制。

fuse过滤器背后的想法是改变哈希在表上的分配方式。我们使用另一种方法，而不是选择散列，使它们在整个表中都是随机的。选择一个窗口大小为 w。然后，对于每个元素x，按以下方式选择h1(x)、h2(x)和h3(x)：

1. 在数组中选择大小为w的随机窗口。
2. 在该窗口内随机选择h1(x)、h2(x)和h3(x)。

(二进制fuse过滤器的实际逻辑与此略有不同，因为它需要将h1(x)、h2(x)和h3(x)分开一点，但现在我们忽略这一点。)

一旦以这种方式分配散列，就会使用与以前相同的剥离策略来填充数组:我们找到一个槽，其中只有一个项散列，删除该项，放置所有其他项，然后将项目放回。

这里最美丽的是剥皮的过程。直观地说，由于我们如何分配散列，最接近数组两端的插槽最有可能只有一个项哈希。为什么？因为只有这样，你才能在两端之间发生碰撞，如果你有两个项目，它们的窗口都非常靠近两端，而且碰巧会在那些窗口中选择离窗口两侧很远的槽。这是相当不可能的，因此，最左边和最右边的项目很可能被剥离。

但是，一旦这些项目被剥离，按照同样的逻辑，现在在极左或极右的项目很可能是可剥离的。这就是“保险丝”这个名字的由来--就像在两端点燃一个保险丝，看着它朝着中心燃烧一样。

事实上，对于哪些项是可剥离的，这里有一些可预见性，这意味着我们需要的表槽比在表中随机分配散列的情况要少。本文引用了所需约1.13n个表槽的空间使用情况，与XOR过滤器所需的1.23n相比，这是一个很大的改进，完全是通过改变分配散列的策略来完成的。挺干净的！