为BST实现hashCode [英] Implementing hashCode for a BST

问题描述

在Java中比较两个反对是否相等，必须同时实现equals方法和hashCode方法.我需要比较两个BST的相等性.在这种情况下如何实现hashCode方法?现在，在Node类上实现hashCode很简单:想象我的数据是int.但是我不能只添加节点的值来检查树是否相等.那我该怎么办呢?有人成功做到了吗?

In Java to compare two objections for equality, you must implement both the equals method and the hashCode method. I need to compare two BSTs for equality. How do I implement the hashCode method in such a case? Now, implementing the hashCode on the Node class is simple enough: imagine my data is int. But I cannot just add the values of the node to check if the trees are equal. So how do I do it? Has anyone done this successfully?

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

I am thinking of many different things that I can do, but I am not sure how scalable they would be. For example I could use level order and for each level multiply by a large prime number, but I can't be sure that this would work. So maybe someone who understands better can help me. Thanks.

推荐答案

我不能只添加节点的值来检查树是否相等.

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

可以. hashCode不必是唯一的，并且如果两个BST的内容相同，那么对节点的内容求和将在每种情况下为您提供相同的结果，这满足hashCode约定.请记住-return 0总是 是hashCode()的有效实现；不需要唯一性.

Sure you can. hashCodes do not have to be unique, and if two BSTs have the same contents, then summing the node contents will give you the same results in each case, which satisfies the hashCode contract. Remember -- return 0 is always a valid implementation of hashCode(); uniqueness is not required.

(实际上，总结节点内容的hashCode就是实现TreeSet.hashCode()的方式.)

(Summing the hashCodes of the node contents is, in fact, how TreeSet.hashCode() is implemented.)

另一方面，如果您关心结构，则可以做一些简单的事情，例如用实现Node.hashCode()

On the other hand, if you care about structure, you could do something simple like implementing Node.hashCode() with

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

...这也将为您提供一个体面的，尊重结构的哈希函数.

...and that'd get you a decent structure-respecting hash function, too.

这篇关于为BST实现hashCode的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！