掌握散列函数、装载因子和冲突处理,比较开放定址与拉链法,并能按请求概率正确计算成功和失败的平均查找长度。

# 一、散列表与散列函数

散列表(哈希表)用数组存放记录,并通过散列函数 H(key)H(key) 将关键字映射到表中的地址。实际记录常由 (key,value)(key,value) 组成;散列函数根据 key 计算地址。

若表长为 mm、当前保存 nn 个记录,装载因子为

α=nm.\alpha=\frac{n}{m}.

装载因子越高,冲突通常越多。散列函数应确定、计算快,并尽量把关键字均匀地映射到地址空间。常见方法包括:

  • 除留余数法:H(key)=keymodmH(key)=key\bmod m,常选与关键字分布不易产生周期相关的表长,如素数。
  • 平方取中法:先对关键字平方,再取中间若干位作为地址。
  • 折叠法:把关键字分成若干段后相加,再映射到表长范围。

不同关键字映射到同一地址称为冲突;散列值相同的关键字互为同义词。有限地址空间无法避免冲突,必须选择冲突处理方法。

# 二、开放定址法

开放定址法将所有记录放在同一个数组中。若初始位置已占用,就按探测序列继续寻找可用单元。常见形式如下。

方法探测序列特点
线性探测Hi(key)=(H(key)+i)modmH_i(key)=(H(key)+i)\bmod m实现简单,容易出现主聚集
平方探测H(key)±12,H(key)±22,…H(key)\pm1^2,\ H(key)\pm2^2,\ldots可缓解主聚集,但探测未必覆盖全表
双散列Hi(key)=(h1(key)+ih2(key))modmH_i(key)=(h_1(key)+i\,h_2(key))\bmod m步长依赖关键字,分布通常更好

双散列的步长应与表长互素,才能保证探测序列有机会遍历整个表;若 mm 为素数,可选择非零且小于 mm 的步长。

查找与插入必须使用相同的探测序列。查找遇到从未使用的空单元时可判定失败;删除不能直接恢复为 “从未使用” 的空单元,否则会截断后续关键字的探测链。常用墓碑标记表示 “曾占用、已删除”,查找越过墓碑,插入时可复用。

开放定址法要求表内保留空位,故通常需 α<1\alpha<1。冲突增加会使探测长度增大。

# 三、拉链法

拉链法(分离链接法)为每个散列地址维护一个链表或其他容器。冲突记录放入同一地址的链中;查找时先计算地址,再在对应链中查找。

拉链法的装载因子可以大于 11,删除链中结点也较直接;代价是每条记录需要额外链接空间。若散列分布均匀且装载因子适中,平均操作通常接近 O(1)O(1);若大量关键字聚集到一个地址,最坏仍退化为 O(n)O(n)。

flowchart LR
    A[散列数组] --> B[槽0:链表]
    A --> C[槽1:链表]
    A --> D[槽2:链表]
    C --> E[key1]
    E --> F[key2:同一散列地址]

开放定址和拉链法的主要差别如下。

对比项开放定址法拉链法
记录位置表数组中的某个探测槽位散列地址对应的链或桶
装载因子必须小于 11可以大于 11
删除需墓碑等机制保护探测链删除链中结点
额外空间槽位可能空置需保存链接或桶结构

# 四、平均查找长度

ASL 是查找长度的期望值。计算前先确定每种请求的概率,以及查找成功或失败时 “查找长度” 按比较次数还是探测次数计。

# 1. 成功查找

若 nn 个表内关键字等概率被查找,成功 ASL 为每个关键字查找探测次数的平均:

ASL⁡成功=1n∑k已存入C(k).\operatorname{ASL}_{成功} =\frac{1}{n}\sum_{k\text{ 已存入}} C(k).

开放定址中,初始位置即可命中的记录长度为 11;发生冲突后,每经过一个探测槽位都要计数。拉链法中,链上第 rr 个记录通常需比较 rr 次。

# 2. 失败查找

失败查找的 ASL 通常对散列函数可能产生的初始地址求平均,而不是盲目对表中所有槽位求平均。每个初始地址沿相应探测序列走到一个从未使用的空槽,统计探测次数后再按地址概率加权。

例如,表长为 77,用线性探测插入 0,7,140,7,14,且 H(key)=keymod7H(key)=key\bmod7,三条记录依次占据槽位 0,1,20,1,2。

查找请求探测过程查找长度
成功查找 000011
成功查找 770,10,122
成功查找 14140,1,20,1,233
失败,初始地址 000,1,2,30,1,2,344
失败,初始地址 111,2,31,2,333
失败,初始地址 222,32,322
失败,初始地址 33、44、55、66各自命中首个空槽各为 11

在成功请求等概率、失败初始地址均匀的前提下:

ASL⁡成功=1+2+33=2,ASL⁡失败=4+3+2+1+1+1+17=137.\operatorname{ASL}_{成功}=\frac{1+2+3}{3}=2,\qquad \operatorname{ASL}_{失败}=\frac{4+3+2+1+1+1+1}{7}=\frac{13}{7}.

# 五、扩容与再散列

散列表扩容时通常申请更大的数组,并对已有关键字重新计算地址、重新插入。不能只把旧数组内容按原下标复制到新表,因为表长改变后 H(key)H(key) 可能改变。扩容阈值取决于冲突方案和性能目标;开放定址表一般要为未命中探测保留足够空槽。

# 六、考场检查清单

  1. 散列函数根据关键字映射地址;冲突是不同关键字竞争同一地址。
  2. 开放定址和拉链法是不同的冲突处理策略,不要混用它们的探测过程。
  3. 开放定址删除需保留探测链信息,墓碑不等于从未使用的空槽。
  4. 成功 ASL 对已存记录求平均;失败 ASL 通常对所有可能的初始地址求平均。
  5. 扩容后表长改变,已有记录通常需要重新散列。
更新于 阅读次数 次

请我喝[茶]~( ̄▽ ̄)~*

梦前辈 微信支付

微信支付

梦前辈 支付宝

支付宝