哈希表查找9.4哈希表的基本概念9.4.11哈希表设要存储的元素个数为n，设置一个长度为m（m≥n）的连续内存单元。以每个元素的关键字k；（0≤i≤n-1）为自变量，通过一个哈希函数h把k,映射为内存单元的地址（或相对地址）h(ki)。并把该元素存储在这个内存单元中。1/62
设要存储的元素个数为n，设置一个长度为m（m≥n）的连续内存 单元。 以每个元素的关键字ki（0≤i≤n-1）为自变量，通过一个哈希函 数h把ki映射为内存单元的地址（或相对地址）h(ki)。 并把该元素存储在这个内存单元中。 1/62
n个对象个数m（m≥n）的连续内存单元哈希函数h存储地址存储地址=h(key)2/62
哈希函数h 存储 地址 存储地址=h(key) n个对象个数 m（m≥n）的连续内存单元 2/62
哈希表ha学号姓名哈希地址分数0王华9020180011学号姓名分数2王华9020180013刘丽622018010n=7m=12李英4822018005陈明542018006h（学号）=学号-2018001陈明542018006张强9520180096许兵762018007许兵7620180077李萍8820180128张强952018009李英8220180059刘丽62201801010李萍11882018012查找学号为2018010的学生分数：先计算h（2018010）=2018010-2018001=9再取ha[9]元素的分数62即可。对应的查找时间为0(1)。3/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 查找学号为2018010的学生分数： 先计算h(2018010)=2018010-2018001=9。 再取ha[9]元素的分数62即可。 对应的查找时间为O(1)。 哈希表ha 3/62
对于两个不同的关键字k;和k，（i≠j）出现h(k;)=h(k,)，这种现象称为哈希冲突。将具有不同关键字而具有相同哈希地址的元素称为“同义词”，这种冲突也称为同义词冲突，需要解决哈希冲突4/62
对于两个不同的关键字ki和kj（i≠j）出现h(ki)=h(kj)，这种现象 称为哈希冲突。 将具有不同关键字而具有相同哈希地址的元素称为“同义词”，这种 冲突也称为同义词冲突。 需 要 解 决哈希 冲突 4/62
哈希函数构造方法9.4.2构造哈希函数的目标：使得到的哈希地址尽可能均匀地分布在m个连续内存单元地址上，同时使计算过程尽可能简单以达到尽可能高的时间效率。根据关键字的结构和分布的不同，有多种构造哈希函数的方法。5/62
构造哈希函数的目标：使得到的哈希地址尽可能均匀地分布在m个连 续内存单元地址上，同时使计算过程尽可能简单以达到尽可能高的 时间效率。 根据关键字的结构和分布的不同，有多种构造哈希函数的方法。 5/62
直接定址法以关键字本身或关键字加上某个数值常量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