数结 华中科技大学 计犷机学院(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