|
散列函数的构造方法 散列函数的选择有两条标准简单和均匀 简单指散列函数的计算简单快速; 均匀指对于关键字集合中的任一关键字散列函数能以等概率将其映射到表空间的任何一个位置上也就是说散列函数能将子 集K随机均匀地分布在表的地址集{…m}上以使沖突最小化 常用散列函数 为简单起见假定关键字是定义在自然数集合上 ()平方取中法 具体方法先通过求关键字的平方值扩大相近数的差别然后根据表长度取中间的几位数作为散列函数值又因为一个乘积的中 间几位数和乘数的每一位都相关所以由此产生的散列地址较为均匀 【例】将一组关键字()平方后得 () 若取表长为则可取中间的三位数作为散列地址集 () 相应的散列函数用C实现很简单 int Hash(int key){ //假设key是位整数 key*=key; key/=; //先求平方值后去掉末尾的两位数 return key%; //取中间三位数作为散列地址返回 } ()除余法 该方法是最为简单常用的一种方法它是以表长m来除关键字取其余数作为散列地址即 h(key)=key%m 该方法的关键是选取m选取的m应使得散列函数值尽可能与关键字的各位相关m最好为素数 【例】若选m是关键字的基数的幂次则就等于是选择关键字的最后若干位数字作为地址而与高位无关于是高位不同而低位相 同的关键字均互为同义词 【例】若关键字是十进制整数其基为则当m=时…等均互为同义词 ()相乘取整法 该方法包括两个步骤首先用关键字key乘上某个常数A( 该函数的C代码为： int Hash(int key){ double d=key *A; //不妨设A和m已有定义 return (int)(m*(d-(int)d));//(int)表示强制转换后面的表达式为整数 } (4)随机数法 选择一个随机函数，取关键字的随机函数值为它的散列地址，即 h(key)=random(key) 其中random为伪随机函数，但要保证函数值是在0到m-1之间。TW.wInGWiT.cOM |
