實現BST的equals和hashcode

Question

這個問題是跟隨Implementing hashCode for a BST。我的問題糟透了，所以我得到了一個我不確定如何使用的答案。

我需要實現equals爲BST：讓當且僅當 2個BSTS在結構和內容相等，則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樹的結構和內容是否相同？

@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

請問以下工作iff樹的結構和內容是否相等？ root.hashCode() == otherRoot.hashCode()

不，它不會工作，因爲散列碼相等是單向街道：當對象相等時，散列碼必須相等。但是，當對象不相等時，散列碼可能相等或不相等。一旦應用了pigeonhole principle，這是有道理的：可能的哈希碼的數量約爲4B，而可能的BST的數量實際上是無限的。如果被比較的節點的值相等

• 檢查：即遞歸 -

  你可以建立你建立的散列碼以同樣的方式進行比較。如果值不同，請返回false

• 檢查兩個節點是否都有左子樹。如果其中一個有左子樹，另一個沒有，則返回false
• 檢查兩個節點是否都有右子樹。如果其中一個有右側子樹，另一個沒有，則返回false
• 將equals遞歸應用到左側子樹。如果結果爲false，則返回false
• 將equals遞歸應用到右子樹。如果結果爲false，返回false
• 返回true

Answer 2

不知道什麼對象是，但你最後的hashCode（）的例子就需要處理空，我想是這樣的：

@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如果樹是深足，所有的h * 31.

hashCode的contract並不保證相等性，所以您可能需要調用等於樹的所有方式以確保一切均衡。

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); 
    } 

} 

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; 
}