第8章-查找讲述.ppt

Hash函数的构造方法 (2) 数字分析法 选取key中随机性较好的若干位作为H(key)。 例 8.15 设记录数为80，记录的key为6位10进制数，即 key=(k1 k2 k3 k4 k5 k6)10，ki(1≤i≤6)=0|1|2|……|9。 k1 k2 k3 k4 k5 k6 2 3 1 5 8 6 2 4 2 3 4 6 2 3 3 7 9 6 2 3 9 8 8 6 … … … … … … 2 4 5 7 8 6 2 3 4 2 9 6 设表长为100，地址空间为00～99，则可令： H(key)=kikj ki、kj为key中的某两位。具体取哪两位呢？ 例如这80个记录的key如右表： k3、k4的随机性较好，故取H(key)= k3 k4。 于是，key=231586的记录被映像到“15”号单元，key=242346的记录被映像到“23”号单元， 依此类推。 这种方法仅适合于key的集合预先知道的情况。 Hash函数的构造方法 (3) 平方取中法 取key2中间的某些位作为H(key)。位数视Hash表的存储空间而定。 例 key为6位数，地址范围为0-4000。设key=172148，则 (172148)2=29634933904，取3493。 说明：若超过4000，可乘以一个比例因子0.4。 随机性较好，key的每一位都起作用。 Hash函数的构造方法 (4) 叠加法 将key分割成位数相同的几部分（最后一部分位数可少），然后将各部分相加作为Hash地址。 该方法又分为“移位叠加”和“间界叠加”，前者是将分割后的每部分低位对齐相加；后者是沿分割线来回折叠、对齐相加。 例 key地址为3位，则Hash地址取 328 348 72 + 748 H(key)= Hash函数的构造方法 (5) 保留余数法 设Hash表长度为m(槽数)，选取一个≤m的最大素数p，令： H(key) = key % p 说明：选择素数的随机性好。 (6) 随机函数法 令：H(key)=C*random(key) 其中random(key)为相应于key的一个随机函数；C为常数，选取相应的C值使得H(key)符合Hash地址的要求。 Hash函数的构造方法 构造/选取Hash函数要考虑的因素： key的长度、类型以及分布的情况； 给定的Hash表表长m； 记录的查找效率等。 目的是使记录尽可能均匀分布，减少冲突的发生。 3.处理冲突的方法 8.4 Hash表的查找 设Hash表地址空间为0～m-1（表长为m）： … R(k) … H(key): 0 1 j-1 j j+1 m-1 冲突：表中某地址j∈[0，m-1]中己存放有记录，而另一个记录的H(key)值也为j。 在处理冲突的过程中，可能发生一连串的冲突，即可能得到一个地址序列H1、H2 、 …、Hn，Hi∈[0，m-1]。H1是冲突时选取的下一地址，而H1中可能己有记录，又设法得到下一地址H2，……，直到某个Hn不发生冲突为止。这种现象称为“聚积”，严重影响Hash表的查找效率。 引起冲突的因素除了Hash函数的随机性不好外，聚积的发生会加剧冲突。还有一个因素是表的装填因子(load factor, 或称负载因子)α，α=n/m，m为表长，n为表中记录个数。一般α在0.7～0.8之间，使表保持一定的空闲余量，以减少冲突和聚积的发生。 (1) 开放地址法 当发生冲突时，在H(key)的前后找一个空闲单元来存放冲突的记录，即在H(key)的基础上获取下一地址： Hi=(H(key) + di) % m 其中，m为表长，%运算是保证Hi落在[0，m-1]区间；di为地址增量。 di的取法有多种： 1）di=1，2，3，……，(m-1)——称为线性探查法 2）di=12，-12，22，-22，……——称为二次探查法（平方探查法） 第1次发生冲突时，地址增量d1取1或12；再冲突时，d2取2或-12，……，依此类推。 处理冲突的方法 处理冲突的方法 例