为 BST 实现 hashCode

Question

在Java中比较两个异议是否相等，必须同时实现equals方法和hashCode方法。我需要比较两个 BST 是否相等。在这种情况下如何实现 hashCode 方法？现在，在 Node class 上实现 hashCode 非常简单：假设我的数据是 int。但是我不能只添加节点的值来检查树是否相等。那我该怎么做呢？有没有人成功地做到了这一点？

我正在考虑我可以做的许多不同的事情，但我不确定它们的可扩展性如何。例如，我可以使用级别顺序，并为每个级别乘以一个大质数，但我不确定这是否有效。所以也许更了解的人可以帮助我。谢谢。

Answer 1

I cannot just add the values of the node to check if the trees are equal.

当然可以。 hashCodes 不必是唯一的，如果两个 BST 具有相同的内容，那么对节点内容求和将在每种情况下得到相同的结果，这满足 hashCode 契约。请记住——return 0 总是 hashCode() 的有效实现；不需要唯一性。

（对节点内容的hashCode求和，其实就是TreeSet.hashCode()的实现方式）

另一方面，如果你关心结构，你可以做一些简单的事情，比如用

实现Node.hashCode()

int h = contents.hashCode();
h = h * 31 + Objects.hashCode(leftChild);
h = h * 31 + Objects.hashCode(rightChild);
return h;

...这也会让您获得一个体面的尊重结构的哈希函数。

为 BST 实现 hashCode

Implementing hashCode for a BST

java

binary-search-tree

equals