60 17 29 38
【例2】 有一组关键字为： (26，38，73，21，54，35，167，32，7，223，52) 试用线性探查法解决冲突，并构造这组关键字的哈希表。设哈 希表的长度为15。 分析：当哈希表的长度为15时，显然P取13比较合理。利用哈 希函数H (K) = K %13进行计算，可知上述关键字序列所对应的哈希地 址如下： 关键字 哈希地址 26 0 38 12 73 8 21 8 54 2 35 9 167 11 32 6 7 7 223 2 52 0
地址 年份 保费 01 1 ……. 02 2 ……. 03 3 ……. …… ……. …… 20 20 ……
桂林电子科技大学信息科技学院 赵莹莹
9.4.2 散列函数的构造方法 散列函数的构造方法(2)
取关键字平方后的中间几位为哈希函数。 （2）平方取中法——取关键字平方后的中间几位为哈希函数。 平方取中法 取关键字平方后的中间几位为哈希函数 如：K=308，K2=94864，H（K）=486 K=308， =94864， 例如，关键字为3632，则36322=13191424。 H(3632)=914。 （3） 除后余数法 除后余数法——设散列表的地址空间大小为m，取关键 设散列表的地址空间大小为m 设散列表的地址空间大小为 字被不大于m的质数p 除后所得的余数为哈希函数， 字被不大于m的质数p， 除后所得的余数为哈希函数， 即： H（K）=K MOD p （p ≤ m ）
表项序号 H(K)=int(K/3)+1
1 01 02
2 05
3
4
09 11
5
13
6 16
7 19
8 21
9 26
10 27
11 31
12
冲突：两个不同的关键字具有相同的存储位置。 冲突：两个不同的关键字具有相同的存储位置。 为了有效地使用散列技术，需要解决两方面的问题： 为了有效地使用散列技术，需要解决两方面的问题： •构造好的哈希函数，使冲突的现象尽可能的少； 构造好的哈希函数，使冲突的现象尽可能的少； 构造好的哈希函数 •设计有效的解决冲突的方法。 设计有效的解决冲突的方法。 设计有效的解决冲突的方法
数据结构第二十讲
桂林电子科技大学信息科技学院 赵莹莹
第九章 查找
桂林电子科技大学信息科技学院 赵莹莹
本章要点
• • • • • • • • • • • • • • • • 9.1 基本概念 9.2 顺序表的静态查找 9.2.1 简单顺序查找 9.2.2 二分查找（折半查找）（重点） 9.2.3 分块查找 9.3 树表的动态查找(简单掌握二叉排序树) 9.3.1 二叉排序树 9.3.2 平衡二叉树 9.3.3 B-树 9.4 散列表的查找 9.4.1 散列表的定义 9.4.2 散列函数的构造 9.4.3 冲突的解决方法 9.4.4 散列表的查找及性能分析 9.4.5 有关散列表的算法 本章小结
桂林电子科技大学信息科技学院 赵莹莹
9.4.1 散列表的基本概念
散列表（HASH）,即哈希表，或杂凑表。 通过一个函数直接将记录关键字值映射成一块连续存储空间的地址，这个函 数称为Hash(哈希)函数，或散列函数，或杂凑函数。 • H:K->A • H(k) • 数据表的这种存储方式叫散列存储，或哈希存储。 • 数据表的存储空间称为散列表，或Hash表。 • 哈希表技术的主要目标是提高查找效率，即缩短查表和填表的时间。 • •
桂林电子科技大学信息科技学院 赵莹莹
0 1
为表长, 设散列函数 H（k）=k ％ m （m为表长 设m=11) （ ） 为表长 若发生冲突， 若发生冲突，设发生冲突的地址为 d , 则沿着一个探查 序列逐个探查，那么，探查的地址序列为： 序列逐个探查，那么，探查的地址序列为：
2 3 4 5 6 7 8 9 10
桂林电子科技大学信息科技学院 赵莹莹
课堂练习： 课堂练习：
• ASL=?
桂林电子科技大学信息科技学院 赵莹莹
本章要点
• • • • • • • • • • • • • • • • 9.1 基本概念 9.2 顺序表的静态查找 9.2.1 简单顺序查找 9.2.2 二分查找 9.2.3 分块查找 9.3 树表的动态查找 9.3.1 二叉排序树 9.3.2 平衡二叉树 9.3.3 B-树 9.4 散列表的查找 9.4.1 散列表的定义 9.4.2 散列函数的构造 9.4.3 冲突的解决方法 9.4.4 散列表的查找及性能分析 9.4.5 有关散列表的算法 本章小结
60 17 29
d +1, d +2, d +3 ,…, m-1 , 0, 1, …, d -1.
桂林电子科技大学信息科技学院 赵莹莹
0 1
设散列函数 H(k)=k MOD 11
2 3 4 5 6 7 8 9 10
桂林电子科技大学信息科技学院 赵莹莹
60、17、29、38在散列表中的位置 在散列表中的位置。 求： 60、17、29、38在散列表中的位置。 H(60)= 60 mod 11 = 5 H(17)= 17 mod 11 = 6 H(29)= 29 mod 11 = 7 H(38)= 38 mod 11 = 5
例：散列表的长度为25，那么散列函数可以为： 散列表的长度为25，那么散列函数可以为： 25 H(K）＝key％ H(K）＝key％23 ）＝key P取与表长最接近的那个数
桂林电子科技大学信息科技学院 赵莹莹
本章要点
• • • • • • • • • • • • • • • • 9.1 基本概念 9.2 顺序表的静态查找 9.2.1 简单顺序查找 9.2.2 二分查找 9.2.3 分块查找 9.3 树表的动态查找 9.3.1 二叉排序树 9.3.2 平衡二叉树 9.3.3 B-树 9.4 散列表的查找 9.4.1 散列表的定义 9.4.2 散列函数的构造 9.4.3 冲突的解决方法 9.4.4 散列表的查找及性能分析 9.4.5 有关散列表的算法 本章小结
学号 34 56 78 91
Hash [9] 下标 0 1
姓名 张三 李四 王二 余六
2 3
英语成绩 68 74 66 80
4 5
高数成绩 78 56 88 67
6 7 8
哈希函数： 哈希函数：
根据关键字直接计算出元素所在位置的函数。 根据关键字直接计算出元素所在位置的函数。 例如：设哈希函数为： 例如：设哈希函数为： int(K/3)+1 01、02、05、09、11、13、16、19、21、26、27、31、 则构造 01、02、05、09、11、13、16、19、21、26、27、31、的散列表 哈希表） (哈希表）为：
桂林电子科技大学信息科技学院 赵莹莹
9.4.3 解决冲突的方法
• 假设哈希表的地址范围为0～m-l，当对给定的关键字k，由哈希函数H(k) 算出的哈希地址为i（0≤i≤m-1）的位置上已存有记录，这种情况就是 冲突现象。 • 处理冲突就是为该关键字的记录找到另一个“空”的哈希地址。即通过 一个新的哈希函数得到一个新的哈希地址。如果仍然发生冲突，则再求 下一个，依次类推。直至新的哈希地址不再发生冲突为止。 解决冲突的方法：
100 150 120 180
110
130
160
200
桂林电子科技大学信息科技学院 赵莹莹
算法性能分析： 算法性能分析：
100 60 40 80 120 150 180
70
90
110
130
160
200
• ASL=? • ASL=1／13 * (1+2+2+3+3+3+3+4+4+4+4+4+4+4)=41 ／13
14
0
15
1
21
2
3
3
32
4
42
5
13
6
• ASL=(1/7)*(1+1+1+1+3+1+6)=2
桂林电子科技大学信息科技学院 赵莹莹
（2）平方探查法 d+1 设 发 生 冲 突 的 地 址 为 d， 则 平 方 探 查 法 的 探 查 序 列 为 ： d+12， d+2 直到找到一个空闲位置为止。 d+22，…直到找到一个空闲位置为止。 直到找到一个空闲位置为止 平方探查法的数学描述公式为： 平方探查法的数学描述公式为： d0=H(k) di=(d0+i2) % m (1≤i≤m-1) ≤i≤m-
桂林电子科技大学信息科技学院 赵莹莹
9.4.2 散列函数的构造方法 散列函数的构造方法(1)
直接定址法——取关键字或关键字的某个线性函数值为散列地址，即 取关键字或关键字的某个线性函数值为散列地址， （1 ） 直接定址法 取关键字或关键字的某个线性函数值为散列地址 =A*K+B或 其中A 为常数） H（K）=K 或 H（K）=A*K+B或 H（K）=K+C ；（其中A、B为常数） 直接定址哈希函数示例：某公司一险种投保费交纳表（20年 直接定址哈希函数示例：某公司一险种投保费交纳表（20年），将年份作关键 哈希函数取关键字本身，若查找第3年应交纳的保费，只要查找表的第3 字，哈希函数取关键字本身，若查找第3年应交纳的保费，只要查找表的第3项 即可。 即可。
桂林电子科技大学信息科技学院 赵莹莹
9.4.3 解决冲突的方法
1) 线性探查法 基本思想是：将哈希表看成是一个循环表。若地址为d(d=H(K))的单 元发生冲突，则依次探查下述地址单元d+1 , d+2 , … , m－1 , 0 , 1 , … , d－1 (m为哈希表的长度)直到找到一个空单元或查找到关 键字为key的元素为止。若沿着该探查序列查找一遍之后，又回到了 地址d，则表示哈希表的存储区已满。