动机
随机化数据结构常常假设不同的键以很小的概率发生碰撞。除非能够构造出合适的哈希族并弄清其抽样代价,否则基于这一假设的分析是不完整的。在二元向量上的一个简单仿射构造,只需一个有限的随机种子,就能给出均匀分布且两两独立的哈希值。
两两独立弱于所有哈希值的完全独立,但对许多期望碰撞数的计算已经足够。我们证明该哈希族的性质,将其应用于哈希表和碰撞并集界,并说明固定输入这一假设在何处起作用。
定义
设键的全集为 ,桶的集合为 ,其中整数 。运算在二元域 上进行。取一个均匀随机的二元 矩阵 ,以及与之独立的均匀随机向量 。定义
种子由 个相互独立的公平比特组成。一个桶就是一个 位向量,因此共有 个可能的桶。
若对任意不同的键 以及任意输出 都有
则称该哈希族具有两两独立的均匀输出。
这蕴含每个输出都是均匀的,且碰撞概率为 。它并不声称三个或更多输出之间联合独立。
定理
定理 10.1.1
(仿射二元哈希族)
对于不同的二元键,哈希族 具有两两独立的均匀输出。它使用 个公平种子比特,并且通过直接做矩阵乘法,可以用 次基本比特运算完成求值。
定理 10.1.2
(固定键集中的期望碰撞数)
对于与随机哈希函数独立选取的、由 个不同键组成的任意固定集合,与指定键碰撞的其他键的期望个数为 。集合中存在任意一对键发生碰撞的概率至多为 。
证明:矩阵的一行
证明
(仿射哈希族的两两独立性)
固定不同的 ,并令 。由于 ,存在某个坐标 等于 1。对于 的一个均匀随机行向量 ,点积 是一个公平比特:固定 的其余所有坐标后,翻转 就会翻转该点积。因此
是一个均匀的 位向量,这是因为矩阵的各行相互独立。
偏移量 是均匀的,并且与 独立。在任意给定 的条件下, 是均匀的。于是,对任意指定的 ,先要求 ,其概率为 ;再要求 ,其条件概率为 。联合概率为 。
对 个相等的输出对 的联合概率求和,得到碰撞概率 。偏移量还使每个单独的输出都是均匀的,对零键也是如此。
证明透视
偏移量提供均匀的取值
各假设用在哪里: 恰好只用一次,用来找出使 的坐标 ;没有它, 为零,两个键必定碰撞。关键一步是把输出对拆成两部分:差 ,由随机矩阵使之均匀;位置 ,由独立的偏移使之均匀。 的各行相互独立,使 的 个比特相互独立; 与 独立,使两个因子 可以相乘。论证只涉及一对 ,所以只证明了两两独立,并不涉及三个键;反例中的四键关系说明更强的结论并不成立。
证明:固定集合的碰撞界
证明
(期望碰撞数与并集界)
对于由 个不同键组成的固定集合 中的一个固定键 ,令 表示 与 是否碰撞的指示变量。发生碰撞的其他键的个数为 。每个指示变量的期望都是 ,因此由线性性得期望为 。这些指示变量不必相互独立。
对于任意一对不同键(无序对),碰撞概率为 。共有 对。由并集界,至少有一对发生碰撞的概率至多为 。若该量超过 1,不等式依然成立,但不能给出有用的概率估计。
集合和查询都是独立于哈希种子而固定的。如果对手在看到所选哈希函数之后,再选取专门设计成发生碰撞的键,那么在没有进一步分析的情况下,就不能套用同样的固定集合概率陈述。
例题详解
例题 10.1.3
(一个输出比特)
对于 ,设随机行为 ,偏移量为 。对于键 和 ,输出分别为 和 。它们恰在 时碰撞,概率为 。
例题 10.1.4
(期望链长)
对于由 个键组成的固定集合,用任何具有相同碰撞界的哈希族将其哈希到 个桶中,一个指定的已存储键与之碰撞的其他键的期望个数至多为 。这里的二元构造本身的宽度是 2 的幂,所以这个数值例子说明的是碰撞定理,而不是声称它使用了满足 的 。
例题 10.1.5
(并集界可能是松的)
对于 和 ,至少发生一次碰撞的并集界为 。它不一定等于真实的碰撞概率,因为不同键对的碰撞事件可能重叠。
例题 10.1.6
(零键仍然有随机输出)
没有偏移量时,对每个矩阵都有 。有了独立的偏移量, 在各个桶上是均匀的。偏移量对于单个键输出的均匀性是必不可少的。
常见错误
反例模式
两两独立不等于完全独立
对于四个两位键 以及任意仿射二元哈希函数,它们的输出之和为零:矩阵项和偏移量各出现偶数次。因此这四个输出满足一个确定性关系,它们并非联合均匀的,尽管其中任意两个不同的输出是两两独立的。
常见错误
(期望很小不代表每个种子都好)
期望碰撞数并不保证每个种子下链都很短。有些被抽到的函数可能产生大量碰撞;例如 会把每个键都映射到 。高概率界需要额外的论证,并且可能弱于完全随机性所能给出的断言。
常见错误
(计算时间不等于种子大小)
表达式 计的是直接求值时的基本比特运算次数。机器字实现对某些维度可能求值更快,而存储种子仍需 个比特。该定理并不保证存在与键长无关的常数大小种子。
概念视角代数
两两独立就是线性映射的满射性
种子 在 上均匀分布,而 是映到 的 线性映射。当 时它是满射,因为 与 可以各自独立地指定;均匀的输入经过满射的线性映射,输出仍然均匀。对四个键 ,像落在输出之和为零的子空间内,所以那个映射不是满射。
应用:链地址法
将每个键存入其哈希桶对应的链表中。对于一个固定的已存储查询键 ,直接扫描所检查的条目数至多为 1 加上同一桶中其他已存储键的个数。因此,除去计算哈希和比较键的开销外,其期望至多为 。
对于不在已存储集合中的固定查询 ,其所在桶中已存储键的期望个数为 ,所以一次不成功的扫描在期望意义下检查这么多个键。这些陈述都假设已存储集合和查询是在随机选取种子之前固定的。它们统计的是链表条目数;比较两个 位键以及计算哈希各有其自身的代价。
若 与 相当,则被检查的链表条目的期望个数为常数。这是对固定输入在哈希种子上的平均,而不是对每个桶长度的最坏情形界。碰撞并集界在另一个方向上更强:它控制是否有任何一对键发生碰撞,但要使其很小,可能需要大得多的 。
自适应选择可以强制产生碰撞
设 ,且对手看到了抽样得到的矩阵 。线性映射 存在非零的核向量 ,因为从 维二元向量空间到 维二元向量空间的映射不可能是单射。对手可以选取 和 。于是
必然成立。这并不与定理矛盾:键 是在看到 之后选取的,所以这一对键并非独立于种子而固定。对于固定的非零 ,在全新的随机矩阵上 的概率仍然是 。
这个例子也说明,公开的哈希种子加上自适应对手,需要超出初等固定键分析的模型。视应用而定,可能需要秘密随机性、定期重建、更强的假设或不同的数据结构。仅凭两两独立性,得不到任何这样的自适应保证。
从期望到尾界
令 为与某个固定已存储查询碰撞的其他已存储键的个数。由于 ,马尔可夫(Markov)不等式对任意整数 给出
这由 以及期望碰撞数公式得到。该界可能是松的,但不需要假设碰撞指示变量相互独立即可成立。特别地,链长期望为常数并不意味着出现很长的链的概率为零。
对于整个固定集合,由同样的指示变量论证,发生碰撞的无序对的期望个数为 。若该期望小于 1,则至少存在一个没有任何碰撞的种子:否则每个种子都至少有一对碰撞,期望就至少为 1。这证明的是存在性,而不是找到这样一个种子的高效确定性方法。穷举检验全部 个种子的代价可能高得无法承受。
有限种子如何使用
矩阵含有 个比特,偏移量再含 个比特。独立且均匀地抽取所有这些比特,就确定了该哈希族中的一个函数。随后,同一个抽到的函数被用于该哈希表或该草图行中的所有键。对每次查找都重新抽取新的函数,通常会改变桶的分配,也就无法维持所描述的数据结构。
要计算一个输出比特,把矩阵的相应行与输入向量在 上相乘,再加上相应的偏移量比特。每行直接求值至多使用 次比特乘法和加法,因此全部 个输出比特共需 次基本比特运算。这一计数假设矩阵和键都是显式给出的。软件实现可以把比特打包进机器字,但其实际的字运算界取决于机器模型和字长。
独立的草图行可以通过为每一行独立抽取种子得到。同一行内的输出具有上面证明的两两性质;不同行的输出因种子独立而相互独立。这一区别在 Count–Min 的分析中很有用:线性性处理同一行内的碰撞,而行与行之间的独立性则放大了至少有一行噪声较小的概率。
四个键的相关性可以逐坐标验证。把 上的输出写成 、、 和 ,其中 是 的两列。它们在 上的和为零。若四个输出是完全独立的均匀 位向量,则这一等式只以概率 成立,而不是必然成立。因此,两两独立性不能推广到这个四键集合。
碰撞并集界有时被称为生日式估计:尽管每一次单独碰撞的概率只有 ,但键对的数目是二次的。例如,要使所示的界至多为 ,需要 。相比之下,要使与某个固定键碰撞的期望次数低于某个常数,只需 与 成正比。这是两种不同的保证,不应互相替换。如果键对的界超过 1,把它换成 1 给出的是一个有效但平凡的概率上界;这并不意味着概率本身超过 1。只有当该界的数值小于这一平凡极限、从而提供信息时,它才有用。
总结
随机二元矩阵加偏移量,用一个显式的有限种子产生均匀且两两独立的哈希输出。对固定键集,两两碰撞概率给出期望链长和并集界,而不要求所有键之间完全独立。
练习
快速检查
(当 时,共有多少个桶?两个固定的不同键的碰撞概率是多少?)
桶的个数是 。
解答 · 答案
共有 个桶,碰撞概率为 。
快速检查
(为什么在二元向量上,当 时 非零?)
在 上, 意味着什么?
解答 · 答案
在 上,若 则 。因此不同的键至少在一个坐标上不同,它们的和在该坐标上为 1。
快速检查
(对于 个已存储键和 个桶,与某个固定已存储键碰撞的其他键的期望个数是多少?)
把其他键的碰撞指示变量相加。
解答 · 答案
在所述的两两均匀哈希族下,它是 。
快速检查
(为什么期望碰撞数的证明不需要碰撞指示变量相互独立?)
期望对任何有限和都成立的是哪个性质?
解答 · 答案
期望对有限和总是可以分配,与是否相依无关。对每个其他键,只需其各自的碰撞概率即可。