编号： 时间：2024年x月x日 书山有路勤为径，学海无涯苦作舟 页码：第1页 共4页 信息检索分析论文
一、HASH函数的构造
桶排序法，先把被排数据所分布的区间[Dmin,Dmax](在这里Dmax,Dmin分别为被排数据的最大，最小值)划分成N个大小相等的子区间，称子为“桶”，然后将N个数据根据其大小分配入相应的“桶”内（桶[1]，桶[2]，…，桶[N]）。借签桶排序中将数据根据其大小分配入相应“桶”的思想，我们在检索时将已排好序的数据也根据其大小将其分配入相应的“桶”内，然后再在“桶”内进行二分检索。假设按升序排列的N个数据已存放在data数组的元素data[0]～data[N-1]中，构造一个HASH函数为:
（式中Dmax=data[N-1],Dmin=data[0],N为数据个数） 二、基于HASH函数的二分检索算法HS 算法HS使用二个数组，data数组的元素data[0]～data[N-1]中存放按升序排列的N个数据,address数组的元素address[1]～address[N]中用来存贮经HASH函数转换后得到相同地址的数据个数。
算法HS HS1[清address数组]将ddress[1]～address[N]都置0 HS2[Dmax中
置
最
大
值
、
Dmin
中
置
最
小
值]Dmax←data[N-1],Dmin←data[0]
HS3[i置初始值]i←0
HS4[求数据data[i]的HASH变换后的地址ad]ad
HS5[地址“碰撞”记数器address[ad]加1]address[ad]←address[ad]+1
第 1 页 共 4 页
编号： 时间：2024年x月x日 书山有路勤为径，学海无涯苦作舟 页码：第2页 共4页 HS6[修改i]i←i+1
HS7[比较i与N-1]若i HS8[address[0]置初值1]address[0]←1 HS9[j置初始值]j←1
HS10[求地址发生“碰撞”的数据在DATA数组中的首地址]address[j]=address[j]+address[j-1]
HS11[修改j]j←j+1
HS12[比较j与N]若j HS13[输入一个被检索的数据X] HS14[对被检索数据X用HASH函数得地址ad] HS15[
确
定“
块”
的下界
low,上
界
high
的
值]low←address[ad-1],high←address[ad]-1
HS16[在“块”内进行二分检索]在给定的下界与上界之间进行二分检索，若找到，则返“检索成功”信息，否则返加回“检索失败”信息。
HS17[本算法结束] 三、平均检索长度的分析
在本检索算法中，首先将被检索数据X经HASH函数转换出一个地址，根据这个地址将被检索的数据直接定位到相应的“块”中，然后在“块”中进行二分检索。因此通过对所有“块”内二分检索法的平均检索长度的计算就可求出本算法的平均检索长度。二分检索法的平均检索长度为：
下面我们来求本算法的平均检索长度。假设在N个数据均匀分布的情况下，经过本检索算法中HASH函数转换，每一个地址出现的概率相同，都等于1/N，因此，有m个数据转换得到相同地址的概率为：
第 2 页 共 4 页
编号： 时间：2024年x月x日 书山有路勤为径，学海无涯苦作舟 页码：第3页 共4页 (m=1,2,…，N)
参考文献[1]的附录中已证明：（1） 所以本检索算法的平均检索长度为（2）
由上式(1)和式(2)两个公式即可求得本算法的平均检索长度，其平均检索长度小于1.352(当N>100时)。
四、算法分析与实验结果
1.本算法的创新之处在于通过HASH函数可将被检索的数据X直接位置定位到相应的“块”（通过HASH函数转换后的地址相同的数据区间）中,再在“块”中进行二分检索。从而不再需要建立索引顺索表检索算法中的索引表,也就省去了索引顺索表检索算法中查找索引表确定所在“块”的平均检索长度。
2.此方法突破了HASH表的平均检索长度是装填因子(=(表中填人的记录数)/(哈希表的长度)的函数,而不是N的函数的弱点。
3.在理想情况下，即数据完全是均匀分布的情况下,本算法的平均检索长度可达理论极限值ASL=1。即使是在最坏的情况下,当N个数据经HASH函数转换后的地址均相同，所有数据均落在同一个“块”中,其平均检索长度ASL也只会下降到二分检索法时的平均检索长度。
4.本算法对于均匀分布的数据是极为有效的,通过计算得出其平均检索长度小于1.352(N>100时)，因此检索效率很高。
5.本算法中的步骤HS1～HS12仅仅是为检索作的准备工作，相当于初始化的工作，只需在检索开始时做一次即可。
6.实验结果。为了对本检索算法的检索效率进行验证，我们用VB6.0
第 3 页 共 4 页
信息检索分析论文
