aspose file tools*
The moose likes Java in General and the fly likes why treeset does not implement equals and hashcode Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login


Win a copy of Spring in Action this week in the Spring forum!
JavaRanch » Java Forums » Java » Java in General
Bookmark "why treeset does not implement equals and hashcode" Watch "why treeset does not implement equals and hashcode" New topic
Author

why treeset does not implement equals and hashcode

ujwwala tem
Ranch Hand

Joined: Feb 10, 2010
Posts: 83
Hello All,

I have a query as how to remove duplicate objects in treeset, does we have to implement comparabble,comparator, why we cant implent hashode and equals as it doesn't provide hashing alogorithm,

Please clarify my doubt, and also I am looking fr source code for removing duplicated from treeset,

Please help..

Regards,
Ujwwala
Ulf Dittmer
Marshal

Joined: Mar 22, 2005
Posts: 42282
    
  64
I don't think I understand the question: all Java objects have equals and hashCode methods. What's more, TreeSet implements the Set interface, the contract of which ensures that it contains no duplicate objects. If your notion of equality is different then you can write a subclass that redefines those methods.


Ping & DNS - my free Android networking tools app
James Sabre
Ranch Hand

Joined: Sep 07, 2004
Posts: 781

Ulf Dittmer wrote:I don't think I understand the question: all Java objects have equals and hashCode methods. What's more, TreeSet implements the Set interface, the contract of which ensures that it contains no duplicate objects. If your notion of equality is different then you can write a subclass that redefines those methods.


equals() and hashcode() are not involved when objects are inserted or removed from a TreeSet. If a Comparator is supplied in a TreeSets construction then it is used to define the order and equality. If no Comparator is supplied then the 'natural ordering' as defined by the Comparable interface which the objects must then implement.


Retired horse trader.
 Note: double-underline links may be advertisements automatically added by this site and are probably not endorsed by me.
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19720
    
  20

Which causes TreeSet to actually break the rules specified by Set.equals (and even Object.equals) which states that one Set is equal to another Set if it contains the same elements. Consider:
These two last lines should both print out the same value but it doesn't. That means that the equals method is no longer symmetric, something that goes against the contract of Object.equals. This is all mentioned on the TreeSet Javadoc page though:
Note that the ordering maintained by a set (whether or not an explicit comparator is provided) must be consistent with equals if it is to correctly implement the Set interface. (See Comparable or Comparator for a precise definition of consistent with equals.) 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, so two elements that are deemed equal by this method are, from the standpoint of the set, equal. The behavior of a set is well-defined even if its ordering is inconsistent with equals; it just fails to obey the general contract of the Set interface.


SCJP 1.4 - SCJP 6 - SCWCD 5 - OCEEJBD 6
How To Ask Questions How To Answer Questions
K Abhijit
Ranch Hand

Joined: Mar 03, 2008
Posts: 88
interesting post; thanks Ujwala

initially thought that the Post Title and description is not in sync.. crazy one...but when thought a bit and saw the post of Rob, got some more idea what could be the query for...

Well Ujwala, if you can elaborate your question, it would be great !

Rob Spoor
These two last lines should both print out the same value but it doesn't.


this is interesting we need to check why?


“The difference between 'involvement' and 'commitment' is like an eggs-and-ham breakfast: the chicken was 'involved' - the pig was 'committed'.”
ujwwala tem
Ranch Hand

Joined: Feb 10, 2010
Posts: 83
Hello Abhijit,

My question was regarding how to compare objects for their equality in treeset, like in hashset we override equala and hashcode but in treeset as per my understanding we
comare the objects and sorts them(automatic sort) so we have to implement comaparable or comarator,

so why we can override equals..

Hello Rob,

Thanks for your reply..
Please clarify me your post once.. In interview I have been asked if we have added objects in Treeset, and want to check the duplicate objects but not with the parameter checking like fields by fields like age,name comaparator we wanted to check just for object equality, need help how can we do that,

Thanks,
Ujwwala
K Abhijit
Ranch Hand

Joined: Mar 03, 2008
Posts: 88
looks at this code:



somehow I see Comparator is used by TreeSet Object while checking for contains(..)
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19720
    
  20

Correct. HashSet uses only the hashCode and equals methods for all of its operations. TreeSet uses either the compareTo method of its Comparable elements, or the compare method of the Comparator if one is used. In this case, the Comparator will lead to results that are quite different.
K Abhijit
Ranch Hand

Joined: Mar 03, 2008
Posts: 88
Thanks Rob, looks more connected now with this logic....

but this is huge leap; this analogy would make a significance difference while using multiple collections like Tree/Hash maps/sets ...
does Sun/Oracle say anything like this in any of their documentations? (i didn't find any )
K Abhijit
Ranch Hand

Joined: Mar 03, 2008
Posts: 88
looks at this code:



somehow I see Comparator is used by TreeSet Object while checking for contains(..)
Lalit Mehra
Ranch Hand

Joined: Jun 08, 2010
Posts: 384

well it's a TREE i suppose ... so it has know which element should be placed at which place ... so for that you need to have something in your class that can compare between two objects of your class and know which should come first and which later ... YOU NEED TO IMPLEMENT THE COMPARABLE INTERFACE for this ONLY



http://plainoldjavaobject.blogspot.in
Rob Spoor
Sheriff

Joined: Oct 27, 2005
Posts: 19720
    
  20

You need to implement Comparable for any place where you need to have sorting, not just TreeSet / TreeMap. How about sorting Lists using Collections.sort? How about the auto-sorting functionality of JTable? These are just two examples.
Mr. C Lamont Gilbert
Ranch Hand

Joined: Oct 05, 2001
Posts: 1170

The interview question is non-sense. Checking for duplicate objects in a Set that is defined not to have duplicate objects makes no sense.

I personally ran into some trouble with TreeSet. I had some objects that were deemed 'equal' based on their IDs. Their hashCode was also based on their ID (as specified). But the objects also had names. The objects in the set were sorted by name.

Well, I renamed an object while it was in the set. Then I attempted to remove the object and re-add it so it could be resorted. But the TreeSet couldn't find the object because the TreeSet expected the object to be in a particular place. e.g. The object was named 'Cat' so the Tree set expected it to be between 'Boy' and 'Dog'. But the objects old name was 'Xylophone'. And even though its new name started with 'C', its position in the map was still as if it started with 'X.' Thus, the object was not removed. What's worse? The object was re-added

The bottom line is, I violated the contract by renaming the object while it was in the set. This resulted in having duplicate objects in the set. Or to put it better, the same object was now in the set twice. There is no automatic way to check for this.
 
I agree. Here's the link: http://aspose.com/file-tools
 
subject: why treeset does not implement equals and hashcode