散列表(哈希表)

📖 题目

以下关于散列表（哈希表），及其查找特性的叙述中，正确的是（57）。

📌 选项解析

A. 在散列表中进行查找时，只需要与待查找关键字及其同义词进行比较

• ❌ 错误。应该是“与散列到同一地址的关键字比较”，不是“同义词”。

B. 只要散列表的装填因子不大于 1/2，就能避免冲突

• ❌ 错误。装填因子小只能降低冲突概率，不能完全避免冲突。

C. 用线性探测法解决冲突容易产生聚集问题

• ✅ 正确。线性探测容易产生一次聚集 (Primary Clustering)。这是 线性探测法的主要缺陷。

D. 用链地址法解决冲突可确保平均查找长度为 1

• ❌ 错误。链地址法的平均查找长度大约是 1+α，取决于装填因子 α，不可能固定为 1。

同义词

👉 不同的关键字经过哈希函数计算后，得到相同的哈希地址

一次聚集

在 开放定址法（线性探测） 的哈希表里，如果多个不同的关键字因为冲突而形成了一段 连续的槽位区间，就叫做 一次聚集。

📖 哈希表-线性探测案例

📖 条件

• 表长 m = 7
• 哈希函数：H(key) = key % 7
• 冲突处理：线性探测

📌 插入过程

1. 插入 1
   • H(1)=1 → 放在槽 [1]
2. 插入 8
   • H(8)=1 → 槽 [1] 冲突 → 向后探测(线性探测)→ 槽 [2] 空 → 放 [2]
3. 插入 9
   • H(9)=2 → 槽 [2] 冲突（已被 8 占） → 向后探测(线性探测) → 槽 [3] 空 → 放 [3]

📊 插入后表状态

[1] = 1
[2] = 8
[3] = 9

📌 查找 e = 9

1. H(9)=2 → 从槽 [2] 开始查
2. 槽 [2] = 8
   • 注意：H(8)=1，和 H(9)=2 不同，所以 8 不是 9 的同义词
   • 这就是题目说的：第一个比较的可以不是同义词
3. 槽 [3] = 9 ✅ 找到目标

📊 所以：

• 同义词集合：指一群不同的关键字映射到同一个哈希地址。
• 某个关键字本身不叫自己的同义词。公式H(key1)=H(key2),key1 ≠ key2

✅ 总结

• 同义词不包括本身，而是指“和它冲突的其他关键字”。
• 但在查找时，我们通常会说“查找关键字要和它及其同义词比较”，这里的“它”是单独列出来的。

哈希地址 (Hash Address) VS 槽 (Slot)

📌 1. 哈希地址 (Hash Address)

• 定义：通过 哈希函数 计算得到的地址值。

• 公式：

  H(key)=key%mH(key) = key % mH(key)=key%m

• 这个结果就是一个 理想位置，表示关键字应该放在哪个槽位。

👉 可以理解成：哈希函数给每个关键字分配的“宿舍号”。

📌 2. 槽 (Slot)

• 定义：哈希表中的一个存储位置，编号从 0 到 m-1。
• 槽是物理存在的存储单元，用来存放元素。
• 数组形式表示：

  table[0], table[1], ..., table[m-1]
  

📌 3. 二者关系

• 哈希地址 = 初始槽号（哈希函数算出来的下标）。
• 如果这个槽空，就放进去。
• 如果冲突了（槽被占），就要根据冲突处理方法（线性探测、二次探测、链地址等）找新的槽。

线性探测、二次探测、链地址

📖 例子条件

• 表长 m = 7，槽位编号 [0..6]
• 哈希函数：H(key) = key % 7
• 要插入关键字：7, 14, 21（它们哈希值都 = 0，肯定冲突）

1️⃣ 线性探测 (Linear Probing)

👉 冲突时，依次往后找下一个空槽（步长=1）。

插入过程：

• 7 → H(7)=0 → 放 [0]
• 14 → H(14)=0 → [0] 被占 → 往后探测 → [1] 空 → 放 [1]
• 21 → H(21)=0 → [0] 占 → [1] 占 → [2] 空 → 放 [2]

表状态：

[0]=7, [1]=14, [2]=21

⚠️ 问题：容易形成 一次聚集 (Primary Clustering)，冲突的元素连成片。

2️⃣ 二次探测 (Quadratic Probing)

👉 冲突时，探测距离按 1², 2², 3²... 增长。

插入过程：

• 7 → H(7)=0 → 放 [0]
• 14 → H(14)=0 → [0] 占 → 探测 1²=1 → [1] 空 → 放 [1]
• 21 → H(21)=0 → [0] 占 → 探测 1²=1 → [1] 占 → 探测 2²=4 → [4] 空 → 放 [4]

表状态：

[0]=7, [1]=14, [4]=21

⚠️ 问题：避免了一次聚集，但可能出现 二次聚集 (Secondary Clustering) —— 同一哈希地址的冲突元素探测路径相同。

3️⃣ 链地址法 (Chaining)

👉 每个槽挂一个链表，冲突的元素直接加到链表里。

插入过程：

• 7 → H(7)=0 → 放 [0] 链表
• 14 → H(14)=0 → 插入 [0] 链表
• 21 → H(21)=0 → 插入 [0] 链表

表状态：

[0] → 7 → 14 → 21
[1] → -
[2] → -
...

⚠️ 特点：不存在一次聚集/二次聚集，装填因子 α 可以大于 1，但链表会增加内存开销。 📊 总结对比

✅ 小口诀：

• 线性探测易一次聚集
• 二次探测避一次聚集但有二次聚集
• 链地址法挂链表，冲突都能存