散列函数的定义域必须包括需要存储的全部关键码-大连理工大学.PPT

在随机存储中： 200302 200305 200301 张三 李四 王五 19 21 20 查找某一条记录需要进行一系列的“比较”。 查找的效率依赖于比较的次数。 能否在记录的关键字和存储地址之间构造这样一种关系 f ，使得关键字和存储地址一一对应 ？ 此对应关系 f 称为散列函数。 学号 姓名 年龄 01 02 03 散列 负载因子 α=n/m 散列表的空间大小为m 填入表中的结点数为n 冲突 某个散列函数对于不相等的关键码计算出了相同的散列地址 在实际应用中，不产生冲突的散列函数极少存在 同义词 发生冲突的两个关键码 散列 把关键码值映射到存储位置的函数，通常用 h 来表示 Address ＝ Hash ( key ) 散列函数 构造散列函数时的几点要求： 散列函数的定义域必须包括需要存储的全部关键码，如果散列表允许有 m 个地址时, 其值域必须在 0 到 m-1 之间。 散列函数计算出来的地址应能均匀分布在整个地址空间中：若 key 是从关键码集合中随机抽取的一个关键码，散列函数应能以同等概率取0 到 m-1 中的每一个值。 散列函数应是简单的，能在较短的时间内计算出结果。 散列函数 除留余数法 折叠法 平方取中法 基数转换法 直接定址法 散列函数 除留余数法 H(key) = key % p 或 H(key) = key % p + c 这里 p m； 余数总在 0 ～ p-1 之间。 散列函数 示例：有一个关键码 key = 962148，散列表大小 m = 25，即 HT[25]。取质数 p= 23。散列函数 hash ( key ) = key % p。则散列地址为 hash ( 962148 ) = 962148 % 23 = 12。 可以按计算出的地址存放记录。需要注意的是，使用上面的散列函数计算出来的地址范围是 0到 22，因此，从23到24这几个散列地址实际上在一开始是不可能用散列函数计算出来的，只可能在处理冲突时达到这些地址。 散列函数 选取 p 为质数的理由： 设 key 值都为奇数，选 p 为偶数； 则 H(key) = key % p ，结果为奇数，一半单元被浪费掉。 设 key 值都为 5 的倍数，选 p 为 95；则 H(key) = key % p ， 结果为：0、5、10、15、…… 90 。4/5 的单元被浪费掉。 散列函数 折叠法（移位法、分界法） key = 381，412，975 选取 768 或 570 作为散列地址。 381 412 975 1 768 975 214 381 1 570 散列函数 平方取中法 e.g: （4731）2 ＝ 223 82 361 ； 选取 82 （在 m ＝100 情况下）。 此方法在词典处理中使用十分广泛。它先计算构成关键码的标识符的内码的平方，然后按照散列表的大小取中间的若干位作为散列地址。 设标识符可以用一个计算机字长的内码表示。因为内码平方数的中间几位一般是由标识符所有字符决定，所以对不同的标识符计算出的散列地址大多不相同，即使其中有些字符相同。 散列函数 标识符 内码 内码的平方 散列地址 A 01 01 001 A1 0134 20420 042 A9 0144 23420 342 B 02 4 004 DMAX 21526443617100 443 DMAX1 0415013034 5264473522151420 352 AMAX 135423617100 236 AMAX1 0115013034 3454246522151420 652 标示符的八进制内码表示及其平方值 散列函数 基数转换法 将关键字k转换为另外一种数字基数，再对表的大小取模。 如：k=(34