哈希函数构造方法研究［毕业设计，精品论文］.doc

设计（论文）题目： 哈希函数构造方法研究 摘 要 本文阐述了哈希函数的构造方法有很多，但应注意两个原则：第一，函数值应在1至记录总数之间；第二，尽可能避免冲突。 设要存放的数据元素有n个，存放数据元素的内存单元有m个，设计哈希函数的目标就是要使通过哈希函数得到的n个数据元素的哈希地址尽可能均匀地分布在m个连续内存单元上，同时使计算过程尽可能简单以达到尽可能高的时间效率。 This paper describes the structure of the hash function of a lot of ways, but should pay attention to two principles: First, the function value should be between 1 to record the total number of the second, as far as possible to avoid conflict 关 键 字 哈希函数，关键字，哈希表，哈希冲突，哈希地址关于哈希函数的构造方法 目 录 摘 要 2 关 键 字 2 关于哈希函数构造方法研究 3 引 言 4 1．直接定址法 4 2．数字分析法 4 2．1 4 2. 2 5 3．折叠法 5 4．平方取中法 6 5.减去法 7 6.基数转换法 7 7.除留余数法 8 8．随机乘数法 8 9．字符串数值哈希法 9 10.旋转法 9 11.伪随机数法 10 小 结 11 参 考 文 献 12 致 谢 13 引 言 构造哈希函数的方法很多。如何构造一个“好”的哈希函数是很强的技术性和实践性问题，这里的“好”指的是哈希函数构造比较简单，并且用此哈希函数产生的映射所发生的冲突可能性最小，换句话说一个好的哈希函数能将给定数据集合均匀地映射到给定的地址区间中。 Hash的原意是“弄乱，切碎”，这里的含义是“杂凑”。基本做法是，根据集合元素值的分布情况，设计一个哈希函数h(ki),存储之素ki时，计算ki的哈希函数值，元素ki存储在a(h)中。 如果“幸运”，所设计的哈希函数很均匀，即任何ki≠kj,都有h(ki)≠h(kj),那么在查找ki时（再计算ki的哈希函数函数值h）,就能在a[h]中找到元素ki。 1．直接定址法 直接定址法是以数据元素关键字k本身或它的线性函数作为它的哈希地址，即：H（k）=k 或 H（k）=a×k+b ； (其中a,b为常数) 例1，有一个人口统计表，记录了从1岁到100岁的人口数目，其中年龄作为关键字，哈希函数取关键字本身，如图(1)： 地址 A1 A2 …… A99 A100 年龄 1 2 …… 99 100 人数 980 800 …… 495 107 可以看到，当需要查找某一年龄的人数时，直接查找相应的项即可。如查找99岁的老人数，则直接读出第99项即可。这种哈希函数简单，并且对于不同的关键字不会产生冲突，但可以看出这是一种较为特殊的哈希函数，实际生活中，关键字的元素很少是连续的。用该方法产生的哈希表会造成空间大量的浪费，因此这种方法适应性并不强。[2]↑ 2．数字分析法 2．1数字分析法是取数据元素关键字中某些取值较均匀的数字位作为哈希地址的方法。即当关键字的位数很多时，可以通过对关键字的各位进行分析，丢掉分布不均匀的位，作为哈希值。它只适合于所有关键字值已知的情况。通过分析分布情况把关键字取值区间转化为一个较小的关键字取值区间。 例2，要构造一个数据元素个数n=80,哈希长度m=100的哈希表。不失一般性，我们这里只给出其中8个关键字进行分析，8个关键字如下所示： K1 K2 K3 K4K5 K6 K7 K8分析上述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种不同的符号在各位上出现的频率不一定相同，可能在某位上分布均匀些，每种符号出现的机会均等；在某位上分布不均匀，只有某几种符号经常出现。可根据哈希表的大小，选取其中各种符号分布均匀的若干位作为哈希地址。计算各位数字中符号分布均