20

I'm having some trouble writing a hashCode() method for a class I created. This class is meant to be used inside a TreeSet, and as such, it implements Comparable. The class has the following variables:

public class Node implements Comparable<Node> {
   Matrix matrix;
   int[] coordinates= new int[2];
   Node father;
   int depth;
   int cost;

Here's the implementation of the compareTo() method. I want the TreeSet to organize these Node structures by their cost, therefore, compareTo() returns the result of a simple subtraction.

public int compareTo(Node nodeToCompare) {
    return this.cost - nodeToCompare.cost;
}

I also implemented an equals() method.

public boolean equals(Object objectToCompare) {
    if(objectToCompare== this) {return true;}
    if(objectToCompare== null || objectToCompare.getClass()!= this.getClass()) {return false;}

    Node objectNode= (Node) objectToCompare;
    return this.father.equals(objectNode.father) &&
            this.depth== objectNode.depth &&
            this.cost== objectNode.cost &&
            this.matrix.equals(objectNode.matrix) &&
            Arrays.equals(this.coordinates, objectNode.coordinates);
}

Having said all of that, I have a few questions:

  1. Since I implemented a new equals() method, should I implement a new hashCode() method?
  2. How can I go about implementing a new hashCode method() with those variables? (Note that the variable matrix of the type Matrix has a hashCode() method implemented)

That's all!

Improve this question

4 Answers 4

Reset to default
25

Your compareTo method is not consistent with your equals method: your compareTo method says that two instances are equivalent if they have the same cost — such that a TreeSet can only ever contain at most one instance with a given cost — but your equals method says that they're only equivalent if they have the same cost and are the same in various other ways.

So, assuming that your equals method is correct:

  • you need to fix your compareTo method to be consistent with it.
  • you need to create a hashCode method that is consistent with it. I recommend using the same sort of logic as is used by java.util.List.hashCode(), which is a straightforward and effective way to assemble the hash-codes of component objects in a specific order; basically you would write something like: 
    int hashCode = 1;
hashCode = 31 * hashCode + (father == null ? 0 : father.hashCode());
hashCode = 31 * hashCode + depth;
hashCode = 31 * hashCode + cost;
hashCode = 31 * hashCode + matrix.hashCode();
hashCode = 31 * hashCode + java.util.Arrays.hashCode(coordinates);
return hashCode;
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

But if I change the compareTo method, won't that change the way things are organized in a TreeSet?
@GonçaloLourenço: Yes. That's my point; right now, if n1.cost == n2.cost, then a TreeSet that contains n1 cannot contain n2. Is that really what you want?
Definitely not. Guess I'll have to use something else instead of TreeSet. Since you were the first to answer my question, I'll mark your answer as the right one. Thanks for all the help!
Just don't agree, if two hashcodes are equal, the objects can be not equal and tree set contains both.
I have, and from what I understood, I need to implement these three things in order for it to work properly with this Node structure. I might be wrong, though.
8

Intellij IDEA can do this as a ' right-click' feature. Just seeing it done correctly will teach you alot.

And you should override both in any case.

Improve this answer

1 Comment

@ToKra in my case, it added this line result = prime * result + getOuterType().hashCode();, but I wanted only the fields to have consistent hashcode (between reloads of the application), so, by commenting that line it worked properly. It was a inner class tho, that's why that line showed up.
3

The contract for the hashCode method states that if two objects are equal, then calling hashCode() should give you the same integer result. The opposite does not have to be true, i.e. if two hashCodes are the same the objects don't have to equal each other.

Looking at your equals method (which needs variable translation btw), you can add the hashCodes of all the internal member variables that need to be equals for your equals method to give true. e.g.

public int hashCode() {
    return this.matrix.hashCode() + 
           this.coordinates[0] + 
           this.coordinates[1] + 
           this.father.hashCode() +
           this.depth + this.cost;               
}

The above assumes that matrix and father are never nulls, you need to make sure that you check for nulls if that's not the case.

If you feel more adventurous you can multiply a few of the above with a prime to ensure you don't get hashCode collisions for different data (this will help improve performance if you are using your class in hashTables and hashMaps). If you need to cater for nulls, the above method can be written a bit better like this:

public int hashCode() {
    return ((this.matrix == null) ? 0 : this.matrix.hashCode()) + 
           17 * this.coordinates[0] + 
           this.coordinates[1] + 
           ((this.father == null) ? 0 : this.father.hashCode()) +
           31 * this.depth + 19 * this.cost;               
}
Improve this answer

6 Comments

Note that father is of type Node, so if it's never null, then your approach will result in infinite recursion and a stack overflow.
Yeah, I was afraid of that. Guess I'll have to change a few things around. Thanks for answering my question!
True, therefore we need to assume that a) either the father is nullable, or b) there are no circular paths in the graph. If neither of the above is true, then we should exclude the father from the hashCode calculation.
Having just posted the above comment, I'm thinking... the equals() method has exactly the same (recursive) problem regarding the father. You need to seriously consider if a different father constitutes a different node, if the rest of the Node's data are the same?
Hm, that's a really good point. I'll keep that in mind, it might be the game changer I'm looking for.
|
0

If your collection is small you can return constant from hashCode method. It use for quick finding. hashCodes is like the boxes, which keep elements. Rules are:

  1. Equal elements must be in same box (have same hashCode) - surely;
  2. Not equal elements can be either in same or in different boxes.

Then you return constant, you obey these 2 rules, but it can significantly decrease perfomance on not small lists (because JVM will look for in all elements, and not in elements in the same box only). But return constant is the bad approach.

PS: Sorry for my writing. English is not my native language.

PPS: usualy you have to implement hashCode method in the same way as equals (use same elements)

Improve this answer

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.