Xor 过滤器

先找只剩一个未知方程的出口 ​

一条方程有三个数组位置，若其中某位置不再被其它待解方程使用，就可以把这条方程暂时拿走。等其它方程都解决后，回到这个私有位置，用它补齐异或差额。这与完整高斯消元的目标相关，但此处只使用度一结构，不任意组合方程。

查询只读三个r位值。构建时却要看全部边，才能找出安全赋值次序。这是用批量预处理换固定查询工作的静态接口，不能把单键查询便宜理解为单键更新也便宜。

四条方程的完整剥离与回放 ​

取b=3、r=3，四个键的端点和指纹为：

开始只有位置7和8度为1。按顶点编号入队并处理，可依次剥离 (c,7)、(d,8)、(a,3)、(b,4)；其中某些先前入队的顶点会过期，弹出时检查度数即可。

逆序赋值为：B[4]=2；B[3]=1；$B[8]=3\oplus B[1]\oplus B[4]=1$；$B[7]=4\oplus B[1]\oplus B[3]=5$。其它位置为0，最终

例如键c得到 $0\oplus 1\oplus 5=4$，键d得到 $0\oplus 2\oplus 1=3$。必须逐条检查方程，不能只验证最后写入的支点。

剥不动不等于方程无解 ​

设两个不同键拥有同一三元组(0,1,2)。三个顶点度数都是2，没有度1出口。如果两键指纹同为5，方程实际相同，仍有许多解；若指纹分别为5和6，则同一左边不可能同时等于两数，确实无解。剥离算法对两种情况都报告失败。

因此失败说明没有获得这套剥离构造的证书，不是一般线性系统不可解的判定。可以换位置函数重试或调整容量，也可以改用更复杂的解方程方法，但不能把后者的能力冒充本文算法。

查询误报需要怎样的随机性 ​

固定非成员x。条件化于位置函数、成功剥离次序及全部成员指纹后，B和查询三个位置的异或值都已确定。如果f(x)仍是独立均匀r位串，则按这个概率分布理路概率分布Probability distribution · Law可测空间上总质量为一的测度；随机变量的律是由样本概率推出的一类分布。

因此无条件误报率也为 $2^{-r}$。充分条件是指纹函数对固定相关键给出完全独立输出，并与位置函数独立；重试成功与否只由位置图决定。仅有每键边缘均匀、两两独立或简单制表的三独立理路简单制表哈希Simple tabulation hashing · 简单表格哈希把键分成定长字符，用各位置独立随机表异或得到哈希值，证明三独立并找出四键的确定相关。，都不足以直接推出给定整张成员表后的条件独立。

工程中常从少量种子展开位置和指纹，需另证相应模型或接受近似随机假设。本页的确定性检查器接收已给定的三元组和指纹，用来验结构与方程，不把伪随机实验当成理想独立性的证明。

每次构建、重试和输出接口分别记账 ​

度数与关联边可用每点计数及边ID异或维护：插入边e时，在其三个端点把e的ID异或进去；度为1时，这个值恰好就是唯一边ID。移除再异或一次。边ID0合法，必须靠度数判断是否唯一，不能把ID异或值0当作空。每条边只移除一次，最多带来三次新度1入队，故队列工作和逆序赋值合计O(n+m)。构建空间O(n+m)个字；最终查询表只有mr位，另存种子等元数据。

上述线性构建从已去重的键集合及已给定位置、指纹开始，原键去重成本单列。下载器用Python集合检查重复键，该检查在通常散列成本模型下是期望线性，不是任意Python键的最坏线性保证。核心操作按每个位置、边ID、计数和r位值装入常数个RAM字计；长键或多字指纹的读取、哈希求值成本不能略去。

一次成功查询固定读三个位置，最坏O(1)。一次构建失败仍已付O(n+m)。只有明确证明每次独立重试的成功概率至少p₀>0，才可用几何分布得期望构建成本 $O((n+m)/p_0)$；本文没有对任意n、b及任意位置函数族承诺这个下界。可以设置重试预算，耗尽就返回未构建，而不是悄悄给出缺成员的表。

n=0时，零数组加三位置查询仍会对指纹0给出误报，概率模型下恰为 $2^{-r}$；若另存空集标记，可直接全部否定。这是一个明确的接口优化，不影响非空集合证明。

与商过滤器理路商过滤器Quotient filter · 商余数过滤器用商确定逻辑桶、只存余数和三种状态位，在循环数组中恢复有序指纹多重集，并约束删除与误报语义。逐项维护指纹多重集不同，本表构建后不支持任意单键插删。随意改一个位置会影响共享它的其它成员方程；集合变化应整批重建，或另设增量结构并重新证明查询组合规则。

终点任务要求交出剥离序列、每步唯一边检查和逆序数组，再构造同端点两键的“有解但剥不动”与“无解”实例。最后固定一份成功表，穷举非成员的全部r位指纹，验证恰有一种通过；这里测试的是条件概率的有限样本空间，而不是一次经验误报率。