《数据结构》5散列表课件.ppt

《《数据结构》5散列表课件.ppt》由会员分享，可在线阅读，更多相关《《数据结构》5散列表课件.ppt（49页珍藏版）》请在三一办公上搜索。

1、6、纪律是自由的第一条件。黑格尔7、纪律是集体的面貌，集体的声音，集体的动作，集体的表情，集体的信念。马卡连柯8、我们现在必须完全保持党的纪律，否则一切都会陷入污泥中。马克思9、学校没有纪律便如磨坊没有水。夸美纽斯10、一个人应该：活泼而守纪律，天真而不幼稚，勇敢而鲁莽，倔强而有原则，热情而不冲动，乐观而不盲目。马克思,牛小飞数据结构5散列表,牛小飞数据结构5散列表6、纪律是自由的第一条件。黑格尔7、纪律是集体的面貌，集体的声音，集体的动作，集体的表情，集体的信念。马卡连柯8、我们现在必须完全保持党的纪律，否则一切都会陷入污泥中。马克思9、学校没有纪律便如磨坊没有水。夸美纽斯10、一个人应该：

2、活泼而守纪律，天真而不幼稚，勇敢而鲁莽，倔强而有原则，热情而不冲动，乐观而不盲目。马克思牛小飞数据结构5散列表散列表散列函数的构造方法处理冲突的方法散列表的查找算法散列表的查找分析小结和作业课堂练习散列的基本思想散列的基本思想已讲查找表的共同特点：记录在表中的位置和它的关键字之间不存在一个确定的关系；查找的过程为给定值依次和关键字集合中各个关键字进行比较；查找的效率取决于和给定值进行比较的关键字个数。,Abstract：It is an inevitable choice for higher vocational colleges because the diversification of

3、 students.There are some difficulties for example how to adopt the multi-level teaching and the against of students and their parents.According to the requirements of students entry level and future development of students stratification，different levels of students have appropriate learning goals，t

4、eaching experiment has achieved good results，but put forward higher expectations.0 引言 孔子在长期教育实践中首创的一个经典教育原则“因材施教”，在现代依然适用。我国高职院校近几年由于受普通高考生源减少的影响，各院校为了保证生源数量而采取多种形式的招生。面对不同学习基础、学习能力和学习兴趣的学生，实行分层次教学将有利于学生的成长。1 分层次教学改革需克服的困难 分层次教学有助于改变传统教学的“一刀切”，从社会需求出发，结合学生基础、兴趣、学习能力及目标来教学是顺应教学改革潮流，符合国家大力发展现代职业教育的目标要

5、求。但是分层次教学改革还存在以下几个现实问题：1.1 如何科学的分层 分层次教学首先要把学生分为不同层次，分层的依据是什么？现在高职院校生源的多样性、学生兴趣和学生的目标都会影响分层的具体实施。同时做为学校本身的运转来说，我们还必须要分班上课，如何分层才能有利于学生的发展，真正做到以“学生为本”是一个难点。1.2 分到低层次学生及家长对分层教学的抵触 分层次教学首先要做的是把学生划分为高层次和低层次。从心理学的角度来说，分到高层次班的学生自然乐于接受，但被分到低层次班级的学生就会产生低人一等的自卑心理。在我国现阶段还是一个关系社会的现状来看，被分到低层次班级的家长们就会寻找关系力争进入高层次班

6、级。而且这种抵触不会自动减少，只有通过教学效果才能证明分层教学对学生有益，但这需要长时间的实践及成效才能改变学生及其家长的认识。1.3 教师对分层次教学的抵触 教师大多已经形成自己的教学理念，开展分层次教学改革要改变已经熟悉的教学方法，拿出很多的精力针对不同层次的学生设计教学内容、教学方法，这必然影响教师已经熟悉的教学节奏和教学方式。在当前职称评定规则下，论文和课题是职称晋级的主要依据，因此教师的精力更愿意放在发表论文和争取课题方面。同时教师对于分层次教学还有一个担忧，如果把好学生都集中到一个班里，那剩下的学生就更难教，在这样的班级教学对教师的能力是一个挑战。2 学院在分层次教学中的积极探索

7、2.1 不同来源学生的特点分析 现在河北女子职业技术学院的学生来源有普通高考、对口招生、单招、“3+2”转段生和提前介入的学生。普通高考是指参加了高考的学生。对口招生是指普通高校对口招收中等职业学校和综合高中职高班的应历届毕业生，需要参加文化课、专业基础课和专业课的考试。达到一定分数线可以进入学院学习。单招是就针对三校生（中专，中技，中职）以及应往届高中毕业生而言，这些学生参加学院的单招考试，单招考试分文化课和专业课，成绩符合要求，可进入学院学习。“3+2”转段生是指三年中专学习结束不需要参加考试直接升入高职院校的学生。提前介入学生是指准备第二年参加学校单招考试，但当年进校学习。作为一线教师，

8、大家最喜欢的授课对象是普通高考的学生。普高学生一般接受能力强、纪律性好，有一定的目标，对新知识有渴求。其中部分学生有强烈的求知欲，对于自己高中的学习不满意，进入大学之后因成绩较好，重新建立了信心，因而希望毕业之后专升本，进入更高一级院校学习。同时部分学生因为高考总分一百多分，她们学习能力较差，不愿意学习，很多好学生是被家长逼着上学，只为了混一个大专文凭容易找工作。对口招生的学生具有会计的基础知识，但由于来源不同，基础也不相同。有的学生来源于职高，为了对口升学，只学对口招生考试中一部分知识；而有的学校重视学生的发展，学习的内容较多，对会计基本技能掌握较好。单招的学生组成更加复杂，含中职、中技毕业

9、生，具有高中同等学力考生及往届高中毕业生，其中中职、中技毕业生中有会计类中职对口单招，也有其他专业的中职生，因为在学习过程中不喜欢原来的专业而转学会计。“3+2”转段生的特点是中考没有考上普通高中，因此这部分学生普遍学习习惯不好。但是这部分学生有一个优点就是经过了三年的中专学习，有一定的基础，有部分学生还取得了会计从业资格证。同时通过学习，对会计专业产生了兴趣。尤其是在中职学习过程中，一些学生在技能竞赛中获奖，增强了学习的信心。2.2 确定学院会计专业的培养目标 立足于学院生源的实际情况，契合当地中小企业众多及历届学生就业单位，确定会计专业的培养目标是适应中小企业的会计专业技术人才。会计专业的

10、培养目标共分为三个层次：取得会计从业资格证、取得初级会计师证书、参加会计技能大赛。学生最低培养层次为经过专科阶段的学习，能够掌握会计专业的基本知识取得会计从业资格证书，这个层次要求100%同学达到。在取得从业资格证书的基础上，通过课内教学和课外多种先进技术的运用，比如微课以及视频课件，一部分优秀的学生取得初级会计职称。在取得初级会计职称的基础上，选拔一部分同学进行培优教学，参加省级和全国会计技能大赛，进一步提高学生的会计技能，另一方面也提高学院的社会影响力。2.3 对学生分层次的依据 依据学院的培养目标和学生基础情况，对学生进行分层。普高的学生依据高考分数分层，对口和单招的学生则结合单招分数及

11、是否取得会计从业资格证进行分层，一学期结束之后则进行全面考试，这样处于低层次的同学可以由原来班级转到高层次班级学习。“3+2”转段的学生因为到学院的学习时间只有两年，“3+2”学生如果人数多则依据是否有会计证进行分层，如果人数少则单独成班，实行班内分层教学。2.4 各层次的教学目标 对每一层次学生的教学目标是不一致的。学生的主观努力不同，同时客观的学习基础、学习能力也不同，在同样的时间内，能够达到的目标也是不一样的。对没有会计基础的和原来学习基础较差的采用适合的教学目标，要求学生在他原来的基础上每天都有进步，而不强求每个学生每天进步的程度相同。因此，教师在讲授时，不是要在一定时间内把知识讲完，

12、而是依据学生的接受能力合理安排教学进度、教学深度，一切以学生为本。2.5 教学实施 只要是分班上课，即使做了班际分层，在每个班中仍存在不同的层次。为了弥补学生层次的不同而教师在课内难以顾及的情况，采取课外多种形式的补充。首先，针对课内某一个难点，做成微课，发到QQ群中，学生可以随时在课下学习。其次，购买会计证考试网校视频及会计练习软件，学生在课下可以根据自己的实际情况确定自己的学习进度。第三，为了帮助已取得会计证的学生参加初级会计师的考试，在周二及周五的下午开展选修课，由教师讲解初级实务和经济法的相关课程。因为初级会计师的个别知识点对高职的学生来说难度较大，在课上的讲解中有些内容可能没有涉及，

13、所以课外的辅导是对课内的有效补充，同时通过这种方式也能促进学生学习。最后，为了参加全省会计技能竞赛和全国会计技能竞赛，从已通过会计证和参加初级会计师课外班的同学中选择一批学生参加竞赛培训。技能竞赛不仅要求学生具有良好的会计基础知识，还要具有良好的心理承受能力以及灵活运用所学知识的能力，同时对会计技能的要求较高。通过竞赛培训可以进一步提高接受能力强和对会计感兴趣学生的会计知识水平、运用能力等，这是学院最高层次的培养目标。3 分层次教学的效果分析及展望 3.1 分层次教学取得的效果 分层次教学以后，尽管学生生源情况并没有改善，但学生取得会计证的比例大幅提升，通过初级会计师的人数也有所增加，并且在全

14、省会计技能比赛中多次取得第一名的成绩，同时在2015全国会计技能比赛中取得了二等奖的成绩，这也是河北省在全国会计技能比赛中的最好成绩，同时提高了学校的社会美誉度。3.2 对分层次教学的展望 首先，学院的分层次教学主要体现是班际分层。但在以班为单位教学的情况下，班内同学的层次也不尽相同。如何在班内实现分层次教学，使每一个学生都能得到恰当的关注，实现个人的最优化发展，这是分层次教学要努力实现的终极目标。其次，创建真实的实践环境。不同层次的学生，都更乐于接受实践教学，尤其是学习能力相对较差的学生，学生动手去做比单纯讲授效果要好。基于会计专业的特殊性，不可能象一些机械制造等专业一样，一个企业接受大批的

15、实习生，但可以利用先进的科学技术创造高仿真的实践环境，提高学生的学习兴趣及主动学习的愿望，并由此改变学习习惯，才是教育最终要达到的目标。我国的基础音乐教育缘起于中国近代的学堂乐歌，从学习外国的基本乐理，走了一条从模仿开始的道路。以西方音乐教育为鉴，逐渐结合我国城乡的学生实际情况，摸索出可行的办法，这种模式至今为止也是通行不悖的。高师音乐理论教学的改革已进行多年，从教学大纲、教学法、教材、课程设置等层层深入，取得了一定成绩，然而基础与速成，技能与素质的矛盾仍然没有很好地解决。国内对于本科院校和高师音乐专业音乐理论教学的研究成果比较多，但针对初招六年制定向本科培养这种特色专业的音乐基础教学研究几乎

16、没有。本课题从我院的特殊情况出发，结合国外和国内的最新教学方法，力图对实践教学做一定的研究并贯穿到日常的课堂之中。国内外研究溯源与评述：中西音乐教育的最终理想都是为了陶冶人的性情，给漫漫人生带来无以言表的快乐和感动。古希腊的“七艺”以及孔子所推崇的“六艺”都给了音乐教育极高的地位和极重的分量。西方音乐的教育一直在信仰的圣殿中进行，通过歌唱圣咏，以及弹奏圣乐最大程度地接近纯净心灵。中国的则是贯穿在整体的教育之中，我们现在所赏析的伟大五言诗歌，七言绝句无不是当时配乐的歌词，只不过音乐已经流逝而词句长存。到近现代，由于中国没有统一的记谱方法，音乐理论在每个朝代都没有经过系统的整编，所以借鉴西方的记谱

17、法以及完整的音乐理论体系无疑是唯一的出路。学堂乐歌是我国近现代音乐教育的开始，它通过学习基本乐理到掌握演唱艺术歌曲开始塑造了一个可以为后世沿用的稳固教学框架。西方完整的音乐教育法被人归纳且发扬也是20世纪才出现的，具体有以下三种：德国奥尔夫教学法、瑞士克罗齐律动教学法以及匈牙利柯达伊教学法。综观目前的音乐教育，无论哪一项都脱离不了这三种模式的影响。只不过，我国目前的音乐教育理论仍然大大落后于新的实际，对于西方的学习以及国内情况的摸索依旧有一段艰苦的长路须走。很多人认为音乐理论是高深莫测的，国外音乐教育从儿童开始就非常重视，三种教育体系几乎都是针对儿童所展开的音乐教学，并且有不同年龄阶段教学重点

18、的区分。可以说，从幼儿到大学音乐课教学都有其一整套完善的教学模式。音乐基础与声乐课、视唱练耳课不同之处在于，它的范围已经足以涵盖到这些方向，学习乐理、音乐史与练习听觉和唱曲能力是需要交织进行的，没有好的理论基础，可以说其他音乐的项目都无以为继。高师音乐理论课程多年以来沿袭声乐、器乐、理论的三重框架。其中，理论是所有的依托。湖南第一师范学院的初招六年制定向本科培养是该校的特色专业培养，同样也是全国的初招六年制教育示范点。面对零基础入读的学生，如何构建完善且针对性强的课程体系，如何在常规教学上进行创新，与以后的六年制基础钢琴学习和全面音乐素质教育联系起来，是需要思考斟酌的问题。首先，初招六年制定向

19、本科培养的音乐基础课程教学方法的创新离不开优化音乐理论课程体系。我们面对的受众是农村初中毕业生，他们大多并没有接受过系统的音乐学习。音乐基础课程对于他们首先是扫盲然后才是逐步引导到正轨上。虽然音乐基础课程是一个课程栏目，但其中涉及到视唱练耳、合唱指挥、音乐理论、中西音乐史、音乐欣赏及歌曲教唱等各方面。每一个方向都可以独立成为课程栏目，但由于学制的特殊，我们只有两年的时间却需要教会如此多的内容，在这一前提下，一元化的教学层次转变为多元化立体化的教学，无论对于教师还是学生都提高了要求，可以称得上是教育的挑战。优化音乐课程理论体系意味着对音乐课程进行整合。这个理念是关于音乐教育发展的一种理想的范式之

20、一，它能够反映出音乐教育的本质特点。在音乐教育实践中，如何正确理解音乐课程整合理念，如何把音乐课程整合理念融会贯通并落实于高师音乐教育课程改革的具体实践中，都是值得关注的重要问题。音乐理论属于音乐教育中的基础教育，纵观21世纪基础教育改革的全球化视野中，课程的改革与研究一直是非常重要的组成部分。但不管课程改革如何在理论上具有全面性、逻辑性、现实性、前瞻性，在实践上最终需要“人”去做，去完成。担当重要角色的首先是广大中小学教师。而高等师范院校承担者培养中小学教师的历史重任，因此可以说高师教育的优劣与否，直接关系着基础教育改革的成败。我们所教授的学生，以后会回到定点的家乡，大多数从事小学教育工作。

21、音乐基础课程将为他们从事音乐课打下稳固的基础。农村小学不分科，往往老师需要一专多能，我们的六年制音乐基础课程的多样性正好满足了这个要求。其次，全日制义务教育音乐课标准（实验稿）的颁布，明确地把审美和情感教育确定为音乐教育的核心。因此，重新构建高师音乐教育中六年制音乐基础课程的教学方法是非常有必要的。课程体系建设要以实现基础教育课程改革纲要（试行）要求为前提，以设计为学生提供投入少、收获大的教育教学服务方案为思路，以培养学生的创造能力，提高学生的人文素质，培养学生终身学习能力，实现学生教育教学能力的个性化发展为目标，以实现课程资源社会效益最大化为原则对高师音乐教育专业传统专业技巧课的调整。正因为

22、小学教育专业是湖南第一师范学院的特色专业，并且学校小学教育专业培养目标定位在“多科型”，即培养的学生既可担任小学语文、数学两门课程的教学，又能兼教一到两门其他课程。基础音乐教育对教师歌唱能力的有比较高的要求，它将歌唱审美与欣赏、歌唱表演、歌曲整合。音乐基础课程中的大量视唱小曲不仅可以为学生提供音准乐感的联系，教师在教学中也可以逐步渗透基本的练声方式，演唱技法。在以后的实践中，音乐课最主要的便是歌曲教唱，掌握专业的声乐教唱方法可以为日后的教学增添专业的基石。而在乐理方面，没有乐理的基础，音乐的学习可以说无法前行。六年制课本中的乐理学到和弦，这就意味着课程设置仅次于专业音乐师范生，且这些学习的积累

23、已足够应付以后的小学音乐教学实践。对于任何对西方教学或者国内最新教学方法的实践都是怀着开放的态度，只不过六年制的特殊性，应该因地制宜因材施教，不能求创新而创新。对于学生来说，掌握音乐基础课程的基本知识是重中之重。音乐基础课程应变成一种动态的、生长性的“生态系统”和完整文化，这意味着课程观的重大变革。在这种背景下，高师音乐教育教学改革才能真正进入教育的内核，成为课程整合与发展的推动力，成为教师与学生追求主体性、获得解放的过程。,若以下标为000 999 的顺序表来表示。,例如：为每年招收的1000名新生建立一张查找表，其关键字为学号，其值的范围为xx000 xx999(前两位为年份)。,则查找过

24、程可以简单进行：取给定值（学号）的后三位，不需要经过比较便可直接从顺序表中找到待查关键字。,散列的基本思想,散列的基本思想,因此在一般情况下，需在关键字与记录在表中的存储位置之间建立一个函数关系，以 f(key)作为关键字为 key 的记录在表中的位置，通常称这个函数 f(key)为哈希函数。,Zhao,Qian,Sun,Li,Wu,Chen,Han,Ye,Dei,例：对于如下9个关键字,设 散列函数 f(key)=(Ord(第一个字母)/2,散列的基本思想举例,Chen,Zhao,Qian,Sun,Li,Wu,Han,Ye,Dei,序号,问题:若添加关键字Zhou,怎么办？,Zhao,Qia

25、n,Sun,Li,Wu,Chen,Han,Ye,Dei,由此可见，,1)散列(Hash)函数是一个将关键字的集合映射到某个地址集合上，它的设置很灵活，只要这个地址集合的大小不超出允许范围即可；,2)对不同的关键字可能得到同一散列地址，即：key1 key2，而 f(key1)=f(key2),因此，很容易产生“冲突”现象；,散列的基本思想结论,3)很难找到一个不产生冲突的散列函数。一般情况下，只能选择恰当的散列函数，使冲突尽可能少地产生。,因此，在构造这种特殊的“查找表”时，除了需要选择一个“好”(尽可能少产生冲突)的散列函数之外；还需要找到一种“处理冲突”的方法。,散列的基本思想结论,根据设

26、定的散列函数 H(key)和所选中的处理冲突的方法，将一组关键字映象到一个有限的、地址连续的地址集(区间)上，并以关键字在地址集中的“象”作为相应记录在表中的存储位置，如此构造所得的查找表称之为“散列表”。,这一过程称为散列造表或者散列，所得的存储位置成为散列地址或者哈希地址。,散列的基本思想定义,散列函数的构造方法,对数字的关键字可有下列构造方法:,若是非数字关键字，则需先对其进行数字化处理。,1.直接定址法,3.平方取中法,5.除留余数法,4.折叠法,6.随机数法,2.数字分析法,散列函数为关键字的线性函数H(key)=key 或者 H(key)=a key+b,1.直接定址法,散列函数的

27、构造方法,散列函数的构造方法,2.数字分析法,假设关键字集合中的每个关键字都是由 s 位数字组成(u1,u2,us)，分析关键字集中的全体，并从中提取分布均匀的若干位或它们的组合作为地址。,此方法仅适合于：能预先估计出全体关键字的每一位上各种数字出现的频度。,散列函数的构造方法,有80个记录，关键字为8位十进制数，散列地址为2位十进制数,分析：只取8 只取1 只取3、4 只取2、7、5 数字分布近乎随机所以：取任意两位或两位 与另两位的叠加作散列地址,散列函数的构造方法,以关键字的平方值的中间几位作为存储地址。求“关键字的平方值”的目的是“扩大差别”，同时平方值的中间各位又能受到整个关键字中各

28、位的影响。,3.平方取中法,此方法适合于:关键字中的每一位都有某些数字重复出现频度很高的现象。,散列函数的构造方法,4.折叠法,将关键字分割成若干部分，然后取它们的叠加和为散列地址。有两种叠加处理的方法：移位叠加和间界叠加。,此方法适合于:关键字的数字位数特别多，而且关键字在每一位上的数字分布大致均匀的情况。,散列函数的构造方法,例 关键字为：0442205864，散列地址位数为4,5 8 6 4,4 2 2 0,0 4,1 0 0 8 8,H(key)=0088,移位叠加,5 8 6 4,0 2 2 4,0 4,6 0 9 2,H(key)=6092,间界叠加,4.折叠法,散列函数的构造方法

29、,5.除留余数法,设定散列函数为:H(key)=key MOD p 其中，pm(表长)并且p 应为不大于 m 的素数 或是 不含 20 以下的质因子,散列函数的构造方法,给定一组关键字为:12,39,18,24,33,21若取 p=9,则它们对应的散列函数值将为:3,3,0,6,6,3,为什么要对p加限制？,可见，若p中含质因子3,则所有含质因子3的关键字均映射到“3的倍数”的地址上，从而增加了“冲突”的可能。,散列函数的构造方法,6.随机数法,设定散列函数为:H(key)=Random(key)其中Random 为随机函数,此方法通常用于对长度不等的关键字构造散列函数。,散列函数的构造方法,

30、实际构造散列表时1.采用哪种构造散列函数的方法取决于建表的关键字集合的情况(包括关键字的范围和形态)2.总的原则是使产生冲突的可能性尽可能的小。3.如果散列造表过程中产生冲突，应当如何处理这些冲突呢？,处理冲突的方法,冲突：由关键字得到的散列地址为j（0jn-1）的位置上已存有记录,处理冲突：为产生冲突的地址寻找下一个空的散列地址,2.不用链表的散列表开放定址法5.4,3.再散列法5.5,1.分离链接法5.3,4.建立一个公共溢出区,处理冲突的方法1,1.分离链接法(separate chaining),将散列到同一个值的所有元素保留到同一线性链表中。,处理冲突的方法1,例如:关键字集合 19

31、,01,23,14,55,68,11,82,36,采用链地址法来构造的散列表：,散列函数为 H(key)=key MOD 7,19,01,23,14,55,68,11,82,36,处理冲突的方法1,执行一次查找：首先使用散列函数来确定需要遍历的链表；然后再在被确定的链表中执行一次查找。,ASL=(61+22+31)/9=13/9,处理冲突的方法1,执行插入操作：首先检查相应的链表中该元素是否已处在适当的位置，否则被插入到链表的前端。,处理冲突的方法2,2.开放定址法,为产生冲突的地址 H(key)求得一个地址序列：H0,H1,H2,Hs 1 sm-1其中：H0=H(key)Hi=(H(key)

32、+di)MOD m i=1,2,s m 为散列表表长,处理冲突的方法2,1.线性探测再散列法,2.平方探测再散列法,3.双散列法,增量di的三种取法,处理冲突的方法2,1.开放定址法,对增量 di 的三种取法-：,1)线性探测再散列 di=c i 最简单的情况 c=1,即di=f(i)=i;即 di=1,2,3,m-1,处理冲突的方法2,例如:关键字集合 19,01,23,14,55,68,11,82,36,设定散列函数 H(key)=key MOD 11(表长=11),采用线性探测再散列法来构造散列表。,19,19,01,01,23,23,23,14,14,55,55,68,68,68,11

33、,82,11,36,11,82,36,1 1 2 1 3 6 2 5 1,处理冲突的方法2,1.开放定址法,对增量 di 有三种取法-：,2)平方（二次）探测再散列 di=f(i)=12,-12,22,-22,处理冲突的方法2,例如:关键字集合 19,01,23,14,55,68,11,82,36,19,19,01,01,23,23,23,14,14,55,55,68,68,68,11,82,11,36,11,82,36,36,设定散列函数 H(key)=key MOD 11(表长=11),采用二次探测再散列法来构造散列表。,1 1 2 1 2 1 4 1 3,处理冲突的方法2,1.开放定址法

34、,对增量 di 有三种取法-：,3)双散列法 di即f(i)是一组随机数列 或者 di=f(i)=iH2(key)(又称随机探测再散列),处理冲突的方法2,H2(key)是另设定的一个散列函数，它的函数值应和 TableSize 互为素数。,若 TableSize 为素数，则 H2(key)可以是 1 至 TableSize-1 之间的任意数;,若 TableSize 为 2 的幂次，则 H2(key)应是 1 至 TableSize-1 之间的任意奇数。,处理冲突的方法,例如，当 m=11时，可设 H2(key)=(3 key)MOD 10+1,19,01,23,14,55,68,11,82

35、,36,2 1 1 1 2 1 2 1 3,设定哈希函数 H(key)=key MOD 11(表长=11),例如:关键字集合 19,01,23,14,55,68,11,82,36,处理冲突的方法2,即：产生的 Hi 均不相同，且所产生的TableSize-1个 Hi 值能覆盖散列表中所有地址。则要求：,注意：增量 di 应具有“完备性”,双散列时TableSize和 di 没有公因子。,平方探测时的表长 TableSize 必为形如 4j+3 的素数（如:7,11,19,23,等）；,处理冲突的方法3,3.再散列法,Hi=RHi(key)i=1,2,3,，k,RHi均是不同的散列函数，在同义词

36、产生地址冲突时计算另一个散列函数地址，直到冲突不再发生。,缺点：增加了计算时间。,处理冲突的方法4,4.建立一个公共溢出区,散列函数的值域0,m-1向量HashTable0.m-1为基本表，每个分量存放一个记录向量OverTable0.v为溢出表对于关键字和基本表HashTable中关键字为同义词的记录，只要发生冲突，都填入溢出表。,课堂练习,设有一组关键字11，54，36，89，51，47，38，59，63，94，15，采用哈希函数：H(key)=key%13。采用开放地址法的线性探测再散列方法解决冲突，试在015的散列地址空间中对该关键字序列构造哈希表。,散列表的查找算法,查找过程和造表过

37、程一致。假设采用开放定址处理冲突，则查找过程为:,1.对于给定值 K,计算散列地址 i=H(K),2.若 ri=NULL 则查找不成功,3.若 ri.key=K 则查找成功,4.否则“求下一地址 Hi”，直至 rHi=NULL(查找不成功)或 rHi.key=K(查找成功)为止。,哈希表的查找分析,从查找过程得知：,由于冲突的产生，哈希表的查找过程仍然是一个给定值和关键字进行比较的过程。,哈希表查找的平均查找长度实际上并不等于零。,哈希表的查找分析,1)选用的哈希函数;2)选用的处理冲突的方法;3）哈希表饱和的程度，装载因子=n/m 值的大小（n记录数，m表的长度，即TableSize）,决定

38、哈希表查找的ASL的因素：,哈希表的查找分析,一般情况下，可以认为选用的哈希函数是“均匀”的，则在讨论ASL时，可以不考虑它的因素。,因此，哈希表的ASL是处理冲突方法和装载因子的函数。,例如：前述例子,线性探测处理冲突时，ASL=,链地址法处理冲突时，ASL=,22/9,13/9,哈希表的查找分析,线性探测再散列,可以证明：查找成功时有下列结果：,随机探测再散列,链地址法,哈希表的查找分析,从以上结果可见，,哈希表的平均查找长度是 的函数，而不是 n 的函数。,这说明，用哈希表构造查找表时，可以选择一个适当的装填因子，使得平均查找长度限定在某个范围内。,小结和作业,散列表,1散列原理,2散列函数的构造方法,3处理冲突的方法,4散列表的查找及分析,作业：P145,5.1 a，b,31、只有永远躺在泥坑里的人，才不会再掉进坑里。黑格尔32、希望的灯一旦熄灭，生活刹那间变成了一片黑暗。普列姆昌德33、希望是人生的乳母。科策布34、形成天才的决定因素应该是勤奋。郭沫若35、学到很多东西的诀窍，就是一下子不要学很多。洛克,