Clever Geek Handbook

Equals and hashcode implementation for BST

This question is kind of a follow-up to BST's hashCode implementation . My question was poorly thought out and so I got the answer that I don't know how to use it.

I need to implement equals

for BST: so iff two BSTs are equal in structure and content then equals

returns true. As such, I suppose I also need to implement the function hashCode

. I got the answer for the hashCode function so that the trees are the same in structure and content.

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

But how do you implement the equals function? Will iff's next job be equal to trees both in structure and in content?

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

Are there circumstances where I might mistakenly trust?

Or should my hashCode be

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

and in this latter case my equals

will avoid false positives?

+3


source to share


4 answers


Will iff's next job be equal trees both in structure and in content?root.hashCode() == otherRoot.hashCode()

No, it won't work because hash code equality is a one-way street: when objects are equal, hash codes must be equal. However, when the objects are not equal, the hash codes may or may not be equal. This makes sense if you apply the pigmentation principle: the number of possible hash codes is about 4B, and the number of possible BSTs is almost infinite.



You can plot the comparison the same way you plotted the hash code, i.e. recursively:

  • Check if the values ​​in the nodes being compared are equal to each other. If the values ​​are different, returnfalse

  • Check if both nodes have a left subtree. If one of them has a left subtree and the other does not, returnfalse

  • Check if both nodes have the correct subtree. If one of them has a right subtree and the other does not, returnfalse

  • Apply equals

    recursively to left subtrees. If result false

    , returnfalse

  • Apply equals

    recursively to the right subtrees. If result false

    , returnfalse

  • Return true

+4


source


Not sure what objects there are, but your latest hashCode () example should handle null, I would think something like:

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


I see an overflowing h if the tree is deep enough, with all h * 31.

The contract for hashCode does not guarantee equality, so you will probably need to call everything equal down the tree to make sure everything balances out.

+1


source


I haven't tested this for sure, but here's to get started

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

}
+1


source


The second implementation hashCode

looks good to me, but you can never avoid collisions with hash codes when the number of possible objects is greater than the range int

- here and here, so you shouldn't use a hash code in equals

.

What you should do is something like this (assuming the name of the class 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;
}
+1


source






More articles:


All Articles