删除应在哈希表中的记录的返回false的函数

Question

我正在制作一个哈希表，它使用线性探测作为冲突解决方法。我已经测试了我的其他函数，它们都能正常工作，我只是不能弄清楚在删除时出了什么问题。我正在尝试使用惰性删除策略，即只在记录中将布尔标记标记为已删除或未标记。我假设我在某个地方遗漏了一个逻辑步骤，因为当传递给函数时，显然找不到应该删除的键。

Answer 1

我看到了remove的几个问题。

主要原因是你的循环中的idx计算是错误的。它应该是

int idx = (hash + i) % LargerMax;

就像你在update中做的那样。

您没有正确处理已删除的记录。想一想，如果您插入两个具有smae散列值的记录( A，然后是B)，然后删除记录A，那么您的列表将是什么样子?如何找到B？(在继续阅读之前请仔细考虑这一点。)

当您遍历records_时，当您找到一个已删除的节点时，您需要跳过它并转到下一个节点。只有在找到空记录时才停止搜索。

如果你已经遍历了所有的节点但没有找到，你也需要在函数的末尾执行return false。