现在我有一个问题,当我在插入过程中使用线性探测时,我被问到从哈希表中删除值的成本.
我可以通过阅读互联网上的各种内容来弄清楚它必须对负载因素做些什么.虽然我不确定,但是我读了加载因子和所需探针之间的关系,它是探针No = 1 /(1-LF).
所以我认为成本必须取决于探针序列.但是,另一个想法毁了一切.
如果元素插入p探针中,现在我试图删除此元素,该怎么办？但在此之前,我已经删除了几个具有相同哈希码的元素,并且是少于p的探针插入的一部分.
在这种情况下,我到达一个阶段,我在哈希表中看到一个空的空格但我不确定我试图删除的元素是否已经被删除或者是因为探测而在某个其他位置.
我还发现,一旦我删除了一个元素,我必须用一些特殊的指示符来标记这个插槽,以告知它是可用的,但这并不能解决我不确定我愿意删除的元素的问题.
有人可以建议如何在这种情况下找到费用吗？如果是非线性探测,方法是否会发生变化？