• Post Reply Bookmark Topic Watch Topic
  • New Topic
programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
  • Campbell Ritchie
  • Jeanne Boyarsky
  • Ron McLeod
  • Paul Clapham
  • Liutauras Vilda
Sheriffs:
  • paul wheaton
  • Rob Spoor
  • Devaka Cooray
Saloon Keepers:
  • Stephan van Hulst
  • Tim Holloway
  • Carey Brown
  • Frits Walraven
  • Tim Moores
Bartenders:
  • Mikalai Zaikin

why treeset does not implement equals and hashcode

 
Ranch Hand
Posts: 87
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
 
Rancher
Posts: 43081
77
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 781
Netbeans IDE Ubuntu Java
  • Likes 2
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator

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.
 
Sheriff
Posts: 22781
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Likes 1
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.

 
Ranch Hand
Posts: 88
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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?
 
ujwwala tem
Ranch Hand
Posts: 87
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 88
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
looks at this code:



somehow I see Comparator is used by TreeSet Object while checking for contains(..)
 
Rob Spoor
Sheriff
Posts: 22781
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 88
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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
Posts: 88
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
looks at this code:



somehow I see Comparator is used by TreeSet Object while checking for contains(..)
 
Ranch Hand
Posts: 384
Spring Java
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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

 
Rob Spoor
Sheriff
Posts: 22781
131
Eclipse IDE Spring VI Editor Chrome Java Windows
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
Ranch Hand
Posts: 1170
Hibernate Eclipse IDE Ubuntu
  • Mark post as helpful
  • send pies
    Number of slices to send:
    Optional 'thank-you' note:
  • Quote
  • Report post to moderator
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.
 
With a little knowledge, a cast iron skillet is non-stick and lasts a lifetime.
reply
    Bookmark Topic Watch Topic
  • New Topic