23

I have a quick question about TreeSet collections and hashCode methods. I have a TreeSet and I'm adding objects to it, before I add an object, I check to see if it exists in the TreeSet using the contains method.

I have 2 distinct objects, each of which produce a distinct hashCode using my implementation of the hashCode method, example below:

public int hashCode()
{
    int hash = 7;
    hash = hash * 31 + anAttribute.hashCode();
    hash = hash * 31 + anotherAttribute.hashCode();
    hash = hash * 31 + yetAnotherAttribute.hashCode();
    return hash;
}

The hashCodes for a particular run are: 76126352 and 76126353 (the objects only differ by one digit in one attribute).

The contains method is returning true for these objects, even though the hashCodes are different. Any ideas why? This is really confusing and help would really be appreciated.

Improve this question

4 Answers 4

Reset to default
53

TreeSet does not use hashCode at all. It uses either compareTo or the Comparator you passed to the constructor. This is used by methods like contains to find objects in the set.

So the answer to your question is that your compareTo method or your Comparator are defined so that the two objects in question are considered equal.

From the javadocs:

a TreeSet instance performs all element comparisons using its compareTo (or compare) method, so two elements that are deemed equal by this method are, from the standpoint of the set, equal.

Improve this answer
Sign up to request clarification or add additional context in comments.

4 Comments

It also uses the equals method, so it's important that equals and the Comparator/compareTo are consistent.
"This is so because the Set interface is defined in terms of the equals operation, but a TreeSet instance performs all element comparisons using its compareTo (or compare) method ..." (from java.sun.com/javase/6/docs/api/java/util/TreeSet.html)
this indeed was the problem, I added an extra attribute, updated equals and hashCode but forgot about compareTo. Thanks!!
what if I am inserting an Integer object in TreeSet and contains() returns false even though an Integer with same value already exists in the TreeSet?
4

From Java Doc:

If two objects are equal according to the equals(Object) method, then calling the hashCode method on each of the two objects must produce the same integer result.

Means: the objects you use for hashing are not equal.

Improve this answer

2 Comments

That's assuming hashCode and equals have been defined in a way that does not break that contract.
@sepp2k This is the 'general contract for hashCode()'. That's why it uses the word 'must'.
0

You need to read Joshua Bloch's "Effective Java" chapter 3. It explains the equals contract and how to properly override equals, hashCode, and compareTo.

Improve this answer

3 Comments

It's even available online: java.sun.com/developer/Books/effectivejava/Chapter3.pdf
I was all ready to upvote gustafc's comment, but the link is now broken :(
Go buy the book. It's still out there.
0

You don't need to checked if it is contained, because the insert() basically does the same operation (i.e. searching the proper position) on its way to the insertion point. If the object can't be inserted (i.e., the object is already contained), insert returns false.

Improve this answer

1 Comment

That's one example (like most of the Collection classes) for a very clean and concise API.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.