708 散列表

散列表

基本概念

散列表 (Hash Table)，也称哈希表，是一种根据关键字 (Key) 直接访问在内存存储位置的数据结构。它通过一个散列函数 (Hash Function) 将关键字映射到表中的一个位置（地址），这个位置称为散列地址 (Hash Address)。

• 核心思想：记录的存储位置与它的关键字之间建立一个确定的对应关系 $f$，使得每个关键字 $key$ 对应一个存储位置 $f(key)$。
• 散列函数：$Addr=H(key)$。将任意长度的输入（关键字）转换为固定长度的输出（散列地址）。
• 冲突 (Collision)：两个或多个不同的关键字，通过散列函数计算后得到了相同的散列地址。处理冲突是散列表设计的关键。
• 同义词 (Synonym)：发生冲突的不同关键字互为同义词。

构造方法

直接定址法

直接使用关键字的某个线性函数值作为散列地址。

$$H(key)=a\cdot key+b$$

• 特点：简单、直观，不会产生冲突。
• 缺点：需要预先知道关键字的分布情况，且关键字集合必须是连续或近似连续的，否则会造成巨大的空间浪费。适用于关键字集合不大且连续性好的情况。

除留余数法

取关键字被某个不大于散列表长度 $m$ 的数 $p$ 除后所得的余数作为散列地址。

$$H(key)=key(\mathrm{mod}p)$$

• 关键：$p$ 的选择。通常选择不大于 $m$ 的质数或不含小于 20 的质因子的合数，可以使关键字分布更均匀，减少冲突。

数字分析法

当关键字是位数较多的数字时，通过分析关键字各位数字的分布情况，选取其中分布比较均匀的几位或其组合作为散列地址。

• 适用场景：适用于已知的关键字集合，且关键字的某些位数的数字分布存在明显的不均匀性。例如，学号的前几位可能代表年份和学院，分布集中，而末几位可能分布更随机。

平方取中法

取关键字的平方值的中间几位作为散列地址。

• 过程：将关键字平方，然后抽取结果的中间若干位。
• 优点：中间几位数与关键字的每一位都相关，因此使得散列地址分布较为均匀，能有效避免冲突。

冲突处理

开放定址法

当发生冲突时，按照某种探测序列在散列表中寻找下一个空的存储位置。其基本公式为：

$$H_i=(H(key)+d_i)(\mathrm{mod}m)$$

其中 $H(key)$ 为初始散列地址，$d_i$ 为第 $i$ 次探测的增量序列。

1. 线性探测法 (Linear Probing)：$d_i=1,2,3,...,m-1$。

   • 特点：当发生冲突时，顺序查找下一个可用位置。
   • 缺点：容易产生“一次聚集 ” (Primary Clustering) 现象，即冲突的元素会聚集在一起，形成连续的块，降低查找效率。
   • 一次聚集形成原因及影响：
     • 固定步长：由于探测步长固定为 1，任何一个新冲突的元素，无论其原始哈希地址是什么，如果遇到冲突，都会尝试占用其哈希地址的下一个可用位置。
     • 链式反应：
       • 无论是原始哈希地址相邻的元素，还是原始哈希地址相距较远的元素，只要它们在探测过程中“碰”到已形成的聚集块，都将被迫沿着该块的末端继续探测以寻找空位。
       • 这意味着，如果一个元素的映射位置已被占用（无论是被其他冲突元素还是“正常”元素），它会继续按序探测（接着找下一个可用位置）。这种顺序探测的行为本身，使得新的元素更容易附着到现有聚集块的末端，使块变得更长。
     • 效率降低：随着聚集块的增大，后续任何映射到该块内部或前端的元素，都将不得不沿着该块的长度继续探测，这显著增加了查找、插入和删除操作的平均探测长度，从而降低了哈希表的整体性能。

2. 平方探测法 (Quadratic Probing)：$d_i=1^2,-1^2,2^2,-2^2,...,\pm k^2$。

   • 特点：探测位置呈二次方增长，可以有效缓解一次聚集。
   • 缺点：可能会产生“二次聚集” (Secondary Clustering)，即具有相同初始散列地址的关键字会具有相同的探测序列。

3. 双重散列法 (Double Hashing)：$d_i=i\cdot H_2(key)$。

   • 特点：使用第二个散列函数 $H_2(key)$ 计算增量。探测序列取决于关键字本身。
   • 优点：能有效避免一次和二次聚集，是开放定址法中性能较好的方法。$H_2(key)$ 的值必须与表长 $m$ 互质，以保证能探测到所有位置。

拉链法（链接法）

将所有散列地址相同的记录存储在同一条链表中。散列表的每个单元存储指向对应链表头结点的指针。

• 优点：
  • 实现简单，非同义词之间不会产生冲突。
  • 无聚集现象，平均查找性能好。
  • 链式存储，便于记录的插入和删除。
  • 装填因子 $\alpha$ 可以大于 1，对 $\alpha$ 不太敏感。
• 缺点：需要额外的指针空间。

散列查找

散列表构造

1. 确定表长 $m$：根据记录数 $n$ 和装填因子 $\alpha$ 确定，$m\approx n/\alpha$。
2. 选择散列函数 $H$：根据关键字的特点选择合适的构造方法。
3. 选择冲突处理方法：根据性能要求和实现复杂度选择。
4. 插入元素：依次将记录根据其关键字计算散列地址，并按选定的冲突处理方法存入表中。

散列表查找过程

1. 计算地址：使用与构造时相同的散列函数计算待查关键字 $key$ 的散列地址 $addr=H(key)$。
2. 比较关键字：
   • 访问散列表中地址为 $addr$ 的单元。若该单元为空，则查找失败。
   • 若该单元中存储的关键字与 $key$ 相等，则查找成功。
   • 若不相等（发生冲突），则根据冲突处理方法继续探测。
3. 冲突处理：
   • 开放定址法：按探测序列依次访问后续单元，直到找到关键字或遇到空单元（查找失败）。
   • 拉链法：遍历对应地址的链表，查找是否存在该关键字。若遍历到链表末尾仍未找到，则查找失败。

查找效率分析

散列表的查找效率主要取决于散列函数的均匀性、冲突处理方法以及装填因子 $\alpha$。

• 装填因子 (Load Factor) $\alpha$：表示散列表的装满程度。
  • 对于开放定址法：$\alpha =\frac{\text{表中记录数 }n}{\text{散列表长度 }m}$，$\alpha \le 1$。
  • 对于拉链法：$\alpha =\frac{\text{表中记录数 }n}{\text{散列表长度 }m}$，$\alpha$ 可以大于 1，表示链表的平均长度。
• 平均查找长度 (Average Search Length, ASL)：
  • 成功查找：找到目标关键字所需的平均比较次数。
  • 不成功查找：确定关键字不存在所需的平均比较次数。

冲突处理方法	平均查找长度 (ASL) - 查找成功	平均查找长度 (ASL) - 查找失败
线性探测法	$\approx \frac{1}{2}\left(1+\frac{1}{1-\alpha }\right)$	$\approx \frac{1}{2}\left(1+{\left(\frac{1}{1-\alpha }\right)}^2\right)$
平方探测法	$\approx \frac{1}{2}\left(1+\frac{1}{1-\alpha }\right)$	$\approx \frac{1}{1-\alpha }$
双重散列法	$\approx -\frac{1}{\alpha }\ln (1-\alpha )$	$\approx \frac{1}{1-\alpha }$
拉链法	$\approx 1+\frac{\alpha }{2}$	$\approx \alpha +e^{-\alpha }$ (或简单理解为 $\alpha$)

核心结论：在理想情况下（散列函数均匀，装填因子 $\alpha$ 合理），散列表的查找、插入和删除操作的平均时间复杂度都接近 O(1)。