哈希函数的构造方法 个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内,以尽可能减 少冲突。但鉴于实际问题中关键字的不同,没法构造出统一的哈希函数。从而构 造哈希函数的方法多种多样,这里只介绍一些比较常用的、计算较为简便的方法。 1.自身函数 关键字自身作为哈希函数,即H(k)=k,也可自身加上一个常数作为哈希函数,即 H(k=k+c。例如上例中建立的哈希函数H(学号)=学号-9900采用的就是这样的方法 但这种函数只适用于给定的一组关键字为关键字集合中的全体元素的情况,故不 常用。 2.除余法 选择一个适当的正整数m,用m去除关键字,取其余数作为散列地址,即H(key) =key%m。上例中后来所设定的函数H(学号)学号%10.用的就是除余法 但是在这种方法中,m的选择是值得研究的。如果选择关键字内部代码基数的幂次来 除关键字,其结果必定是关键字的低位数字均匀性较差。若取m为任意偶数,则 当关键字内部代码为偶数时,得到的哈希函数值为偶数;若关键字内部代码为奇 数,则哈希函数值为奇数。因此,m为偶数也是不好的。理论分析和试验结果均 证明m应取小于存储区容量的素数。哈希函数的构造方法 一个好的哈希函数应使函数值均匀的分布在存储空间的有效地址范围内，以尽可能减 少冲突。但鉴于实际问题中关键字的不同，没法构造出统一的哈希函数。从而构 造哈希函数的方法多种多样，这里只介绍一些比较常用的、计算较为简便的方法。 1．自身函数 关键字自身作为哈希函数，即H（k）=k，也可自身加上一个常数作为哈希函数，即 H(k)=k+c。例如上例中建立的哈希函数H(学号)=学号-9900采用的就是这样的方法。 但这种函数只适用于给定的一组关键字为关键字集合中的全体元素的情况，故不 常用。 2．除余法 选择一个适当的正整数m，用m去除关键字，取其余数作为散列地址，即H（key） =key%m。上例中后来所设定的函数H(学号)=学号%10采用的就是除余法。 但是在这种方法中，m的选择是值得研究的。如果选择关键字内部代码基数的幂次来 除关键字，其结果必定是关键字的低位数字均匀性较差。若取m为任意偶数，则 当关键字内部代码为偶数时，得到的哈希函数值为偶数；若关键字内部代码为奇 数，则哈希函数值为奇数。因此，m为偶数也是不好的。理论分析和试验结果均 证明m应取小于存储区容量的素数