动机
哈希表把一个很大的键全集映射到较小的桶集合中。当键的个数多于桶的个数时,没有任何映射能够避免所有碰撞。然而,如果键集在抽取哈希函数之前就已固定,那么一个精心选取的随机哈希族可以使每一个特定的碰撞都不太可能发生。
我们用素域上的仿射映射来构造这样的哈希族。当桶的个数不能整除素数时,从域元素到桶编号的约化会使各桶的大小略有不均。证明将精确地处理这种不均衡。证明同时也说明,为什么在对手看到所选哈希函数之后,针对固定键的保证不能原样沿用。
定义
定义 5.2.1
(随机仿射映射后接桶约化)
固定素数 与整数 。键全集为 ,并与 等同。独立地从 中均匀选取 ,从 中均匀选取 。定义
其中第一个余数用 中的整数表示。输出是 中的一个桶。
由互不相同的键组成的集合 在随机种子 之外事先固定。在分析其期望链长时,一个不成功查询的键同样独立于该种子而固定。概率陈述均针对所述的种子随机选取。
对于桶 j,令 为 中模 m 与 j 同余的整数个数。当 时,某些桶可能为空。由带余除法可知,每个桶(无论是否为空)的大小要么是 ,要么是 。
定理/命题
定理 5.2.2
(通用碰撞界)
对任意两个互不相同的固定键 ,
该结论对每个 成立,包括 的情形。两个键的桶输出不必相互独立,也不必在全部 m 个桶上各自均匀分布。
定理 5.2.3
(期望碰撞数与链式哈希)
对于由 个互不相同的键组成的固定集合 ,令 为发生碰撞的无序键对的个数。则
对固定的 ,其所在桶的期望占用量至多为 。对固定的查询 ,其所在桶的期望占用量至多为 。
证明思路
两个不同键的域像是均匀分布的
证明
(两个不同键给出互异域像的均匀有序对)
对于固定的互异 ,考虑给定的互异域元素 。方程
在 中有唯一解 与 。两个差均不为零,因此得到的 是允许的。反过来,每个允许的种子都给出互异的像,因为乘以非零的 a 是单射。
共有 个等可能的种子,互异有序对 的个数与之相同。因此 在这些对上是均匀分布的。特别地,每一个单独的域像都是均匀的,但这一对并不独立:两个像永远不会相等。素域中的除法是合法的,因为 ;对于任意的合数模数,这一构造并没有这样的证明。
桶大小不等时仍得到所述的界
证明
(计算共同的桶)
以第一个域像为 u 作条件。第二个域像在其余 个元素中均匀分布。若 u 所在的桶大小为 c,则恰有 c−1 种选择与之碰撞,因此条件碰撞概率为 。
每个桶的大小至多为 ,并且
因此对每个 u,条件概率至多为 。对 u 取平均即证明了碰撞界。当 时,每个被占用的桶恰含一个域元素,所以碰撞概率实际上为零。当 时,界为一,且每一对键都发生碰撞。
证明透视
条件化利用的是互异的域像,而不是桶之间的独立性
固定第一个域像之后,第二个域像在其余 p−1 个域元素中取值。数一数第一个像所在桶中的其他成员,即使各桶大小不同也能得到该界。桶输出的独立性既没有被假设,也不需要。
用示性变量数对
证明
(期望键对数与桶占用量)
对 S 中每一对互异的键,使用一个恰在碰撞时取一的示性变量。它们的和就是 X。由期望的线性性(它不要求这些示性变量相互独立)即得所示的期望。事件 由对非负整数随机变量 X 的 Markov 不等式给出,而概率永远不会大于一。
对于固定的键 ,其所在桶的占用量等于一加上 x 与其余每个键之间的碰撞示性变量之和。对于 S 之外的固定查询,它等于该查询与所有已存储键的碰撞示性变量之和。同样的键对界与线性性给出这两个占用量估计。对于 S 之外的查询,该论证也包括 的情形;而当 S 为空时,S 内没有可选取的键。
概念视角组合
把碰撞概率看成有序对的计数
种子与互异域元素的有序对 一一对应。因此对任意两个互异键,碰撞概率恰好等于这些有序对中落在同一个桶的比例:
当 、 时,桶的大小为 ,得到 。界 来自把这个与种子无关的计数同最大可能的桶大小作比较。
例题
例题 5.2.4
(一个具体的仿射表)
令 ,,,。键 分别映射到桶 。恰有一对无序键发生碰撞,即键 1 与键 3。对于这个固定的四键集合,定理给出在全部种子上的期望键对数的界为 ;该界是对种子取平均的结果,并不是断言这个特定的种子有两次碰撞。
例题 5.2.5
(桶数多于域元素个数)
取 ,,第二次取余使每个域代表元保持不变。每个允许的仿射映射都是 的一个置换,所以互异的键从不碰撞。桶 5、6、7 为空。一般的上界 是成立的,但并不紧。
例题 5.2.6
(一个固定的不成功查询)
设 ,一个固定集合含有 个键,使用 个桶。对集合之外的任意固定查询键,其所在桶中已存储键的期望个数至多为二。因此,对不成功查询进行简单链扫描的期望键比较次数至多为二。某些种子仍可能给出更长的链;该期望并不是对每个种子都成立的最坏情形界。
从碰撞界到随机化重试
为一个固定集合抽取种子后,把它的键插入各桶,并检查是否有桶含有多于一个键。若没有,则该映射在 S 上是单射。除了计算哈希值与抽取种子的代价之外,这一检查可通过初始化 m 个计数器并扫描 n 个键来实现,共需 次桶操作。
对于 ,若 ,则碰撞概率至多为二分之一。每次失败之后独立地重新抽取一个新种子。前 t 次尝试全部失败的概率至多为 ,期望尝试次数至多为二:尾和公式给出 作为上界。对于 ,每个种子在 S 上本来就是单射。
这是一个带有可检验成功条件的构造,而不是对试验次数的确定性最坏情形界。它也并不意味着使用 个桶的无碰撞表总是空间效率最高的选择。如果种子是在有限的公平比特预算下抽取并允许中止,那么该抽样过程的影响需要另行分析。
桶约化之后依赖性依然存在
取 ,,桶零包含代表元 ,而桶一与桶二各含两个代表元。对于互异的固定 x,y,两个域像都落在桶零的概率为
每个单独的输出为零的概率是 ,其乘积为 ,而不是 。因此在这个例子中两个桶输出并不独立,而且它们在三个桶上也不是均匀分布的。尽管如此,它们的碰撞概率满足已证明的上界。通用的键对碰撞控制弱于关于桶输出独立且均匀的断言。
如果改为从全部 (包括零)中均匀选取 a,那么两个互异键的域像将是独立的均匀域元素:同样的两个方程对每个有序对(包括相等的对)都恰有一个解。约化之后它们的桶输出是独立的,但一般不均匀。对于 ,所得的碰撞概率为 。因此,对这一约化而言,把零乘子包括在内会改变碰撞保证。
查询代价与固定输入条件
采用分离链接时,对固定的 的成功查找,所比较的键不超过其所在桶的占用量。对 S 之外的固定不成功查询,所比较的键至多为该桶的占用量。因此,除了计算哈希本身之外,期望比较次数的界可由该定理得到。成功的扫描可能更早停止;这一上界不需要对链内顺序作任何假设。
这些期望并不自动适用于在看到种子之后才选定的集合或查询。举一个具体的对比,令 ,。从七个键到三个桶的每个映射,都有某个桶至少含三个键。先看到所选哈希函数的观察者可以在这样的桶中选取任意三个键。于是三对键全部碰撞,所以对这个依赖于种子的选取,X 总是三。而 时的固定集合定理对期望键对数给出的上界是一。两者并不矛盾:该定理中的集合必须独立于种子。
反例模式
碰撞期望并不是个别情形的最坏界
一个诱人的说法:固定的三键集合的期望碰撞键对数至多为一,所以我们挑选的任意三个键至多产生一对碰撞。当键是在种子之后才选取时,这并不成立。取 、、、,即在 上 。键 全部落入桶零,;而定理只对在种子之前已固定的集合给出 。Markov 界同样只控制固定集合至少出现一次碰撞的概率,它可以等于平凡的界一,也不意味着每个种子都无碰撞。
计算范围
该构造假定已给出素数 p,且键用域元素表示;它并没有证明寻找合适的素数是没有代价的。它还假定按规定均匀抽取 与 。在简单的机器字操作模型中,当所表示的值能放入机器字模型时,可以把域运算与取余运算视为基本操作。若 p 与 m 以任意二进制编码给出,则模乘、除法与种子生成的比特代价必须另行计算。
只有互异的键才符合集合模型。同一个键的重复出现总是哈希到一起,应按多重性或按另一约定下的存储记录来计入。碰撞保证针对的是互异的输入键,而不是同一个键的两种表示恰好相等这种偶然情形。
常见错误
常见错误
(把键对碰撞界读成独立均匀的输出)
对 、 及两个互异的固定键,两个输出同为桶零的概率是 ,但每个输出为桶零的概率是 ,而 。两个输出既不独立,在三个桶上也不均匀,当 不能整除 时尤其如此。受到控制的只是碰撞概率,其上界为 。
常见错误
(让乘数可以取零)
若允许 取遍 的全部元素,两个域像便成为独立的均匀元素,碰撞概率为 。对 、,此值为 ,界 不再成立。排除 是证明的一部分。
常见错误
(把期望链长当作实际链长)
界 是对事先固定的查询键就种子取的平均。取 、、 及集合之外的查询键 ,查询所在桶内已存储键数的期望至多为 ;但种子 、 把两个已存储的键都放进查询键所在的桶,扫描就要与两个键比较。
总结
非零仿射乘子把两个互异的固定键送到互异域元素的均匀有序对。数出它们可能共有的余数桶,即证明碰撞概率至多为 ,即使各桶大小不均。线性性给出期望键对数与链占用量;一次检查加上独立的重试,给出期望尝试次数受控的固定集合无碰撞构造。每一个这样的概率陈述都依赖于种子与键选取模型。
练习
快速检查
(对 ,列出键 0、1、2、3 所在的桶,并数出发生碰撞的键对个数。)
解答 · 答案
输出为 。键 0 与键 2 构成一对碰撞,键 1 与键 3 构成另一对,因此共有两对。
快速检查
(若 且 ,该定理对至少发生一次碰撞的概率给出什么上界?)
解答 · 答案
界为 。
快速检查
(为什么可以通过对键对概率求和来界定期望碰撞键对数,而无需假设碰撞事件相互独立?)
解答 · 答案
碰撞键对数是有限个碰撞示性变量之和。无论这些示性变量之间是否相互依赖,期望的线性性都成立。
快速检查
(对 ,每个桶中各有多少个域代表元?)
解答 · 答案
代表元为 、 与 ,因此大小分别为 3、2、2。