java - 为 BST 实现 equals 和 hashcode

Question

这个问题是对 Implementing hashCode for a BST 的跟进.我的问题没有经过深思熟虑，所以我得到了一个我不确定如何使用的答案。

我需要为 BST 实现 equals:以便 iff 两个 BST 在结构和内容上相等，然后 equals 返回 true。因此，我想我还需要实现 hashCode 函数。我得到了 hashCode 函数的答案，使得树的结构和内容相同。

@Override
puclic int hashCode(){
  int h = Objects.hashCode(data);//data is int
  int child=0;
  if(null != left)
    child =left.hashCode();
  if(null != right)
    child+= right.hashCode();
  if(0<child) h= h*31+child;
  return h;
}

但是我该如何实现 equals 函数呢？以下是否可行当且仅当树在结构和内容上都相同？

@Override
public boolean equals(Node otherRoot){
   return root.hashCode() == otherRoot.hashCode();
}

在某些情况下我可能会误报吗？

或者我的hashCode应该是

@Override
public int hashCode(){
  int h = contents.hashCode();
  h = h * 31 + Objects.hashCode(leftChild);
  h = h * 31 + Objects.hashCode(rightChild);
  return h;
}

在后一种情况下，我的 equals 会避免误报吗？

Answer 1

Will the following work iff the trees are equal in both structure and content? root.hashCode() == otherRoot.hashCode()

不，这是行不通的，因为哈希码相等是一条单行道:当对象相等时，哈希码必须相等。但是，当对象不相等时，哈希码可能相等也可能不相等。一旦您应用 pigeonhole principle，这就有意义了: 可能的哈希码数量约为 4B，而可能的 BST 数量几乎是无限的。

您可以采用与构建哈希码相同的方式构建比较 - 即递归:

• 检查被比较节点的值是否彼此相等。如果值不同，则返回 false
• 检查两个节点是否都有左子树。如果其中一个有左子树而另一个没有，则返回 false
• 检查两个节点是否都有右子树。如果其中一个有右子树而另一个没有，则返回 false
• 将 equals 递归地应用于左子树。如果结果为false，则返回false
• 递归地将等于应用于右子树。如果结果为false，则返回false
• 返回true