基于哈希函数的查找算法设计及性能分析

贾 丹，张 兴

(辽宁工业大学电子与信息工程学院，辽宁锦州121001)

查找是计算机程序设计中重要的操作，查找操作指的是如何根据给定的记录关键字的值，在查找表中查找是否有和给定值相等的记录存在．如果存在，则查找成功;否则，查找失败［1］．查找操作是非常常见的操作，广泛用于管理系统的设计及检索的实现．本文提出了基于哈希函数的查找算法，不需要进行比较，直接定位到要查找的记录，从而提高查找效率．

1 传统的查找算法

1．1 数据结构的定义

以图书馆中图书信息的查询为例，图书数据的存储结构定义如下:

Typedef struct

{char isbn［20］;//图书的 ISBN 号

char name［40］;//图书名字

char author［20］;//作者姓名

char press［20］;//出版社名字

float price;//价格

}book［］;

1．2 顺序查找算法设计及性能分析

顺序查找是最简单的查找方法，其对应的类C算法如下:

int sequen(book a，char number［20］)

{//在图书信息表中顺序查找ISBN号为number的图书，如果查找成功，返回其位置，否则，返回0值．

a［0］．isbn=number;//查找的关键字放到监督哨位置

i=n;//n代表图书表的长度

while(a［i］．isbn!=number)

－－i;

Return(i);

}

在该算法中，－－i这条语句是在分析算法时间复杂度时选择的源操作语句，该语句重复频度最大值为n，所以该算法的时间复杂度T(n)=O(n)，也就是随着问题规模n的增长，算法执行时间的增长率和n的增长率相同［2］．由上述分析可见，顺序查找算法简单，适用范围广，但是查找效率低．

1．3 折半查找算法设计及性能分析

如果图书信息是按ISBN号有序排列的，可以选择另外一种高效的查找算法——折半查找，其对应的类C算法设计如下:

int binary(book a，char number［20］)

{//在图书信息表中折半查找ISBN号为number的图书，如果查找成功，返回其位置，否则，返回0值．low=1;hig=n;

while(low＜=hig)

{

mid=(low+hig)/2;

if(number==a［mid］．isbn)

return(mid);

else if(number＞a［mid］．isbn)

low=mid+1;

else hig=mid－1;

}

return(0);

}

折半查找算法中，单纯通过选择源操作语句频度来分析算法的时间复杂度是比较困难的，可以通过折半查找判定树来推导算法的时间复杂度．如图1所示，对于长度为n的有序表，折半查找在查找成功时和给定值进行比较的关键字个数不会超过判定树的深度，折半查找判定树的深度为，因此，可以得到该算法的时间复杂度

2 基于哈希函数的查找算法

在上述传统的查找算法中，无论是顺序查找还是折半查找，均需要待查找的关键字和查找表中记录的关键字进行比较来实现，并以比较次数来衡量算法的效率．哈希函数则是在记录的关键字和存储位置之间建立一个对应关系H(key)，key是关键字，H(key)是记录的存储位置，当进行查找操作时，只需要根据输入的关键字的值，通过哈希函数计算出存储位置，而不需要进行关键字的比较，从而提高查找效率．从理论上来说，比较次数为0，但是由于有冲突的存在，还达不到ASL=0的理想状态，但相对于传统的查找方法，查找效率非常高．

2．1 哈希函数的选择

哈希函数的设定有很多方法，例如，直接定址法、折叠法、数字分析法、平方取中法、随机数法、除留余数法［4］等，经过综合分析图书信息中数据的特点，本文选择数字分析法和折叠法的一种结合方法来作为哈希函数．

通常ISBN号是13位的十进制数字，假如有800条图书记录，则哈希表的表长为1000就可以了，则可取3位十进制数组成哈希地址．如何选取3位并使冲突尽可能地减少呢?以下是一组图书的ISBN号:

9787560625300

9787302314158

9787115333735

．．．．

9787302023685

9787302086567

9787115069719

首先采用数字分析法分析数字特点，前4位是9787的概率较高，第5、6、7位是115或302的概率较高，而第8～13位分布比较均匀，可以选择其中任意3位做为哈希地址．为了进一步减少冲突，综合折叠法的思想，取第8～10位和第11～13位之和然后舍去进位位作为哈希地址．哈希函数选定后，根据这个思想建立哈希表，并在哈希表的基础上进行查找［5］．

2．2 哈希函数的设计

哈希函数的构造算法如下:

Int Hash(char a［］)

{//a为图书的ISBN号，输入a值，经过转换和运算，输出其存储位置

char str1［4］ ={""};

strncat(str1，a+7，3);//取出 ISBN 号中的第 8～10位

char str2［4］ ={""};

strncat(str2，a+10，3);//取出 ISBN 号中的第 11～13位

int s1=atoi(str1);//将第8～10位转换成为整数

int s2=atoi(str2);//将第11～13位转换成为整数

return(s1+s2)%1000;//取二者之和然后舍去进位位作为哈希地址

}

2．3 哈希冲突处理

哈希冲突指的是，对于不同的关键字，得到相同的哈希地址．即key1!=key2，Hash(key1)=Hash(key2)．比如，对于不同的图书，ISBN号分别是9787723458736和9787734069125，采用上述的哈希函数，得到相同的哈希地址194．冲突是不可能完全避免的，只能尽可能地减少冲突，当有冲突发生的时候，要选择合适的方法处理冲突．处理冲突的方法有很多，常见的有开放定址法、链地址法、再哈希法和建立一个公共溢出区等方法．由于本文设计的哈希函数分布比较均匀，可以选择比较简单的开放定址法中的线性探测再散列来处理冲突，具体的公式为:

式中，Hi代表经过i次冲突后得到的下一个哈希地址，Hash(key)代表哈希函数的值，di是一个增量序列［6］，在线性探测再散列中，di=i，m代表哈希表的表长．

当设计好哈希函数，选择好相应的处理冲突的方法后，就可以将一组记录根据ISBN的值将其映像到一个有限的连续的地址区间上，并用关键字在地址区间中的“像”作为记录在表中的存储位置，此时用于存储记录的表就称之为哈希表．例如，根据上述的哈希函数，笔者将ISBN为9787560625300的记录存储在表中的第925位置上．

2．4 哈希查找算法的设计

int hashsearch(book a，char number［20］)

{//在图书信息哈希表中按上述设计的哈希函数和处理冲突的方法查找ISBN号为number的图书，如果查找成功，返回其位置，否则，返回0值．

k=Hash(number)//首先求出ISBN号为number的哈希函数的值，即哈希地址

i=1;

while(a［k］．isbn!=number＆＆(a［k］．isbn!=null)//在哈希地址中未找到查找记录且未找到空记录

{k=(Hash(key)+di)%m;//计算经过冲突后的下一个哈希地址

i++:

}

if(a［k］．isbn==number)return(k);//查找成功

else return 0;//找到一个空记录，查找失败

}

3 性能分析

通过对以上3种查找算法的分析，可以得到表1所示的性能对比结果．可见，随着待查找记录个数n的增长，顺序查找与折半查找算法执行时间的增长率分别与n和log2n的增长率成正比，但是哈希查找算法执行时间的增长率与n无关，是查找效率非常高的查找算法．

表1 3种查找算法的性能对比

4 结束语

查找是计算机程序设计中最为普遍的操作，查找的效率也是计算机领域一直关注的问题．本文以图书信息检索为例，在传统的顺序查找和折半查找基础上，提出了哈希查找的思想，结合数字分析法和折叠法建立了哈希函数，采用线性探测再散列解决冲突．与传统的方法相比，查找效率更高．

［1］严蔚繁，吴伟民．数据结构(C语言版)［M］．北京:清华大学出版社，2008．

［2］王云鹏．线性时间选择算法时间复杂度深入研究［J］．软件开发与设计，2009(14):3－5．

［3］AnanyLevitin．Introduction to The Design and Analysis of Algorithms［M］．北京:清华大学出版社，2004．

［4］叶军伟．哈希函数构造方法及其适用情况［J］．科技致富向导，2014(8):278－279．

［5］邹又姣，马文平，冉占军，等．改进的多变量哈希函数［J］．计算机科学，2013，6(40):45－49．

［6］肖丽．哈希查找中散列函数的运用［J］．技术研发，2009，8(16):18－20．