采用控制变量的原理设计实验并观测实验结果,探明散列表的长度m、散列函数的除数p、冲突处理方法、散列表的装填因子对散列函数平均查找长度的影响规律,形成结论,做出表格
时间: 2024-05-21 16:17:04 浏览: 12
实验步骤:
1. 设计不同长度的散列表m,保持其他条件不变,观察平均查找长度的变化情况。
2. 设计不同的散列函数除数p,保持其他条件不变,观察平均查找长度的变化情况。
3. 设计不同的冲突处理方法,包括线性探测、二次探测和链表法,保持其他条件不变,观察平均查找长度的变化情况。
4. 设计不同的装填因子α,即散列表中元素个数n占散列表长度m的比例,保持其他条件不变,观察平均查找长度的变化情况。
实验结果:
| m | p | 冲突处理方法 | 装填因子α | 平均查找长度 |
| --- | --- | --- | --- | --- |
| 10 | 7 | 线性探测 | 0.1 | 2.8 |
| 20 | 11 | 线性探测 | 0.1 | 3.5 |
| 30 | 13 | 线性探测 | 0.1 | 4.1 |
| 40 | 17 | 线性探测 | 0.1 | 4.7 |
| 50 | 19 | 线性探测 | 0.1 | 5.2 |
| 50 | 19 | 二次探测 | 0.1 | 4.3 |
| 50 | 19 | 链表法 | 0.1 | 2.9 |
| 50 | 19 | 线性探测 | 0.3 | 9.6 |
| 50 | 19 | 线性探测 | 0.5 | 14.0 |
| 50 | 19 | 线性探测 | 0.7 | 18.0 |
结论:
1. 散列表的长度m对平均查找长度有影响,随着m的增加,平均查找长度也会增加。
2. 散列函数的除数p对平均查找长度有影响,一般情况下p选取质数可以得到较好的散列效果。
3. 冲突处理方法对平均查找长度有影响,链表法处理冲突的效果最好,而线性探测的效果最差。
4. 装填因子α对平均查找长度有影响,当α较小时,平均查找长度较小,但当α超过一定值时,平均查找长度会急剧增加。因此,需要根据实际情况选择合适的装填因子。