四、算法分析与实验结果
1.本算法的创新之处在于通过HASH函数可将被检索的数据X直接位置定位到相应的“块”（通过HASH函数转换后的地址相同的数据区间）中,再在“块”中进行二分检索。从而不再需要建立索引顺索表检索算法中的索引表,也就省去了索引顺索表检索算法中查找索引表确定所在“块”的平均检索长度。
2.此方法突破了 HASH 表的平均检索长度是装填因子(=( 表中填人的记录数 )/( 哈希表的长度 ) 的函数 , 而不是 N 的函数的弱点。
3.在理想情况下，即数据完全是均匀分布的情况下 ,本算法的平均检索长度可达理论极限值 ASL=1。即使是在最坏的情况下, 当 N 个数据经HASH 函数转换后的地址均相同，所有数据均落在同一个“块”中, 其平均检索长度 ASL 也只会下降到二分检索法时的平均检索长度。
4.本算法对于均匀分布的数据是极为有效的, 通过计算得出其平均检索长度小于1.352(N>100时)，因此检索效率很高。
5.本算法中的步骤HS1～HS12仅仅是为检索作的准备工作，相当于初始化的工作，只需在检索开始时做一次即可。
6.实验结果。为了对本检索算法的检索效率进行验证，我们用VB6.0编写了本算法以及二分检索法的程序，将二种检索算法的平均检索长度进行实际测定，实验中所用的数据由VB6.0的随时函数产生，数据的范围为（0～10000），实验结果如下表所示：
VB6.0程序二种检索算法平均检索长度对比表
我们在实验中测定平均检索长度时，通过程序对所有数据逐个检索，统计出检索完所有数据需进行比较的总次数再除以数据总数后得出。上表中当N=100时，本算法实际测定的值（1.38）与理论计算(1.352)略有误差，原因是我们用VB6.0中的随机函数产生的随机数在数据量较小时分布不一定很均匀。从表1中可以看到:当数据量稍大一些（N>100）,本算法的平均检索长度的实测结果完全与理论分析一对致，并且远小于二分检索法的平均检索长度。本算法的平均检索长度随着数据量N的增加几乎不变。
百度搜索“77cn”或“免费范文网”即可找到本站免费阅读全部范文。收藏本站方便下次阅读，免费范文网，提供经典小说计算机一种高效率的信息检索算法(2)在线全文阅读。
