哈希表（Hash Table）不成功搜索原理及答案依据咨询

注：原提问附带对应的哈希表问题示意图，以下基于哈希表不成功搜索的通用逻辑及常见题型进行解析。

一、什么是哈希表的不成功搜索 #

当尝试查找一个不存在于哈希表中的键时，搜索过程会严格遵循哈希表的冲突解决规则（如线性探测、链地址法等）持续检查哈希槽，直到触发终止条件（比如遇到空槽、遍历完所有关联节点），这个过程就是不成功搜索。我们通常关注这类搜索的平均比较次数，以此衡量哈希表的查找性能。

二、常见冲突策略下的不成功搜索逻辑与计算 #

1. 线性探测（开放寻址法） #

线性探测的规则是：若目标键的哈希位置已被占用，则依次检查下一个槽（表尾后循环到表头），直到找到空槽或遍历完整个表。

• 终止条件：遇到空槽（因为如果键存在，必然在从哈希位置开始的连续占用槽中，所以空槽的出现意味着目标键不存在）。

• 平均次数计算：
  若哈希表大小为m，已填入n个元素，装填因子α = n/m，理论上线性探测下不成功搜索的平均比较次数为：

  (1 + 1/(1-α)²) / 2
  

  若是给定具体的哈希表示例，则需逐个分析每个可能的哈希位置（共m个），统计从该位置开始到遇到空槽的比较次数，最后取所有位置的平均值。

  举个实例：假设哈希表大小为10，已填充槽为0、1、3、4、6，空槽为2、5、7、8、9。

  • 哈希到0：需检查0→1→2（共3次，遇空槽2终止）
  • 哈希到1：检查1→2（2次）
  • 哈希到2：直接遇空槽（1次）
  • 哈希到3：检查3→4→5（3次）
  • 哈希到4：检查4→5（2次）
  • 哈希到5：直接遇空槽（1次）
  • 哈希到6：检查6→7（2次）
  • 哈希到7：直接遇空槽（1次）
  • 哈希到8：直接遇空槽（1次）
  • 哈希到9：直接遇空槽（1次）
    总比较次数为17，平均次数为17/10=1.7次。

2. 链地址法（拉链法） #

链地址法中每个哈希槽对应一个链表，所有哈希到该槽的元素都存储在链表中。

• 终止条件：遍历完对应哈希槽的整个链表（未找到目标键且到达链表尾部）。
• 平均次数计算：
  若哈希表大小为m，总元素数n，每个槽的平均链表长度为α = n/m，则不成功搜索的平均比较次数等于α（需遍历完对应槽的整个链表，平均长度为α）。

三、答案推导的核心依据 #

所有不成功搜索的答案推导都基于三个核心点：

• 冲突解决规则：决定了搜索的路径和终止条件，是计算的基础；
• 装填因子：哈希表的填充程度直接影响冲突概率，装填因子越高，搜索次数越多；
• 哈希表的具体状态：若为给定实例题，需逐个分析每个哈希位置的搜索路径，统计总次数后取平均。

内容的提问来源于stack exchange，提问作者Hothyfa Suliman