实现二叉搜索树的equals和hashcode方法

Question

这个问题是对实现BST的hashCode的跟进。我的问题思考不够充分，所以我得到了一个答案，但我不确定如何使用它。

我需要为BST实现equals：当且仅当两个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函数呢？如果树的结构和内容相等，以下代码是否有效？请注意，"iff" 是 "if and only if" 的缩写。

@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方法能避免误判吗？

- Katedral Pillon

---

两个哈希码相同并不意味着两个对象相等。规则应该是“被认为相等的两个对象应该具有相同的哈希码”。将哈希码乘以31没有任何有用的作用；对于足够大的树或整数值，你很可能会引起算术溢出。 - Apprentice Queue

Answer 1

如果两棵树的结构和内容相同，那么下面这个代码是否会起作用呢？ root.hashCode() == otherRoot.hashCode() 不会，因为哈希码的相等是单向的：当对象相等时，哈希码必须相等。然而，当对象不相等时，哈希码可能相等也可能不相等。这在应用鸽笼原理后就很容易理解了：可能的哈希码数量约为4B，而可能的二叉搜索树数量几乎是无限的。

你可以像递归计算哈希码一样递归地构建比较方法。

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

- Sergey Kalinichenko

Answer 2

我不确定Objects是什么，但是你最后一个hashCode()的例子需要处理null，我认为应该像这样：

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

我可以看到如果树足够深，所有的 h * 31 就会溢出。

hashCode 的 合同 并不保证相等性，所以你可能需要一直调用 equals 来确保整个树都平衡。

- Scott Sosna

---

Objects.hashCode会处理空值检查。 - Raniz

Answer 3

我没有确切地测试过这个，但这里是一个开始的地方。

public boolean equals(Object o) {
  // exact same object
  if(this === o) {
    return true;
  }

  if(!o instanceof Node) {
    return false
  }

  Node otherTree = (Node) o;

  boolean selfHasLeft = this.left == null,
          selfHasRight = this.right == null,
          otherHasLeft = otherTree.left == null,
          otherHasRight = otherTree.right == null;

  // this tree must have the same children as the other tree
  if(selfHasLeft != otherHasLeft || selfHasRight != otherHasRight) {
    return false;
  }

  // must have same value
  if(this.value != other.value) {
    return false;
  }

  // if they have no children then now they should be the same tree
  // otherwise, check that their children are the same
  if(!selfHasLeft && !selfHasRight) {
    return true;
  } else if(selfHasLeft && !selfHasRight) {
    return this.left.equals(otherTree.left);
  } else if(selfHasRight && !selfHasLeft) {
    return this.right.equals(otherTree.right);
  } else {
    return this.left.equals(otherTree.left) && this.right.equals(otherTree.right);
  }

}

- Transcendence

Answer 4

你的第二个hashCode实现看起来不错，但是当可能对象的数量大于int的范围时（这里就是这种情况），你永远无法避免哈希码冲突，因此你不应该在equals中使用哈希码。

你应该做的是像这样（假设类名为BST）：

public boolean equals(Object other) {
    if(this == other) {
        return true;
    }
    if(!(other instanceof BST)) {
        // If other is null we will end up here
        return false;
    }

    BST bst = (BST) other;

    // Check equality of the left child
    if(left != null) {
        if(!left.equals(other.left)) {
            // Left childs aren't equal
            return false;
        }
    } else if (other.left != null) {
        // this.left is null but other.left isn't
        return false;
    }

    // Check equality of the right child
    if(right != null) {
        if(!right.equals(other.right)) {
            // Right childs aren't equal
            return false;
        }
    } else if (other.right != null) {
        // this.right is null but other.right isn't
        return false;
    }
    // Both left and right childs are equal
    return true;
}

- Raniz