java - 哈希表线性探测

Question

我正在制作一个带有一个 String 数组一维和一个二维 int 数组的哈希表。我正在使用线性探测来进行碰撞检测，当我意识到如果检测到碰撞时，这个词的 hashCode 将不再是索引。我将如何保存该索引以供以后使用？

Answer 1

这是线性探测的缺点之一。如果发生冲突，您需要转到下一个可用索引，但这并不能确保下一个元素将是您正在寻找的元素，从而导致您的复杂度为 O(n) 而不是预期的 O(1 ）。您也许可以考虑为每个索引设置一个存储桶。如果发生冲突，您仍然可以使用正确的索引，例如，您只需遍历 LinkedList 即可找到您要查找的值。

线性探测更适用于存储空间有限的设备。如果您在桌面上编写程序，我建议您使用存储桶方法或官方术语分离链接。希望这可以帮助

Answer 2

在开放式寻址中，线性探测不仅用于解决冲突，还用于解决冲突。它还用于搜索正在查找的键。您总是从从哈希码派生的索引开始，然后继续前进，直到找到您要查找的内容，或者到达一个空槽或具有不同哈希码的条目。这实际上与单独的链接并没有什么不同，您还需要遵循链，直到找到关键。