Question

哈希函数构造方法

Answer 1

哈希函数构造方法如下：

1、除留余数法。取关键字被某个不大于哈希表长m的数p除后所得的余数为哈希地址。

2、随机法。采用一个伪随机函数做哈希函数，即：H（key）=random（key）。其中random为随机函数。通常，当关键字长度不等时采用此法构造哈希函数较为恰当。

3、平方取中法。当无法确定关键字中哪几位分布较均匀时，可以先求出关键字的平方值，然后按需要取平方值的中间几位作为哈希地址。这是因为：平方后中间几位和关键字中每一位都相关，故不同关键字会以较高的概率产生不同的哈希地址。

4、折叠法。这种方法是按哈希表地址位数将关键字分成位数相等的几部分（最后一部分可以较短），然后将这几部分相加，舍弃最高进位后的结果就是该关键字的哈希地址。具体方法有折叠法与移位法。移位法是将分割后的每部分低位对齐相加，折叠法是从一端向另一端沿分割界来回折叠（奇数段为正序，偶数段为倒序），然后将各段相加。

5、直接定址法。取关键字或关键字的某个线性函数值为哈希地址。

6、数字分析法。如果事先知道关键字集合，并且每个关键字的位数比哈希表的地址码位数多时，可以从关键字中选出分布较均匀的若干位，构成哈希地址。