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

基本思想：在记录的存储地址和它的关键字之间建立一个确定的对应关系；这样，不经过比较，一次存取就能得到所查元素的查找方法
定义
哈希函数——在记录的关键字与记录的存储地址之间建立的一种对应关系叫~
哈希函数是一种映象，是从关键字空间到存储地址空间的一种映象
哈希函数可写成：addr(ai)=H(ki)
ai是表中的一个元素
addr(ai)是ai的存储地址
ki是ai的关键字哈希表——应用哈希函数，由记录的关键字确定记录在表中的地址，并将记录放入此地址，这样构成的表叫~
哈希查找——又叫散列查找，利用哈希函数进行查找的过程叫~例11个元素的关键字分别为18，27，1，20，22，6，10，13，41，15，25。选取关键字与元素位置间的函数为f1（key）=keymod11，则元素存放在如下的哈希表中：哈希地址从例子可见：
哈希函数只是一种映象，所以哈希函数的设定很灵活，只要使任何关键字的哈希函数值都落在表长允许的范围之内即可。
在一般情况下，散列表的空间必须比结点集合的空间大，这样虽然浪费了一些空间，但却可提高查找的效率。假设散列表的空间大小为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)=keyMODp，pm
特点
简单、常用，可与上述几种方法结合使用
p一般选取质数，若哈希表表长为m，则要求p≤m，且接近m或等于m。选取哈希函数，考虑以下因素：
计算哈希函数所需时间
关键字长度
哈希表长度（哈希地址范围）
关键字分布情况
记录的查找频率9.3.3处理冲突的方法
处理冲突的方法基本上有两大类：开放定址法和拉链法
开放定址法
方法：当冲突发生时，形成一个探查序列；沿此序列逐个地址探查，直到找到一个空位置（开放的地址），将发生冲突的记录放到该地址中，即Hi=(H(key)+di)MODm，i=1,2,……k(km-1)
其中：H(key)——哈希函数
m——哈希表表长
di——增量序列
分类
线性探测再散列：di=1,2,3,……m-1
二次探测再散列：di=1²,-1²,2²,-2²,3²,……±k²(km/2)线性探测法
基本思想：将哈希表HT[m-1]看成一个环行表，若地址为d的单元发生冲突，则依次查找下述单元：d+1，d+2，……m-1，0，1，…….d-1，直到找到一个空单元或查找到一个关键字相等的单元。
用线性探测法解决冲突，求下一个开放地址的公式为：
Hi=（Hash（key）+di）modm（1≤i<m）
其中：Hash（key）为哈希函数
di为增量序列1，2，……，m-1，且di=i例 假设关键字集合为{47，7，29，11，16，92，22，8，3}，哈希表表长为11，Hash（key）=keymod11，用线性探测法处理冲突构造这组关键字的哈希表。建表如下：二次探测法
基本思想：二次探测法的探查序列是12,-12,22,-22,……等，发生冲突时，将同义词来回散列在第一个哈希地址的两端
公式为：
Hi=（Hash（key）±di）modm
其中：Hash（key）为哈希函数
m为哈希表长度，m要求是某个4k+3的质数（k是整数）
di为增量序列12,-12,22,-22,……,q2,-q2且q≤（m-1）/2例表长为11的哈希表中已填有关键字为17，60，29的记录，
H(key)=keyMOD11,现有第4个记录，其关键字为38，
按三种处理冲突的