Java 使用桶法的哈希表

Question

如何在哈希解决方案中搜索某个存储桶以找到密钥？我无法弄清楚如何查看我的密钥是否已经在给定的存储桶编号中。我不明白如何读取数组中的桶。

我正在使用不是 Java 的桶编写自己的哈希数据结构。

Answer 1

根据哈希码找到项目所在的存储桶后，您将必须在同一存储桶中的所有对象中查找有问题的项目。现在所有这些对象都具有相同的 hashCode，因为它们都在同一个桶中。因此，您必须实际将这些对象与 .equals 方法进行比较，以查看您实际要查找的项目是否存在。

如何管理共享同一个存储桶的这组项目取决于您。您可能有一个列表、子数组或任何包含对象集合的数据结构。

事实上，您根本不需要将它们全部放在同一个桶中。有称为开放哈希的方案，其中具有相同哈希 'spill' 的项目从目标桶中取出，并占据顶部数组中的连续桶。

在不知道您的确切数据结构的情况下，我无法提供更具体的信息。但基本上你使用 hashCode 将你带到顶部桶，然后你使用 equals 在具有相同 hashcode 的对象组中找到对象。