tem*_*def 9 xor bloom-filter data-structures
有一种相对较新的数据结构 (2020)，称为XOR 过滤器，它被用作布隆过滤器的替代品。
什么是异或滤波器？与布隆过滤器相比，它有哪些优势？它是如何运作的？
tem*_*def 27
在预先知道要存储在过滤器中的所有项目的情况下，XOR 过滤器被设计为布隆过滤器的直接替代品。与布隆过滤器一样，它表示不允许误报但允许误报的集合的近似值。
\n与布隆过滤器类似，异或过滤器存储大量位。不过，与布隆过滤器不同，我们将每个位视为其自己的数组槽，在异或过滤器中，这些位被组合在一起形成 L 位序列，对于我们稍后将选择的某些参数 L。例如，XOR 过滤器可能如下所示：
\n +-------+-------+-------+-------+-------+-------+-------+-------+-------+\n | 11011 | 10010 | 11101 | 11100 | 01001 | 10101 | 01011 | 11001 | 11011 |\n +-------+-------+-------+-------+-------+-------+-------+-------+-------+\n接下来，我们选择三个哈希函数h 1、h 2和h 3，它们就像布隆过滤器一样，将项目哈希到数组中的槽中。这些哈希函数让我们获取一个项目x并计算其表代码，这是通过将点h 1 (x)、h 2 (x) 和h 3 (x)中的项目异或在一起来完成的。此处显示了一个示例：
\n +-------+-------+-------+-------+-------+-------+-------+-------+-------+\n | 11011 | 10010 | 11101 | 11100 | 01001 | 10101 | 01011 | 11001 | 11011 |\n +-------+-------+-------+-------+-------+-------+-------+-------+-------+\n ^ ^ ^\n | | |\n h3(x) h1(x) h2(x)\n \n Table code for x: 10010 xor 01001 xor 10101\n = 01110\n为了完成这幅图，我们还需要一个称为指纹函数的哈希函数，表示为f (x)。指纹识别函数将一个值作为输入并输出一个 L 位数字，称为x 的指纹。为了查看 x 是否存储在表中，我们检查 x 的表代码是否与 x 的指纹匹配。如果是这样，我们就说 x（可能）在表中。如果不是，我们就说 x（肯定）不在表中。
\n将这个想法与布隆过滤器进行比较是有帮助的。使用布隆过滤器，我们将 x 哈希到多个位置，然后通过对所有内容进行 AND 运算，从这些位置导出一个值，最后检查我们得到的值是否等于 1。使用 XOR 过滤器，我们将 x 哈希为三个位置，通过将这些位置异或在一起得出一个值，最后检查我们得到的值是否等于f (x)。
\n要更改 XOR 过滤器的误报率，我们只需更改 L 的值。具体来说，f (x) 恰好与h 1 (x)、h 2 (x)给出的三个位置的 XOR 相匹配的可能性)，h 3 (x) 为 2 -L，因为这是随机 L 位值与另一个值匹配的概率。因此，为了获得 \xce\xb5 的误报率，我们只需设置 L = log 2 \xce\xb5 -1。
\n具有挑战性的部分是填写表格。事实证明，有一个非常简单的策略可以做到这一点。要存储 n 个元素的列表，请创建一个大小为 1.23n 的表。然后，使用此递归过程：
\n如果每个表槽至少有两个项对其进行哈希处理，则此过程有轻微的机会陷入步骤 (2)，但可以证明，只要您使用至少 1.23n 个表槽，发生这种情况的概率为非常小。如果发生这种情况，只需选择新的哈希函数并重试即可。
\n与常规布隆过滤器相比，异或过滤器有几个优点。
\n相对于布隆过滤器，异或过滤器有一个主要缺点，那就是在构造过滤器之前必须提前知道要存储在异或过滤器中的所有项目。这与布隆过滤器形成鲜明对比，布隆过滤器中的项目可以在很长一段时间内增量添加。但除此之外，XOR 过滤器还提供更好的性能和内存使用。
\n有关 XOR 过滤器的更多信息，以及它们在时间和空间方面与布隆过滤器和布谷鸟过滤器的比较，请查看这组讲座幻灯片，其中解释了它们的工作原理，以及 1.23 常数的来源以及我们的原因始终使用三个哈希函数。
\n