哈希函数构造方法研究

《哈希函数构造方法研究》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、学科分类号：　理工科类摘要本文阐述了哈希函数的构造方法有很多，但应注意两个原则：第一，函数值应在1至记录总数之间；第二，尽可能避免冲突。设要存放的数据元素有n个，存放数据元素的内存单元有m个，设计哈希函数的目标就是要使通过哈希函数得到的n个数据元素的哈希地址尽可能均匀地分布在m个连续内存单元上，同时使计算过程尽可能简单以达到尽可能高的时间效率。Thispaperdescribesthestructureofthehashfunctionofalotofways,butshouldpayattentiontotwoprinciples:First,thefunctionvalu

2、eshouldbebetween1torecordthetotalnumberofthesecond,asfaraspossibletoavoidconflict关键字哈希函数，关键字，哈希表，哈希冲突，哈希地址13关于哈希函数的构造方法目录摘要2关键字2关于哈希函数构造方法研究3引言41．直接定址法42．数字分析法42．142.253．折叠法54．平方取中法65.减去法76.基数转换法77.除留余数法88．随机乘数法89．字符串数值哈希法910.旋转法911.伪随机数法10小结11参考文献12致谢1313引言构造哈希函数的方法很多。如何构造一个“好”的哈希函数是很强的技术性

3、和实践性问题，这里的“好”指的是哈希函数构造比较简单，并且用此哈希函数产生的映射所发生的冲突可能性最小，换句话说一个好的哈希函数能将给定数据集合均匀地映射到给定的地址区间中。Hash的原意是“弄乱，切碎”，这里的含义是“杂凑”。基本做法是，根据集合元素值的分布情况，设计一个哈希函数h(ki),存储之素ki时，计算ki的哈希函数值，元素ki存储在a(h)中。如果“幸运”，所设计的哈希函数很均匀，即任何ki≠kj,都有h(ki)≠h(kj),那么在查找ki时（再计算ki的哈希函数函数值h）,就能在a[h]中找到元素ki。1．直接定址法直接定址法是以数据元素关键字k本身或它的线性函

4、数作为它的哈希地址，即：H（k）=k或H（k）=a×k+b；(其中a,b为常数)例1，有一个人口统计表，记录了从1岁到100岁的人口数目，其中年龄作为关键字，哈希函数取关键字本身，如图(1)：地址A1A2……A99A100年龄12……99100人数980800……495107可以看到，当需要查找某一年龄的人数时，直接查找相应的项即可。如查找99岁的老人数，则直接读出第99项即可。这种哈希函数简单，并且对于不同的关键字不会产生冲突，但可以看出这是一种较为特殊的哈希函数，实际生活中，关键字的元素很少是连续的。用该方法产生的哈希表会造成空间大量的浪费，因此这种方法适应性并不强。[2

5、]↑2．数字分析法2．1数字分析法是取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法。即当关键字的位数很多时，可以通过对关键字的各位进行分析，丢掉分布不均匀的位，作为哈希值。它只适合于所有关键字值已知的情况。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间。例2，要构造一个数据元素个数n=80,哈希长度m=100的哈希表。不失一般性，我们这里只给出其中8个关键字进行分析，8个关键字如下所示：K1=61317602K2=61326875K3=62739628K4=6134363413K5=62706815K6=62774638K7=61381262K8=

6、61394220分析上述8个关键字可知，关键字从左到右的第1、2、3、6位取值比较集中，不宜作为哈希地址，剩余的第4、5、7、8位取值较均匀，可选取其中的两位作为哈希地址。设选取最后两位作为哈希地址，则这8个关键字的哈希地址分别为：2，75，28，34，15，38，62，20。[1]↑2.2设有n个d位数，每一位可能有r种不同的符号，这r种不同的符号在各位上出现的频率不一定相同，可能在某位上分布均匀些，每种符号出现的机会均等；在某位上分布不均匀，只有某几种符号经常出现。可根据哈希表的大小，选取其中各种符号分布均匀的若干位作为哈希地址。计算各位数字中符号分布均匀度rk的公式为：

7、rk=其中，aki表示第i个符号k位上出现的的期望值。计算出rk值越小，i=1表明在该位（第k位）各种符号分布越不均匀。例3，有一组关键字，对其各位编码如下：9214891269905279163091805915589204790001①②③④⑤①位仅“9”出现8次r1=(8-8/10)2*1+(0-8/10)2*9=57.60②位“0，2”各出现2次，“1”出现4次r2=(2-8/10)2*2+(4-8/10)2*1+（0-8/10）2*7=17.60③位“0，5”各出现2次，“1，2，6，8”各出