数据结构 散列 (Hashing).pptVIP

散列 (Hashing) 散列方法在表项的存储位置与它的关键字之间建立一个确定的对应函数关系Hash( )，使每个关键字与结构中一个唯一存储位置相对应： Address ＝ Hash ( Rec.key ) 在查找时，首先对表项的关键字进行函数计算，把函数值当做表项的存储位置，在结构中按此位置取表项比较。若关键字相等，则查找成功。在存放表项时，依相同函数计算存储位置，并按此位置存放。 哈希函数的构造方法 1. 直接定址法 此类函数直接取关键字或关键字的某个线性函数值作为散列地址： Hash ( key ) ＝ a * key + b { a, b为常数 } 这类散列函数是一对一的映射，一般不会产生冲突。 但是，它要求散列地址空间的大小与关键字集合的 大小相同。 2. 数字分析法 设有n个d位数，每一位可能有r种不同的符号。这 r 种不同的符号在各位上出现的频率不一定相同，可能在某些位上分布均匀些；在某些位上分布不均匀，只有某几种符号经常出现。可根据散列表的大小，选取其中各种符号分布均匀的若干位作为散列地址。 3. 平方取中法 此方法在词典处理中使用十分广泛。它先计算构成关键字 的标识符的内码的平方，然后按照散列表的大小取中间 的若干位作为散列地址。 设标识符可以用一个计算机字长的内码表示。因为内 码平方数的中间几位一般是由标识符所有字符决定， 所以对不同的标识符计算出的散列地址大多不相同， 即使其中有些字符相同。 在平方取中法中，一般取散列地址为2的某次幂。例 如，若散列地址总数取为m = 2r，则对内码的平方数 取中间的r位。如果r = 3，所取得的散列地址参看 图的最右一列。 4. 折叠法 此方法把关键字自左到右分成位数相等的几部分，每一部分的位数应与散列表地址位数相同，只有最后一部分的位数可以短一些。 把这些部分的数据叠加起来，就可以得到具有该关键字的记录的散列地址。 有两种叠加方法： 移位法 — 把各部分的最后一位对齐相加； 分界法 — 各部分不折断，沿各部分的分界来回折叠，然后对齐相加，将相加的结果当做散列地址。 示例：设给定的关键字为 key = 23938587841，若存储空间限定 3 位, 则划分结果为每段 3 位. 上述关键字可划分为 4段： 239 385 878 41 把超出地址位数的最高位删去, 仅保留最低的3位，做为可用的散列地址。 一般当关键字的位数很多，而且关键字每一位上数字的分布大致比较均匀时，可用这种方法得到散列地址。 5. 除留余数法 设散列表中允许的地址数为m,取一个不大于m，但最接近于或等于m的质数p,或选取一个不小于20的质因数的合数作为除数，利用以下公式把关键字转换成散列地址。散列函数为： hash ( key ) = key % p p ? m 其中, “%”是整数除法取余的运算，要求这时的质数p不是接近2的幂。 示例：有一个关键字 key = 962148，散列表大小 m = 25，即 HT[25]。取质数 p= 23。散列函数 hash ( key ) = key % p。则散列地址为： hash ( 962148 ) = 962148 % 23 = 12 可以按计算出的地址存放记录。需要注意的是，使用上面的散列函数计算出来的地址范围是 0到 22，因此，从23到24这几个散列地址实际上在一开始是不可能用散列函数计算出来的，只可能在处理溢出时达到这些地址。 以上介绍了几种常用的散列函数。在实际工作中应根据关键字的特点，选用适当的方法。有人曾用“轮盘赌”的统计分析方法对它们进行了模拟分析，结论是平方取中法最接近于“随机化”。 在应用平方取中法时，若关键字不是整数而是字符串时，可以把每个字符串转换成整数。 转换的方法： 把字符串从右向左，按一个固定长度 (例如 4 ) 进行分段，必要时可在最左端添一些空格。 把每一个字符看成为一个数字，把字符串的每一段看作为一个整数。如, ASCII码采用7位字符代码，因此每一个字符可以看成一个128进制的数字。字符串abcd看成整数 a*(128)3 + b*(128)2 + c*(128) + d。 把字符串的每一段都转换成一个整数后，再把各段转换成的整数加起来。 如果这个整数之和太大，再选择一个适当的常数C (大于任一段字符串转换成的整数)来除这个和并取其余数，就得到这个字符串所对应的整数了。 1. 开放定址法（闭散列）——是处理溢出的一种常用的方法 Hash函数： Hi = (H(key)+di) MOD m, i=1,2,…,k(k≤m-1) 其中：H