散列( 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为常数 } ▪ 这类散列函数是一对一的映射，一般不会产生冲突。 但是，它要求散列地址空间的大小与关键字集合的 大小相同
2.数字分析法 设有n个d位数,每一位可能有r种不同的符号。这r 种不同的符号在各位上出现的频率不一定相同,可能 在某些位上分布均匀些;在某些位上分布不均匀,只 有某几种符号经常出现。可根据散列表的大小,选取 其中各种符号分布均匀的若干位作为散列地址
2005-02-03 2. 数字分析法 设有n个d位数，每一位可能有r种不同的符号。这 r 种不同的符号在各位上出现的频率不一定相同，可能 在某些位上分布均匀些；在某些位上分布不均匀，只 有某几种符号经常出现。可根据散列表的大小，选取 其中各种符号分布均匀的若干位作为散列地址
99999999 4444444 2 12568500 46230540 89705871 40 数字分析法仅适用于事先明确知道表中所有关键字每一位数 值的分布情况,它完全依赖于关键字集合。如果换一个关键字集 合,选择哪几位要重新决定
2005-02-03 9 4 2 1 4 8 9 4 1 2 6 9 9 4 0 5 2 7 9 4 1 6 3 0 9 4 1 8 0 5 9 4 1 5 5 8 9 4 2 0 4 7 9 4 0 0 0 1 ① ② ③ ④ ⑤ ⑥ 数字分析法仅适用于事先明确知道表中所有关键字每一位数 值的分布情况，它完全依赖于关键字集合。如果换一个关键字集 合，选择哪几位要重新决定
3.平方取中法 此方法在词典处理中使用十分广泛。它先计算构成关键字 的标识符的内码的平方,然后按照散列表的大小取中间 的若干位作为散列地址 ■设标识符可以用一个计算机字长的内码表示。因为内 码平方数的中间几位一般是由标识符所有字符决定, 所以对不同的标识符计算出的散列地址大多不相同, 即使其中有些字符相同。 在平方取中法中,一般取散列地址为2的某次幂。例 如,若散列地址总数取为m=2r,则对内码的平方数 取中间的r位。如果r=3,所取得的散列地址参看 图的最右一列
2005-02-03 3. 平方取中法 ▪ 此方法在词典处理中使用十分广泛。它先计算构成关键字 的标识符的内码的平方，然后按照散列表的大小取中间 的若干位作为散列地址。 ▪ 设标识符可以用一个计算机字长的内码表示。因为内 码平方数的中间几位一般是由标识符所有字符决定， 所以对不同的标识符计算出的散列地址大多不相同， 即使其中有些字符相同。 ▪ 在平方取中法中，一般取散列地址为2的某次幂。例 如，若散列地址总数取为m = 2 r ，则对内码的平方数 取中间的r位。如果r = 3，所取得的散列地址参看 图的最右一列
4.折叠法 此方法把关键字自左到右分成位数相等的几部分,每 部分的位数应与散列表地址位数相同,只有最后 部分的位数可以短一些。 把这些部分的数据叠加起来,就可以得到具有该关键 字的记录的散列地址 有两种叠加方法: ·移位法—把各部分的最后一位对齐相加; ·分界法—各部分不折断,沿各部分的分界来回折 叠,然后对齐相加,将相加的结果当做散列地址
2005-02-03 4. 折叠法 ▪ 此方法把关键字自左到右分成位数相等的几部分，每 一部分的位数应与散列表地址位数相同，只有最后一 部分的位数可以短一些。 ▪ 把这些部分的数据叠加起来，就可以得到具有该关键 字的记录的散列地址。 ▪ 有两种叠加方法： • 移位法 — 把各部分的最后一位对齐相加； • 分界法 — 各部分不折断，沿各部分的分界来回折 叠，然后对齐相加，将相加的结果当做散列地址
示例:设给定的关键字为key=23938587841,若 存储空间限定3位,则划分结果为每段3位.上 述关键字可划分为4段: 239 385 878 移位法 分界法 239 385 583 878 878 41 14 1:543 1714 把超出地址位数的最高位删去,仅保留最低的3位, 做为可用的散列地址
2005-02-03 ▪ 示例：设给定的关键字为 key = 23938587841，若 存储空间限定 3 位, 则划分结果为每段 3 位. 上 述关键字可划分为 4段： 239 385 878 41 ▪ 把超出地址位数的最高位删去, 仅保留最低的3位， 做为可用的散列地址