c++ - 您如何搜索具有哈希名称的 vector 以进行匹配？

Question

所以我的教授给我们分配了这个项目。它非常简单，因为它是我们的第一个散列程序。该程序是将 15 个名称作为输入并将它们散列并存储在某个东西中。我在一个 vector 中做到了。现在，一旦对它们进行哈希处理，用户输入另一个名称，它将对该名称进行哈希处理，并尝试将其与 vector 中的名称相匹配。也许是我，也许是他写问题的方式，但我有点困惑。我们的程序假设有碰撞保护。这意味着我们对输入的名字运行一个算法，它会吐出一个数字，这个数字就是我们在 vector 中存储名字的地方。如果那个位置已经有另一个名字，我们假设将它存储在下一个可用位置。

假设我输入了名字 jordan 和 jon。该算法会告诉我将它们存储在同一个位置(比如说位置 8)，但是碰撞保护会识别出乔丹已经占据了位置(8)并且它将乔恩移动到下一个可用位置(比如说位置 9) .现在，当用户输入名称以查看它是否已经在 vector 中并且他输入 jon 时，算法将看到它应该在位置 8 中。你认为我应该检查一下那个位置是否为空，如果不是的话在第 8 个位置找到了一个匹配项，即使第 8 个位置中的名字是 jordan 并且输入的名字是 jon。或者我应该从位置 8 开始，看看字符串是否匹配，如果他们不检查下一个位置等等，直到我回到原来的位置或找到匹配项？

我写了这个程序并且运行良好，我只是遇到了这个难题，无法完成这个程序。谢谢

Answer 1

您的方法是 Open Addressing碰撞处理。

根据这种方法，当您搜索一个元素时，您应该“继续”直到找到第一个空位 - 只有这样才能保证所请求的元素不会被存储。