桶保存键值,不提供保证
用哈希表表示键值集合时,查询不能把哈希值相同的不同键值混为一谈。拉链法使用函数 把每个键值映到 个桶之一,每个桶存储该桶键值的链表。
定义 5.1.1
(拉链哈希表与负载因子)
以哈希函数 和 个桶建立的拉链哈希表,存储 个不同键值,使每个已存键值 恰好位于一个链表,即桶 的链表。其负载因子为 。
- 搜索先算桶,再逐个比较该链表中的键值,直至找到相等者或到达末尾。
- 插入先检查键值是否已存在,若不存在才加入该桶。
- 删除从链表移除相等的键值。
因此即使发生碰撞,结构仍表示由不同键值组成的集合。
假设计算 、比较两个键值及访问桶都需常数时间,每访问一个键值算一次比较。链表删除也需保存前一节点的引用或等价链接。
一个具体表格
例题 5.1.2
(五个键值放入五个桶)
令 、,依次插入 ,并在桶尾加入。非空链表为
搜索 访问桶 ,做两次键值比较;搜索不存在的 访问桶 ,也做两次。删除 后,桶 剩下 ,不影响找到 。键值碰撞不等于键值相等,所以搜索必须实际比较。
常见错误
(把同一个桶当成相等的键值)
在上面的表中, 与 的哈希值同为 。若搜索在发现桶非空时就停止,就会回答 存在,但桶 的链表其实是 。哈希值相同只说明应该到哪里找;是否属于集合,要靠把查询键值与已存键值比较来决定,所以上面的搜索要做两次比较后才报告不存在。
反例模式
平均负载不是最坏情况界
负载因子 是每桶存储键值数目的平均值,不是每个桶的上界。对相同的余数哈希,当 ,键值 全进入桶 :负载因子是 ,但该链表长度为 。对每个 ,使用模 余数哈希并插入 。负载保持为 ,但一条链有 个键值;查询不存在的 需比较 次。确定性的哈希及小平均负载本身不能建立常数最坏查询界。
碰撞假设及其结果
定义 5.1.3
(具逐对碰撞界的函数族)
从键值映到 个桶的有限函数族 具有逐对碰撞界,若每对不同键值 都满足
其中 从 均匀选取。
从这样的函数族均匀选取 ,只选一次,并且在存储任何键值之前完成。固定一组 个不同键值的集合 及查询 ,并要求它们独立于随机选取 。
定理 5.1.4
(逐对碰撞界下的期望搜索成本)
设 取自具逐对碰撞界的函数族,且 与 的固定不依赖 。则在存储 的拉链表中,键值比较次数的期望至多为
- 不成功搜索():;
- 成功搜索():。
在上述成本假设下,不成功搜索的期望时间为 。
证明
(计算与查询同桶的键值)
设 ,令 为被搜索桶中属于 的键值数目。由期望的线性性,
不成功搜索恰好比较这 个键值,其余工作(计算 、到达桶)为常数,因此期望时间为 。
对 ,被搜索链表的长度为
同一假设用于其余 个键值 ,使其期望长度至多为 。成功搜索访问的键值不多于整条链表,故无论链表次序如何,其期望比较次数至多为此值。
证明透视
线性性论证用了什么
论证只用到两项:每个 的逐对界,以及期望的线性——它把 个这样的界相加,不要求各事件之间有任何相依性条件。 与 独立于 而固定,才能对每一对套用逐对界。成功搜索多出的 就是查询键值本身,它必定在自己的链表中。期望是对 的选择而言,所以定理没有说明某一个表的最长链;上面的反例表明,一个表可以有长度为 的链。
因此在此模型中,保持 有界可得期望常数查询界。若看过哈希函数后才自适应选择集合或查询,上面的固定输入论证不会自动适用。扩容及重新哈希有其自身成本,此处未分析。链表及桶数组使用 空间。
例题 5.1.5
(小型函数族的精确期望链长)
取三个可能的键值 、两个桶,并令 为从键值到两个桶的全部 个函数。对两个不同键值,恰好一半的函数使哈希值相同,所以碰撞概率为 ,此族具有逐对碰撞界。存储 ,搜索 ,即 、、。
若 ,则 这四种选择下,桶 中的已存键值数目依次为 。 的情形对称。所以每一半中 取值 ,而
界在此取等号,而各个别表并不相同:有的有两个键值的链,有的链是空的。
例题 5.1.6
(一个桶与空表)
若 ,每个函数都把全部键值送到桶 ,所以任何函数族的碰撞概率都是 ,逐对碰撞界显然成立。含 个键值的表就是一条链表,不成功搜索要做 次比较,而 :界 恰好取到,表只是一个链表。
空表 时每个链表都是空的。搜索计算 ,到达空链表,不作任何键值比较,成本只是哈希与到达桶的常数工作。这与 时的 吻合。
常见错误
(存好键值后才重新抽取哈希函数)
期望界针对的是插入之前作出的一次随机选择 。若查询到达时才抽取新函数 ,已存键值仍然放在旧函数 的链表中。以上面的表为例,存放在桶 的键值 ,可能被到桶 查找而报告不存在。只有把每个已存键值移到新函数给出的桶,更换函数才是合理的。
习题与解答
快速检查
(桶跟踪。具体表格搜索 时查哪个桶?若它不存在需多少次比较?)
解答 · 答案
由于 ,查桶 。它含 ,故比较一次。
快速检查
(确定的碰撞。若不同键值满足 ,表格能否丢弃其中之一?)
解答 · 答案
不能。两者都留在链表中,并由相等比较区分。
快速检查
(期望次数。在所述碰撞界下, 时不成功搜索的期望比较次数有什么上界?)
解答 · 答案
对独立于 的固定集合及不存在的固定查询,至多 。
快速检查
(假设。证明是否需要不同 的碰撞事件互相独立?)
解答 · 答案
不需要;期望线性性及各自的概率上界已足够。