(2)平方探测法发生冲突时前后查找空位置描述公式为：dg=h(k)，d,=(d士i2） mod m(1≤i≤m-1)3245678.****16/62
发生冲突时前后查找空位置。 描述公式为：d0=h(k)， di=(d0±i 2) mod m (1≤i≤m-1) 0 1 2 3 4 5 6 7 8 9 * * * * * * * * 16/62
平方探测法可以避免出现堆积问题。缺点是不能探测到哈希表上的所有单元，但至少能探测到一半单元。17/62
平方探测法可以避免出现堆积问题。 缺点是不能探测到哈希表上的所有单元，但至少能探测到一半单元。 17/62
【例9.18】假设哈希表ha长度m=13，采用除留余数法和线性探测法解决冲突建立关键字集合{16，74，60，43，54，90，46，31，29，88，77)的哈希表。解：n=11，m=13，除留余数法的哈希函数为：h(k)=k mod pp应为小于等于m的素数，假设p取值13。18/62
【例9.18】假设哈希表ha长度m=13，采用除留余数法和线性探测法解决 冲突建立关键字集合{16，74，60，43，54，90，46，31，29，88，77}的 哈希表。 解：n=11，m=13，除留余数法的哈希函数为： h(k)=k mod p p应为小于等于m的素数，假设p取值13。 18/62
哈希函数：h（k）=kmod13解决冲突方法：线性探测法ha[3]=16,共1次探测h(16)=3ha[9]=74,共1次探测h(74)=9ha[8]=60,共1次探测h(60)=8h(43)=4ha[4]=43,共1次探测ha[2]=54,共1次探测h(54)=2h(90)=12ha[12]=90,共1次探测h(46)=7ha[7]=46,共1次探测h(31)=5ha[5]=31,共1次探测19/62
哈希函数：h(k)=k mod 13 解决冲突方法：线性探测法 h(16)=3 ha[3]=16,共1次探测 h(74)=9 ha[9]=74,共1次探测 h(60)=8 ha[8]=60,共1次探测 h(43)=4 ha[4]=43,共1次探测 h(54)=2 ha[2]=54,共1次探测 h(90)=12 ha[12]=90,共1次探测 h(46)=7 ha[7]=46,共1次探测 h(31)=5 ha[5]=31,共1次探测 19/62
有冲突h(29)=3仍有冲突dg=3, di=(3+1) % 13=4仍有冲突dz=(4+1) % 13=5ds=(5+1) % 13=6ha[6]=29,共4次探测h(88)=10ha[10]=88,共1次探测有冲突h(77)=12ha[0]=77，共2次探测de=12, di=(12+1) % 13=0哈希表ha[0..12]下标3702568910111214k77541643312946608890741421111111探测次数120/62
h(29)=3 有冲突 d0=3，d1=(3+1) % 13=4 仍有冲突 d2=(4+1) % 13=5 仍有冲突 d3=(5+1) % 13=6 ha[6]=29,共4次探测 h(88)=10 ha[10]=88,共1次探测 h(77)=12 有冲突 d0=12，d1=(12+1) % 13=0 ha[0]=77，共2次探测 下标 0 1 2 3 4 5 6 7 8 9 10 11 12 k 77 54 16 43 31 29 46 60 74 88 90 探测次数 2 1 1 1 1 4 1 1 1 1 1 哈希表ha[0.12] 20/62