二分查找

是: 如何选取 p ? p 应为不大于m 的最大质数 例：设表长m=8，16，32，64，128，1001 则 p=7，13，31，61，127，1001四、冲突的概念与处理方法四、冲突的概念与处理方法　　　若对于不同的键值k1和k2,且k1 ≠ k2, 　但 hash(k1)=hash(k2)，即具有相同的散列地址，这种现象称为冲突。 称 k1、k2称为同义词。 例8.4 key={3,15,20,24}，m=5（表长）， hash(k)=k%5 hash(15)=0 hash(20)=0 产生冲突。 冲突的处理——链地址法冲突的处理——链地址法将具有相同散列地址的记录都存储在同一个线性链表中。 例8.5 key={14,1,68,27,55,23,11,10,19,20,79,84}, hash(key)=key % 13, 用链地址法解决冲突, 构造hash表。 hash(14)=hash(1)=hash(27)=hash(79)=1 hash(68)=hash(55)=3 hash(19)=hash(84)=6 hash(20)=7 hash(23)=hash(10)=10 hash(11)=11 null127 79hash(key)= key % 13 hash(14)=1 hash(1)=1 hash(68)=3 hash(27)=1 hash(55)=3 hash(23)=10 hash(11)=11 hash(10)=10 hash(19)=6 hash(20)=7 hash(79)=1 hash(84)=6146819 2023 11 55 84 10ASL=（6*1+4*2+1*3+1*4）/12=21/12冲突的处理——线性探测法冲突的处理——线性探测法 对给定的关键值 key，若地址d (即hash(key)=d) 的单元发生冲突，则依次探查下述地址单元：　　 　　　d+1,d+2,….,m-1, 0 ,1,…d-1 直到找到一个开放的地址（空位置）止，将发生冲突的键值 放到该地址中。 设增量函数为d(i)=1,2,3,……m-1, m表长 i: 为探测次数。 null例8.6　以{14,1,68,27,55,23,11,10,19,20,79,84} , 构造 hash表。hash表长度为17, hash(key)=key % 17。 用线性探测法解决冲突。 hash 表： 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 14681552720198479112310比较次数： 3 3 ASL=(1*10+3*2)/12=16/12