数据结构9-查找b课件.ppt

9.3 哈希(Hash)表和哈希法 采用连续存储单元存储数据元素的查找表有两种： （1）顺序表，对数据元素的存储一般有两种形式： (a) 是按到来次序连续存放，则查找时使用顺序查找法； (b) 二是按关键字的相对关系整理后以递增或递减形式连续存放，则查找时使用顺序查找法和二分查找法。 （2）哈希表：存储数据元素时，利用一个Hash函数根据数据元素的关键字计算出该数据元素的存储位置，查找时，也是根据给定的数据元素的关键字计算出该数据元素可能存储位置，这样一来，存储和查找的效率相当高， 哈希表也称为散列表，其数据元素的存储一般是不连续的。 通过Hash函数计算出的地址称为哈希地址或散列地址。 9.3.1 根据设定的哈希函数H(k)和处理冲突的方法， Hash函数实现的是将一组关键字映象到一个有限的地址区间上， 理想的情况是不同的关键字得到不同的地址。 设K1和K2为关键字, 若K1≠K2,H(K1)=H(K2),则称 K1,K2为同义词,K2与K1为发生了冲突 例 设 H(k)=k%17 k1=5 k2=22 ∵ H(5)=5%17=5 H(22)=22%17=5 H(5)=H(22)=5 ∴ 5和22是同义词,5和22发生冲突 9.3.2 构造哈希函数的方法 1.直接定址法 取关键字或关键字的某个线性函数值为哈希地址 H(key)=key H(key)=a.key+b 例1 人口统计表 例2 学生成绩表 例3 标识符表 2.除留余数法 设哈希表HT[0..m-1]的表长为m，哈希地址为key除以p 所的的余数： H(key)=key MOD p //PASCAL语言 H(key)=key % p //C语言 其中：MOD,%为取模或求余 p=m ，p为接近m的质数(素数), 如： 3,5,7,11,13,17,19,23,29,31,37...... 或不包含小于20的质因子的合数，如：713(=23*31) 例1 设 m=130, 取p=127, H(key)=key % 127 例 设哈希表的地址范围为0～20,哈希函数为H(K)=K % 19 输入关键字序列：39,22,21,37,36,38,19,解决冲突的 方法为线性探测再散列(哈希),构造哈希表HT[0..20]。 例 设哈希表的地址范围为0～20,哈希函数为H(K)=K % 19 输入关键字序列：39,22,21,37,36,38,19,解决冲突的 方法为线性探测再散列(哈希),构造哈希表HT[0..20]。 对于H(k)=k % 19，所有的19a+b为同义词,0≤b≤19 如：5,24,43,62,81,..... 3.平方取中法----取关键字平方后的中间某几位为哈希地址,即： H(k)=取k2的中间某几位数字 4.折叠法 将关键字分割成位数相同的几部分,然后取这几部分的叠加 和作为哈希地址。 4.折叠法 将关键字分割成位数相同的几部分,然后取这几部分的叠加 和作为哈希地址。 5.数字分析法 设哈希表中可能出现的关键字都是事先知道的,则可取关键 字的若干分布均匀的位组成哈希地址。 6.随机数法 H(key)=random(key) random(key)为产生伪随机数的函数 7.灵活构造哈希函数 9.3.3 如何解决冲突 1.开放地址法(开式寻址法) 假定记录Ri,RX的关键字Ki,KX为同义词，散列地址为q,Ri已存 入HT[0..m-1]中的HT[q]中，则RX 存入HT中的某个空位上。 依次在地址q+1,q+2,...,m-1,0,1,...,q-1中寻找一个空 位，叫做线性探测再散列。 (1) 线性探测再散列 课堂练习：设 H(k)=k的首字母在字母表中的序号,用线性探测再 散列法解决冲突，依次用下列关键字，造哈希表 HT[0..28]。 例 设 H(k)=k的首字母在字母表中的序号，用线性探测再散列 法解决冲突，依次用下列关键字，造哈希表HT[0..28]。 (2) 二次探测再散列 假定记录Ri和Rj的关键字Ki和Kj为同义词，散列地址为q, Ri已存入HT[0..m-1]中的HT[q]中。 若依次在地址q+12,q-12,q+22,q-22,...,q+i2,q-i2 ,...中 寻找一个空位，叫做二次