编程实验篇--线性探测哈希表

线性探测哈希表性能测试实验报告

1. 实验目的

编程实现线性探测哈希表。
编程测试线性探测哈希表。
了解线性探测哈希表的性能特征，并运行程序进行验证。

2. 实验背景与理论基础

哈希表是一种高效的数据结构，用于实现符号表（Symbol Table），支持快速的插入、查找和删除操作。当不同的键哈希到同一个地址时，会发生冲突。线性探测（Linear Probing）是一种常见的开放寻址（Open Addressing）冲突解决策略，它通过探测当前位置的下一个连续槽位来寻找空闲位置。

线性探测的性能分析主要关注查找操作所需的平均探测次数。根据教材，当冲突通过线性探测解决时，哈希表大小为 $M$ 且包含 $\alpha M$ 个键时，其平均探测次数有以下理论近似值（Property 14.3）：

查找失败 (misses) 的平均探测次数：
$\frac{1}{2}\left(1 + \frac{1}{(1-\alpha)^2}\right)$

其中， $\alpha = N/M$ 是哈希表的负载因子。

此外，查找失败的平均成本也可以通过分析哈希表中形成的聚簇（clusters）来计算：
$\text{查找失败的平均成本} = 1+\frac{N}{2M}+\frac{\sum_i^kt_i^2}{2M}$
其中， $t_i$ 是插入过程中形成的第 $i$ 个聚簇的长度，总共有 $k$ 个聚簇。

本次实验将重点关注查找失败的平均成本。

根据实验设计，我们将 $N /2$ 个随机整数插入到大小为 $N$ 的哈希表中，因此负载因子 $\alpha = (N/2) / N = 0.5$ 。代入查找失败的理论公式，可计算出在此负载因子下的理论平均成本：
$\text{理论平均成本} = \frac{1}{2}\left(1 + \frac{1}{(1-0.5)^2}\right)= 2.5$
因此，对于本次实验中的所有测试用例，理论上的查找失败平均成本应为 2.5 次探测。

3. 实验设计与实现

实验任务： 编写程序实现 Exercise 14.28，即插入 $N /2$ 个随机整数到大小为 $N$ 的哈希表中，并计算查找失败的平均成本。

Exercise1428

程序实现

哈希表结构： 使用数组 st 作为哈希表，存储 Item 指针。Item 包含 Key 和 Value。
初始化 (STinit)： 根据传入的最大元素数量 max，将哈希表大小 M 设置为 2 * max。由于实验要求插入 $N /2$ 个元素到大小为 $N$ 的表，所以 M 在这里对应练习题中的 $N$ 。
哈希函数 (hash)： 采用简单的整数哈希函数 (11 * x) % M。
插入 (STinsert)： 采用线性探测解决冲突。如果初始哈希位置被占用，则向右（索引递增）探测直到找到空槽位。
簇分析 (analyze_clusters)：
- 遍历哈希表，识别所有形成的聚簇。一个聚簇被定义为连续的被占用槽位序列。
- 计算每个聚簇的长度 $t_i$ 。
- 累加所有聚簇长度的平方和 $\sum t_i^2$ 。
- 根据公式 $1+\frac{N}{2M}+\frac{\sum_i^kt_i^2}{2M}$ 计算出基于簇长度的查找失败平均成本（即实验值 average_cost）。
- 同时，根据负载因子 $\alpha = N/M$ 和 Property 14.3 的公式计算理论平均成本（theory_cost）。
- 打印实验值和理论值以便对比。
测试用例： 设计了四组测试，分别对应 $N=10^{3}, 10^{4}, 10^{5}, 10^{6}$ 。在每个测试中，向表中插入 $N /2$ 个随机整数。
- test_insert_1000(): M=1000, 插入 500 个随机数。
- test_insert_10000(): M=10000, 插入 5000 个随机数。
- test_insert_100000(): M=100000, 插入 50000 个随机数。
- test_insert_1000000(): M=1000000, 插入 500000 个随机数。
随机数生成： 使用 srand(time(NULL)) 进行随机数播种，以确保每次程序运行生成不同的随机序列。

4. 实验结果

程序运行后，得到以下输出：

Table(M=1000):the average cost of unsuccessful search in that table is 1.558000, theory cost: 2.500000
Table(M=10000):the average cost of unsuccessful search in that table is 2.488200, theory cost: 2.500000
Table(M=100000):the average cost of unsuccessful search in that table is 2.481630, theory cost: 2.500000
Table(M=1000000):the average cost of unsuccessful search in that table is 2.503940, theory cost: 2.500000

5. 结果分析

这些结果清晰地展示了线性探测哈希表在不同规模下，查找失败平均成本的实验值与理论值之间的关系。

M=1000 (表大小为 1000，插入 500 个元素)：
- 实验平均成本为 1.558000，而理论平均成本为 2.500000。
- 分析： 在这种较小规模的哈希表中，实验结果与理论值存在较明显的偏差。这是因为理论平均值是基于大量随机插入的统计结果，而单次运行（尤其在数据量较小的情况下）可能因随机数的具体序列偶然地形成了比平均情况更少或更短的簇，从而导致实际观察到的探测次数低于理论预测。这反映了小样本量下的统计波动性。
M=10000 (表大小为 10000，插入 5000 个元素)：
- 实验平均成本为 2.488200，理论平均成本为 2.500000。
- 分析： 实验结果与理论值已非常接近。这表明随着哈希表规模的增大（以及插入元素数量的增加），线性探测在随机插入下的实际行为开始向其统计平均值收敛。随机性带来的局部波动效应被更大量的数据所平均。
M=100000 (表大小为 100000，插入 50000 个元素)：
- 实验平均成本为 2.481630，理论平均成本为 2.500000。
- 分析： 实验结果继续保持与理论值的高度吻合，进一步证实了这种收敛性。
M=1000000 (表大小为 1000000，插入 500000 个元素)：
- 实验平均成本为 2.503940，理论平均成本为 2.500000。
- 分析： 实验结果与理论值几乎完全一致，仅存在微小的正常波动。这完美地展示了当数据量足够大时，线性探测在半满情况下的性能是如何精确符合理论模型的。

6. 结论

该程序 Exercise1428 的运行结果有力地验证了以下几点：

理论公式的有效性： 教材中关于线性探测查找失败平均成本的理论公式 (Property 14.3) 在实践中是准确的预测器。通过实验结果与理论值的对比，可以清晰地看到二者的高度吻合，尤其是在大规模数据量下。
规模效应： 随着哈希表规模的增大，线性探测在随机插入条件下的实际性能会越来越接近其理论平均值。小规模表的结果可能因随机性而有较大波动，但随着 $N$ 的增长，这种波动逐渐减小。
线性探测的特性： 即使在负载因子为 $0.5$ （即哈希表半满）这种相对较低的情况下，查找失败的平均成本也不是理想的 $1$ 次探测，而是大约 $2.5$ 次。这反映了线性探测固有的“初级聚簇”（primary clustering）问题：即使表不满，连续的占用槽位也会导致查找路径变长，从而产生额外的探测成本。这也解释了为什么在线性探测中，通常建议将负载因子保持在更低的水平（例如，远小于 0.5），以避免性能随着表接近满而急剧下降。