数据结构第9章查找剖析.ppt

哈希函数的构造方法 直接定址法 构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=a·key+b 特点 直接定址法所得地址集合与关键字集合大小相等，对于不同关键字不会发生冲突 实际中能用这种哈希函数的情况很少 例 关键字集合为{100，300，500，700，800，900}，选取哈希函数为： Hash（key）=key/100 则在哈希表中存放如下： 0 1 2 3 4 5 6 7 8 9 100 300 500 700 800 900 数字分析法 构造:如果事先知道关键字的集合，且关键字的位数比哈希表的地址位数多，则可选取数字分布比较均匀的若干位作为哈希函数。 适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况 例 有80个记录，关键字为8位十进制数，哈希地址为2位十进制数 8 1 3 4 6 5 3 2 8 1 3 7 2 2 4 2 8 1 3 8 7 4 2 2 8 1 3 0 1 3 6 7 8 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 8 1 3 6 8 5 3 7 8 1 4 1 9 3 5 5 ….. ….. ?? ? ??? ?? 分析： ?只取8 ?只取1 ?只取3、4 ?只取2、7、5 ????数字分布近乎随机 所以：取????任意两位或两位 与另两位的叠加作哈希地址 表长若为1000，可取四、六、七位的数字作为哈 希地址。若表长为100，则可取四、五与六、七位 之和并舍去进位来作为哈希地址等。 关键字 哈希地址1(0~999) 哈希地址2(0~99) 8 1 3 4 6 5 3 2 465 99 8 1 3 7 2 2 4 2 722 96 8 1 3 8 7 4 2 2 874 29 8 1 3 0 1 3 6 7 013 37 8 1 3 2 2 8 1 7 228 03 8 1 3 3 8 9 6 7 389 34 平方取中法 构造：取关键字平方后中间几位作哈希地址 适于不知道全部关键字情况 例 关键字集合{0100，1100 ，1200 ，1160 ，2061}就无法使用数字选择法得到较为均匀的哈希函数。此时使用平方取中法，所取位数由表长决定。 关键字 0100 (关键字)2 0010000 函数地址 010 1100 1200 1210000 1440000 210 440 1160 2061 1370400 4310541 370 310 折叠法 构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址 种类 移位叠加：将分割后的几部分低位对齐相加 间界叠加：从一端沿分割界来回折送，然后对齐相加 适于关键字位数很多，且每一位上数字分布大致均匀情况 例 关键字为 ：0442205864，哈希地址位数为4 5 8 6 4 4 2 2 0 0 4 1 0 0 8 8 H(key)=0088 移位叠加 5 8 6 4 0 2 2 4 0 4 6 0 9 2 H(key)=6092 间界叠加 除留余数法 构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p，p?m 特点 简单、常用，可与上述几种方法结合使用 p的选取很重要；p选的不好，容易产生同义词 p一般选取质数，若哈希表表长为m，则要求p≤m，且接近m或等于m。 例 m=8，16，32，64，128，256，512，1024 p=7，13，31，61，127，251，503，1019 随机数法 构造：取关键字的随机函数值作哈希地址，即H(key)=random(key) 适于关键字长度不等的情况 选取哈希函数，考虑以下因素： 计算哈希函数所需时间 关键字长度 哈希表长度（哈希地址范围） 关键字分布情况 记录的查找频率 处理冲突的方法 处理冲突的方法基本上有两大类：开放定址法和拉链法 开放定址法 方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di)MOD m，i=1,2,……k(k?m-1) 其中：H(key)——哈希函数 m——哈希表表长 di——增量序列 分类