2、哈希表的构造方法
直接定址法 除余法 基数转换法 平方取中法 折叠法 移位法 随机数法
2、哈希表的构造方法
直接定址法： 直接定址法：取关键字或关键字的某个线性函数 值为哈希地址。 值为哈希地址。 key） 即：H（key）=key 或 H(key)=a*key+b
例如：有一个从1到100岁的人口数字统计表，其中，年龄作为 例如：有一个从 到 岁的人口数字统计表，其中， 岁的人口数字统计表 关键字，哈希函数取关键字自身。 关键字，哈希函数取关键字自身。 地址 年龄 01 1 02 2 ... ... 25 25 26 26 ... 27 27 ... ... ... ... 100 ... ...
3、处理冲突方法
拉链法
例2： 已知一组关键字为 ，14，23，01， ： 已知一组关键字为(19， ， ， ， 68，20，84，27，55，11，10，79)， 68，20，84，27，55，11，10，79)，散列 函数h=key%13 ，用用拉链法解决冲突构造 函数 这组关键字的散列表（哈希表）。 这组关键字的散列表（哈希表）。
1、什么是哈希表
如果我们以学生姓名为关键字，如何建立查找表， 如果我们以学生姓名为关键字，如何建立查找表， 使得根据姓名可以直接找到相应记录呢？ 使得根据姓名可以直接找到相应记录呢？ 刘丽 刘宏英
姓名中各拼音 首字母 用所有首字编 号值相加 求和
吴军 wj
吴小艳 wxy
李秋梅 陈伟 ... lqm cw ...
成绩二... 成绩二
95
1、什么是哈希表
如果将来要查李秋梅的成绩， 如果将来要查李秋梅的成绩，可以用上述 方法求出该记录所在位置： 方法求出该记录所在位置： 李秋梅:lqm 取表中第42条记 李秋梅:lqm 12+17+13=42 取表中第42条记 录即可。 录即可。 问题： 问题：如果两个同学分别叫 刘丽 刘兰 该如 何处理这两条记录？ 何处理这两条记录？ 这个问题是哈希表不可避免的， 这个问题是哈希表不可避免的，即冲突现 象：对不同的关键字可能得到同一哈希地 址。
再哈希法
hi=(h(key)+i*h1(key))％ 0≤i≤m- //即 hi=(h(key)+i*h1(key))％m 0≤i≤m-1 //即di=i*h1(key)
拉链法 建立一个公共溢出区
3、处理冲突方法
（1）开放地址法（线性探测再散列、二次探测 开放地址法（线性探测再散列、 再散列、 再散列、随机探测再散列） 1： 已知一组关键字为(26，36，41，38， 例1： 已知一组关键字为(26，36，41，38， 44，15，68，12，06，51)，散列函数 ， ， ， ， ， ， h=key%p ，p=13.取m=13（存储空间为 取 （ 13）.用线性探查法解决冲突构造这组关 ） 用线性探查法解决冲突构造这组关 键字的散列表。 键字的散列表。 若用二次探测再散列法哪？ 若用二次探测再散列法哪？
练习
例7：哈希查找中 k个关键字具有同一哈希值， 个关键字具有同一哈希值， 若用线性探测法将这k 若用线性探测法将这k个关键字对应的记录 存入哈希表中，至少要进行( )次探测 次探测。 存入哈希表中，至少要进行( )次探测。 A.k B.k+1 C.k(k+1)/2 D.1+k(k+1)/2
2、哈希表的构造方法
平方取中法： 平方取中法：先通过求关键字的平方值扩 大相近数的差别， 大相近数的差别，然后根据表长度取中间 的几位数作为散列函数值。 的几位数作为散列函数值。又因为一个乘 积的中间几位数和乘数的每一位都相关， 积的中间几位数和乘数的每一位都相关， 所以，因此产生的散列地址较为均匀。 所以，因此产生的散列地址较为均匀。
4、Hash表的查找 Hash表的查找
哈希查找的方法是一种直接计算存储 地址的方法，在查找过程中， 地址的方法，在查找过程中，如果构造哈 希表所选择的哈希函数使得地址分布均匀 的话，几乎无需进行比较， 的话，几乎无需进行比较，就可以得出 找到”或者“找不到”的结论的。 “找到”或者“找不到”的结论的。但由 于在构造哈希函数时难以避免发生冲突， 于在构造哈希函数时难以避免发生冲突， 因此，在考察哈希查找的效率时， 因此，在考察哈希查找的效率时，不但要 考虑查找时所需比较的次数， 考虑查找时所需比较的次数，还需考虑求 取哈希地址所需的时间，显然， 取哈希地址所需的时间，显然，此时仍然 可以用平均查找长度作为评价哈希查找效 可以用平均查找长度作为评价哈希查找效 率的标准 。
人数 3000 2000 ... 1050 ...
2、哈希表的构造方法
除余法： 除余法：以关键码除以表元素总线后得 到的余数为哈希地址。 到的余数为哈希地址。
例：对21、30、11三个数，利用k mod 3的方式，求 、 、 三个数，利用 的方式， 三个数 的方式 他们的哈希地址： 他们的哈希地址： 21 Mod 3=0 30 Mod 3=0 11 Mod 3=2
练习
例5：（ 10 ， 8 ， 17 ， 16 ， 4 ， 7 ， 25 ， 18 ）进行 ：（ 哈希制表， 哈希制表，地址空间为 0 ～ 9 ，取，p=7，以除留余数 ， 法构造哈希函数，线性探查法解决冲突， 法构造哈希函数，线性探查法解决冲突，画出哈希表并 计算查找成功的平均查找长度。 计算查找成功的平均查找长度。 例6：设哈希表长为 14，哈希函数是 ： ，哈希函数是H(key)=key%11, 表中已有数据的关键字为15， ， ， 共四个 共四个， 表中已有数据的关键字为 ，38，61，84共四个，现 要将关键字为49的结点加到表中 的结点加到表中， 要将关键字为 的结点加到表中，用二次探测再散列 法解决冲突，则放入的位置是( ) 法解决冲突，则放入的位置是 A．8 B．3 C．5 D．9 ． ． ． ．
线性探查法解决冲突
21 30 11
2、哈希表的构造方法
基数转换法： 基数转换法：将关键码看作是某个基数制 上的整数， 上的整数，然后将其转换为另一基数制上 的数。 的数。
三个数， 例：对21、30、11三个数，进行基数转换法求哈希 、 、 三个数 地址。 地址。 把这三个数看作是八进制，转成十进制为： 、 把这三个数看作是八进制，转成十进制为：17、 24、9，然后分别将其存放在相应的存取空间。 、 ，然后分别将其存放在相应的存取空间。
三个数进行平方取中法求哈希地址： 例：对21、30、11三个数进行平方取中法求哈希地址： 、 、 三个数进行平方取中法求哈希地址 21*21=441 30*30=900 11*11=121 哈希地址分别为 4、0、2 、 、
3、处理冲突方法
开放地址法（线性探测再散列、二次探测再散列、 开放地址法（线性探测再散列、二次探测再散列、 随机探测再散列） hi=（h（key）+i）mod m 其中0≤i≤m-1 hi=（ key）+i） 其中0≤i≤mi=1,2,3……m 1,线性探测再散列 i=1,2,3……m-1,线性探测再散列； 线性探测再散列； i=12,-12, 22,-22 ,32,-32 ……±k2,二次探测再散列； ……± 二次探测再散列； i=伪随机数序列，称伪随机探测再散列。 i=伪随机数序列 称伪随机探测再散列。 伪随机数序列，
ll
lhy
24
46
33
72
42
26
...
最小值可能为3 最大值可能为78 可放76个学生 最小值可能为 最大值可能为 ，可放 个学生
成绩一 3 ... 24 25 26 ... 33 ... 42 ... 46 ... 72 ... 78 ... ... 刘丽 ... 陈伟 ... 吴军 ... 李秋梅 ... 刘宏英 ... 吴小艳 ... ... 82
练习
例4：已知一个线性表（38，25，74，63，52， 已知一个线性表（38，25，74，63，52， 48），假定采用散列函数h（key）=key%7计 48），假定采用散列函数h key）=key%7计 ），假定采用散列函数 算散列地址， 算散列地址，并散列存储在散列表 A[0,1……6]中 A[0,1……6]中，若采用线性探测方法解决冲 突，则在该散列表上进行等概率成功查找的 平均查找长度为（ 平均查找长度为（ ） A. 1.5 B. 1.7 C. 2.0 D. 2.3
Hash
什么是哈希表？ 什么是哈希表？ Hash函数的构造方法； Hash函数的构造方法； 函数的构造方法 处理冲突方法； 处理冲突方法； Hash表的查找 Hash表的查找。 表的查找。
1、什么是哈希表
Hash表又可称哈希表、散列表、杂凑表。 Hash表又可称哈希表、散列表、杂凑表。 表又可称哈希表 它是一种十分实用的查找技术， 它是一种十分实用的查找技术，具有极高 的查找效率。 的查找效率。 哈希表最常见的例子是以学生学号为关键 字的成绩表， 字的成绩表，１号学生的记录位置在第一 １０号学生的记录位置在第１０条 号学生的记录位置在第１０ 条，１０号学生的记录位置在第１０条...
4、Hash表的查找 Hash表的查找
按照建立哈希表时的哈希函数，根据给定 按照建立哈希表时的哈希函数， 关键字值，直接求出其哈希地址： 关键字值，直接求出其哈希地址： 若该地址中数据元素为空，则查找失败； （1）若该地址中数据元素为空，则查找失败； 若该地址中数据元素不为空， （2） 若该地址中数据元素不为空，且其关键 字值与给定关键字值相等，则查找成功； 字值与给定关键字值相等，则查找成功； 若该地址中数据元素不为空， （3） 若该地址中数据元素不为空，但其关键 字值不等于给定关键字值， 字值不等于给定关键字值，则需按照建立哈 希表时解决冲突的办法，继续在“ 希表时解决冲突的办法，继续在“下一个哈 希地址”中查找，如此深入， 希地址”中查找，如此深入，直至找到或者 某一哈希地址中的元素为空时结束。 某一哈希地址中的元素为空时结束。