散列表 (Hash Table) 查找

散列表（哈希表）查找 —— 以 2010 统考真题为锚

📌 核心概念

一句话定义：散列表通过散列函数将关键字映射到表的一个位置，配合冲突处理策略实现近乎 $O(1)$ 的查找。 大白话：就像你根据书名首字母去书架找书，不用一排排翻，直接走到对应字母区。如果那格被占了，就按规则往旁边找空位。

---

⚠️ 极其容易混淆的点

1. 装填因子 $\alpha =n/m$ 是用来求表长的，不是用来直接算 ASL 的。题目给了 $\alpha$ 一定要先算表长 $m$。
2. 查找不成功的 ASL，分母是哈希函数值域大小（即可能的地址个数），不是表长 $m$。这是每年很多人踩的坑！
3. 探测次数计数方法：线性探测时，第1次比较就算1次。例如直接命中（无冲突）算1次，探测到第2个位置才命中算2次，依次类推。

---

⚠️ 注意事项（操作层面的坑）

1. 看到“装填因子”第一反应不是算 ASL，而是算表长

• 错误示范：看到 $\alpha =0.7$，心想“哦，装填因子，跟平均查找长度有关”，然后直接用关键字个数 7 开始画表。
• 正确做法：$m=n/\alpha =7/0.7=10$，表长是 10，不是 7。表长算错，整题报废。

2. 线性探测时，探测次数怎么数？

• 插入时：第 1 次看的就是 1 次，直接命中也是 1 次，不是 0 次。
• 失败时：从起始地址开始数，一直数到第一个空位，空位本身也算一次（因为你看了它才知道是空的）。
  • 例如：从地址 5 开始，探测序列为 $5\to 6\to 7\to 8\to 9(\text{空})$，探测次数 = 5 次，不是 4 次。

3. 失败 ASL 的地址范围不是 $0\sim 9$，而是 $0\sim 6$

• 因为 $H(\text{key})=(\text{key}\times 3)\mathrm{mod}7$，结果只可能是 $0,1,2,3,4,5,6$。
• 错误示范：对 $0\sim 9$ 共 10 个地址分别算失败探测次数，然后除以 10。
• 正确做法：只对 $0\sim 6$ 这 7 个地址算，除以 7。
• 线性探测 → 从入口开始，如果位置被占了，就往后挪一位（下标+1），直到遇到空位 ∧ 为止。
  每看一个位置，算 1 次探测（空位也算一次，因为你要看到它才知道它是空的）。
• 一句话记死：散列函数 $\mathrm{mod}$ 几，失败 ASL 分母就是几！

4. 成功 ASL 的分母永远是有几个关键字，就是几

• 不管表长多少，成功 ASL 分母 = 关键字个数 $n$（本题即为 7）。

5. 画表时，空位必须明确标出

• 画表时空位用 $\wedge$ 或“空”清晰标出。失败 ASL 的终止条件依赖“遇到第一个空位”，如果表没画全或空位没标，失败探测次数必然数错。

---

🌰 通俗例子

生活化比喻（秒懂原理）

想象一个快餐厅的取餐窗口：

1. 你点餐后拿到一张小票，上面有个取餐号（哈希地址）。
2. 如果那个窗口没人（无冲突），你直接取走。
3. 如果窗口有人在等（冲突），服务员让你往旁边窗口挪（线性探测），挨个窗口问，直到找到你的餐。
4. 查找失败：你走到一个窗口，发现是空窗口（没人也没餐），你就知道“我的餐不在这儿，而且后面的窗口也不用找了”。

学科内典型例子（本题核心数据表）

构造过程示例表：

关键字	$H(\text{key})$	冲突过程	最终位置	成功探测次数
18	5	$5(\text{有 }11)\to 6(\text{有 }30)\to 7(\text{空})$	7	3
9	6	$6(\text{有 }30)\to 7(\text{有 }18)\to 8(\text{空})$	8	3
140	0	$0(\text{有 }7)\to 1(\text{空})$	1	2

失败探测示例（以地址 5 为例）：

• 从地址 5 开始：$5(\text{有 }11)\to 6(\text{有 }30)\to 7(\text{有 }18)\to 8(\text{有 }9)\to 9(\text{空})$，共探测 5 次。
• 总结：
  • 成功 ASL = 每个元素插入时探测次数之和 / 元素个数 $n$（看“插入过程”）
  • 失败 ASL = 每个可能哈希地址到第一个空位的探测次数之和 / 地址个数（看“空位位置”）

---

🛠 怎么用（解题步骤）

• 适用信号词：散列存储、哈希表、装填因子、线性探测 / 链地址法、平均查找长度
• 解题步骤：
  1. 算表长：看到装填因子 $\alpha$，立刻执行 $m=n/\alpha$。（第一步，千万别漏！）
  2. 画表：
     • 逐个关键字算 $H(\text{key})$，冲突则按题目指定的方法找空位。
     • 每个元素插入时，顺手记录探测次数（后续算成功 ASL 要用）。
     • 表中空位必须标出，不能留白。
  3. 算成功 ASL：
     • 分母 = 关键字个数 $n$。
     • 分子 = 插入时所有探测次数之和。
  4. 算失败 ASL：
     • 确定散列函数的值域范围（即所有可能的哈希地址），不是表长 $m$。
     • 对每个可能地址，按冲突处理方法向后探测，直到遇到第一个空位，记录探测次数。
     • 分母 = 值域大小，分子 = 所有地址的失败探测次数之和。

---

⚡ 快速记忆

• 口诀：

  “$\alpha$ 先算表长，成功看插入，失败探到空，分母看值域。”

• 核心关键词：
  • 表长 ($\alpha \to m$)
  • 探测次数（插入次数 / 到空位次数）
  • 空位（失败探测的终点）
  • 值域（失败 ASL 的分母）

---

🔗 知识关联

• 线性探测再散列：解决冲突的一种方式，简单但会产生“二次聚集（堆积）”现象。
• 链地址法：另一种冲突处理方式，失败 ASL 的计算逻辑完全不同（每个地址下链表长度之和 / 地址数）。
• 平均查找长度 ASL：评价所有查找方法的统一指标，顺序查找、折半查找、散列表查找都用它来衡量。

---

✅ 自测题

自测题 1

设散列表长 $m=11$，散列函数 $H(\text{key})=\text{key}\mathrm{mod}7$，用线性探测法处理冲突。若某关键字插入时探测了 4 次才找到空位，则该关键字的成功查找需要比较多少次？

点击展开答案

答案：4 次。 解析：插入时探测的次数 = 查找成功时比较的次数（因为插入过程就是先查找空位的过程），两者完全相等。

自测题 2

上题中，查找不成功的 ASL 分母应该是多少？

点击展开答案

答案：7。 解析：因为 $\text{key}\mathrm{mod}7$ 的结果只有 $0\sim 6$ 共 7 种，散列函数值域大小为 7。分母是值域大小，而不是表长 11。