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

回顾 1 静态查找表查找的ASL是？对应的时间复杂度 2 动态树表查找的ASL，对应的时间复杂度 3 一个查找算法最理想的的时间复杂度应该是什么？ 4 在数组中按编号查找某个元素的时间复杂度是？ 5 对给定的查找表（数据元素的集合）能否把它们采用特别的方法组织到数组中呢？ 把数据元素的关键码通过某种计算方法直接确它在数组中的存储位置 这样构造的数组就是哈希表 8.4 动态查找表2——哈希表查找 8.4.1 哈希表的概念 1. 哈希查找的基本思想 在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样不经过比较(或进行少量比较），一次存取就能得到所查元素的查找方法。 2. 哈希函数 在记录的关键字与记录的存储地址之间建立的一种对应关系叫哈希函数。 哈希函数可写成：addr(ai)=H(ki) 其中：ai 是表中的一个元素, addr(ai)是ai的存储地址, ki 是ai的关键字 3 哈希表 应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫哈希表( 数组的推广）。 4. 哈希查找 又叫散列查找，利用哈希函数进行查找的过程叫哈希查找。(注意到哈希表建立的时候用哈希函数） 5. 冲突 k1?k2，但H(k1)=H(k2)的现象叫冲突(Collision)，映射到同一哈希地址上的关键码称为“同义词”。 我们希望能找到尽可能产生均匀映射的哈希函数，从而尽可能降低发生冲突的概率；哈希方法需要解决以下两个问题： ⑴ 尽量构造好的哈希函数，好的哈希函数有三个方面的含义： 一是所构造的函数应该尽可能简单，以便提高哈希地址的计算速度； 二是所构造的函数应该尽量减少存储空间的浪费； 三是根据所选函数计算出的地址，应在哈希地址集中大致均匀分布，减少冲突。 ⑵ 制定解决冲突的方案，如果发生了冲突怎么解决。 8. 4.2 哈希函数的构造方法 1. 直接定址法 【构造】 取关键字或关键字的某个线性函数作哈希地址，即 H(key)=key 或 H(key)=a·key+b 比如：统计1-100岁的人口，用年龄做关键字，哈希函授可以就取关键字本身。 【特点】 直接定址法所得地址集合与关键字集合大小相等，不会发生冲突 实际中能用这种哈希函数的情况很少 2. 数字分析法 【构造】 对关键字进行分析，取关键字的若干位或其组合作哈希地址。 比如：取学号某些位排定学生宿舍号。 11 0611 2 01 楼号 层号 房间号 【特点】 适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况。 3. 平方取中法 构造：取关键字平方后中间几位作哈希地址 适于不知道全部关键字情况 例如，若关键码K＝1234，哈希表长为1000，则有：K2=1522756，取中间3位227作为哈希地址。 4. 折叠法 构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址 种类 移位叠加：将分割后的几部分低位对齐相加 间界叠加：从一端沿分割界来回折送，然后对齐相加 适于关键字位数很多，且每一位上数字分布大致均匀情况 5. 除留余数法 构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即 H(key)=key MOD p，p?m 特点 简单、常用，可与上述几种方法结合使用 p的选取很重要；p选的不好，容易产生同义词 例：设有关键码序列{2049，1756，0056，3187，4356，6349} 若p = 100， 则对应的哈希地址就是关键码的后两位即49，56，56，87，56，49，很不均匀 实践证明 一般选取 p=m的最大质数效果比较好。 6. 随机数法 构造：取关键字的随机函数值作哈希地址，即H(key)=random(key) 适于关键字长度不等的情况 【选取哈希函数应考虑的因素】 计算哈希函数所需时间 关键字长度 哈希表长度（哈希地址范围） 关键字分布情况 记录的查找频率 8.4.3 处理冲突的方法 1 开放定址法 2 再哈希方法 3 拉链方法 4 建立公共溢出区 1. 开放定址法 【方法】当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即 Hi=(H(key)+di)MOD m，i=1,2,……k(k?m-1) 其中：H(key)——哈希函数 m——哈希表表长