使用链地址法（拉链法）解决哈希冲突时，每个哈希地址对应一个链表，所有哈希到该地址的关键字按链表形式存储-洪萨配资

使用链地址法（拉链法）解决哈希冲突时，每个哈希地址对应一个链表，所有哈希到该地址的关键字按链表形式存储。下面以题目给出的参数进行详细构造和分析。

1. 链地址法构造哈希表

逐个计算哈希地址并插入：

最终哈希表结构如下（链表顺序为插入顺序）：

地址 0: [33] 地址 1: [34] → [12] 地址 2: [13] 地址 3: [47] → [3] 地址 4: 空 地址 5: [38] → [27] 地址 6: 空 地址 7: 空 地址 8: [52] 地址 9: 空 地址10: 空

2. 成功查找的平均查找长度（ASL）

成功查找：对每个元素查找时，需比较的次数等于其在链表中的位置（从头开始比较）。

统计：

总比较次数 = 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）

我们逐个插入，并在线性探测下解决冲突。

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	1	2	3	4	5	6	7	8	9	10
内容	33	34	13	47	12	38	27	3	52	空	空

每次查找从初始地址开始探测，直到找到目标元素，比较次数 = 探测次数 + 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