直接定址法以关键字本身或关键字加上某个数值常量c作为哈希地址的方法。即h(k)=k+C。这种哈希函数计算简单，并且不可能有冲突发生。当关键字的分布基本连续时，可用直接定址法的哈希函数：否则，若关键字分布不连续将造成内存单元的大量浪费。6/62
以关键字k本身或关键字加上某个数值常量c作为哈希地址的方法。 即h(k)=k+c。 这种哈希函数计算简单，并且不可能有冲突发生。 当关键字的分布基本连续时，可用直接定址法的哈希函数；否则， 若关键字分布不连续将造成内存单元的大量浪费。 1. 直接定址法 6/62
哈希表ha学号姓名哈希地址分数0王华9020180011姓名学号分数2王华9020180013刘丽622018010n=7m=12李英4822018005陈明542018006h（学号）=学号-2018001陈明54y2018006张强9520180096许兵762018007许兵7620180077李萍8820180128张强952018009李英8220180059刘丽62201801010李萍118820180127/62
学号 姓名 分数 2018001 王华 90 2018010 刘丽 62 2018006 陈明 54 2018009 张强 95 2018007 许兵 76 2018012 李萍 88 2018005 李英 82 哈希地址 学号 姓名 分数 0 2018001 王华 90 9 2018010 刘丽 62 5 2018006 陈明 54 8 2018009 张强 95 6 2018007 许兵 76 11 2018012 李萍 88 4 2018005 李英 82 1 2 3 7 10 n=7 m=12 h(学号)=学号-2018001 哈希表ha 7/62
2.除留余数法用关键字R除以某个不大于哈希表长度m的数p所得的余数作为哈希地址的方法。除留余数法的哈希函数h(k)为：h(k)=kmodp（mod为求余运算，p≤m)p最好是质数（素数）。8/62
用关键字k除以某个不大于哈希表长度m的数p所得的余数作为哈希 地址的方法。 除留余数法的哈希函数h(k)为：h(k)=k mod p (mod为求余运算， p≤m) p最好是质数（素数）。 2. 除留余数法 8/62
哈希表hah(k)=k mod pRm-1p≤m保证地址有效p为质数→保证冲突尽可能小9/62
0 1 2 ⁞ m-1 哈希表ha k h(k)=k mod p p≤m 保证地址有效 p为质数 保证冲突尽可能小 9/62
3.数字分析法提取关键字中取值较均匀的数字位作为哈希地址的方法。适合于所有关键字值都已知的情况，并需要对关键字中每一位的取值分布情况进行分析。10/62
提取关键字中取值较均匀的数字位作为哈希地址的方法。 适合于所有关键字值都已知的情况，并需要对关键字中每一位的取 值分布情况进行分析。 3. 数字分析法 10/62