索引结构与散列.pptVIP

第十章 索引结构与散列 散列 记录的存放位置和标识它的关键码之间的对应关系? 选择适当的数据结构, 很方便地根据记录的关键码检索到对应记录的信息。 表项的存放位置及其关键码之间的对应关系可以用一个二元组表示： ( 关键码key，表项位置指针addr ) §10.4 散列 (Hashing) 散列表 在表项存储位置与其关键码之间建立一个确定的对应函数关系Hash( )，使每个关键码与结构中一个唯一存储位置相对应： Address ＝ Hash ( Rec.key ) 在有哪些信誉好的足球投注网站时, 先对表项的关键码进行函数计算,把函数值当做表项的存储位置, 在结构中按此位置取表项比较。在存放表项时, 依相同函数计算存储位置, 并按此位置存放。此方法称为散列方法。 在散列方法中使用的转换函数叫做散列函数。按此方法构造出来的表或结构就叫做散列表。 对于散列方法, 需要讨论以下两个问题： 对于给定的一个关键码集合, 选择一个计算简单且地址分布比较均匀的散列函数, 避免或尽量减少冲突； 拟订解决冲突的方案。 1. 直接定址法 此类函数取关键码的某个线性函数值作为散列地址： Hash ( key ) ＝ a * key + b { a, b为常数 } 这类散列函数是一对一的映射，一般不会产生冲突。但是，它要求散列地址空间的大小与关键码集合的大小相同。 散列函数 例：有一组关键码如下：{ 942148, 941269, 940527, 941630, 941805, 941558, 942047, 940001 }。散列函数为 Hash (key) = key - 940000 Hash (942148) = 2148 Hash (941269) = 1269 Hash (940527) = 527 Hash (941630) = 1630 Hash (941805) = 1805 Hash (941558) = 1558 Hash (942047) = 2047 Hash (940001) = 1 可以按计算出的地址存放记录。 3. 除留余数法 设散列表中允许地址数为 m, 取一个不大于 m, 但最接近于或等于 m 的质数 p 作为除数, 利用以下函数把关键码转换成散列地址： 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. 平方取中法 此方法在词典处理中使用十分广泛。 它先计算构成关键码的标识符的内码的平方, 然后按照散列表的大小取中间的若干位作为散列地址。 例：标识符的八进制内码表示及其平方值 标识符 内码 内码的平方 散列地址 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 5. 折叠法 此方法把关键码自左到右分成位数相等的几部分, 每一部分的位数应与散列表地址位数相同, 只有最后一部分的位数可以短一些。 把这些部分的数据叠加起来, 就可以得到具有该关键码的记录的散列地址。 有两种叠加方法： 移位法 — 把各部分的最后一位对齐相加； 分界法 — 各部分不折断, 沿各部分的分界来回折叠, 然后对齐相加, 将相加的结果当做散列地址。 例: 设给定的关键码为 key = 23938587841, 若存储空间限定 3 位, 则划分结果为每段 3 位。 上述关键码可划分为 4段： 239 385