掌握散列函数、装载因子和冲突处理,比较开放定址与拉链法,并能按请求概率正确计算成功和失败的平均查找长度。
# 一、散列表与散列函数
散列表(哈希表)用数组存放记录,并通过散列函数 将关键字映射到表中的地址。实际记录常由 组成;散列函数根据 key 计算地址。
若表长为 、当前保存 个记录,装载因子为
装载因子越高,冲突通常越多。散列函数应确定、计算快,并尽量把关键字均匀地映射到地址空间。常见方法包括:
- 除留余数法:,常选与关键字分布不易产生周期相关的表长,如素数。
- 平方取中法:先对关键字平方,再取中间若干位作为地址。
- 折叠法:把关键字分成若干段后相加,再映射到表长范围。
不同关键字映射到同一地址称为冲突;散列值相同的关键字互为同义词。有限地址空间无法避免冲突,必须选择冲突处理方法。
# 二、开放定址法
开放定址法将所有记录放在同一个数组中。若初始位置已占用,就按探测序列继续寻找可用单元。常见形式如下。
| 方法 | 探测序列 | 特点 |
|---|---|---|
| 线性探测 | 实现简单,容易出现主聚集 | |
| 平方探测 | 可缓解主聚集,但探测未必覆盖全表 | |
| 双散列 | 步长依赖关键字,分布通常更好 |
双散列的步长应与表长互素,才能保证探测序列有机会遍历整个表;若 为素数,可选择非零且小于 的步长。
查找与插入必须使用相同的探测序列。查找遇到从未使用的空单元时可判定失败;删除不能直接恢复为 “从未使用” 的空单元,否则会截断后续关键字的探测链。常用墓碑标记表示 “曾占用、已删除”,查找越过墓碑,插入时可复用。
开放定址法要求表内保留空位,故通常需 。冲突增加会使探测长度增大。
# 三、拉链法
拉链法(分离链接法)为每个散列地址维护一个链表或其他容器。冲突记录放入同一地址的链中;查找时先计算地址,再在对应链中查找。
拉链法的装载因子可以大于 ,删除链中结点也较直接;代价是每条记录需要额外链接空间。若散列分布均匀且装载因子适中,平均操作通常接近 ;若大量关键字聚集到一个地址,最坏仍退化为 。
flowchart LR
A[散列数组] --> B[槽0:链表]
A --> C[槽1:链表]
A --> D[槽2:链表]
C --> E[key1]
E --> F[key2:同一散列地址]开放定址和拉链法的主要差别如下。
| 对比项 | 开放定址法 | 拉链法 |
|---|---|---|
| 记录位置 | 表数组中的某个探测槽位 | 散列地址对应的链或桶 |
| 装载因子 | 必须小于 | 可以大于 |
| 删除 | 需墓碑等机制保护探测链 | 删除链中结点 |
| 额外空间 | 槽位可能空置 | 需保存链接或桶结构 |
# 四、平均查找长度
ASL 是查找长度的期望值。计算前先确定每种请求的概率,以及查找成功或失败时 “查找长度” 按比较次数还是探测次数计。
# 1. 成功查找
若 个表内关键字等概率被查找,成功 ASL 为每个关键字查找探测次数的平均:
开放定址中,初始位置即可命中的记录长度为 ;发生冲突后,每经过一个探测槽位都要计数。拉链法中,链上第 个记录通常需比较 次。
# 2. 失败查找
失败查找的 ASL 通常对散列函数可能产生的初始地址求平均,而不是盲目对表中所有槽位求平均。每个初始地址沿相应探测序列走到一个从未使用的空槽,统计探测次数后再按地址概率加权。
例如,表长为 ,用线性探测插入 ,且 ,三条记录依次占据槽位 。
| 查找请求 | 探测过程 | 查找长度 |
|---|---|---|
| 成功查找 | ||
| 成功查找 | ||
| 成功查找 | ||
| 失败,初始地址 | ||
| 失败,初始地址 | ||
| 失败,初始地址 | ||
| 失败,初始地址 、、、 | 各自命中首个空槽 | 各为 |
在成功请求等概率、失败初始地址均匀的前提下:
# 五、扩容与再散列
散列表扩容时通常申请更大的数组,并对已有关键字重新计算地址、重新插入。不能只把旧数组内容按原下标复制到新表,因为表长改变后 可能改变。扩容阈值取决于冲突方案和性能目标;开放定址表一般要为未命中探测保留足够空槽。
# 六、考场检查清单
- 散列函数根据关键字映射地址;冲突是不同关键字竞争同一地址。
- 开放定址和拉链法是不同的冲突处理策略,不要混用它们的探测过程。
- 开放定址删除需保留探测链信息,墓碑不等于从未使用的空槽。
- 成功 ASL 对已存记录求平均;失败 ASL 通常对所有可能的初始地址求平均。
- 扩容后表长改变,已有记录通常需要重新散列。
