9.3哈希查找9.3.1什么是哈希表查找效率由比较一次缩小的查.ppt

9.3 哈希查找 9.3.1 什么是哈希表 查找效率由比较一次缩小的查找范围决定。 顺序查找是对无序集的查找，关键字比较的结果为“=”或“≠”两种可能，其平均时间为O（n）。 而二分法查找和各种树表的查找是对有序集的查找，关键字比较的结果为“”、“=”、“”三种可能，其查找速度较快，平均时间为O（log2n）。 要想提高查找的效率，就不能只是依赖于比较进行查找。理想的情况是依据关键字直接得到其对应的数据元素位置，即要求关键字与数据元素间存在一一对应关系，通过这个关系，能很快地由关键字得到对应的数据元素位置，其查找的时间期望值为O（1）。 基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法 定义 哈希函数——在记录的关键字与记录的存储地址之间建立的一种对应关系叫~ 哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象 哈希函数可写成：addr(ai)=H(ki) ai是表中的一个元素 addr(ai)是ai的存储地址 ki是ai的关键字 哈希表——应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫~ 哈希查找——又叫散列查找，利用哈希函数进行查找的过程叫~ 例 11个元素的关键字分别为 18，27，1，20，22，6，10，13，41，15，25。选取关键字与元素位置间的函数为 f1（key）=key mod 11，则元素存放在如下的哈希表中： 从例子可见： 哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可。 在一般情况下，散列表的空间必须比结点集合的空间大，这样虽然浪费了一些空间，但却可提高查找的效率。假设散列表的空间大小为m，装入哈希表中的结点数是n，则称α=n/m为哈希表的装填因子。在使用时，一般取α=0.65~0.9之间。 冲突：key1?key2，但H(key1)=H(key2)的现象叫~。哈希函数通常是一种压缩映象，所以冲突不可避免，只能尽量减少；同时，冲突发生后，应该有处理冲突的方法 所以，哈希方法需要解决以下两个问题： 　① 构造好的哈希函数 　② 制定解决冲突的方案。 9.3.2 哈希函数的构造方法 直接定址法 构造：取关键字或关键字的某个线性函数作哈希地址，即H(key)=key 或 H(key)=a·key+b 特点 直接定址法所得地址集合与关键字集合大小相等，不会发生冲突 实际中能用这种哈希函数的情况很少 数字选择法 构造：如果事先知道关键字的集合，且关键字的位数比哈希表的地址位数多，则可选取数字分布比较均匀的若干位作为哈希函数。 适于关键字位数比哈希地址位数大，且可能出现的关键字事先知道的情况 平方取中法 构造：取关键字平方后中间几位作哈希地址 适于不知道全部关键字情况 折叠法 　构造：将关键字分割成位数相同的几部分，然后取这几部分的叠加和（舍去进位）做哈希地址 　种类 　移位叠加：将分割后的几部分低位对齐相加 　间界叠加：从一端沿分割界来回折送，然后对齐相加 　适于关键字位数很多，且每一位上数字分布大致均匀情况 除留余数法 构造：取关键字被某个不大于哈希表表长m的数p除后所得余数作哈希地址，即H(key)=key MOD p，p?m 特点 简单、常用，可与上述几种方法结合使用 p一般选取质数，若哈希表表长为m，则要求p≤m，且接近m或等于m。 选取哈希函数，考虑以下因素： 计算哈希函数所需时间 关键字长度 哈希表长度（哈希地址范围） 关键字分布情况 记录的查找频率 9.3.3 处理冲突的方法 处理冲突的方法基本上有两大类：开放定址法和拉链法 开放定址法 方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di)MOD m，i=1,2,……k(k?m-1) 其中：H(key)——哈希函数 m——哈希表表长 di——增量序列 分类 线性探测再散列：di=1,2,3,……m-1 二次探测再散列：di=12,-12,22,-22,32,……±k2(k?m/2) 链地址法 思想：将所有关键字为同义词的记录存储在一个单链表中，并用一维数组存放头指针 方法：设哈希函数得到的哈希地址域在区间[0，m-1]上，以每个哈希地址作为一个指针，指向一个链，即分配指针数组HTP[m]，建立m个空链表，由哈希函数对关键字运算后，映射到同一哈希地址i的同义词均加入到HTP[i]指向的链表中。 9.3.4 哈希查找过程及分析 哈希查找过程 哈希查找分析 哈希查找过程仍是一个给定值与关键字进行比较的过程