散列表的检索 检索算法 ■与插入过程类似 假设散列函数h,给定的值为K 采用的探查序列也相同 素实袤地址对应的空间未被占用,则 否则将该地址中的值与K比较,若相等 检索成功 我期查费毕设来舱处理3费蓀 关键码比较相等,检寰成功 地址空间未被占用,检索失败 丰检索算法(程序 删除 ate <class Key class Elem, cass KEComp class 删除记录的时候,有两点需要重点考虑 int i =0, pos=homee b/k Elem& @) const( (2)释放的存储位置应该能够为将来插入使用 套玨方法(分离的同义词子表)可 return true: 别凑法都只能作标记(惠碑),不能 若真正删除了探查序列将断掉 olPwhile home p(K, ) 法“直到某个地址空间未被占用(检失 基碑标记增加了平均检索长度 权新有:轨命究 T恤息@ 删除,断线索 删除带来的问题? M=15 ■另一方面,删除后释放的槽应该 h(key )=key %o13 能够为将来的插入使用 不想让散列表中的位置由于删除 而永远不可用 删隐41,检囊15 键码41和15的基地址鄙是第2个 果从毫中删除41,对15的检宗必票仍探查算2个19 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 109 散列表的检索 „ 与插入过程类似 „ 采用的探查序列也相同 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 110 检索算法 假设散列函数h，给定的值为K „ 若表中该地址对应的空间未被占用，则 检索失败 „ 否则将该地址中的值与K比较，若相等 则检索成功 „ 否则，按建表时设定的处理冲突方法查 找探查序列的下一个地址，如此反复下 去 „ 关键码比较相等，检索成功 „ 地址空间未被占用，检索失败 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 111 检索算法（程序） template <class Key, class Elem, class KEComp, class EEComp> bool hashdict<Key, Elem, KEComp, EEComp>:: hashSearch(const Key& K, Elem& e) const{ int i=0, pos= home= h(K); // 初始位置 while (!EEComp::eq(EMPTY, HT[pos])) { if (KEComp::eq(K, HT[pos])) { // 找到 e = HT[pos]; return true; } i++; pos = (home + p(K, i)) % M; }//while return false; } 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 112 删除 „ 删除记录的时候，有两点需要重点考虑： „ (1) 删除一个记录一定不能影响后面的检索 „ (2) 释放的存储位置应该能够为将来插入使用 „ 只有开散列方法（分离的同义词子表）可 以真正删除 „ 闭散列方法都只能作标记（墓碑），不能 真正删除 „ 若真正删除了探查序列将断掉 „ 检索算法 “直到某个地址空间未被占用（检索失 败）” „ 墓碑标记增加了平均检索长度 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 113 删除，断线索 „ M = 15 „ h(key) = key%13 „ 删除41，检索15 „ 关键码41和15的基地址都是第2个槽，15被线性探查放到第3个 „ 如果从表中删除41，对15的检索必须仍然探查第2个槽，断线索 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 26 25 41 15 68 44 6 36 38 12 51 北京大学信息学院 张铭 编写 ©版权所有，转载或翻印必究 Page 114 删除带来的问题? „ 另一方面，删除后释放的槽应该 能够为将来的插入使用 „ 不想让散列表中的位置由于删除 而永远不可用