数结 华中科技大学 计犷机学院(11) 200=g=
2001 -- 12 --31 华中科技大学 数据结构计算机学院(11)
9.3哈希(Hash)表和哈希法 常用连续存储单元存储数据元素的查找表有两种: (1)顺序表,对数据元素的存储一般有两种形式: (a)是按到来次序连续存放,则查找时使用顺序查找法; (b)二是按关键字的相对关系整理后以递增或递减形式连续 存放,则查找时使用顺序查找法和二分查找法。 (2)哈希表:存储数据元素时,利用一个Hash函数根据数据元素 的关键字计算出该数据元素的存储位置,查找时,也是根据给 定的数据元素的关键字计算出该数据元素可能存储位置,这样 一来,存储和查找的效率相当高, 哈希表也称为散列表,其数据元素的存储一般是不连续的。通 过Hash函数计算出的地址称为哈希地址或散列地址
9.3 哈希(Hash)表和哈希法 常用连续存储单元存储数据元素的查找表有两种： （1）顺序表，对数据元素的存储一般有两种形式： (a) 是按到来次序连续存放，则查找时使用顺序查找法； (b) 二是按关键字的相对关系整理后以递增或递减形式连续 存放，则查找时使用顺序查找法和二分查找法。 （2）哈希表：存储数据元素时，利用一个Hash函数根据数据元素 的关键字计算出该数据元素的存储位置，查找时，也是根据给 定的数据元素的关键字计算出该数据元素可能存储位置，这样 一来，存储和查找的效率相当高， 哈希表也称为散列表，其数据元素的存储一般是不连续的。 通 过Hash函数计算出的地址称为哈希地址或散列地址
9.3.1根据设定的哈希函数H(k)和处理冲突的方法, Hash函数实现的是将一组关键字映象到一个有限的地址区 间上, 理想的情况是不同的关键字得到不同的地址。 设K1和K2为关键字,若K1≠K2,H(K1)=H(K2),则称 K,K2为同义词,K2与K1为发生了冲突 例设H(k)=k%17 k1=5 k2=22 H(5)=5%17=5H(22)=2%17=5 H(5)=H(22)=5 5和22是同义词,5和22发生冲突
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发生冲突
例1人口统计表 9.3.2构造哈希函数的方法 序号 (地址)年龄人数(万) 直接定址法 10.5 取关键字或关键字的 212.6 某个线性函数值为哈希地 [31 址 420.8 H(key) =key H(key)=a key+b 150 150 key H(key)=key=地址 H(年龄)=年龄
例1 人口统计表 1 10.5 2 12.6 3 11.0 4 20.8 ... ... 150 ... 序号 (地址) 年 龄 人 数(万) 1 2 3 4 150 H(key)=key = 地址 H(年龄）= 年龄 key 9.3.2 构造哈希函数的方法 1.直接定址法 取关键字或关键字的 某个线性函数值为哈希地 址 H(key)=key H(key)=a.key+b
例2学生成绩表 序号 (地址)学号姓名性别数学外语 [2004刘大海」男」8075 2[20021伟男9083 3|20003吴晓英女8288 420141伟女8090 key H(key)=key-200040=地址 H(学号)=学号-200040
例2 学生成绩表 200041 刘大海 男 80 75 200042 王 伟 男 90 83 200043 吴晓英 女 82 88 200044 王 伟 女 80 90 ...... ..... ... .. .. ...... ..... ... .. .. 1 2 3 4 n key 序号 (地址)学 号 姓 名 性别 数学 外语 H(key) = key - 200040 = 地址 H(学号)= 学号- 200040
例3标识符表 序号标识符(key) 1 ABC H(key)=key的第一个字母在 23456 CAD 字母表中的序号 DAT key =ABC CAD DAT FOX YAb ZOO H(key)=13462526 FOX 25 YAB 26200
例3 标识符表 ABC CAD DAT FOX YAB ZOO 1 2 3 4 5 6 25 26 序号 标识符(key) H(key)=key的第一个字母在 字母表中的序号 key =ABC CAD DAT FOX YAB ZOO H(key)=1 3 4 6 25 26
2.除留余数法 设哈希表HT[0..m1]的表长为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)
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设m130,取p=127,H(key)=key%127 012 129 例2设m=256取p=251H(key)=key%251 012 255
例1 设 m=130, 取p=127, H(key)=key % 127 0 1 2 ..... 129 例2 设 m=256 取 p=251 H(key)=key % 251 0 1 2 ..... 255
例设哈希表的地址范围为0~20,哈希函数为H(K)=K%19 输入关键字序列:39,22,21,37,36,38,19,解决冲突的 方法为线性探测再散列(哈希),构造哈希表HT[0.20]。 HT[0..20] 关键字KH(K)=K%19 38 3939‰19=1 39 2222%19=3 21 2121‰19=2 22 3737%19=18 345 19 3636‰19=17 3838%19=0 1919%19=0 17 36 19与38冲突,再与39,21 18 37 22冲突,存入HT[4] 19 20
例 设哈希表的地址范围为0～20,哈希函数为H(K)=K % 19 输入关键字序列：39,22,21,37,36,38,19,解决冲突的 方法为线性探测再散列(哈希),构造哈希表HT[0..20]。 38 39 21 22 19 36 37 关键字K H(K)=K%19 39 39%19=1 22 22%19=3 21 21%19=2 37 37%19=18 36 36%19=17 38 38%19=0 19 19%19=0 19与38冲突,再与39,21, 22冲突,存入HT[4] 0 1 2 3 4 5 17 18 19 20 HT[0..20] key
再输入17,56,55 HT[0..20] 17%19=17 38 17与36冲突,再与37冲突,存入 39 HT[19]。 21 56‰19=18 22 56与37冲突,再与17冲突,存入 19 HT[20]。 55 55%19=17 17 55与36冲突,再与37,17,56冲突 36 37 与38,39,21,22,19冲突,存入[5。1917 20 56 对于H(k)=k%19,所有的19a+b为 key 同义词,0≤b≤19 如:5,24,43,62,81
38 39 21 22 19 55 36 37 17 56 再输入17,56,55 17%19=17 17与36冲突,再与37冲突,存入 HT[19]。 56%19=18 56与37冲突,再与17冲突,存入 HT[20]。 55%19=17 55与36冲突,再与37,17,56冲突,再 与38,39,21,22,19冲突,存入HT[5]。 对于H(k)=k % 19，所有的19a+b为 同义词,0≤b≤19 如：5,24,43,62,81,..... 0 1 2 3 4 5 17 18 19 20 HT[0..20] key