使用链地址法（拉链法）解决哈希冲突时，每个哈希地址对应一个链表，所有哈希到该地址的关键字按链表形式存储。下面以题目给出的参数进行详细构造和分析。
1. 链地址法构造哈希表
- 哈希表长度：11（地址从 0 到 10）
- 哈希函数：
H(key) = key mod 11 - 关键字序列：47, 34, 13, 12, 52, 38, 33, 27, 3
逐个计算哈希地址并插入：
| key | H(key) = key mod 11 | 插入位置（链表） |
|---|---|---|
| 47 | 47 mod 11 = 3 | 地址 3 |
| 34 | 34 mod 11 = 1 | 地址 1 |
| 13 | 13 mod 11 = 2 | 地址 2 |
| 12 | 12 mod 11 = 1 | 地址 1 → 冲突，链入 34 后 |
| 52 | 52 mod 11 = 8 | 地址 8 |
| 38 | 38 mod 11 = 5 | 地址 5 |
| 33 | 33 mod 11 = 0 | 地址 0 |
| 27 | 27 mod 11 = 5 | 地址 5 → 冲突，链入 38 后 |
| 3 | 3 mod 11 = 3 | 地址 3 → 冲突，链入 47 后 |
最终哈希表结构如下（链表顺序为插入顺序）：
地址 0: [33] 地址 1: [34] → [12] 地址 2: [13] 地址 3: [47] → [3] 地址 4: 空 地址 5: [38] → [27] 地址 6: 空 地址 7: 空 地址 8: [52] 地址 9: 空 地址10: 空2. 成功查找的平均查找长度（ASL）
成功查找：对每个元素查找时，需比较的次数等于其在链表中的位置（从头开始比较）。
- 地址 0: 33 → 1 次比较
- 地址 1: 34（第1个）→ 1 次，12（第2个）→ 2 次
- 地址 2: 13 → 1 次
- 地址 3: 47（第1个）→ 1 次，3（第2个）→ 2 次
- 地址 5: 38（第1个）→ 1 次，27（第2个）→ 2 次
- 地址 8: 52 → 1 次
统计：
- 1 次比较的元素：33, 34, 13, 47, 38, 52 → 共 6 个
- 2 次比较的元素：12, 27, 3 → 共 3 个
总比较次数 = 6×1 + 3×2 = 6 + 6 = 12
元素总数 = 9
因此，
ASL = 12 / 9 ≈1.33
注：原题中写 ASL ≈ 1.34 可能是四舍五入误差，正确值为 1.33（即 4/3）
3. 其他哈希冲突解决方法
再哈希法（双重哈希）
冲突时使用另一个哈希函数重新计算地址，如H_i = (H1(key) + i×H2(key)) mod table_size，直到找到空位。
✅ 优点：减少聚集现象（尤其是线性探测导致的“堆积”）
❌ 缺点：计算开销大，需多个哈希函数公共溢出区法
设主表和一个溢出表（如数组或链表），主表存放无冲突元素，冲突元素统一放入溢出区。
查找时先查主表，若冲突则查溢出区。
✅ 优点：结构清晰，便于管理
❌ 缺点：溢出区可能变慢，查找效率下降
4. 哈希表的查找特点
- 必须使用与插入时相同的哈希函数和冲突处理策略来定位地址。
- 实际查找过程中仍需进行关键字比较（因为哈希值相同不一定关键字相同）。
- 查找效率用平均查找长度（ASL）衡量。
- 影响因素：
- 哈希函数的好坏（是否均匀分布）
- 冲突处理方法（链地址 vs 开放寻址）
- 装填因子 α = 元素个数 / 表长（α 越小，冲突越少，性能越好）
使用开放地址法中的线性探测（Linear Probing）处理哈希冲突时，当发生冲突，会顺序向后查找下一个空闲位置，直到找到空槽为止。其基本公式为：
H_i(key) = (H(key) + i) mod m
其中：
H(key) = key mod m是初始哈希值i = 0, 1, 2, ..., m-1是探测次数m是哈希表长度（本例中为 11）
📌 参数回顾：
- 哈希表长度：11（地址 0 ~ 10）
- 哈希函数：
H(key) = key mod 11 - 关键字序列：47, 34, 13, 12, 52, 38, 33, 27, 3
我们逐个插入，并在线性探测下解决冲突。
🔧 插入过程详解：
| key | H(key) | 探测过程 | 最终位置 | 说明 |
|---|---|---|---|---|
| 47 | 47 mod 11 = 3 | 地址 3 空 → 插入 | 3 | 成功 |
| 34 | 34 mod 11 = 1 | 地址 1 空 → 插入 | 1 | 成功 |
| 13 | 13 mod 11 = 2 | 地址 2 空 → 插入 | 2 | 成功 |
| 12 | 12 mod 11 = 1 | 地址 1 已被占 → 检查 2 → 被占 → 检查 3 → 被占 → 检查 4 | 4 | 探测 i=3: (1+3)=4，空，插入 |
| 52 | 52 mod 11 = 8 | 地址 8 空 → 插入 | 8 | 成功 |
| 38 | 38 mod 11 = 5 | 地址 5 空 → 插入 | 5 | 成功 |
| 33 | 33 mod 11 = 0 | 地址 0 空 → 插入 | 0 | 成功 |
| 27 | 27 mod 11 = 5 | 地址 5 占 → 6 空？是 → 插入 | 6 | 探测 i=1: (5+1)=6 |
| 3 | 3 mod 11 = 3 | 地址 3 占 → 4 占（12）→ 5 占 → 6 占（27）→ 7 空 → 插入 | 7 | 探测 i=4: (3+4)=7 |
✅ 构造完成后的哈希表（索引 0~10）：
| 地址 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| 内容 | 33 | 34 | 13 | 47 | 12 | 38 | 27 | 3 | 52 | 空 | 空 |
📊 成功查找的平均查找长度（ASL）
每次查找从初始地址开始探测，直到找到目标元素，比较次数 = 探测次数 + 1（每探一次算一次比较）
| key | 初始地址 | 实际位置 | 探测步数（i） | 比较次数 |
|---|---|---|---|---|
| 47 | 3 | 3 | 0 | 1 |
| 34 | 1 | 1 | 0 | 1 |
| 13 | 2 | 2 | 0 | 1 |
| 12 | 1 | 4 | 从1→2→3→4，第3步成功 | 4（检查1,2,3,4） |
| 52 | 8 | 8 | 0 | 1 |
| 38 | 5 | 5 | 0 | 1 |
| 33 | 0 | 0 | 0 | 1 |
| 27 | 5 | 6 | 第1次探测成功（5→6） | 2 |
| 3 | 3 | 7 | 从3→4→5→6→7，共4步 | 5 |
注意：线性探测中，“比较次数”是指在查找路径上逐个比对关键字的次数。
总比较次数 = 1+1+1+4+1+1+1+2+5 =17
元素个数 = 9
👉 ASL = 17 / 9 ≈1.89
⚠️ 特点与问题
- 优点：实现简单，缓存友好（连续访问内存）
- 缺点：
- 容易产生“聚集现象”（如地址1~4连续被占，形成“主集团”）
- 插入和查找效率随装填因子升高急剧下降
- 删除操作复杂（不能直接清空，需标记为“已删除”）
