数据结构散列表精品文稿.ppt

《数据结构散列表精品文稿.ppt》由会员分享，可在线阅读，更多相关《数据结构散列表精品文稿.ppt（34页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数据结构散列表第1 页，本讲稿共34 页7.3 散列表的查找技术顺序查找、折半查找等。这些查找技术都是通过一系列的给定值与关键码的比较，查找效率依赖于查找过程中进行的给定值与关键码的比较次数。查找操作要完成什么任务？待查值k确定k 在存储结构中的位置我们学过哪些查找技术？这些查找技术的共性？在存储位置和关键码之间建立一个确定的对应关系能否不用比较，通过关键码直接确定存储位置？第2 页，本讲稿共34 页概 概 述 述散列的基本思想：散列的基本思想：在记录的存储地址和它的关键码之 在记录的存储地址和它的关键码之间建立一个确定的对应关系。这样，不经过比较，一 间建立一个确定的对应关系。这样，不经过比

2、较，一次读取就能得到所查元素的查找方法。次读取就能得到所查元素的查找方法。7.3 散列表的查找技术关键码集合ki riH(ki)H第3 页，本讲稿共34 页散列表：散列表：采用散列技术将记录存储在一块 采用散列技术将记录存储在一块连续 连续的存储 的存储空间中，空间中，这块连续的存储空间 这块连续的存储空间称为散列表。称为散列表。概 概 述 述7.3 散列表的查找技术关键码集合ki ri H(ki)H散列表数组第4 页，本讲稿共34 页散列函数：散列函数：将关键码映射为散列表中适当存 将关键码映射为散列表中适当存储位置的 储位置的函数。函数。概 概 述 述7.3 散列表的查找技术散列表关键码集

3、合ki riH(ki)H散列函数数组第5 页，本讲稿共34 页散列地址：散列地址：由散列函数 由散列函数所得的存储位置 所得的存储位置。概 概 述 述7.3 散列表的查找技术散列表关键码集合ki riH(ki)H散列函数散列地址下标数组第6 页，本讲稿共34 页例子l 一组数：12，37，52，43，84，99l 散列函数为:H(k)=k%11l 散列表：长度为110 1 2 3 4 5 6 7 8 9 1012 37 52 43 84 99第7 页，本讲稿共34 页概 概 述 述7.3 散列表的查找技术散列技术仅仅是一种查找技术吗？散列既是一种查找技术，也是一种存储技术。散列只是通过记录的关

4、键码定位该记录，没有完整地表达记录之间的逻辑关系，所以，散列主要是面向查找的存储结构。散列是一种完整的存储结构吗？第8 页，本讲稿共34 页散列技术的关键问题：散列技术的关键问题：散列函数的设计。如何设计一个简单、均匀、存储 散列函数的设计。如何设计一个简单、均匀、存储利用率高的散列函数。利用率高的散列函数。冲突的处理。如何采取合适的处理冲突方法来解决 冲突的处理。如何采取合适的处理冲突方法来解决冲突。冲突。7.3 散列表的查找技术概 概 述 述第9 页，本讲稿共34 页冲突：冲突：对于两个不同关键码 对于两个不同关键码k ki i k kj j，有，有H H(k ki i)H H(k kj

5、j)，即两个不同的记录 即两个不同的记录需要存放在同一个存储位置 需要存放在同一个存储位置,k ki i和 和k kj j相对于 相对于H H称做 称做同义词 同义词。7.3 散列表的查找技术概 概 述 述 ri关键码集合ki H(ki)kjH(kj)第10 页，本讲稿共34 页散列函数 散列函数7.3 散列表的查找技术设计散列函数一般应遵循以下原则：设计散列函数一般应遵循以下原则：计算 计算简单 简单。散列函数不应该有很大的计算量，否。散列函数不应该有很大的计算量，否则会降低查找效率。则会降低查找效率。函数值即散列地址分布 函数值即散列地址分布均匀 均匀。函数值要尽量均匀。函数值要尽量均匀散

6、布在地址空间，这样才能保证存储空间的有效利 散布在地址空间，这样才能保证存储空间的有效利用并减少冲突。用并减少冲突。第11 页，本讲稿共34 页1 1、散列函数、散列函数 直接定址法 直接定址法散列函数是关键码的线性函数，即：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 910 30 50 70 80 90适用情况？事先知道关键码，关键码集合不是很大且连续性较好。7.3 散列表的查找技术第12 页，本讲稿共34 页散列函数为：H(key)=key mod

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

8、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、散列函数、散列函数 数字分析法 数字分析法第14 页，本讲稿共34 页适用情况:能预先估计出全部关键码的每一位上各种数字出现的频度，不同的关键码集合需要重新分析。7.3 散列表的查找技术3 3、散列函数、散列函数 数字分析法 数字分析法第15 页，本讲稿共34 页对关键码平方后，按散列表大小，取中间的若干位作为散列地址（平方后截取）。7.3 散列表的查找技术4 4、散列函数、散列函数 平方取中法 平方取中法事先不知道关键码的分布且关键码的位数不是很大。适用情况:例：散

9、列地址为2位，则关键码123的散列地址为：(1234)21522756第16 页，本讲稿共34 页将关键码从左到右分割成位数相等的几部分，将这几部分叠加求和，取后几位作为散列地址。7.3 散列表的查找技术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 间界叠加适用情况:关键码位数很多，事先不知道关键码的分布。第17 页，本讲稿共34 页1 1、处理冲突的方法、处理冲突的方法 开放定址法 开放定址法由

10、关键码得到的散列地址一旦产生了冲突，就去寻找下一个空的散列地址，并将记录存入。如何寻找下一个空的散列地址?7.3 散列表的查找技术（1）线性探测法（2）二次探测法（3）随机探测法第18 页，本讲稿共34 页（1）线性探测法当发生冲突时，从冲突位置的下一个位置起，依次寻找空的散列地址。对于键值key，设H(key)=d，闭散列表的长度为m，则发生冲突时，寻找下一个散列地址的公式为：Hi=(H(key)di)%m（di=1，2，m-1）7.3 散列表的查找技术用开放定址法处理冲突得到的散列表叫闭散列表。第19 页，本讲稿共34 页例：关 键 码 集 合 为 47,7,29,11,16,92,22,

11、8,3，散列 表 表 长 为11，散 列 函 数 为H(key)=key mod 11，用 线性探测法处理冲突，则构造的散列表为：0 1 2 3 4 5 6 7 8 94772911 16 92 292222883 333堆积：在处理冲突的过程中出现的非同义词之间对同一个散列地址争夺的现象。7.3 散列表的查找技术（1）线性探测法第20 页，本讲稿共34 页用线性探测法构造的散列表中查找算法伪代码1.计算散列地址j;2.若htj=k，则查找成功，返回记录在散列表中的下标；否则3.若htj 为空或将散列表探测一遍，则查找失败，转4；否则，j 指向下一单元，转2；4.若整个散列表探测一遍，则表满，

12、抛出溢出异常；否则，将待查值插入；7.3 散列表的查找技术第21 页，本讲稿共34 页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;7.3 散列表的查找技术在线性探测法构造的散列表中查找算法C+描述第22 页，本讲稿共34 页（2）二次探测法当发

13、生冲突时，寻找下一个散列地址的公式为：Hi=(H(key)di)%m（di=12，12，22，22，q2，q2且qm/2）7.3 散列表的查找技术第23 页，本讲稿共34 页 0 1 2 3 4 5 6 7 8 947 72911 16 92 29222288333例：关 键 码 集 合 为 47,7,29,11,16,92,22,8,3，散 列 表 表 长 为11，散 列 函 数 为H(key)=key mod 11，用二次探测法处理冲突，则散列表为：（2）二次探测法7.3 散列表的查找技术第24 页，本讲稿共34 页（3）随机探测法当发生冲突时，下一个散列地址的位移量是一个随机数列，即寻找

14、下一个散列地址的公式为：Hi=(H(key)+di)%m（di是一个随机数列，i=1，2，m-1）7.3 散列表的查找技术计算机中产生随机数的方法通常采用线性同余法，其 中，d称 为 随 机 种 子。当b、c 和m 的 值 确 定 后，给定一个随机种子，产生确定的随机数序列。0=d a=+=-1,2,Lmod)(1n m c ba an n第25 页，本讲稿共34 页基本思想：将所有散列地址相同的记录，即所有同义词的记录存储在一个单链表中（称为同义词子表），在散列表中存储的是所有同义词子表的头指针。用拉链法处理冲突构造的散列表叫做开散列表。设n个记录存储在长度为m 的散列表中，则同义词子表的平

15、均长度为n/m。7.3 散列表的查找技术2 2、处理冲突的方法、处理冲突的方法 拉链法（链地址法）拉链法（链地址法）第26 页，本讲稿共34 页例：关键码集合 47,7,29,11,16,92,22,8,3，散列函数为H(key)=key mod 11，用拉链法处理冲突，构造的开散列表为：7.3 散列表的查找技术 0 1 2 3 4 5 6 7 8 910 11 22 47 3 92 16 7 29 8 第27 页，本讲稿共34 页在拉链法构造的散列表查找算法伪代码1.计算散列地址j；2.在第j 个同义词子表中顺序查找；3.若查找成功，则返回结点的地址；否则，将待查记录插在第j 个同义词子表的

16、表头。7.3 散列表的查找技术第28 页，本讲稿共34 页Node*HashSearch2(Node*ht,int m,int k)j=H(k);p=htj;while(p&p-data!=k)p=p-next;if(p-data=k)return p;else q=new Node;q-data=k;q-next=htj;htj=q;7.3 散列表的查找技术在拉链法构造的散列表查找算法C+描述第29 页，本讲稿共34 页基本思想：散列表包含基本表和溢出表两部分（通常溢出表和基本表的大小相同），将发生冲突的记录存储在溢出表中。查找时，对给定值通过散列函数计算散列地址，先与基本表的相应单元进行比

17、较，若相等，则查找成功；否则，再到溢出表中进行顺序查找。7.3 散列表的查找技术3 3、处理冲突的方法、处理冲突的方法 公共溢出区 公共溢出区第30 页，本讲稿共34 页例：关键码集合 47,7,29,11,16,92,22,8,3，散列函数为H(key)=key mod 11，用公共溢出区法处理冲突，构造的散列表为：7.3 散列表的查找技术 0 1 2 3 4 5 6 7 8 910 基本表 溢出表 11 47 92 16 7 8 0 1 2 3 4 5 6 7 8 910 29 22 3 第31 页，本讲稿共34 页散列查找的性能分析 散列查找的性能分析 由于冲突的存在，产生冲突后的查找仍

18、然是给定值与关键码进行比较的过程。在查找过程中，关键码的比较次数取决于产生冲突的概率。而影响冲突产生的因素有：（1）散列函数是否均匀（2）处理冲突的方法（3）散列表的装载因子=表中填入的记录数/表的长度7.3 散列表的查找技术第32 页，本讲稿共34 页查找成功时 查找不成功时线性探测法二次探测法拉链法ASL处理冲突方法几种不同处理冲突方法的平均查找长度7.3 散列表的查找技术第33 页，本讲稿共34 页开散列表与闭散列表的比较 开散列表与闭散列表的比较7.3 散列表的查找技术不产生产生有没有堆积现象 结构开销 插入/删除 查找效率开散列表闭散列表效率高效率低效率高效率低估计容量不需要需要第34 页，本讲稿共34 页