简单制表哈希

异或保留一份未揭示的随机性 ​

若Z均匀，固定任意a，映射 $Z\mapsto Z\oplus a$ 是一一对应，结果仍均匀。制表哈希把每个键拆成几个小查表；只要能为要分析的键保留一份独占随机表项，就能逐键确定输出而不约束其它剩余键。

表项可以共享。两个键只差最后一字符时，大部分异或项都相同，但最后两项独立，仍给出独立的两份输出。问题不在于“是否共享过表项”，而在于共享方式能否形成无法消去的关系。

手算四键矩形 ​

令c=2、Σ={0,1}、r=3，抽得 $T_0=[1,6]$、$T_1=[3,5]$。数字按三位二进制异或：

这四个输出的异或为0。对任意随机表也成立，因为每个表项恰出现两次：

知道前三个输出后，第四个已经确定；四个独立均匀r位串却只以 $2^{-r}$ 的概率满足这条关系。配套检查器把r改成2，穷举 $4^4=256$ 张随机表：前三输出的64种组合各出现4次；四输出也只有64种，而独立四元组应有256种。

当c=1时，每个不同键直接读取不同表项，反而具有任意阶独立性。非四独立的结论必须保留至少两个位置、至少两个字符的条件。

截位、取模与键编码 ​

保留固定的b个输出位，$1\le b\le r$，仍给均匀且三独立的b位输出，适合 $2^b$ 个桶。直接对非二次幂m取模则不一定均匀。例如均匀三位数0至7模3，三个桶概率为3/8、3/8、2/8。对两个独立输入，此时碰撞概率为 $22/64>1/3$，不能继续引用“恰为1/m”。

输入元组必须完整表示原键。若可变长字符串只补零，不记录长度，两个原本不同的字符串可能先被编码成同一元组；之后再强的哈希独立性也无法把它们分开。使用定长键域，或先规定单射编码及可容纳的长度范围。

同一张表用于所有位置也会破坏结论：$T[a]\oplus T[b]=T[b]\oplus T[a]$，字符交换便产生必然碰撞。这是更改了构造，不是上述三独立族的一次坏种子。

时间、空间和保证的使用范围 ​

设一个字符下标和一个r位表项都装进常数个RAM字。一次求值读c项并做c−1次异或，需O(c)时间；生成和保存全部表需要 $c|\mathrm{\Sigma }|$ 个表项、$c|\mathrm{\Sigma }|r$ 位主数据。只有c固定时才称查询常数时间。若r超过字长，异或与读写还要乘上相应字数；获取真正独立随机位也是建表所需资源。

三独立蕴含两独立，所以对固定键对的桶碰撞可直接使用通用哈希的分析。但线性探测理路线性探测Linear probing · 线性探查哈希从哈希首页开始逐槽循环扫描的开放定址结构，以连续内存换取良好局部性，同时必须控制聚簇、墓碑和哈希独立性。的长聚簇依赖许多键联合落点，不能仅凭“三独立”三个字推出期望常数探测。原论文证明简单制表对线性探测等问题有超出一般三独立族的良好性质，依靠的是这套表项结构的专门分析。[1, §§1、3]

它也不是密码学伪随机函数。看到种子后的攻击者可以利用四键关系；本文概率结论针对先固定的键，而不是自适应挑选碰撞的安全游戏。Xor过滤器理路Xor 过滤器Xor filter · 异或过滤器把静态成员集写成三位置异或方程，度一剥离后逆序赋值，并把构建失败、查询误报与哈希独立性分别证明。的精确误报证明还要求非成员指纹在给定全部成员信息后保持均匀，不能未经证明就用这里的三独立替代该条件。

终点任务要求复算三独立的小空间分布，再作两个结构修改：共享位置表、把输出模3。分别指出哪个证明前提消失，并给实际碰撞分布；只换一张随机种子不能完成这两项检查。