散列( Hashing 在线性表、树结构中査找纪录是通过与关键 字的“比较”完成的。 顺序查找,比较的结果为“=2或 ·非顺序査找,比较的结果为“<,“=”,“> 散列的思想: 根据纪录的关键字直接找到记录的存储位置, 即为关键字和记录的存储位置建立一个对应 关系f,使每个关键字和结构中一个唯一的 存储位置相对应 对应关系f为散列函数,按该思想建立的表 为散列表
2005-02-03 散列 (Hashing) ▪ 在线性表、树结构中查找纪录是通过与关键 字的“比较”完成的。 • 顺序查找，比较的结果为“=”或“≠” • 非顺序查找，比较的结果为“<” ， “=” ， “>” ▪ 散列的思想： 根据纪录的关键字直接找到记录的存储位置， 即为关键字和记录的存储位置建立一个对应 关系f，使每个关键字和结构中一个唯一的 存储位置相对应。 对应关系f为散列函数，按该思想建立的表 为散列表
哈希表的定义 根据设定的哈希函数H(key)和处理冲突的方法将 组关键字映像到一个有限的连续的地址集(区间)上, 并以关键字在地址集中的“像”作为纪录在表中的存储 位置,这种表便称为哈希表,这一影像过程称为哈希造 表或散列,所得存储位置称哈希地址或散列地址 20050203
2005-02-03 根据设定的哈希函数H(key)和处理冲突的方法将一 组关键字映像到一个有限的连续的地址集（区间）上， 并以关键字在地址集中的“像”作为纪录在表中的存储 位置，这种表便称为哈希表，这一影像过程称为哈希造 表或散列，所得存储位置称哈希地址或散列地址。 哈希表的定义
散列方法在表项的存储位置与它的关键字之间建立 个确定的对应函数关系Hash(),使每个关键字与结构 中一个唯一存储位置相对应: Address= Hash( Rec key 在查找时,首先对表项的关键字进行函数计算,把函 数值当做表项的存储位置,在结构中按此位置取表项 比较。若关键字相等,则查找成功。在存放表项时, 依相同函数计算存储位置,并按此位置存放
2005-02-03 ▪ 散列方法在表项的存储位置与它的关键字之间建立一 个确定的对应函数关系Hash( )，使每个关键字与结构 中一个唯一存储位置相对应： Address ＝ Hash ( Rec.key ) ▪ 在查找时，首先对表项的关键字进行函数计算，把函 数值当做表项的存储位置，在结构中按此位置取表项 比较。若关键字相等，则查找成功。在存放表项时， 依相同函数计算存储位置，并按此位置存放
哈希函数的构造方法 构造散列涵数时的几点要求: ■散列函数的定义域必须包括需要存储的全部关 键码,如果散列表允许有m个地址时,其值域必 须在0到m-1之间。 ■散列函数计算出来的地址应能均匀分布在整个 地址空间中:若key是从关键字集合中随机抽 取的一个关键字,散列函数应能以同等概率取 0到m-1中的每一个值。 散列函数应是简单的,能在较短的时间内计算 出结果
2005-02-03 构造散列函数时的几点要求： ◼ 散列函数的定义域必须包括需要存储的全部关 键码，如果散列表允许有m个地址时,其值域必 须在 0 到 m-1 之间。 ◼ 散列函数计算出来的地址应能均匀分布在整个 地址空间中：若 key是从关键字集合中随机抽 取的一个关键字，散列函数应能以同等概率取 0到 m-1 中的每一个值。 ◼ 散列函数应是简单的，能在较短的时间内计算 出结果。 哈希函数的构造方法
1.直接定址法 此类函数直接取关键字或关键字的某个线性函数值 作为散列地址: Hash(key)=a米key+b{a,b为常数 这类散列函数是一对一的映射,一般不会产生冲突 但是,它要求散列地址空间的大小与关键字集合的 大小相同
2005-02-03 1. 直接定址法 此类函数直接取关键字或关键字的某个线性函数值 作为散列地址： Hash ( key ) ＝ a * key + b { a, b为常数 } ▪ 这类散列函数是一对一的映射，一般不会产生冲突。 但是，它要求散列地址空间的大小与关键字集合的 大小相同