1 School of Computing and Information Engineering.

Presentation on theme: "1 School of Computing and Information Engineering."— Presentation transcript:

1 1 School of Computing and Information Engineering

2 第7章 查找 7.1 查找的基本概念 7.2 静态查找表 7.3动态查找表 7.4 哈希表

3 上节内容回顾 1 查找的基本概念 2 静态查找表 3 动态查找表
查找表、查 找、查找成功、查找不成功、静态查找、 动态查找、关键字、主关键字、次关键字、平均查找长 度ASL 2 静态查找表 顺序查找（线性查找） 折半查找（二分或对分查找） 分块查找（索引顺序查找） 3 动态查找表 二叉排序树 平衡二叉树 3

4 引入 对于频繁使用的查找表，希望ASL=1。 静态查找表： 动态查找表
例如：为每年招收的1000名新生建立一张查找表，其关键字为学号， 其值的范围为xxxx000-xxxx999（前四位为年份） 若以下标为 的顺序表表示 预先知道所查关键字在表的位置 查找过程：取给定值（学号）的后三位，不需要经过比较便可直接从 顺序表中找到待查关键字。 动态查找表 4

5 引入 散列表 动态查找表 需要关键字与记录在表中的存储位置之间建立一个函数关系， 以f(key)作为关键字为key的记录在表中的位置。
表长不确定 在设计查找表时，只知道关键字所属范围，而不知道确切的关键字。 需要关键字与记录在表中的存储位置之间建立一个函数关系， 以f(key)作为关键字为key的记录在表中的位置。 例1：对于如下9个关键字{Zhao, Qian, Sun, Li, Wu, Chen, Han， Yan，Dai},设 f(key) = (字符串中首字母-‵A‵+1)/2 Chen Dai Han Li Qian Sun Wu  Yan Zhao 散列表 5

6 7.4 散列表 一、散列表的基本概念 二、散列函数的构造方法 三、处理冲突的方法 四、散列表的查找及性能分析 6

7 教学目标 1.理解散列表的概念。 2.掌握散列函数的构造方法及处理冲突的方法。 3.掌握散列表的查找及性能分析的方法。

8 一、散列表的基本概念 散列方法：选取某个函数，依该函数按关键字计算元素的存储 位置，并按此存放；查找时，由同一个函数对给定值k计算地 址，将k与地址单元中元素关键字进行比较，确定查找是否成 功。 散列函数：散列方法中使用的转换函数。 散列表：一个有限连续的空间地址，用以存储按散列函数计算 得到相应散列地址的数据记录。 冲突：将不同的关键字映射到同一个散列地址上，这种现象称 为冲突。 同义词：具有相同函数值的关键字对该函数来说称为同义词。 散列法存储的基本思想：建立关键字与其存储位置的对应关系，或者说，由关键字的值决定数据的存储地址。 8

9 一、散列表的基本概念 散列函数 散列表 有冲突！ 同义词
例1：对于如下9个关键字{Zhao, Qian, Sun, Li, Wu, Chen, Han， Yan，Dai},设 f(key) = (字符串中首字母-‵A‵+1)/2 添加关键字Zhou Chen Dai Han Li Qian Sun Wu  Yan Zhao Zhao 散列表 Zhou 有冲突！ 影响散列方法好坏的因素？ 同义词 9

10 一、散列表的基本概念 影响散列方法好坏的因素： 1）散列函数 2）解决冲突的方案 （a）所选函数尽可能简单，以便提高转换速度；
（b）所选函数对关键字计算出的地址，应在散列地址集中大致均匀分布，以减少空间浪费。即一个好的散列函数，对于记录中的任何关键字，将其映射到地址集合中任何一个地址的概率应该是相等的 2）解决冲突的方案 查找时，如果从散列函数计算出的地址中查不到关键字，则应当依据解决冲突的规则，有规律地查询其它相关单元。 10

11 二、散列函数的构造方法 数字分析法 平方取中法 折叠法 除留余数法 11

12 1、数字分析法 特点：某关键字的某几位组合成散列地址。所选的位应当是：各种符号在该位上出现的频率大致相同。
例2：有一组（例如80个）关键字，其样式如下： 位号：① ② ③ ④ ⑤ ⑥ ⑦ 适用范围：适用于事先明确知道表中所有关键字每一位数值的分布情况，它完全依赖于关键字集合。如果换一个关键字集合，选择哪几位要重新决定。 12

13 特点：对关键字平方后，按散列表大小，取中间的若干位作为散列地址。 理由：因为一个数平方后的中间几位与数的每一位都相关。
2、平方取中法 特点：对关键字平方后，按散列表大小，取中间的若干位作为散列地址。 理由：因为一个数平方后的中间几位与数的每一位都相关。 例：2589的平方值为 ，可以取中间的029为地址。 适用范围：适合于不能事先了解关键字的所有情况，或难于直接从关键字中找到取值较分散的几位。 中间所取的位数，由散列表长决定 通常在选定散列函数时不一定能知道关键字的全部情况，取哪几位也不一定合适，而一个平方后的中间几位与数的每一位都相关，如果取关键字平方后的中间几位或其组合作为散列地址，则使随机分布的关键字得到的散列地址也是随机的，具体所取的位数由表长决定。 适用范围：关键字中的每一位都有某些数字重复出现且频度很高的情况 13

14 特点：将关键字分割成位数相等的几部分（最后一部分位数可以短些），然后将这几部分的叠加和（舍去进位）作为散列地址。
3、折叠法 特点：将关键字分割成位数相等的几部分（最后一部分位数可以短些），然后将这几部分的叠加和（舍去进位）作为散列地址。 适用范围：折叠法适合于关键字的数字位数特别多，而且每一位上数字分布大致均匀的情况。 法1：移位叠加法 ── 将各部分的最后一位对齐相加。 法2：间界叠加法──从一端向另一端沿分割界来回折叠后，最后一位对齐相加。 14

15 3、折叠法（续） 例3：关键字为： ，散列地址位数为4 0 4 H(key)=0088 移位叠加 0 4 H(key)=6092 间界叠加

16 H (key)=key mod p (p是一个整数)
4、除留余数法 特点：取关键字被某个不大于散列表长m的数p除后所得余数为散列地址。 H (key)=key mod p (p是一个整数) 关键：如何选取合适的p？ 技巧：选p为小于或等于表长的最大质数。 例4：给定一组关键字为: 12,39,18,24,33,21，若取 p=9, 则他们对应的散列函数值将为: 3, 3, 0, 6, 6, 3 可见，若p中含质因子3, 则所有含质因子3的关键字均映射到“3 的倍数”的地址上，从而增加了“冲突”的可能。 适用范围：除留余数法是一种最简单、最常用的构造散列函数的方法，不但可以对关键字直接取模(MOD)，也可在折叠、平方取中等运算之后取模。 比如：表长为100，可以取P=97 16

17 散列函数没有“万能”通式，要根据元素集合的特性而分别构造。
明确 散列函数没有“万能”通式，要根据元素集合的特性而分别构造。 构造散列函数的原则 实际造表时，采用何种构造散列函数的方法取决于建表的关键字集合的情况（包括关键字的范围和形态），总的原则是使产生冲突的可能性降到尽可能地小。 17

18 三、处理冲突的方法 开放定址法（开地址法） 链地址法（拉链法） 再散列法（双散列函数法） 建立一个公共溢出区 18

19 Hi=(H (key)+di) mod m ( 1≤i < m )
1、开放定址法（开地址法） 设计思路：有冲突时就去寻找下一个空的散列地址，只要散列表足够大，空的散列地址总能找到，并将数据元素存入。 具体实现： 1)线性探测法 Hi=(H (key)+di) mod m ( 1≤i < m ) 其中： H (key)为散列函数 m为散列表长度（质数） di 为增量序列 1，2，…m-1，且di=i 含义：一旦冲突，就找附近（下一个）空地址存入。 19

20 1、开放定址法（开地址法） 例5： 关键字集为 {47，7，29，11，16，92，22，8，3}， 设：散列表表长为m=11；
散列函数为H (key)=key mod 11； 拟用线性探测法处理冲突。建散列表如下： 11 16 92 22 3 29 8 47 7 △ ▲ △ △ 二次聚集：即在处理冲突的过程中发生的两个第一个散列地址不同的记录争夺同一个后继散列地址的现象。） 20

21 线性探测法的优点：只要散列表未被填满，保证能找到一个空地址单元存放有冲突的元素；
1、开放定址法（开地址法） 线性探测法的优点：只要散列表未被填满，保证能找到一个空地址单元存放有冲突的元素； 线性探测法的缺点：可能出现很多元素在相邻的散列地址上“堆积”起来（“二次聚集” ），大大降低了查找效率。 解决方案：可采用二次探测法，以改善“堆积”问题。 21

22 1、开放定址法（开地址法） 2） 二次探测法 Hi=(H (key)±di) mod m 其中：H (key)为散列函数
di为增量序列 12，-12，22，-22，…，q2 例6改用二次探测法处理冲突 11 22 3 47 92 16 7 29 8 ▲ 22

23 2、链地址法(拉链法） 基本思想：将具有相同散列地址的记录链成一个单链表，m个散列地址就设m个单链表，然后用一个数组将m个单链表的表头指针存储起来，形成一个动态的结构。 例6： 设{ 47, 7, 29, 11, 16, 92, 22, 8, 3, 50, 37, 89 }的散列函数为： H (key)=key mod 11， 用拉链法处理冲突。 1 2 3 4 5 6 7 8 9 10 22 11 89 47 37 92 29 16 50  注：有冲突的元素可以插在表尾,也可以插在表头 23

24 3、再散列法（双散列函数法） 4 、 建立一个公共溢出区 特点：构造若干个散列函数，当发生冲突时，计算下一个散列地址，直到冲突不再发生，即：
Hi=RHi(key) i=1, 2, …，k RHi均是不同的散列函数。 优点：不易产生聚集； 缺点：增加了计算时间。 4 、 建立一个公共溢出区 思路：除设立散列基本表外，另设立一个溢出向量表。 所有关键字和基本表中关键字为同义词的记录，不 管它们由散列函数得到的地址是什么，一旦发生冲突，都填入溢出表。 24

25 四、散列表的查找及性能分析 算法步骤 算法描述 在散列表上查找定值为K的记录的过程 P239 给定k值 计算H(k) Y 此地址为空?
查找失败 查找成功 按处理冲突 方法计算Hi N Y 算法步骤 在散列表上查找定值为K的记录的过程 算法描述 P239

26 四、散列表的查找及性能分析 讨论：散列存储的平均查找长度ASL是否为真正的1？ 不是。由于冲突的产生，使得散列表ASL 大于1。
选用的散列函数 选用的处理冲突的方法 散列表的装填因子

27 四、散列表的查找及性能分析 哈希表的装填因子是哈希表中填入的记录数与哈希表的长度的比值，即： 装填因子α标志哈希表的装满程序 0≤≤1
 越大，表中记录数越多，说明表装得越满，发生冲突的可能性就越大，查找时比较次数就越多。

28 讨论： 1） 散列存储的查找效率到底是多少？ 答：ASL与装填因子有关！既不是严格的O(1)，也不是O(n) 2）“冲突”是不是特别讨厌？
答：不一定！正因为有冲突，使得文件加密后无法破译（不可逆，是单向散列函数，可用于数字签名）。

29 哈希函数为：H(key)=key MOD 13, 哈希表长为m=16， 设每个记录的查找概率相等
例7 已知一组关键字(19,14,23,1,68,20,84,27,55,11,10,79) 哈希函数为：H(key)=key MOD 13, 哈希表长为m=16， 设每个记录的查找概率相等 (1) 用线性探测法处理冲突，即Hi=(H(key)+di) MOD m 14 1 68 27 55 19 20 84 79 23 11 10 H(19)=6 H(11)=11 H(14)=1 H(10)=10 冲突，H1=(10+1)MOD16=11 冲突，H2=(10+2)MOD16=12 H(23)=10 H(1)=1 冲突，H1=(1+1) MOD16=2 H(79)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 冲突，H4=(1+4)MOD16=5 冲突，H5=(1+5)MOD16=6 冲突，H6=(1+6)MOD16=7 冲突，H7=(1+7)MOD16=8 冲突，H8=(1+8)MOD16=9 H(68)=3 H(20)=7 H(84)=6 冲突，H1=(6+1)MOD16=7 冲突，H2=(6+2)MOD16=8 H(27)=1 冲突，H1=(1+1)MOD16=2 冲突，H2=(1+2)MOD16=3 冲突，H3=(1+3)MOD16=4 H(55)=3 冲突，H1=(3+1)MOD16=4 冲突，H2=(3+2)MOD16=5 ASL=(1*6+2+3*3+4+9)/12=2.5

30 (2) 用链地址法处理冲突 14 ^ 1 27 79 68 55 19 84 20 23 10 11 ASL=(1*6+2*4+3+4)/12=1.75

31 小结 散列表的概念 散列函数的构造方法 处理冲突的方法 散列表的查找及性能分析 数字分析法 平方取中法 折叠法 除留余数法
开放定址法（开地址法） 链地址法（拉链法） 再散列法（双散列函数法） 建立一个公共溢出区 散列表的查找及性能分析

32 作业 给定关键字序列11，78，10，1，3，2，4，21， 试分别用顺序查找、二分查找、散列查找(散列 函数H(k)=k%11，用线性探测法处理冲突)来实 现查找，试画出它们的对应存储形式(顺序查找 的顺序表，二分查找的判定树及散列查找的散 列表)，并求出每一种查找的成功平均查找长度。