为BST实现hashCode

Question

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

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

Answer 1

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

你当然可以. hashCodes不必是唯一的,如果两个BST具有相同的内容,那么对节点内容求和将在每种情况下给出相同的结果,这满足hashCode合同.记住- return 0是永远的有效执行hashCode(); 不需要唯一性.

(实际上,总结节点内容的hashCodes是如何TreeSet.hashCode()实现的.)

在另一方面,如果你关心的结构,你可以做一些简单的像实施Node.hashCode()与

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

......那也会让你得到一个体面的结构 - 尊重哈希函数.