数据结构与算法 · 单选题 · 第 51 题
计算机基础面试八股 · 第 51 题
哈希表用线性探测的开放定址法处理冲突时,如果删除元素时直接把该位置置为空,会出现什么问题?
- A哈希函数的计算结果被改变,之后所有键都会映射到错误的位置上
- B哈希表的容量会被自动缩小为原来的一半,并触发一次全量的重新哈希
- C被删除元素占用的内存永远无法释放,长期运行后会产生严重的内存泄漏
- D后面查找经过这个空位时会提前停止,导致找不到实际存在的元素
答案
D D. 后面查找经过这个空位时会提前停止,导致找不到实际存在的元素
解析
线性探测查找时遇到空位就认为键不存在。某个元素当初可能是因为冲突被放到了后面,中间的位置一旦被清空,探测链就断了。正确做法是打上「已删除」标记(墓碑):查找时跳过它继续探测,插入时可以复用它。