6

我知道在使用 hashCode 和 equals 时还有其他关于一般最佳实践的问题，但我有一个非常具体的问题。

我有一个作为实例变量的类，它是同一个类的数组。更明确地说，这是代码：

Class Node{
    Node arr[] = new Node[5];
}

我需要覆盖类 Node 的 hashCode，而数组是确定两个 Node 是否相同的重要决定因素。如何有效地将数组合并到 hashCode 的计算中？

- 编辑 -

我正在尝试检查两个节点是否相同，这意味着它们具有相同数量的子节点，并且这些子节点会导致完全相同的状态。因此，我有效地尝试比较两个节点处的子树。我想知道是否可以使用散列来进行这种相等性检查。

我认为我实际上需要散列整个子树，但鉴于我的类定义的递归性质，我不确定我将如何去做。

4

5 回答 5

4

包括 http://download.oracle.com/javase/6/docs/api/java/util/Arrays.html#hashCode(java.lang.Object[]) 作为 hashCode() 实现的一部分。

于 2011-05-04T17:35:01.873 回答
2

我正在尝试检查两个节点是否相同，这意味着它们具有相同数量的子节点，并且这些子节点会导致完全相同的状态。因此，我有效地尝试比较两个节点处的子树。我想知道是否可以使用散列来进行这种相等性检查。

不，不应该使用散列来检查相等性。这不是它的目的。它最终可以帮助您找出对象是否不相等，但它不会告诉您它们是否相等。

相同的对象会产生相同的哈希值，但是两个不相等的不同对象也可以产生相同的哈希值。换句话说，如果散列值不同，你肯定知道对象是不同的。而已。

如果要测试相等性，则需要实现 equals。在您的情况下，您的方法可能会递归并引发堆栈溢出。如果您的对象包含对自身的引用怎么办？

如果要生成哈希，可以考虑数组的大小（以及它是否为空的事实），但我不会尝试使用数组中对象的哈希值，因为可能无限循环。它并不完美，但已经足够好了。

还有另一种激进的方法也可以提供良好的结果。不是动态计算哈希值，而是为每个 Node 对象实例设置一个随机的 int 值（我的意思是在创建时一劳永逸并始终返回该值）。在您的情况下，您不会通过获取数组中对象实例的哈希值来冒无限循环的风险。

如果哈希值相等，那么您需要开始比较数组对象实例。

REM：如果节点包含其他属性，则计算这些其他属性的哈希并忘记数组。当且仅当两个对象之间的哈希值相同时，才开始调查数组内容/大小。

REM2：评论提到 DAG 图，这意味着我们不会遇到递归问题。但是，该条件不足以保证 deepHashCode() 会成功。此外，这也将是矫枉过正。有一种更有效的方法可以解决这个问题。

如果 Node 使用的 hash 方法只使用数组来计算 hash 值，那么 deepHashCode() 可能会起作用。但这不会是有效的。如果哈希方法使用其他节点属性，那么这些属性也必须相等。

有一种更快的方法来比较节点是否相等。用唯一的编号标记每个节点实例。然后，要比较两个节点，首先比较它们的数组大小。如果相等，则使用它们的唯一编号比较每个数组中的节点。如果一个数组没有“拥有”另一个节点，那么我们不是在处理相等的节点。这个解决方案比递归要快得多。

于 2011-05-04T18:04:21.163 回答
1

这取决于你的平等标准是什么。数组中的顺序重要吗？如果是这样，您可能希望散列码取决于数组中节点的顺序。如果没有，您可能需要对数组中所有节点的哈希码进行异或运算。大概有些值可能是空的（所以要小心）。

基本上，您需要覆盖hashCode并equals一致地使得如果两个对象相等，它们将具有相同的哈希码。这是黄金法则。

Eric Lippert 有一篇关于.NET的精彩博客文章GetHashCode——该建议同样适用于 Java。

需要注意的一个潜在问题 - 如果您最终在节点中出现一个循环（对节点 A 的引用出现在节点 B 的数组中，反之亦然），您最终可能在哈希码计算中也有一个循环。

于 2011-05-04T17:35:27.480 回答
1

你可以使用Arrays.hashCode()和Arrays.equals()方法。

于 2011-05-04T17:37:17.450 回答
0

如果性能有任何问题，请在当前答案中添加几点。

首先，您需要确定节点中子节点的顺序是否重要。如果他们不这样做，则不能将哈希码用于数组。考虑围绕java.util.Set. 还可以考虑在内部使用一些排序来提高 equals 性能。例如，如果子树的深度/高度不同，您可以按深度排序。

其次，如果您的子树很深，您的哈希码可能会变得非常昂贵。所以我会缓存哈希码，并在构造时计算它（如果你的节点是不可变的），或者在突变时失效并按需重新计算。

第三，如果您的子树很深，请检查 equals() 中的哈希码并尽早返回 false。是的，哈希码由 Map 实现检查，但有些地方代码只是使用 equals() 比较两个对象，它们可能会付出很大的代价。

最后，考虑使用 Arrays.asList() （如果子排序很重要）或 HashSet （如果排序无关紧要并且没有两个子节点相等）而不是简单的数组。然后将equals和hashcode简化为将调用委托给容器实例......当然，适当缓存hashcode。

于 2011-05-04T19:31:45.913 回答