数据结构散列表.ppt

《数据结构散列表.ppt》由会员分享，可在线阅读，更多相关《数据结构散列表.ppt（33页珍藏版）》请在优知文库上搜索。

1、7.3 散列表的查找技术散列表的查找技术顺序查找、折半查找等。顺序查找、折半查找等。这些查找技术都是通过一系列的给定值与关键码的这些查找技术都是通过一系列的给定值与关键码的比较，查找效率依赖于查找过程中进行的给定值与比较，查找效率依赖于查找过程中进行的给定值与关键码的比较次数。关键码的比较次数。查找操作要完成什么任务？查找操作要完成什么任务？待查值待查值k确定确定k在存储结构中的位置在存储结构中的位置我们学过哪些查找技术？这些查找技术的共性？我们学过哪些查找技术？这些查找技术的共性？在存储位置和关键码之间建立一个确定的对应关系在存储位置和关键码之间建立一个确定的对应关系能否不用比较，通过关键码

2、直接确定存储位置？能否不用比较，通过关键码直接确定存储位置？概概 述述散列的基本思想：散列的基本思想：在记录的存储地址和它的关键码之在记录的存储地址和它的关键码之间建立一个确定的对应关系。这样，不经过比较，一间建立一个确定的对应关系。这样，不经过比较，一次读取就能得到所查元素的查找方法。次读取就能得到所查元素的查找方法。7.3 散列表的查找技术散列表的查找技术关关键键码码集集合合ki riH( (ki) )H散列表：散列表：采用散列技术将记录存储在一块采用散列技术将记录存储在一块连续连续的存的存储空间中，储空间中，这块连续的存储空间这块连续的存储空间称为散列表。称为散列表。概概 述述7.3 散

3、列表的查找技术散列表的查找技术关关键键码码集集合合ki riH( (ki) )H散列表散列表数组数组散列函数：散列函数：将关键码映射为散列表中适当存将关键码映射为散列表中适当存储位置储位置的函数。的函数。概概 述述7.3 散列表的查找技术散列表的查找技术散列表散列表关关键键码码集集合合ki riH( (ki) )H散列函数散列函数数组数组散列地址：散列地址：由散列函数由散列函数所得的存储位置所得的存储位置 。概概 述述7.3 散列表的查找技术散列表的查找技术散列表散列表关关键键码码集集合合ki riH( (ki) )H散列函数散列函数散列地址散列地址下标下标数组数组例子例子l一组数：12，37

4、，52，43，84，99l散列函数为:H(k)=k%11l散列表： 长度为11012345678910123752438499概概 述述7.3 散列表的查找技术散列表的查找技术散列技术仅仅是一种查找技术吗？散列技术仅仅是一种查找技术吗？散列既是一种查找技术，也是一种存储技术。散列既是一种查找技术，也是一种存储技术。散列只是通过记录的关键码定位该记录，没有完散列只是通过记录的关键码定位该记录，没有完整地表达记录之间的逻辑关系，所以，散列主要整地表达记录之间的逻辑关系，所以，散列主要是是面向查找面向查找的存储结构。的存储结构。散列是一种散列是一种完整的存储结构完整的存储结构吗？吗？散列技术的关键问

5、题：散列技术的关键问题： 散列函数的设计。如何设计一个简单、均匀、存散列函数的设计。如何设计一个简单、均匀、存储利用率高的散列函数。储利用率高的散列函数。 冲突的处理。如何采取合适的处理冲突方法来解冲突的处理。如何采取合适的处理冲突方法来解决冲突。决冲突。7.3 散列表的查找技术散列表的查找技术概概 述述冲突：冲突：对于两个不同关键码对于两个不同关键码kikj，有，有H( (ki) )H( (kj) )，即两个不同的记录即两个不同的记录需要存放在同一个存储位置需要存放在同一个存储位置, ,ki和和kj相对于相对于H称做称做同义词同义词。 7.3 散列表的查找技术散列表的查找技术概概 述述 ri

6、关关键键码码集集合合kiH(ki)kjH(kj)散列函数散列函数7.3 散列表的查找技术散列表的查找技术设计散列函数一般应遵循以下原则：设计散列函数一般应遵循以下原则： 计算计算简单简单。散列函数不应该有很大的计算量，否。散列函数不应该有很大的计算量，否则会降低查找效率。则会降低查找效率。 函数值即散列地址分布函数值即散列地址分布均匀均匀。函数值要尽量均匀。函数值要尽量均匀散布在地址空间，这样才能保证存储空间的有效利散布在地址空间，这样才能保证存储空间的有效利用并减少冲突。用并减少冲突。1 1、散列函数、散列函数直接定址法直接定址法散列函数是关键码的线性函数散列函数是关键码的线性函数，即：即：

7、H(key) = a key + b （a，b为常数）为常数）例：关键码集合为例：关键码集合为10, 30, 50, 70, 80, 90，选取的散，选取的散列函数为列函数为H( (key) )=key/10，则散列表则散列表为：为： 0 1 2 3 4 5 6 7 8 9103050708090适用情况？适用情况？事先知道关键码，关键码集合不是很大且连续性较好。事先知道关键码，关键码集合不是很大且连续性较好。 7.3 散列表的查找技术散列表的查找技术散列函数为：散列函数为：H( (key) )=key mod p 7.3 散列表的查找技术散列表的查找技术2 2、散列函数、散列函数除留余数法除

8、留余数法如何选取合适的如何选取合适的 p，产生较少同义词？，产生较少同义词？一般情况下，选一般情况下，选p为小于或等于表长（最好接近表长）为小于或等于表长（最好接近表长）的最小素数。的最小素数。适用情况？适用情况？除留余数法是一种最简单、也是最常用的构造散列除留余数法是一种最简单、也是最常用的构造散列函数的方法，并且不要求事先知道关键码的分布。函数的方法，并且不要求事先知道关键码的分布。 根据关键码在各个位上的分布情况，选取分布比较根据关键码在各个位上的分布情况，选取分布比较均匀均匀的若干位组的若干位组成散列地址。成散列地址。 例：关键码为例：关键码为8位十进制数，散列地址为位十进制数，散列地

9、址为2位十进制数位十进制数8 1 3 4 6 5 3 28 1 3 7 2 2 4 28 1 3 8 7 4 2 28 1 3 0 1 3 6 78 1 3 2 2 8 1 7 8 1 3 3 8 9 6 7 7.3 散列表的查找技术散列表的查找技术3 3、散列函数、散列函数数字分析法数字分析法适用情况适用情况:能预先估计出全部关键码的每一位上各种数字出现能预先估计出全部关键码的每一位上各种数字出现的频度，不同的关键码集合需要重新分析。的频度，不同的关键码集合需要重新分析。7.3 散列表的查找技术散列表的查找技术3 3、散列函数、散列函数数字分析法数字分析法对关键码平方后，按散列表大小，取中间

10、的若干位作对关键码平方后，按散列表大小，取中间的若干位作为散列地址（为散列地址（平方平方后后截取截取）。）。 7.3 散列表的查找技术散列表的查找技术4 4、散列函数、散列函数平方取中法平方取中法事先不知道关键码的分布且关键码的位数不是很大。事先不知道关键码的分布且关键码的位数不是很大。适用情况适用情况:例：散列地址为例：散列地址为2位，则关键码位，则关键码123的散列地址为：的散列地址为：(1234)21522756将关键码从左到右分割成位数相等的几部分，将这几将关键码从左到右分割成位数相等的几部分，将这几部分叠加求和，取后几位作为散列地址。部分叠加求和，取后几位作为散列地址。 7.3 散列

11、表的查找技术散列表的查找技术5 5、散列函数、散列函数折叠法折叠法例：设关键码为例：设关键码为2 5 3 4 6 3 5 8 7 0 5，散列地址为三位。，散列地址为三位。 2 5 3 4 6 3 5 8 7 + 0 5 1 3 0 8 移位叠加移位叠加 2 5 3 3 6 4 5 8 7 + 5 0 1 2 5 4 间界叠加间界叠加适用情况适用情况:关键码位数很多，事先关键码位数很多，事先不知道关键码的分布。不知道关键码的分布。 1 1、处理冲突的方法、处理冲突的方法开放定址法开放定址法由关键码得到的散列地址一旦产生了冲突，就去寻找由关键码得到的散列地址一旦产生了冲突，就去寻找下一个空下一个

12、空的散列地址，并将记录存入。的散列地址，并将记录存入。 如何寻找下一个空的散列地址如何寻找下一个空的散列地址?7.3 散列表的查找技术散列表的查找技术（1）线性探测法）线性探测法（2）二次探测法）二次探测法（3）随机探测法）随机探测法（1）线性探测法）线性探测法当发生冲突时，从冲突位置的下一个位置起，依次当发生冲突时，从冲突位置的下一个位置起，依次寻找空的散列地寻找空的散列地址。址。 对于键值对于键值key，设，设H( (key) )=d，闭散列表的长度为，闭散列表的长度为m，则发生冲突时，寻找下一个散列地址的公式为：则发生冲突时，寻找下一个散列地址的公式为： Hi=( (H( (key) )

13、di) ) % m （di=1，2，m- -1） 7.3 散列表的查找技术散列表的查找技术用开放定址法处理冲突得到的散列表叫用开放定址法处理冲突得到的散列表叫闭散列表闭散列表。 例：关键码集合为例：关键码集合为 47, 7, 29, 11, 16, 92, 22, 8, 3，散，散列表表长为列表表长为11，散列函，散列函数为数为H( (key) )=key mod 11，用，用线性探测法处理冲突，则构造的散列表为：线性探测法处理冲突，则构造的散列表为： 0 1 2 3 4 5 6 7 8 947729111692292222883333堆积：堆积：在处理冲突的过程中出现的在处理冲突的过程中出现

14、的非同义词非同义词之间对之间对同一个散列地址争夺的现象同一个散列地址争夺的现象。7.3 散列表的查找技术散列表的查找技术（1）线性探测法）线性探测法用线性探测法构造的散列表中查找算法用线性探测法构造的散列表中查找算法伪代码伪代码1. 计算散列地址计算散列地址j;2. 若若htj=k，则查找成功，返回记录在散列表中的下标；，则查找成功，返回记录在散列表中的下标； 否则否则3. 若若htj为空或将散列表探测一遍，则查找失败，转为空或将散列表探测一遍，则查找失败，转4； 否则，否则，j指向下一单元，转指向下一单元，转2；4. 若整个散列表探测一遍，则表满，抛出溢出异常；若整个散列表探测一遍，则表满，

15、抛出溢出异常； 否则，将待查值插入；否则，将待查值插入；7.3 散列表的查找技术散列表的查找技术int HashSearch1(int ht , int m, int k) int j=k%m;if (htj=k) return j; /没有发生冲突，比较一次查找成功没有发生冲突，比较一次查找成功 int i=(j+1) % m; while (i!=j) if (hti=k) return i; /发生冲突发生冲突 if(hti=0) break;i=(i+1) % m ;/向后探测一个位置向后探测一个位置 if (i=j) throw 溢出溢出; else hti=k; return i;

16、7.3 散列表的查找技术散列表的查找技术在线性探测法构造的散列表中查找算法在线性探测法构造的散列表中查找算法C+描述描述（2）二次探测法）二次探测法当发生冲突时，寻找下一个散列地址的公式为：当发生冲突时，寻找下一个散列地址的公式为： Hi=( (H( (key) )di) )% m（di=12，12，22，22，q2，q2且且qm/2） 7.3 散列表的查找技术散列表的查找技术 0 1 2 3 4 5 6 7 8 94772911169229222288333例：关键码集合为例：关键码集合为 47, 7, 29, 11, 16, 92, 22, 8, 3，散，散列表表长为列表表长为11，散列函，散列函数为数为H( (key) )=key mod 11，用，用二次探测法处理冲突，则散列表为：二次探测法处理冲突，则散列表为：（2）二次探测法）二次探测法7.3 散列表的查找技术散列表的查找技术（3）随机探测法）随机探测法当发生冲突时，下一个散列地址的位移量是一个随当发生冲突时，下一个散列地址的位移量是一个随机数列，即机数列，即寻找下一个散列地址的公式寻找下一个散列地址的公式为：为： Hi=(