判断下列说法是否正确：若采用开放定址法处理冲突，则删除元素只

[单选题]

判断下列说法是否正确：若采用开放定址法处理冲突，则删除元素只需直接将该元素从哈希表中删去即可。( )

```
正确
```
```
错误
```

推荐

Jino.

按照线性探测的规则，先后插入彼此冲突的一组元素都将存放在同一个查找序列中，而更确切地讲：它们应该按照逻辑次序构成整个查找链的一个前缀，其中不得有任何的空桶缝隙。因此元素的删除操作需要做额外的一些处理，如果我们不做一些事先准备，直接将词条删除（就类似对于链表，删除节点的时候不做链条调整，而直接free那个单元，那不直接凉了），就会造成查找链断裂，后续词条丢失——明明存在但访问不到。

对于这种连续空间的单元删除，一个直观的构想是：将后续词条悉数取出，再重新插入。但这太特么慢了，时间复杂度爆炸。其实对于这个问题有一种典型的处理手法：lazy delete，仅做一个删除标记，比如里面预留一个del变量，设置为TRUE。

那么在日后查找中，遇到之后就应该越过继续往后查找而不是在此返回。在插入时遇到，就把它视作一个空单元，数据覆盖即可。应该说针对开放定址策略，懒惰删除不仅是“不得已而为之”的方法，甚至可以说是针对这种情况的最优方法。因为毕竟在开放定址策略中，每一个桶单元都同时属于多个查找链。

编辑于 2019-12-06 14:14:16 回复(0)

白驹之过隙

选B。

用开放定址法解决冲突的做法是：当冲突发生时，使用某种探测技术在散列表中形成一个探测序列。沿此序列逐个单元地查找，直到找到给定的关键字，或者碰到一个开放的地址（即该地址单元为空）为止（若要插入，在探查到开放的地址，则可将待插入的新结点存人该地址单元）。查找时探测到开放的地址则表明表中无待查的关键字，即查找失败。

发表于 2019-12-05 22:10:10 回复(0)