c++ - 双重哈希 - 删除和重新哈希函数

Question

我正在处理散列映射，但在使用双散列开放地址式映射的删除函数时遇到了问题。假设我在一个大小为 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 - 但它不能因为它使用 key 0 作为其增量，所以它跳转到索引 1。因此，它永远不会在集群中找到后续项目。我该怎么做？？？

Answer 1

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

本讲座详细解释:Open Addressing