S9.4.4散列表上的运算 §9.4.4散列表上的运算 3、除 ◆不成功 开地址法不能真正除（置空），而应该置特定标记Deleted 线性探测：直到探测到开地址为止 香查找制：银测到Deleted标记时，锁块绿测 ASL=(9+8+7+6+5+4+3+2+1+1+2+1+10/13=4.541m=13 令摘入时：裸测到Deed标记时，将其滑作开地址，捕入新销点 当有除操作时，一般不用开地址法，而用拉链法 0123456789101112 T0.1261241156840651■☐3638 4、性能分析 探测次数98765432112110 只分析查找时间，插取决于查找，因为冲突，仍需比较。 ■例子（见例1和例2图） 注意：当m>p(p=散列地址集)时，分母应该为p 令成功 线性探：ASL=(16+22+31+91)/10=2.2n=10 拉链法：不包括空指针判定 拉藏法：ASL=(17+22+3*1)y10=1.4ln=0 ASL=(1+0+2+1+0+1+1+0+0+0+1+0+3/13=0.771m130 §9.4.4散列表上的运算 §9.4.4散列表上的运算 。不成功 鲁一般情况 拉继法：不包括空指针判定 令就性探闲 ASL=(1+0+2+1+0+1+1+0+0+0+1+0+3)/13=0.77m=13 成功：ASL=(1+1(1-a)2 26A 失意：ASL=(1+1(1-a)2)2 盟然，只与a相关，只要a合适，ASL=O(1)。 4 5冈 ◆其他方法优于线性探，略 68A A 44 06 5、用途 ”加速查找 36 加密等信息安全领城 A 12 3831251 比较次数：1 2 3 99 49 § 9.4.4 散列表上的运算 3、删除 „ 开地址法不能真正删除（置空），而应该置特定标记Deleted ™ 查找时：探测到Deleted标记时，继续探测 ™ 插入时：探测到Deleted标记时，将其看作开地址，插入新结点 „ 当有删除操作时，一般不用开地址法，而用拉链法 4、性能分析 只分析查找时间，插删取决于查找，因为冲突，仍需比较。 „ 例子（见例1和例2图） ™ 成功 线性探测：ASL＝(1*6+2*2+3*1+9*1)/10=2.2 //n=10 拉链法： ASL＝(1*7+2*2+3*1)/10=1.4 //n=10 50 § 9.4.4 散列表上的运算 ™ 不成功 线性探测：直到探测到开地址为止 ASL＝(9+8+7+6+5+4+3+2+1+1+2+1+10)/13=4.54 //m=13 注意：当m>p（p＝|散列地址集|）时，分母应该为p 拉链法：不包括空指针判定 ASL＝(1+0+2+1+0+1+1+0+0+0+1+0+3)/13=0.77 //m=13 T[0..12] 0 1 2 3 4 5 6 7 8 9 10 11 12 26 12 41 15 68 44 06 51 36 38 探测次数 9 8 7 6 5 4 3 2 1 1 2 1 10 51 § 9.4.4 散列表上的运算 ™ 不成功 拉链法：不包括空指针判定 ASL＝(1+0+2+1+0+1+1+0+0+0+1+0+3)/13=0.77 //m=13 0 1 2 3 4 5 6 7 8 9 10 11 12 44 ^ 41 15 26 68 06 36 38 12 ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ 51 比较次数： 1 2 3 52 § 9.4.4 散列表上的运算 „ 一般情况 ™ 线性探测 成功：ASL＝（1＋1/(1－α)）/2 失败：ASL＝（1＋1/(1－α)2）/2 显然，只与α相关，只要α合适，ASL＝O(1)。 ™ 其他方法优于线性探测：略 5、用途 „ 加速查找 „ 加密等信息安全领域