Java 哈希表实现

Question

在我的哈希表实现中，我的哈希函数只是获取我传递的项的值，调用 hashCode(继承自 Object 类)，并对内部数组的大小取模。这个内部数组是一个 LinkedList 数组。现在，如果我的 LinkedList 变得太长(并且我的效率开始从 O(1) 滑落到 O(n))，我认为简单地增加数组的大小是有意义的。但这就是我的问题所在，因为我说过我对传递的项目进行哈希处理并对数组的大小(刚刚更改)进行取模。如果我继续，散列是否会指向数组中的不同索引，从而失去引用散列表中项目的能力？我该如何解决这个问题？

Answer 1

您需要每个项目的实际哈希值，以便可以将它们放入调整大小的表中的正确哈希链中。 (否则，正如您所观察到的，这些元素很可能最终出现在错误的链上，并且因此无法定位。)

有两种方法可以解决这个问题:

• 您只需在将每个项目添加到新表时重新计算其哈希值即可。

• 您可以为哈希链中的每个项目保留原始哈希值的副本。这就是标准 Java HashMap 实现的作用……至少在我看过的版本中是这样。

(后者是时间与空间的权衡，如果您的项目具有昂贵的 hashcode 方法，可能会带来巨大的返回。但是，如果您摊销哈希表的生命周期，此优化不会改变任何公共(public) API 方法的“大 O”复杂性……假设您的哈希表大小调整是指数级的；例如，您每次大约将表大小增加一倍。)