数据结构课件(c语言).pptxVIP

1第8章查找

8.1基本概念与基本运算8.2静态查找表8.3动态查找表1——树表8.4动态查找表2——哈希表查找

回顾静态查找表查找的ASL是？对应的时间复杂度1动态树表查找的ASL，对应的时间复杂度2一个查找算法最理想的的时间复杂度应该是什么？3在数组中按编号查找某个元素的时间复杂度是？4对给定的查找表（数据元素的集合）能否把它们采用特别的方法组织到数组中呢？5

这样构造的数组就是哈希表把数据元素的关键码通过某种计算方法直接确它在数组中的存储位置0m–1h(k1)h(k4)h(k3)U(universeofkeys)k1k2k3k5k4

8.4.1哈希表的概念1.哈希查找的基本思想在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样不经过比较(或进行少量比较），一次存取就能得到所查元素的查找方法。2.哈希函数在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。哈希函数可写成：addr(ai)=H(ki)其中：ai是表中的一个元素,addr(ai)是ai的存储地址,ki是ai的关键字

哈希表应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表(数组的推广）。

4.哈希查找又叫散列查找，利用哈希函数进行查找的过程叫哈希查找。(注意到哈希表建立的时候用哈希函数）例30个地区的各民族人口统计表编号地区总人口汉族回族…...1北京2上海…...…...以编号作关键字，构造哈希函数：H(key)=keyH(1)=1H(2)=2以地区作关键字，取地区名称第一个拼音字母的序号作哈希函数：H(Beijing)=2H(Shanghai)=19H(Shenyang)=19

5.冲突k1?k2，但H(k1)=H(k2)的现象叫冲突(Collision)，映射到同一哈希地址上的关键码称为“同义词”。0m–1h(k1)h(k4)h(k3)U(universeofkeys)k1k2k3k5k4

我们希望能找到尽可能产生均匀映射的哈希函数，从而尽可能降低发生冲突的概率；哈希方法需要解决以下两个问题：尽量构造好的哈希函数，好的哈希函数有三个方面的含义：一是所构造的函数应该尽可能简单，以便提高哈希地址的计算速度；二是所构造的函数应该尽量减少存储空间的浪费；三是根据所选函数计算出的地址，应在哈希地址集中大致均匀分布，减少冲突。制定解决冲突的方案，如果发生了冲突怎么解决。

8.4.2哈希函数的构造方法1.直接定址法【构造】取关键字或关键字的某个线性函数作哈希地址，即H(key)=key或H(key)=a·key+b比如：统计1-100岁的人口，用年龄做关键字，哈希函授可以就取关键字本身。【特点】直接定址法所得地址集合与关键字集合大小相等，不会发生冲突实际中能用这种哈希函数的情况很少

2.数字分析法01对关键字进行分析，取关键字的若干位或其组合作哈希地址。比如：取学号某些位排定学生宿舍号。0611201楼号层号房间号【构造】02【特点】适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。

例有80个记录，关键字为8位十进制数，哈希地址为2位十进制数，怎么取合适？8134653281372242813874228130136781322817813389678136853781419355…..…..????????分析：?只取8?只取1?只取3、4?只取2、7、5????数字分布近乎随机所以：取????任意两位或两位与另两位的叠加作哈希地址

231构造：取关键字平方后中间几位作哈希地址适于不知道全部关键字情况例如，若关键码K＝1234，哈希表长为1000，则有：K2=1522756，取中间3位227作为哈希地址。平方取中法

构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址种类01移位叠加：将