文档介绍：[ 摘要] 构造一个新的 HASH 函数,结合索引顺序表和二分检索法的思想,提出了一种高效率的信息检索算法,通过理论计算和实验证明此算法的平均检索长度小于 (N>100) 。[ 关键词] HASH 函数检索平均检索长度信息时代如何提高信息检索的效率一直是信息管理人员关注的问题。提高信息检索效率的有效途径是构建被检索信息与其存放地址之间的关系(HASH) 。到目前为止,构造 HASH 函数的方法很多, 常用的方法有: 直接定址法、数字分析法、平方取中法、折叠法、除留余数法、随机数法等转换算法。但是不论哪种算法都会出现“碰撞”现象, 因而就限制了上述方法的普遍使用。为了解决或减少“碰撞”, 我们把 HASH 的思想和索引顺序表检索的思想, 以及二分检索法的思想结合起来提出一种基于 HASH 表的二分检索法,通过理论分析和实验证明,该算法检索效率极高。一、 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] ← addre