字典必须区分不同的键,即使它们关联的值相同。哈希表先把键转换为较小的桶索引,再在桶内区分实际的键。这种转换之所以有用,正是因为桶的数量可以远少于可能的键数。因此,碰撞通常无法避免;正确的设计必须处理碰撞,而不是假设它永不发生。
链地址法的正确性容易看清:每个桶存储一条条目的链表,查询沿链表比较真正的键。性能则是另一个问题。我们先说明为什么负载因子本身不能保证短链,再从适当的随机哈希族中选择函数,证明期望成本界。
桶是位置,不是键的身份
定义 16.1.1
(链表不变量与映射操作)
设固定哈希函数为 ,共有 个桶。每个存储条目是一个键值对。链表不变量要求:
- 每个已存储键 恰好出现一次,并且位于桶 。
- 该条目存储目前与 关联的值。
- 每个桶都是有限、无环的链表。
get(x) 返回与 关联的值,或表示键不存在。put(x,v) 替换已有键的值;如果 不存在,则新增条目。erase(x) 在键存在时删除它。不同键可以有相同桶索引,而不违反不变量。
查询先计算 ,只搜索这条链。如果找到相等的键,唯一性就确定了所需的值。如果到达链尾,键就是不存在:不变量禁止它出现在其他桶。只比较桶索引,反而会丢失区分碰撞键所需的信息。
插入先搜索已有键。找到时只修改值,不新增条目,也不改变键数;否则将新条目接到所选链的开头。删除则修改桶头指针或前一个条目的 next 指针,将匹配条目从链中移除。其他条目的键和桶位置不变,因此这些局部修改保持不变量。
跟踪碰撞,不丢失任何键
例题 16.1.2
(三个不同键,共用一条链)
使用五个桶,对 0 至 16 的整数键定义
两次取模是分开的步骤:
| 键 | 桶 | |
|---|---|---|
依次插入 (0, "A")、(5, "B")、(9, "C"),每次将新条目放到链头。桶 1 变为
head -> (9, "C") -> (5, "B") -> (0, "A") -> end
get(5) 先比较 9,再比较 5,返回 "B"。put(5, "B2") 只修改该条目的值,长度仍为三,不能另外增加第二个键为 5 的条目。
现在执行 erase(5),使 9 的条目直接指向 0 的条目。其余两个键仍然可达。失败查询 get(13) 比较这两项后才报告不存在,不能仅因为 13 也在桶 1,就返回其中某个值。
链长可以大于一,而每个条目仍然有效。删除中间节点也不会留下需要标记的空洞,因为链指针已经绕过它。这些叙述适用于链地址法;通过探测其他数组位置处理碰撞的表,具有不同的搜索不变量。
常见错误
(先搜索,才放到链首)
若 put(5, "B2") 直接把新条目放到链首,桶 1 会变成 (5, "B2") -> (9, "C") -> (5, "B") -> (0, "A"):同一个键有两个条目。之后 erase(5) 只会移除第一个,旧值 "B" 便会在 get(5) 中重现。链表不变量规定每个键至多出现一次,所以插入前必须先搜索该链,然后才放到链首。
负载因子能说明什么?
存储 个键时,定义负载因子为 。所有链长的总和为 ,所以对桶取平均的链长恰好是 。但这个算术事实,没有保证某次查询选中的链很短。
反例模式
平均很小,查询选中的链仍可能很长
考虑确定性规则 。键 全在桶 0,其余四个桶为空。负载因子是 ,但失败查询 20 需要比较全部四项。继续插入五的不同倍数,只会延长同一条链。
一般而言,如果全部 个键都在查询的桶中,查询可能需要 次比较;各桶平均仍为 。有用的期望时间结论因此必须说明随机性的来源和碰撞保证,不能仅从负载因子的定义推出。
精确说明随机性保证什么
定义 16.1.3
(通用哈希族)
从 到 个桶的有限哈希族 称为通用,如果对每对固定且不同的键 ,都有
随机的是所选函数。叙述中的键固定,而且不依赖这次选择。通用哈希族不要求每个被选中的函数都没有碰撞。哈希族按参数索引;不同参数可以恰好定义相同的桶函数。
选好函数后,只要条目仍留在原桶,就保持函数不变。下面的期望是对最初的选择取平均,不是对键值或链内条目的随机顺序取平均。
常见错误
(每次操作都重新抽取哈希函数)
下面的期望针对的是在存储任何条目之前所作的一次随机选择。若每次查询都重新抽取函数,不变量就会被破坏:键 0 存放在桶 ,而查询搜索桶 ,通常会找不到。只有在同时把所有已存条目重新哈希之后,更换函数才是合理的。
定理 16.1.4
(通用族下的期望链长)
设 是映入 个桶的通用族,并设 从中均匀选取一次。设 为含 个存储键的集合, 为一个键,两者都固定而不依赖 。在链式表中,查询 比较的键数:
- 若 ,期望至多为 ;
- 若 ,期望至多为 。
证明
(用指示变量计算碰撞的键)
先设 。对每个 ,令
被查询链的条目数是 。利用期望的线性及通用性,
失败查询恰好比较这 个键。哈希计算及取桶只需常数工作,所以若键的哈希与比较均需常数时间,期望时间就是 。
现设 。对 中的 个键 作同样论证,得到与 同桶的其他键,其期望数目至多为 。即使 的条目位于链尾,查询也在该处停止,所以比较次数至多是一次加上每个其他同桶键各一次:
证明透视
指示变量论证用了什么
论证用到三项要素,各用一次。通用性把每一对 限制在 以内;期望的线性把这 个上界相加; 与 在 之前已经固定,通用性不等式才能适用于每一对。指示变量 不必相互独立,因为线性并不要求独立。若键是在观察 之后才选的,例如 个键全落在同一桶,链长便是 ,界 就不成立,正如上面的反例。
put 和 erase 内的搜索具有相应的界,之后的指针或值更新只需常数时间。某个已选函数仍可能产生长链,所以最坏查询时间仍为线性。如果先观察函数,再刻意选择碰撞键,也不满足证明所用的独立选择假设。
用素数模数构造通用族
设 为素数,,键限制为整数 。从 均匀选择 ,从 均匀选择 ,两次选择独立。定义
第一步在域 中运算;第二步把 种输出分到 个桶。要证明碰撞界,必须同时分析两个不同的键,而不只是说一个输出分布得很散。
定理 16.1.5
(素数模数下的仿射族是通用族)
设 为素数,。从 均匀选 ,从 均匀选 ,两次选择独立,并在键 上令 。则对所有不同的键 ,
证明
(先数不同的域输出对,再数桶碰撞)
固定 中的 。对于指定的不同输出 ,方程
在 中有唯一解
因为 是素数且 非零,逆元存在。这个解满足 。反过来,非零 不会把不同的 映射为相同的域输出。
因此, 个等可能的参数对 ,恰好各自产生一次每个有序且不同的输出对 。给定第一个输出 ,第二个输出在其余 个余数中均匀分布。两个输出必定不同,所以并不独立。
再对 取模后,每桶至多含 个域余数。固定 后,其余余数中至多有 个与它同桶。因此
它不要求 可以被 整除,也不要求最后各桶的概率完全相等。
证明透视
由参数到输出的变量替换
关键一步,是不再把 当作随机对象,而改为观察输出对 :映射 是由 个参数对到有序且不同的余数对的双射。素性只用一次,就是求 的逆元。条件 恰好对应 ,所以 取遍全部余数,而 不能。最后对 取模是界唯一可能放松的地方:它只数出至多 个与 同桶的余数。若 与 在 中相等,则对 根本无解,见下面的反例。
例题 16.1.6
(精确碰撞概率不必等于上界)
取 、,固定键 0 和 1。参数 有 种选择,对应全部有序且不同的域输出对。
桶 0 含余数 ,桶 1 含 。位于同一桶的有序不同输出对共有
精确碰撞概率为 ,不超过 。单个域输出在五个余数中均匀分布,但桶概率是 和 ,不是各一半。指示变量证明只需要通用性的碰撞不等式,不需要桶输出完全均匀。
反例模式
键的定义域是定理的一部分
如果程序把 0 和 17 当作不同键,却使用 的族,那么每组参数下, 和 对 17 取模后都相同。两个键的碰撞概率为一,不会因为随机选择 而改善。
这没有矛盾:两者在 中是同一个元素,违反了不同域键的假设。实现必须将允许的键单射地表示为域元素,或者使用另一种有依据的哈希构造。同样,证明依靠素数保证逆元,不能随意用合数替换 。
例题 16.1.7
(一个桶与空表)
取 。映入一个桶的函数都是常数函数,所以任何族都是通用的,因为 ,而碰撞概率至多为 1。每个键都在桶 0,所以存储 个键时,失败查询要比较全部 个。此时 ,定理的期望界恰好取等号,表已退化为单个链表。
另一端是空表 。查询计算 ,到达空链,不作任何键比较,成本就是哈希与取桶的常数。这与 时的 吻合:界中的 不能省略。
直接实现映射不变量
下面的实现接受 中的整数键。构造时假设 prime 确实是素数;本例不处理素数测试。程序检查参数范围,但不会随机选择参数。传入 (17, 5, 3, 1) 可以重现前面的确定性例子。要使用期望界,必须按照上述均匀分布选择参数,并且选择不依赖输入键。
class Entry:
def __init__(self, key, value, next_entry):
self.key = key
self.value = value
self.next = next_entry
class ChainedMap:
def __init__(self, prime, bucket_count, a, b):
if not (1 <= bucket_count <= prime and
1 <= a < prime and 0 <= b < prime):
raise ValueError("invalid hash parameter range")
self.prime = prime
self.a, self.b = a, b
self.buckets = [None] * bucket_count
self.size = 0
def _index(self, key):
if not isinstance(key, int) or not 0 <= key < self.prime:
raise ValueError("key outside the integer field domain")
return ((self.a * key + self.b) % self.prime) % len(self.buckets)
def get(self, key):
node = self.buckets[self._index(key)]
while node is not None:
if node.key == key:
return node.value
node = node.next
raise KeyError(key)
def put(self, key, value):
index = self._index(key)
node = self.buckets[index]
while node is not None:
if node.key == key:
node.value = value
return False
node = node.next
self.buckets[index] = Entry(key, value, self.buckets[index])
self.size += 1
return True
def erase(self, key):
index = self._index(key)
previous = None
node = self.buckets[index]
while node is not None:
if node.key == key:
if previous is None:
self.buckets[index] = node.next
else:
previous.next = node.next
self.size -= 1
return True
previous, node = node, node.next
return False
条目仍在表内时,保持 prime、a、b 以及桶数不变。改变函数或桶数时,必须按照新索引重新分配每个条目,否则查询不变量失效。条目占用 空间,桶头指针占用 ,初始化需要 时间。
在负载因子有界、随机选择和机器字运算假设成立时,操作的期望成本为常数。表增长时要保持有界负载,需要扩容和重新哈希策略。重建整张表是额外操作,其序列成本必须另外分析;本节的固定状态期望界不会使重建变为常数时间。
练习与详解
快速检查
(更新碰撞键,不能新增重复条目)
沿用五个桶的例子,插入 (0, "A")、(5, "B")、(9, "C"),把 5 的值改为 "B2",再删除 9。给出桶 1 的最终链、键数、get(5),以及失败查询 get(13) 的键比较次数。
解答 · 答案
最终链为 (5, "B2") -> (0, "A") -> end。更新 5 只修改值,删除链头 9 则修改桶头指针。键数为二,get(5) 返回 "B2";get(13) 比较剩下的两个键后,才报告不存在。
快速检查
(应用期望比较次数界)
固定的一千个键用均匀选择的通用哈希函数放入 250 个桶。固定的不存在查询,其期望比较次数上界是多少?固定的存在查询又是多少?是否每次实际运行都满足这些界?
解答 · 答案
不存在查询的界为 。存在查询的界为 。哈希计算另加常数工作。期望是针对函数选择而言,键与查询都固定而不依赖该选择。某个选择仍可能产生长链,所以不是每次实际运行的界。
快速检查
(找出指示变量证明真正需要的假设)
不同存储键的碰撞指示变量必须相互独立吗?应用通用性不等式时,对查询和存储键使用了什么假设?
解答 · 答案
不需要相互独立,因为任意有限和都满足期望的线性性。每对不同键分别需要满足碰撞概率界。存储集合和查询固定,不依赖随机哈希选择;如果知道函数后才自适应地选择键,就需要另一个论证。
快速检查
(解释每组参数都会产生的碰撞)
素数为 17 时,为什么整数键 2 和 19 永远具有相同的域输出?如果字典要区分它们,应用通用族定理前必须改变哪项条件?
解答 · 答案
两个键的差为 17,所以对每个 ,。它们表示同一个域元素。定理要求允许的不同键具有不同的域表示;例如,对于有限的非负整数键域,选择比所有键都大的素数。仅改变随机种子,无法修复定义域问题。
快速检查
(精确计算小型族的碰撞数)
对于 及固定不同键,为什么二十种参数中有八种碰撞?某个桶的概率为 ,是否违反通用性?
解答 · 答案
仿射参数将全部有序不同域输出对各列举一次。桶 0 的三个余数贡献 对;桶 1 的两个余数贡献 对,共八对。因此碰撞概率为 。通用性限制两个不同键的碰撞概率,不要求各桶概率恰好为 。
快速检查
(修改参数会改变查询位置)
用 存储键 0。不移动条目,直接将参数改成 。键 0 实际在哪个桶?新查询会搜索哪个桶?缺少什么操作?
解答 · 答案
条目仍实际位于旧索引的桶 1。新函数将 0 映射到桶 0,查询就会错误地报告不存在。修改参数时,必须将每个已存储条目重新哈希到新桶。新函数在数学上有效,不代表旧表的表示不变量仍然成立。