散列函数的构造方法.doc

《散列函数的构造方法.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、散列函数的构造方法1、散列函数的选择有两条标准：简单和均匀。　简单指散列函数的计算简单快速；　均匀指对于关键字集合中的任一关键字，散列函数能以等概率将其映射到表空间的任何一个位置上。也就是说，散列函数能将子集K随机均匀地分布在表的地址集{0，1，…，m-1}上，以使冲突最小化。2、常用散列函数　为简单起见，假定关键字是定义在自然数集合上。（1）平方取中法　具体方法：先通过求关键字的平方值扩大相近数的差别，然后根据表长度取中间的几位数作为散列函数值。又因为一个乘积的中间几位数和乘数的每一位都相关，所以由此产生的散列地址较为均匀。　【例】将一组关键字(0100，011

2、0，1010，1001，0111)平方后得(，，，，)　若取表长为1000，则可取中间的三位数作为散列地址集：(100，121，201，020，123)。相应的散列函数用C实现很简单：intHash(intkey){//假设key是4位整数key*=key；key/=100；//先求平方值，后去掉末尾的两位数returnkey％1000；//取中间三位数作为散列地址返回}（2）除余法　该方法是最为简单常用的一种方法。它是以表长m来除关键字，取其余数作为散列地址，即h(key)=key％m　该方法的关键是选取m。选取的m应使得散列函数值尽可能与关键字的各位相关。m最

3、好为素数。　【例】若选m是关键字的基数的幂次，则就等于是选择关键字的最后若干位数字作为地址，而与高位无关。于是高位不同而低位相同的关键字均互为同义词。　【例】若关键字是十进制整数，其基为10，则当m=100时，159，259，359，…，等均互为同义词。（3）相乘取整法　该方法包括两个步骤：首先用关键字key乘上某个常数A(0

4、：intHash(intkey){doubled=key*A；//不妨设A和m已有定义return(int)(m*(d-(int)d))；//(int)表示强制转换后面的表达式为整数}（4）随机数法　选择一个随机函数，取关键字的随机函数值为它的散列地址，即h(key)=random(key)　其中random为伪随机函数，但要保证函数值是在0到m-1之间。