清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS 由R;所对应的键名查找 拥有该键的记录队列 否 找到了吗 是 由记录队列查找R; 返回空 否 找到了吗? 是 返回R;的逻辑地址)(返回空) 图76记录R的搜索过程
图7.6 记录 Ri的搜索过程
清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS 对键或记录的搜索与其他数据搜索问题一样,都属 于表格搜索问题。有许多搜索算法用来解决表格搜 索问题。这些算法可以大致分为三种类型。即,(1) 线性搜索法( Iinear search),(2)散列法(hash coding),(3)二分搜索法( binary search algorithm) 下面分别简单地介绍这几种搜索算法。 (1)线性搜索法 它从第一个键或记录开始,依次和所要搜索的键或 记录相比较,直到找到所需要的记录为止。线性搜 索法所需要的搜索时间与所搜索的表格大小的1/2 成正比。这是因为找到一个所需要的记录平均要和 表中登记的总项数的1/2项比较后才能得到。 线性搜索法的搜索效率较低,在文件中记录个数较 多时不宜采用
对键或记录的搜索与其他数据搜索问题一样，都属 于表格搜索问题。有许多搜索算法用来解决表格搜 索问题。这些算法可以大致分为三种类型。即，(1) 线性搜索法(linear search)，(2) 散列法(hash coding)，(3) 二分搜索法(binary search algorithm)。 下面分别简单地介绍这几种搜索算法。 (1) 线性搜索法 它从第一个键或记录开始，依次和所要搜索的键或 记录相比较，直到找到所需要的记录为止。线性搜 索法所需要的搜索时间与所搜索的表格大小的 1/2 成正比。这是因为找到一个所需要的记录平均要和 表中登记的总项数的1/2项比较后才能得到。 线性搜索法的搜索效率较低，在文件中记录个数较 多时不宜采用
清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS (2)散列法 散列搜索法被被广泛用于现代操作系统的数据查找。 散列法的核心思想是定义一个散列函数h(k),使得 对于给定的键k,散列函数h(k将其变换为所对应 的逻辑地址。 在使用散列函数进行搜索时,有时会出现两个不同 的输入值变换到同一地址的问题。即对于k=k2, 有h(k1)=h(k2)=A。显然,k和k2中,至少有一个与 A中的内容不一致。也就是说,由散列变换得到的 结果并不是所要搜索的键。这种问题称为散列冲突 解决散列冲突的方法是采用多次散列探索。例如, 设第i次散列变换的结果为h(k),i=2,3.,则可令 h; (k)=(h,( k)+d (mod t)
(2) 散列法 散列搜索法被被广泛用于现代操作系统的数据查找。 散列法的核心思想是定义一个散列函数h(k)，使得 对于给定的键k，散列函数h(k)将其变换为 k所对应 的逻辑地址。 在使用散列函数进行搜索时，有时会出现两个不同 的输入值变换到同一地址的问题。即对于k1 !=k2， 有h(k1 )=h(k2 )=A。显然，k1和k2 中，至少有一个与 A中的内容不一致。也就是说，由散列变换得到的 结果并不是所要搜索的键。这种问题称为散列冲突。 解决散列冲突的方法是采用多次散列探索。例如， 设第i 次散列变换的结果为hi (k)，i=2,3…，则可令 hi (k) =(h1 (k) +di )(mod t)
清华大学出版社 TSINGHUA UNIVERSITY PRESS 这里,t为被搜索表格长度,d为第次搜索所得地址 与第1次搜索所得地址之间的距离。d的取值方法 很多,最简单的方法是设d为的线性函数,即 d=a*i(a为一大于零的常数)。这种方法称线性散列 法。但是,使用线性散列法并不能完全解决散列冲 突问题。例如,对于认!=j,k=1,2…,如果 h(k)=h(k2),则存在h+k(k1)=h+k(k2) 解决散列冲突的另一个方法是生成一组随机数 {r1,r2,…,rn},且令d=r;o显然,除了 h1(k1)=h1(k2)可能存在之外,h1(k1)=h1+k(k2)的可能 性很小,不过,使用随机数的方法需要占用一定的 存储空间来生成和存放随机数组
这里，t 为被搜索表格长度，di为第i 次搜索所得地址 与第1次搜索所得地址之间的距离。di的取值方法 很多，最简单的方法是设di为i的线性函数，即 di=a*i(a为一大于零的常数)。这种方法称线性散列 法。但是，使用线性散列法并不能完全解决散列冲 突问题。例如，对于i!=j，k=1,2…，如果 hi (k1 )=hj (k2 )，则存在 hi+k(k1 )=hj+k(k2 ) 解决散列冲突的另一个方法是生成一组随机数 {r1 ,r2，…，rn }，且令di=ri。显然，除了 h1 (k1 )=h1 (k2 )可能存在之外，h1 (k1 )=h1+k(k2 )的可能 性很小，不过，使用随机数的方法需要占用一定的 存储空间来生成和存放随机数组
清华大学出版社 000000 TSINGHUA UNIVERSITY PRESS 还有一个解决散列冲突的方法是采用平方散列函数 方法。即令:h(k=(h1(k)+c*(*i)(modt) 这里,t是一个表示被搜索表格长度的素数,c是 个大于零的常数。可以证明,对于p1(modt),即 使有h1(k)=h(k2),那么,对于i1,2,…,t1,有 h(k1)}=h+lk2) (3)二分搜索法 对于顺序结构排列的键或记录来说,二分搜索法具 有较高的搜索效率。 设键K,K1K2,…,K1(n>1)按键间距d排列,如果K0 的逻辑位置为a,则有K的逻辑位置为a0+d
还有一个解决散列冲突的方法是采用平方散列函数 方法。即令： hi (k) =(h1 (k)+c*(i*i))(mod t) 这里，t是一个表示被搜索表格长度的素数，c 是一 个大于零的常数。可以证明，对于j>1(mod t)，即 使有 h1 (k1 )=hj (k2 )，那么，对于i=1,2，…，t-1，有 hi (k1 )!=hj+i(k2 )。 (3) 二分搜索法 对于顺序结构排列的键或记录来说，二分搜索法具 有较高的搜索效率。 设键K0 ,K1 ,K2，…，Kn (n>1)按键间距d排列，如果K0 的逻辑位置为a0，则有Ki的逻辑位置为a0+i*d