1

我正在研究一个哈希图，并且在使用双哈希开放地址样式映射的删除功能时遇到了问题。假设我在大小为 10 的表上插入，我的 2 个哈希函数如下：

int hash( int key, std::size_t M ) { return key % M; }
int hash2( int key, std::size_t M ) { return key % (M-1) + 1; }

如果我使用键 0、10 和 20 插入项目，这些项目将转到位置 0、2 和 3。

<[ 0:A, - , 10:B, 20:C, - , - , - , - , - , - ]>

但是，在删除项目时，我想删除该项目并重新散列同一集群中的以下项目。当我删除密钥为 0 的项目时，它会发现要删除的项目没有问题。但是，它现在需要跳转到索引 2 - 但它不能因为它使用键 0 作为它的增量，所以它跳转到索引 1。因此，它永远不会在集群中找到后续项目。我该怎么做呢？？？

4

1 回答 1

3

通常，您可以通过在该位置放置已删除标记来删除项目。出于搜索的目的，它被占用，因此碰撞并需要探测才能找到的项目不是孤立的。但是在插入时，您可以重复使用该位置。如果表中已删除标记的数量变大，您可以重新散列表以清理它。

本讲座更详细地解释：开放寻址

于 2014-11-30T17:06:43.663 回答