HashCode implementation for BST
In Java, to compare two equality objections, you must implement both a method equals
and a method hashCode
. I need to compare two BSTs for equality. How to implement the method hashCode
in this case? The implementation hashCode
in the class Node
is now simple enough: imagine my data int
. But I can't just add the node values to check if the trees are equal. So how do I go about doing this? Has anyone done this successfully?
I am thinking of many different things I can do, but I am not sure how scalable they are. For example, I could use the order of the levels and multiply by a large prime for each level, but I cannot be sure that this will work. So maybe someone who understands better can help me. Thank.
source to share
I can't just add node values to check if the trees are equal.
Sure. hashCode
do not have to be unique, and if two BSTs have the same content, then summing the contents of the node will give you the same results in each case, which satisfies the contract hashCode
. Remember - is return 0
always a valid version hashCode()
; uniqueness is not required.
(Summing the hash codes of the contents of a node is essentially implemented as TreeSet.hashCode()
.)
On the other hand, if you care about structure, you can do something as simple as implement Node.hashCode()
with
int h = contents.hashCode(); h = h * 31 + Objects.hashCode(leftChild); h = h * 31 + Objects.hashCode(rightChild); return h;
... and that will give you a decent hash function structure too.
source to share