河池学院：《数据结构》课程电子教案（PPT教学课件）第9章 查找 9.4 哈希表查找

设要存储的元素个数为n，设置一个长度为m（m≥n）的连续内存 单元。 以每个元素的关键字ki（0≤i≤n-1）为自变量，通过一个哈希函 数h把ki映射为内存单元的地址（或相对地址）h(ki)。 并把该元素存储在这个内存单元中。 1/62

哈希函数h 存储 地址 存储地址=h(key) n个对象个数 m（m≥n）的连续内存单元 2/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

对于两个不同的关键字ki和kj（i≠j）出现h(ki)=h(kj)，这种现象 称为哈希冲突。 将具有不同关键字而具有相同哈希地址的元素称为“同义词”，这种 冲突也称为同义词冲突。 需 要 解 决哈希 冲突 4/62

构造哈希函数的目标：使得到的哈希地址尽可能均匀地分布在m个连 续内存单元地址上，同时使计算过程尽可能简单以达到尽可能高的 时间效率。 根据关键字的结构和分布的不同，有多种构造哈希函数的方法。 5/62

以关键字k本身或关键字加上某个数值常量c作为哈希地址的方法。 即h(k)=k+c。 这种哈希函数计算简单，并且不可能有冲突发生。 当关键字的分布基本连续时，可用直接定址法的哈希函数；否则， 若关键字分布不连续将造成内存单元的大量浪费。 1. 直接定址法 6/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

用关键字k除以某个不大于哈希表长度m的数p所得的余数作为哈希 地址的方法。 除留余数法的哈希函数h(k)为：h(k)=k mod p (mod为求余运算， p≤m) p最好是质数（素数）。 2. 除留余数法 8/62

0 1 2 ⁞ m-1 哈希表ha k h(k)=k mod p p≤m 保证地址有效 p为质数 保证冲突尽可能小 9/62

提取关键字中取值较均匀的数字位作为哈希地址的方法。 适合于所有关键字值都已知的情况，并需要对关键字中每一位的取 值分布情况进行分析。 3. 数字分析法 10/62